ПОИСК Статьи Рисунки Таблицы Поиск при наличии оврагов целевой функции из "Методы оптимизации в химической технологии издание 2" Метод поочередного изменения переменных, называемый также методом Гаусса—Зейделя, по существу аналогичен рассмотренному выше методу релаксации. Отличие заключается лишь в том, что в этом методе не определяется осевое направление, вдоль которого значение целевой функции изменяется наиболее сильно, а поочередно Изменяются все независимые переменные так, чтобы по каждой из них достигалось наименьшее (наибольшее) значение целевой функции. Очередность варьирования независимых переменных при этом устанавливается произвольно и обычно не меняется в процессе поиска. Заметим, что для двух независимых переменных оба метода поиска, т. е. метод релаксации и метод поочередного изменения переменных, совпадают. [c.507] Как и в методе релаксации, каждая уточняемая переменная варьируется до. тех пор, пока в данном осевом направлении не будет найден минимум, после чего начинается процесс шагового поиска по следующему осевому направлению. Стратегия поиска минимума по каждой переменной при этом может быть также любая. В частности, можно использовать один из описанных выше методов поиска экстремума функции одной переменной. [c.507] Метод сканирования заключается в последовательном просмотре значений критерия оптимальности в ряде точек, принадлежащих области изменения независимых переменных, и нахождении среди этих точек такой, в которой критерий оптимальности имеет минимальное (максимальное) значение. Точность метода, естественно, определяется тем, насколько густо располагаются выбранные точки в допустимой области изменения независимых переменных. . [c.508] Основным достоинством метода сканирования является то, что при его использовании с достаточно густым расположением исследуемых точек всегда гарантируется отыскание глобального оптимума, так как анализируется вся область изменения независимых переменных. Другое достоинство — независимость поиска от вида оптимизируемой функции. [c.508] К недостаткам метода относится, в первую очередь, необходимость вычисления значений целевой функции для большего числа точек. Это должно гарантировать, что оптимум не будет пропущен при применении данного метода поиска. [c.508] Общий недостаток градиентных методов в оптимизации, за исключением, может быть, метода тяжелого шарика , состоит в том, что все они застревают в ближайшем локальном оптимуме, в область притяжения которого попадает выбранная начальная точка спуска. В отличие от этих методов метод сканирования никак не связан с наличием локальных оптимумов целевой функции. Поэтому его можно использовать иногда для предварительного грубого установления границ областей притяжения указанных оптимумов, после чего могут уже применяться градиентные методы спуска для измерения точной глубины каждого локального оптимума. . [c.508] Для произвольного числа независимых переменных шаг по-каждой следующей переменной производится после того, как полностью завершен цикл по предыдущей. [c.509] Таким образом, число вычислений критерия оптимальности при определении положения оптимума методом сканирования возрастает в показательной зависимости от размерности решаемой задачи. Поэтому эффективное применение данного метода в основном ограничивается задачами невысокой размерности п = 2 — 3, если используется простейший алгоритм поиска, рассмотренный выше, для отыскания оптимума с невысокой точностью. [c.510] На рис. IX-20 показан поиск с переменным шагом для функции двух переменных. Кружком обозначено истинное положение оптимума, а крестом — приближение, найденное в результате грубого поиска. [c.511] Имеются и другие модификации метода сканирования, например сканирование по спирали (рис. IX-21), за счет чего также удается сократить объем вычислений. При этом можно иногда предположить, что если при очередном витке спирали меньшее значение функции цели не найдено, оптимум расположен внутри данного витка. [c.512] Положение оптимума може-т быть уточнено, если перенести центр сканирования в определенную на предыдущем этапе точку наименьшего значения функции цели и новое сканирование проводить с уменьшенным приращением радиуса витка. [c.512] Следует отметить, что сканирование по спирали удобно применять лишь для случая двух независимых переменных, так как при большем числе переменных -расчеты положения очередной проверяемой точки существенно усложняются. Например, для трех переменных исследуемыми точками нужно покрывать уже сферическую поверхность. [c.512] Попыткой избежать необходимости вычисления производных для определения направления наискорейшего продвижения к оптимуму и в то же время сохранить возможность достаточно быстрого движения к нему является алгоритм симплексного метода [5]. [c.512] Основная идея этого метода заключается в том, что по известным значениям целевой функции в вершинах выпуклого многогранника, называемого симплексом, находится направление, в котором требуется сделать следующий шаг, чтобы получить наибольшее уменьшение (увеличение) критерия оптимальности. При этом под симплексом в /г-мерном пространстве понимается многогранник, имеющий ровно п + 1 вершин, каждая из которых определяется пересечением п гиперплоскостей данного пространства. Примером симплекса в двухмерном пространстве, т. е. на плоскости, является треугольник (рис. IX-22, а). В трехмерном-пространстве симплексом будет любая четырехгранная пирамида, имеющая четыре вершины, каждая из которых образована пересечением трех плоскостей— граней пирамиды, (рис. 1Х-22,б). [c.512] Рассмотрим наглядную иллюстрацию алгоритма симплексного метода на примере задачи отыскания наименьшего значения целевой функции двух независимых переменных с линиями постоянного уровня, изображенными на рис. IX-23. [c.513] В новой вершине 5ц вычисляется значение целевой функции, которое сравнивается с известными значениями для других вершин нового симплекса (S2o и S3o), и снова находится вершина S3o с наибольшим значением целевой функции, подлежащая исключению при построении следующего симплекса SuSaoSsi, и т. д. [c.513] Критерием окончания поиска могут служить размеры сим-плеска. Поиск можно прекратить, например, если все ребра симплекса станут меньше заданной достаточно малой величины. [c.514] Таким образом, алгоритм симплексного метода допускает автоматическое. изменение величины шага, при использовании которого вдали от оптимума возможно применение симплексов большого размера, что обеспечивает более быстрый спуск. [c.514] Случаи зацикливания могут встретиться и в задачах более высокой размерности. Если на очередном шаге исключению подлежит вновь полученная вершина, то это и служит сигналом о возникновении зацикливания. В этом случае размеры симплекса изменяются и поиск продолжается до обнаружения нового зацикливания. [c.514] Рассмотрим порядок построения нового симплекса для задач произвольной размерности п. [c.514] Вернуться к основной статье