Лекция: Метод Хука-Дживса (метод конфигураций)
В этом методе каждая итерация состоит из двух фаз:
1) исследующий поиск;
2) движение по образцу (ускоряющий шаг).
Исследующий поиск аналогичен одному циклу покоординатного спуска. Конечную точку цикла называют базовой. Две последовательные базовые точки определяют направление поиска на 2-й фазе. Точка, получаемая в результате ускоряющего шага, называется временной. Начальная точка одновременно является базовой и временной.
Сначала приведем вариант метода, предложенный Хуком и Дживсом и описываемый в литературе под названием «метод конфигураций». В нем используются только дискретные шаги. Процедура поиска показана на рис. 8.20. Из начальной точки X(0) делается шаг D по x1 в одну сторону и, если успешно, то значение фиксируется, иначе направление шага изменяется на противоположное. Также делается по остальным координатам. Итогом первого исследующего поиска является точка X(1). В направлении X(1) — X(0) осуществляется движение по образцу, дающее временную точку Y(1)= X(1)+a (X(1) — X(0)), где a – коэффициент ускорения (рекомендуется брать от 1 до 2). Из полученной временной точки снова проводится исследующий поиск, приводящий в очередную базовую точку X(2). Ускоряющий шаг в направлении X(2) — X(1) дает временную точку Y(2). Фазы поиска повторяются без изменения величины шага, если f(Y(k))<f(X(k)). В противном случае, если D<e, поиск заканчивается и X(k) принимается за решение, а иначе следует положить Y(k)= X(k), уменьшить шаг в два раза и перейти к исследующему поиску из точки Y(k). Иначе говоря, после каждого ускоряющего шага проверяется его успешность, и в зависимости от результата выбираются последующие действия..
Модификация метода Хука-Дживса заключается в замене дискретных шагов одномерной минимизацией. В этом варианте исследующий поиск полностью совпадает с одним циклом покоординатного спуска, то есть по каждой координате выполняются не дискретные шаги, а ищется минимум. При движении по образцу также ищется минимум функции только по одной неизвестной – коэффициенту ускорения a:
По оптимальному значению a* определяется временная точка
Поиск завершается, когда расстояние между двумя смежными базовыми точками становится меньше заданной величины:
.
К этому условию можно добавить и требование по точности функции:
На рис. 8.21 и 8.22 приведены примеры применения метода с одномерной минимизацией. Как видно, такой вариант метода обеспечивает быстрое приближение к области искомого решения. Другим важным достоинством метода является его работоспособность в условиях оврага. Траектория поиска хорошо приспосабливается к изгибам дна оврага (рис. 8.22).