Метод Хука и Дживса

Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке.

При заданном начальном векторе исследующий поиск по координатным направлениям приводит в точку . Последующий поиск по образцу в направлении приводит в точку . Затем исследующий поиск, начинающийся из точки , дает точку . Следующий этап поиска по образцу вдоль направления дает . Затем процесс повторяется.

Рисунок 5.3.1 - Первые две итерации метода Хука и Дживса

Алгоритм Хука и Дживса с использованием одномерной минимизации

Рассмотрим вариант метода, использующий одномерную минимизацию вдоль координатных направлений и направлений поиска по образцу.

Начальный этап. Выбрать число для остановки алгоритма. Выбрать начальную точку , положить и перейти к основному этапу.

Основной этап.

Шаг 1.Вычилить - оптимальное решение задачи минимизации при условии принадлежит . Положить . Если , то заменить на и вернуться к шагу 1. Если , то положить . Если , то остановиться; в противном случае перейти к шагу 2.

Шаг 2. Положить и найти - оптимальное решение задачи минимизации при условии принадлежит . Положить , заменить на и перейти к шагу 1.

1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.