Метод оврагов (нелокальный метод).

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

К 1-группе (несущественные переменные) относят переменные, изменение которых приводит к существенным, легко обнаруживаемым изменениям функции.

Ко 2-й группе (существенные переменные) относят переменные, изменение которых вызывает весьма малые, несущественные изменения функции.

Название метода связано с тем, что в описанной ситуации структура поверхности, соответствующей оптимизируемой функции, вызывает наглядную геометрическую ассоциацию с оврагом.

Изменения несущественных переменных определяют крутые склоны оврага, а изменения существенных переменных характеризуют рельеф дна.

Метод оврагов реализуется следующим образом:

Из произвольной точки А0 (рисунок 1), используя любую локальную процедуру (градиентные методы), производится ряд итераций спуска.

Рис. 29 Итерации спуска

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

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

Обнаружив это, остановимся (пусть это будет точка В0).

Сделаем теперь случайный шаг в направлении, отличном от направления спуска, и величиной, существенно превышающей шаг локального спуска. Из полученной точки А1 вновь осуществим локальный спуск, который приводит в точку В1, вообще говоря, отличную от В0. Обе точки (В0 и В1) лежат на дне оврага. Осуществим большой шаг вдоль луча, соединяющего В0 и В1 , в сторону точки с меньшим значением функции, величину которого выберем пропорционально средней крутизне дна оврага между В0 и В1.

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

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

Случайный шаг используется лишь один раз (от точки В0 к точке А1). В дальнейшем чередуются градиентные и овражные шаги.

Поиск глобального экстремума по методу оврагов содержит элементы самоорганизации.

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