б) Методы организации процесса поиска

Сущность организации процесса поиска заключается в обеспечении движения системы к точке экстремума на основе использования сигналов, зависящих от компонент градиента, или сигналов отклонений от точки экстремума.

Для функции нескольких переменных возможно большое число вариантов организации поиска экстремума. Наиболее просты следующие.

Метод Гаусса — Зайделя (поочередное изменение переменных). Метод заключается в поочередном изменении координат и определении частных экстремумов вида:

при

Первоначально изменяется координата в направлении уменьшения абсолютной величины компоненты градиента при постоянных значениях остальных координат. После обращения в нуль компоненты градиента начинается изменение координаты в сторону уменьшения компоненты градиента при постоянных значениях остальных координат. Далее следует аналогичный поиск по координате

После осуществления поиска по всем координатам вновь происходит изменение координаты до обращения в нуль и цикл повторяется. Переходный процесс поиска заканчивается, когда все компоненты градиента становятся меньше порога чувствительности, зависящего, в частности, от величины поисковых колебаний, служащих для определения градиента (см. выше).

Процесс поиска по методу Гаусса — Зайделя иллюстрирует рис. 19-11 (ломаная 1).

Рис. 19-11. Характер переходных процессов поиска. 1 — метод Гаусса-Зайделя; 2 - метод градиента; 3 — метод наискорейшего спуска.

Функция двух переменных представлена здесь линиями равных значений Вблизи точки экстремума линии равных значений близки к концентрическим эллипсам. Движение, параллельное оси координат при данном методе поиска, происходит до тех пор, пока соответствующая производная не обратится в нуль, что происходит в точке касания прямой с одной из линий равных значений

Из рис. 19-11 ясно, что путь движения изображающей точки к экстремуму при методе Гаусса — Зайделя не является кратчайшим.

Метод градиента. Данный метод заключается в том, что определяются все компоненты градиента и обеспечивается движение изображающей точки в направлении, близком к мгновенному направлению вектора градиента. Движение может быть непрерывным или шаговым.

В случае непрерывного движения и линейного регулирования скорости изменения координат устанавливаются пропорциональным и соответствующим компонентам мгновенного вектора градиента:

где для случая

экстремума-максимума и для случая экстремума-минимума.

При шаговом поиске после измерения градиента делается шаг, составляющие которого по осям координат пропорциональны соответствующим компонентам градиента в исходной точке:

Далее вновь определяется градиент, происходит следующий шаг в направлении вектора градиента и т. д.

При непрерывном движении траектория изображающей точки в пространстве координат нормальна к поверхностям равных значений На рис. 19-11 траектория, соответствующая непрерывному движению по методу градиента, обозначена 2.

Легко показать, что непрерывный процесс поиска по методу градиента в его идеальной форме (19-10) обеспечивает устойчивость, т. е. приводит систему к экстремуму при произвольных начальных условиях Действительно, из выражения (19-5) и соотношений (19-10) следует:

где для экстремума-максимума и для экстремума-минимума. Выражение в скобках — положительная величина, за исключением точки экстремума, где она обращается в нуль.

Таким образом, при наличии экстремума-максимума и функция в процессе поиска монотонно нарастает во времени до достижения точки экстремума, где Аналогично при наличии экстремума-минимума и функция монотонно уменьшается вплоть до достижения минимального значения.

Достоинством поиска по методу градиента является плавный характер движения к точке экстремума. При шаговом выполнении движения имеет место также относительно малый размах колебаний вокруг точки экстремума [19-8].

Метод наискорейшего спуска. При методе наискорейшего спуска определяется направление вектора градиента в начальной точке состояния системы и происходит движение в этом направлении до тех пор, пока частная производная взятая вдоль указанного направления, не обратится в нуль. В точке, где частная производная обращается в нуль, вновь определяется, направление вектора градиента и происходит движение вдоль этого вектора до обращения в нуль частной производной, взятой по новому направлению градиента, и т. д.

Характер движения изображающей точки при поиске методом наискорейшего спуска представлен ломаной 3 на рис. 119-11. Изменения направления движения происходят здесь в точках касания прямых движения с линиями равных значений функции Последовательные участки движения перпендикулярны. Движение по самой сущности метода наискорейшего спуска является шаговым. Оджако на каждом данном участке (между изменениями направления) движение может быть как шаговым, так и непрерывным.

Для метода наискорейшего спуска характерно относительно малое время выхода в окрестность экстремума при крупных шагах движения на начальном этапе поиска.

Возможно применение различных комбинаций методов поиска, например метода наискорейшего спуска при больших отклонениях и метода градиента при малых отклонениях.