Cтраница 4
Хотя метод золотого сечения и обладает высокой эффективностью, ясно, что он не является оптимальным при заданном числе вычислений целевой функции. Если конструктору заранее известно, что он сможет использовать лишь два значения целевой функции, то он, конечно, предпочтет метод дихотомии, который позволяет уменьшить интервал неопределенности сразу вдвое, а не в 1 / 0 618 раза, как метод золотого сечения. Если есть возможность в процессе поиска оптимума изменять расположение точек, в которых вычисляются значения целевой функции, то можно соединить преимущества симметричного расположения точек, о которых говорилось выше, с преимуществами метода дихотомии и построить оптимальный алгоритм поиска. [46]
Коррекцию графа следует начать с проверки эффективности обоих вариантов в целом. Для этого достаточно определить оптимальные сечения графов, построенных по обоим методам ( сверху вниз и снизу вверх), и провести сравнение значений стоимостей. При использовании метода дихотомии отклонения от оптимального определяются точностью аппроксимации и выбором типа стоимостных характеристик. В случае применения метода объединения заявок ошибка может возникнуть из-за неправильного ранжирования признаков и ограниченности диапазона переборов. [47]
Самыми простыми генетическими операторами являются ОК, ОМ, инверсии, сегрегации, транслокации, удаления, вставки и их модификации на основе пассивного поиска, когда случайным образом производится выбор пар и точек разрыва на исследуемых хромосомах. При использовании последовательного поиска выполняется перебор точек разрыва для нахождения хромосомы с оптимальной ЦФ. Построение генетических операторов с использованием метода дихотомии реализуется за счет механизма перебора точек разрыва. [48]
Такое множество W называется полным множеством монотонных цепей графа G. Заметим, что, согласно свойству 2, цепи из полного множества упорядочены. Следовательно, можно применить к W метод дихотомии ( т.е. двоичный поиск), в котором элементарной операцией вместо простого сравнения чисел теперь будет дискриминация точки относительно цепи. Итак, если у нас г цепей в W и в самой длинной цепи р вершин, то поиск займет в наихудшем случае О ( log r - log р) времени. [49]
Заметим, что применение итерационного метода требует обоснования его сходимости, что может вызвать затруднения. Для реализации на ЭВМ особенно удобен метод дихотомии ( половинного деления), который применительно к рассматриваемой задаче состоит в следующем. [50]
При работе на ЭВМ предлагается провести решение одного уравнения методами дихотомии и хорд при одинаковой точности и сравнить количество итераций. Для этого в программы следует добавить счетчик итераций и вывод на дисплей текущих значений аргумента х и функции f ( x) при каждом ее вычислении. В большинстве случаев при решении уравнений методом хорд требуется меньшее количество итераций по сравнению с методом дихотомии. Так, для уравнения (1.9) на отрезке [1, 2] с погрешностью Ю-6 корень х 1.363 02 при параметрах рх - 0.1 и р2 10 - 7 находится методом хорд после 11 вычислений левой части уравнений. Метод дихотомии требует для этого примера вдвое большего количества итераций. [51]
Хотя метод золотого сечения и обладает высокой эффективностью, ясно, что он не является оптимальным при заданном числе вычислений целевой функции. Если конструктору заранее известно, что он сможет использовать лишь два значения целевой функции, то он, конечно, предпочтет метод дихотомии, который позволяет уменьшить интервал неопределенности сразу вдвое, а не в 1 / 0 618 раза, как метод золотого сечения. Если есть возможность в процессе поиска оптимума изменять расположение точек, в которых вычисляются значения целевой функции, то можно соединить преимущества симметричного расположения точек, о которых говорилось выше, с преимуществами метода дихотомии и построить оптимальный алгоритм поиска. [52]
В главе четыре рассмотрены инструментальные средства ЭМ, в которых используется ряд методов одномерного градиентного поиска, а также статистических методов оптимизации. В рамках одномерного поиска описаны следующие методы: пассивный; последовательный; дихотомии; Фибоначчи; золотого сечения; поиск в глубину, в ширину, с возвращением, с использованием И-ИЛИ деревьев и метод горизонта. Последовательный поиск выполняется путем перебора значений целевой функции ( ЦФ) для нахождения оптимального значения. Метод дихотомии реализуется за счет механизма обычного перебора возможных точек разрыва. Он аналогичен методу деления отрезка пополам для нахождения точки, в которой ЦФ имеет локальный оптимум. [53]
Согласно (4.18), расположение первого эксперимента точнее, двух первых) зависит от общего числа экспериментов п, которые мы намерены проводить. В то же время для метода Фибоначчи такое число требуется задать. Заметим, что метод дихотомии, например, не нуждается в этом. Мы сейчас опишем еще один метод, не зависящий от числа готовящихся экспериментов и почти столь же эффективный, что и метод Фибоначчи. [54]
Эффективность метода дихотомии экспоненциально растет с ростом числа хромосом. Она обычно задается ЛПР или определяется в интеллектуальной ИС на основе адаптации. Отметим, что существует большое количество способов конкретной реализации ОК метода дихотомии. Целесообразность ОК метода дихотомии определяется на основе вероятности его выживания, которая определяется по формулам (3.3), (3.4) или их модификациям. [55]
При работе на ЭВМ предлагается провести решение одного уравнения методами дихотомии и хорд при одинаковой точности и сравнить количество итераций. Для этого в программы следует добавить счетчик итераций и вывод на дисплей текущих значений аргумента х и функции f ( x) при каждом ее вычислении. В большинстве случаев при решении уравнений методом хорд требуется меньшее количество итераций по сравнению с методом дихотомии. Так, для уравнения (1.9) на отрезке [1, 2] с погрешностью Ю-6 корень х 1.363 02 при параметрах рх - 0.1 и р2 10 - 7 находится методом хорд после 11 вычислений левой части уравнений. Метод дихотомии требует для этого примера вдвое большего количества итераций. [56]
Эффективность метода дихотомии экспоненциально растет с ростом числа хромосом. Она обычно задается ЛПР или определяется в интеллектуальной ИС на основе адаптации. Отметим, что существует большое количество способов конкретной реализации ОК метода дихотомии. Целесообразность ОК метода дихотомии определяется на основе вероятности его выживания, которая определяется по формулам (3.3), (3.4) или их модификациям. [57]