Метода - дихотомия
Cтраница 2
 |
График поиска максимума методом золотого сечения.| График движения в пространстве факторов при оптимизации методом покоординатного спуска. [16] |
Как и в методе дихотомии, здесь имеем две точки л и п; но, в отличие от дихотомии, расстояние между ними не мало, и вероятность, что точка экстремума попадет между ними, достаточно велика. Но в левой части ( мы приняли, что функция унимодальна) максимума быть не может. Таким образом, на каждом этапе расчета, кроме самого первого, мы должны рассчитывать F только в одной точке, что повышает эффективность метода. [17]
Для однофакторных задач используются следующие стратегии поиска различной эффективности: 1) метод дихотомии; 2) метод чисел Фибоначчи; 3) метод золотого сечения; 4) поиск по дискретным точкам. После проведения десяти опытов, спланированных по методу дихотомии, исходный интервал неопределенности уменьшается в 32 раза, по методу чисел Фибоначчи - в 89 раз, по методу золотого сечения - в 76 раз, а при поиске по дискретным точкам - в 143 раза. [18]
 |
Метод дихотомии. [19] |
В дальнейшем при использовании метода дихотомии выполняются те же операции, что и при использовании метода деления интервала пополам. Отметим, однако, что для достижения одинаковых сужений интервала неопределенности метод дихотомии требует вычисления целевой функции в точках на одну меньше. [20]
Отдельную группу детерминированных методов поиска составляют покоординатные методы, в связи с тем что человек, работающий в диалоговой системе оптимизации, обычно выбирает пошаговый покоординатный принцип работы с поочередным варьированием переменных. Покоординатное изменение параметров сводит поиск к одномерному, и наибольшими возможностями в однопарамет-рическом поиске обладают известные итерационные приемы, такие, как методы дихотомии, метод золотого сечения, сходимость которых проверена на многих задачах. [21]
Сравнение (4.11) и (4.10) показывает, что метод дихотомии существенно эффективнее метода поиска однородными парами. Так, для уменьшения интервала неопределенности до 0 01, если пренебречь величиной е, требуется 198 пассивных экспериментов и всего 14 -по методу дихотомии. Интересно поставить вопрос об отыскании оптимальной стратегии последовательного поиска. Такая задача была поставлена и решена в 1953 г. Кифером, причем неожиданно она оказалась связана с работами математика XII века Фибоначчи и его знаменитыми числами, и даже с геометрическими построениями Евклида. [22]
Несколько эффективней метода дихотомии так называемый метод Фибоначчи, в основу которого положена особая числовая последовательность, применявшаяся математиком XII века Фибоначчи. Как и метод дихотомии, метод Фибоначчи выражается правилом деления каждого очередного интервала неопределенности, но не на две, а на три части, и не приращением А / ( х), а результатом одного вычисления в отличие от метода дихотомии, но так же, как при способе направленного перебора, число вычислений в каждом конкретном случае применения метода Фибоначчи колеблется в зависимости от непредвиденных сочетаний обсчитываемых точек и точки минимума х на каждом шаге поиска. Поэтому в отношении метода Фибоначчи применим только минимаксный принцип оптимальности, что обязательно надо иметь в виду, рассматривая изложенное ниже обоснование метода. [23]
Затем выполняется оператор инверсии. Предлагаются две версии данного оператора: случайная и направленная. Здесь также предусматривается применение следующих операторов инверсии: специального, метода золотого сечения, метода Фибоначчи, метода дихотомии, а также ряд других модификаций для получения реальных решений оптимизационных задач. [24]
Рассмотрены алгоритмы распознавания изоморфизма графов. Основная идея заключается в разбиении исследуемых графов на предполагаемо изоморфные подграфы. После получения подмножеств разбиения в подмножествах наибольшей мощности выполняются модифицированные генетические операторы. Наилучшие результаты показывают новые генетические операторы, основанные на жадной стратегии, методе дихотомии, минимального кластера, методе золотого сечения и методе Фибоначчи. Они позволяют параллельно анализировать все подмножества вершин и снижают время нахождения результата. [25]
Рассмотрены основные принципы эволюции в живых и искусственных системах. Проанализированы подходы к построению архитектур искусственных систем на основе различных моделей эволюции. Описаны основные проблемы синергетики. Рассмотрены состояния, проблемы, перспективы, способы построения и развития иерархических искусственных систем. Исследованы стратегии взаимодействия поисковых методов и эволюционного моделирования. Приведены нестандартные архитектуры решения инженерных задач, позволяющие получать набор квазиоптимальных решений за полиномиальное время. Сформулированы ряд положений и основные принципы теории эволюционного моделирования. Проанализирована теорема генетических алгоритмов, показывающая вероятность выживания лучших решений. Сформулирована постановка оптимизационных задач принятия решений на графах. Описаны генетические операторы, использующие фрактальные структуры, методы дихотомии, золотого сечения и чисел Фибоначчи. Рассмотрены подходы к решению основных инженерных задач. [26]
Страницы: 1 2