Случайных направлений с обратным шагом

2.4. Поиск при наличии «оврагов» целевой функции

Приведенные выше методы оказываются малоэффективными при наличии «оврагов» у целевой функции. Поэтому при решении оптимизационных задач, целевые функции которых имеют особенность типа «оврагов» разработаны специальные методы. Один из таких методов называется методом шагов по «оврагу» [1].

Алгоритм решения задачи методом шагов по «оврагу»

1. Переменные, входящие в целевую функцию разбиваются на две группы:

а) переменные, изменение которых существенно влияет на значение целевой функции;

б) переменные, при изменении которых значение целевой функции изменяется не столь значительно.

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

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

2. Рассчитывается значение целевой функции в начальной точке поиска

.

3. Производится шаг в направлении изменения переменной первой группы, например для х₁

.

4. Любым методом поиска, в данном случае методом релаксации, осуществляется поиск минимума целевой функции. В результате поиска придем на «дно оврага»

.

5. Из начальной точки x⁽⁰⁾ производится шаг в направлении изменения переменных второй группы, в результате которого придем в новое состояние, например для x₂ в случае функции двух переменных

.

Вычисляется значение целевой функции в этой точке.

6. Из полученного состояния производится поиск минимума целевой функции, следуя п. 3-4. В результате поиска придем на новое «дно оврага»

7. Выполняется шаг по «оврагу», например для функции двух переменных, шаг по «оврагу» можно произвести следующим образом. Если , то

, .

Если , то

,

Далее вычисляется значение целевой функции в точке .

8. Если значение целевой функции в точке меньше, чем в предыдущей точке, то поиск продолжается, начиная с п.6., при этом движение к новому дну «оврага» осуществляется из точки . Если же оно больше, то предполагается, что оптимум находится между новой точкой и предыдущей точкой.

9. Любым методом поиска находится минимум целевой функции между предыдущей точкой и точкой .

Блок – схема алгоритма решения задачи методом шагов по «оврагу»