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

Метод конфигураций (метод Хука-Дживса [R. Hook, T.A. Jeeves]) представ­ляет собой комбинацию исследующего (пробного) поиска с циклическим изменением пере­менных и ускоряющего поиска по образцу. Исследующий поиск ориентирован на выявление локального поведения целевой функции и определение направления ее убывания вдоль "оврагов". Полученная информация используется при поиске по образцу при движении вдоль "оврагов".

Исследующий поиск начинается в некоторой начальной точке , называе­мой старым базисом. В качестве множества направлений поиска выбирается множество координатных направлений. Задается величина шага, которая может быть различной для разных координатных направлений и переменной в процессе поиска. Фиксируется первое координатное направление и делается шаг в сторону увеличения соответствующей переменной. Если значение функции в пробной точке меньше значения функции в исходной точке, шаг считается удачным. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположном направлении с последующей проверкой поведения функции. После перебора всех координат исследующий поиск завершается. Полученная точка называется новым базисом (на рис. 3.1 в точке произведен исследующий поиск и получена точка - новый базис). Если исследующий поиск с дан­ной величиной шага неудачен, то она уменьшается и процедура продолжается. Поиск заканчивается, когда текущая величина шага станет меньше некоторой величины.

Рисунок 3.1

Поиск по образцу заключается в движении по направлению от старого базиса к новому (от точки через точку , из точки через точку , из точки через точку на рис. 3.1). Величина ускоряющего шага задается ускоряющим множителем . Успех поиска по образцу определяется с помощью исследующего поис­ка из полученной точки (например, из точек 6, 11, 15 на рис. 3.1). Если при этом значение в наилучшей точке меньше, чем в точке предыдущего базиса, то поиск по образцу удачен (точки 6, 11 - результат удачного поиска по образцу, а точка 15 - неудачного). Если поиск по образцу неудачен, происходит возврат в новый базис, где продолжается исследующий поиск с уменьшенным шагом.

На рис. 3.1 удачный поиск отображается сплошными линиями, а неудач­ный - пунктирными, числа соответствуют порождаемым алгоритмом точкам. Обозначим через - координатные направления

При поиске по направлению меняется только переменная , а остальные переменные остаются зафиксированными.

Алгоритм:

Шаг 1. Задать начальную точку , число для остановки алгоритма, начальные величины шагов по координатным направлениям , ускоряющий множитель , коэффициент уменьшения шага . Положить .

Шаг 2. Осуществить исследующий поиск по выбранному координатному направлению:

а) если , шаг считается удачным. Положить и перейти к шагу 3;

б) если в пункте а) шаг неудачен, то делается шаг в противоположном направлении. Если , шаг считается удачным. В этом случае следует положить и перейти к шагу 3;

в) если в пунктах а) и б) шаги неудачны, положить .

Шаг 3. Проверить условия:

а) если , то положить и перейти к шагу 2;

б) если , проверить успешность исследующего поиска

- если , перейти к шагу 4;

- если , перейти к шагу 5;

Шаг 4. Провести поиск по образцу. Положить , , , и перейти к шагу 2.

Шаг 5. Проверить условие окончания:

а) если все , то поиск по закончить: ;

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

Замечания:

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

б) Существует модификация метода, где при исследующем поиске и поиске по образцу используется одномерная минимизация.

Пример: Найти локальный минимум функции методом конфигураций

Решение:

1. Зададим - старый базис, , , .

Положим k = 0, i = 1, .

2⁰. Т.к. то шаг неудачен.

Т.к. то шаг удачный: .

3⁰. Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.

2¹. Т.к. то шаг неудачен.

Т.к. то шаг удачный: .

3¹. Т.к. i = 2 = n = 2 и , переходим к шагу 4.

4⁰. Положим - новый базис, i = 1, k = k + 1 = 1, найдем . Выполнен поиск по образцу. Переходим к шагу 2.

2². Т.к. и

то шаги неудачные, а .

3². Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.

2³. Т.к. и

то шаги неудачные, а .

3³. Т.к. i = 2 = n = 2 и , переходим к шагу 4.

4¹. Положим - новый базис, i = 1, k = k + 1 = 2, найдем . Выполнен поиск по образцу. Переходим к шагу 2.

2⁴. Т.к. то шаг удачен:

.

3⁴. Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.

2⁵. Т.к. то шаг удачен:

.

3⁵. Т.к. i = 2 = n = 2 и , то поиск по образцу неудачен. Осуществляется возврат в точку . Переходим к шагу 5.

5⁰. Т.к. то уменьшим шаг: Положим i = 1, k = k + 1 = 3 и перейдем к шагу 2.

2⁶. Т.к. и

то шаги неудачные, а .

3⁶. Т.к. i = 1 < 2 = n, то i = i + 1 = 2 и переходим к шагу 2.

2⁷. Т.к. и

то шаги неудачные, а .

3⁷. Т.к. i = 2 = n = 2 и , то исследующий поиск неудачен. Перейдем к шагу 5.

5¹. Т.к. то поиск закончен: .

Геометрическая интерпретация решения задачи представлена на рисунке 3.2. Здесь изображены полученные точки; сплошной линией отмечены удачные итерации, а пунктирной – неудачные.

Рисунок 3.2

Дата добавления: 2015-07-20