2.1.2 Метод прямого поиска Хука - Дживса.
Метод включает два этапа: “исследующий поиск” вокруг базисной точки и “поиск по образцу” в направлении, выбранном для минимизации. В исследующем поиске задается начальное приближение X(1) и приращения по координатам X. Рассчитывается значение f(X(1)) в базисной точке. Затем в циклическом порядке совершаются пробные шаги. Если приращение улучшает целевую функцию, то шаг считается “удачным”. По этой переменной значение изменяется на величину шага и дается приращение по другой переменной Иначе – “неудачным” и делается шаг в противоположном направлении. И если он тоже оказался “неудачным”, то значение этой переменной оставляют без изменения, и дается приращение по другой переменой и т.д. пока не будут изменены все независимые переменные. На этом завершается первый исследующий поиск, найдена точка X(2). Поиск по образцу осуществляется вдоль направления, соединяющего X(2) и X(1). Совершается один или несколько шагов до тех пор, пока шаги являются “удачными”.
Применяют две модификации метода прямого поиска:
в исследующем поиске используется одномерная минимизация вдоль координатных направлений;
исследующий поиск осуществляется на основе дискретных шагов по направлениям.
Алгоритм метода Хука-Дживса с минимизацией по направлению.
Начальный
этап. Выбрать
начальную точку X(1),
и
0 - скаляр, используемый в критерии
остановки. Пусть
единичные
координатные направления, α – коэффициент
сжатия шага. Положить Y(1) = X(1),
k = j = 1
и перейти к основному этапу.
Основной
этап. Шаг
1. Любым
методом одномерной оптимизации найти
j* - оптимальное
решение задачи минимизации функции
f(Y(j) + j
)
при условии
и положить
Y(j+1) = Y(j) + j*
.
Если j n,
то заменить j
на j + 1
и вернуться к шагу 1. Если j=n,
то перейти к шагу 2.
Шаг 2. Положить X(k+1) = Y(n). Если ||X(k+1) - X(k)|| , то остановиться; в противном случае вычислить шаг а=||X(k+1) - X(k)|| ·α, Y(1) = X(k), заменить k на k + 1, положить j = 1 и перейти к шагу 3.
Шаг 3. Вычислить Y(j+1) = Y(j)+a и f(Y(j) ), f(Y(j+1) ). Если f(Y(j+1) )< f(Y(j) ), то j=j+1 и вернуться к шагу 3. Иначе положить X(k)= Y(j) ,j=1, Y(1) = X(k), и вернуться к шагу 1.
Пример расчета экстремума функции методом прямого поиска Хука-Дживса.
Постановка задачи. Определить экстремум функции f(x)=(x1-2)4+( x1- 2x2)2 с точностью =0,05 для начального приближения Х(0)=[2.5; 2.5].
Расчет экстремума методом Хука-Дживса для поставленной задачи реализован средствами EXСEL. Результаты расчета представлены в таблице 2.2, а траектория поиска приведена на рисунке 2.2.
Таблица 2.2.
Результаты расчетов минимума функции f(x)=(x1-2)4+( x1- 2x2)2 методом Хука-Дживса.
|
Исследующий поиск | |||||||
|
№ |
х1 |
х2 |
f(X) |
S1 |
S2 |
λ1 |
λ2 |
|
1 |
2.500 |
2.500 |
6.3125 |
0.500 |
-1.000 |
0.0500 |
-0.100 |
|
3.000 |
1.500 |
1.0000 | |||||
|
Поиск по образцу | |||||||
|
№ |
х1 |
х2 |
f(X) |
λ1 |
λ2 |
||X(k+1) - X(k)|| |
Критерий |
|
1 |
2.500 |
2.500 |
6.3125 |
0.05 |
-0.1 |
1.0125 |
Не достигнут |
|
2 |
2.550 |
2.400 |
5.1540 |
| |||
|
3 |
2.600 |
2.300 |
4.1296 |
| |||
|
4 |
2.650 |
2.200 |
3.2410 |
| |||
|
5 |
2.700 |
2.100 |
2.4901 |
| |||
|
6 |
2.750 |
2.000 |
1.8789 |
| |||
|
7 |
2.800 |
1.900 |
1.4096 |
| |||
|
8 |
2.850 |
1.800 |
1.0845 |
| |||
|
9 |
2.900 |
1.700 |
0.9061 |
| |||
|
10 |
2.950 |
1.600 |
0.8770 |
| |||
|
11 |
3.000 |
1.500 |
1.0000 |
| |||
|
Исследующий поиск | |||||||
|
№ |
х1 |
х2 |
f(X) |
S1 |
S2 |
λ1 |
λ2 |
|
2 |
2.950 |
1.600 |
0.8770 |
-0.300 |
-0.275 |
-0.03 |
-0.0275 |
|
2.650 |
1.375 |
0.1885 | |||||
|
Поиск по образцу | |||||||
|
№ |
х1 |
х2 |
f(X) |
λ1 |
λ2 |
||X(k+1) - X(k)|| |
Критерий |
|
1 |
2.950 |
1.600 |
0.8770 |
-0.03 |
-0.0275 |
0.5049 |
Не достигнут |
|
2 |
2.920 |
1.573 |
0.7670 | ||||
|
3 |
2.890 |
1.545 |
0.6674 | ||||
|
4 |
2.860 |
1.518 |
0.5777 | ||||
|
5 |
2.830 |
1.490 |
0.4971 | ||||
|
6 |
2.800 |
1.463 |
0.4253 | ||||
|
7 |
2.770 |
1.435 |
0.3616 | ||||
|
8 |
2.740 |
1.408 |
0.3055 | ||||
|
9 |
2.710 |
1.380 |
0.2566 | ||||
|
10 |
2.680 |
1.353 |
0.2144 | ||||
|
11 |
2.650 |
1.325 |
0.1785 | ||||
|
12 |
2.620 |
1.298 |
0.1484 | ||||
|
13 |
2.590 |
1.270 |
0.1236 | ||||
|
14 |
2.560 |
1.243 |
0.1039 | ||||
|
15 |
2.530 |
1.215 |
0.0888 | ||||
|
16 |
2.500 |
1.188 |
0.0780 | ||||
|
17 |
2.470 |
1.160 |
0.0712 | ||||
|
18 |
2.440 |
1.133 |
0.0680 | ||||
|
19 |
2.410 |
1.105 |
0.0681 | ||||
|
Исследующий поиск | |||||||
|
№ |
х1 |
х2 |
f(X) |
S1 |
S2 |
λ1 |
λ2 |
|
3 |
2.440 |
1.133 |
0.0680 |
-0.201 |
-0.013 |
-0.0201 |
-0.0013 |
|
2.239 |
1.119 |
0.0033 | |||||
|
Поиск по образцу | |||||||
|
№ |
х1 |
х2 |
f(X) |
λ1 |
λ2 |
||X(k+1) - X(k)|| |
Критерий |
|
1 |
2.440 |
1.133 |
0.0680 |
-0.0201 |
-0.0013 |
0.0492 |
Достигнут |
|
2 |
2.420 |
1.131 |
0.0558 | ||||
|
3 |
2.400 |
1.130 |
0.0451 | ||||
|
4 |
2.380 |
1.129 |
0.0357 | ||||
|
5 |
2.360 |
1.127 |
0.0277 | ||||
|
6 |
2.339 |
1.126 |
0.0209 | ||||
|
7 |
2.319 |
1.125 |
0.0153 | ||||
|
8 |
2.299 |
1.123 |
0.0108 | ||||
|
9 |
2.279 |
1.122 |
0.0073 | ||||
|
10 |
2.259 |
1.121 |
0.0048 | ||||
|
11 |
2.239 |
1.119 |
0.0033 | ||||
|
12 |
2.219 |
1.118 |
0.0026 | ||||
|
13 |
2.199 |
1.117 |
0.0028 | ||||
Таким образом, из таблицы видно, что экстремум найден на третьей итерации, точка [2.199;1.117] является минимумом заданной функции с точностью 0,05.
Р
ис.2.2.
Графическая иллюстрация поиска
экстремума функции методом прямого
поиска Хука-Дживса.