Координатная стратегия

Координатная стратегия Гаусса и Зайделя [54] представляет собой расширение одномерной стратегии оптимизации на многомерные задачи. В соответствии с этой стратегией, начиная с исходного состояния, оптимизируется только первый пара­метр, пока функция качества не достигнет максимума, в это время все остальные параметры остаются постоянными. В соответствии с тем же принципом оптимизиру­ются и все остальные параметры. Если в результате модификации параметров каче­ство не улучшается, процесс оптимизации прекращается. Одномерная стратегия для поиска оптимума выбирается свободно. При использовании базовой формы данного метода поиск может проводиться как в положительном, так и в отрицательном на­правлениях.

Метод поворота координат

Эта стратегия была разработана на основе координатной стратегии [75]. При ис­пользовании метода поворота координат направление поиска не задается линиями, параллельными одной из координатных осей. Вместо этого для поиска оптимума вво­дится новая система координат. Одна из осей этой системы координат совпадает с направлением вектора, получаемого путем соединения начальной и конечной точек предыдущего шага итераций. Оси координат для остальных измерений всегда орто­гональны по отношению к этой оси и к остальным направлениям координат. С помо­щью этой процедуры возрастает вероятность нахождения правильного направления поиска, что обычно выражается в возрастании скорости схождения.

Поиск по шаблону (прямой поиск)

Поиск по шаблону Хука-Дживиса [62] представляет собой усовершенствован­ную координатную стратегию. При использовании этого метода первый шаг поиска выполняется аналогично тому, как это делается при использовании координатной стратегии. Предполагая, что линия, соединяющая начальную и конечную точки, пред­ставляет собой наиболее перспективное направление, в этом направлении методом экстраполяции производится одна итерация (движение по шаблону). Об успехе экс­траполяции судят только после оценки качества дополнительного шага поиска. Если ход оказывается неудачным, то шаг отменяется; в случае успеха перемещение в этом направлении продолжается. Изменяя величину и направление шага экстраполяции, можно реагировать на результаты отдельных шагов таким образом, чтобы при посте­пенном изменении оптимального направления поиска длина шага экстраполяции вре­мя от времени изменялась, сокращая таким образом время поиска.

Стратегия Дэвиса, Сванна и Кэмпи (ДСК)

Стратегия Дэвиса, Сванна и Кэмпи представляет собой комбинацию стратегии поворотных координат и стратегии линейного поиска [50]. С начальной точки в на­правлении каждой из осей координат проводится линейный поиск оптимума. Затем, начиная с оптимальной конечной точки, выбранной этим способом, выполняется одномерная оптимизация в направлении линии, соединяющей начальную и конеч­ную точки. Далее оси координатной системы перенаправляются таким образом, что­бы сформировать нормализованную прямоугольную систему координат, и выполня­ется новый линейный поиск в направлении осей координат этой системы. После этого вновь выполняется одномерная оптимизация в направлении линии, соединяющей начальную и конечную точки.

Симплексные и комплексные методы

Еще одна стратегия поиска оптимума, отличная от рассмотренных выше, разрабо­тана на основе симплексного метода Педлера и Мида [71]. В соответствии с этим методом в w-мерном пространстве поиска указывается как минимум п + 1 начальная точка, что соответствует одному набору параметров. Выбранные начальные точки находятся на одинаковых расстояниях друг от друга. В общем случае эта конфигура­ция соответствует правильному многограннику, называемому симплексом. Оптими­зация в соответствии с данной стратегией начинается с оценки всех вершин, каждая из которых описывает набор параметров (обычно эта оценка производится с помо­щью функции качества, или оценочной функции). На следующем шаге находится вершина, для которой значение оценочной функции является наихудшим среди всех. Этот набор параметров отбрасывается и заменяется новым, генерируемым путем ото­бражения точки выхода относительно центра оставшихся точек. Если вновь получен­ная вершина на следующей итерации также дает наихудшую оценку, то производится отражение вершины, которая дает наихудший результат. Далее эта процедура повто­ряется. Если в результате этого итерационного процесса симплекс приближается к оптимуму, он поворачивается вокруг вершины, дающей наилучшую оценку. При этом лучшее приближение может быть получено за счет уменьшения длины ребра симплекса. На рис. 4.32 показан ход выполнения этой процедуры в двухмерном про­странстве поиска. Замкнутые кривые на этой иллюстрации соответствуют точкам, в которых значение оценочной функции одинаково. При этом начальные точки обо­значены как О1,02 и О3. Точка 1 получается за счет отражения точки О1 относительно центра линии, соединяющей точки О2 и О3 и т. д.

Рис. 4.32. Стратегия симплекса

Усовершенствование этого метода — комплексный подход, который позволяет включать дополнительные условия в форме неравенств [52]. Его наиболее существен­ные отличия от метода симплекса заключаются в большем количестве вершин и в уве­личении после каждого отражения размера многогранника, называемого комплексом.