Нелинейное программирование (стр. 7 из 7)
- текущая базовая точка, 
- предыдущая базовая точка, 
- точка, построенная при движении по образцу, 
- следующая (новая) базовая точка.Приведенная последовательность характеризует логическую структуру поиска по методу Хука — Дживса.
Структура метода поиска Хука — Дживса
Шаг 1 . Определить:
начальную точку
,приращения
коэффициент уменьшения шага
,параметр окончания поиска
.Ш а г 2. ровести исследующий поиск.
Ш а г 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением
целевой функции)?
Да: перейти к шагу 5.
Нет: продолжать.
Ш а г 4. Проверка на окончание поиска.
Выполняется ли неравенство
?Да: прекратить поиск; текущая точка аппроксимирует точку оптимума
.Нет: уменьшить приращения по формуле
Перейти к шагу 2.
Ш а г 5. Провести поиск по образцу:
Шаг 6. Провести исследующий поиск, используя
в качестве базовой точки;пусть
полученная в результате точка.Ш а г 7. Выполняется ли неравенство
?Да: положить
Перейти к шагу 5.Нет: перейти к шагу 4.
Пример 6 Поиск по методу Хука — Дживса
Найти точку минимума функции
используя начальную точку 
.Решение.
Для того чтобы применить метод прямого поиска .Хука — Дживса, необходимо задать следующие величины:
векторная величина приращения = 
, 
коэффициент уменьшения шага = 2, 
параметр окончания поиска = 10-4.Итерации начинаются с исследующего поиска вокруг точки
, которой соответствует значение функции 
Фиксируя 
, дадим приращение переменной 
: 
Успех.Следовательно, необходимо зафиксировать
и дать приращение переменной : 
Успех.Таким образом, в результате исследующего поиска найдена точка
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Далее проводится исследующий поиск вокруг точки
, который оказывается удачным при использовании положительных приращений переменных х1 и х2. В результате получаем точку 
Поскольку
, поиск по образцу следует считать успешным, и 
становится новой базовой точкой при следующем проведении поиска по образцу. Итерации продолжаются, пока уменьшение величины шага не укажет на окончание поиска в окрестности точки минимума. Последовательные шаги реализации метода показаны на рисунке.Из примера следует, что метод Хука — Дживса характеризуется несложной стратегией поиска, относительной простотой вычислений и невысоким уровнем требований к объему памяти ЭВМ, который оказывается даже ниже, чем в случае использования метода поиска по симплексу.
 |
Итерации поиска по методу Хука-Дживса на примере