Метод Хука-Дживса (метод конфигураций)

В этом методе каждая итерация состоит из двух фаз:

1) исследующий поиск; 2) движение по образцу (ускоряющий шаг).

Исследующий поиск аналогичен одному циклу покоординатного спуска. Конечную точку цикла называют базовой. Две последовательные базовые точки определяют направление поиска на 2-й фазе. Точка, получаемая в результате ускоряющего шага, называется временной. Начальная точка одновременно является базовой и временной.

Сначала приведем вариант метода, предложенный Хуком и Дживсом и описываемый в литературе под названием "метод конфигураций". В нем используются только дискретные шаги. Процедура поиска показана на рис. Из начальной точки X⁽⁰⁾ делается шаг D по x ₁ в одну сторону и, если успешно, то значение фиксируется, иначе направление шага изменяется на противоположное. Также делается по остальным координатам. Итогом первого исследующего поиска является точка X⁽¹⁾. В направлении X⁽¹⁾- X⁽⁰⁾ осуществляется движение по образцу, дающее временную точку Y⁽¹⁾= X⁽¹⁾+ a (X⁽¹⁾- X⁽⁰⁾), где a – коэффициент ускорения (рекомендуется брать от 1 до 2). Из полученной временной точки снова проводится исследующий поиск, приводящий в очередную базовую точку X⁽²⁾. Ускоряющий шаг в направлении X⁽²⁾- X⁽¹⁾ дает временную точку Y⁽²⁾. Фазы поиска повторяются без изменения величины шага, если f(Y^{( k )})<f(X^{( k )}). В противном случае, если D< e, поиск заканчивается и X^{( k )} принимается за решение, а иначе следует положить Y^{( k )}= X^{( k )}, уменьшить шаг в два раза и перейти к исследующему поиску из точки Y^{( k )}. Иначе говоря, после каждого ускоряющего шага проверяется его успешность, и в зависимости от результата выбираются последующие действия..

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

По оптимальному значению a ^* определяется временная точка

Поиск завершается, когда расстояние между двумя смежными базовыми точками становится меньше заданной величины:

.

К этому условию можно добавить и требование по точности функции:

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