- •Лекция 4. Методы многомерной оптимизации
- •4.1.Метод Нелдера-Мида
- •4.2.Метод Хука-Дживса
- •4.3.Градиентные методы оптимизации
- •4.3.1.Метод наискорейшего спуска
- •4.3.2.Метод Ньютона
- •4.3.3.Модифицированный метод Ньютона
- •4.3.4.Метод Марквардта
- •4.3.5.Квазиньютоновские методы
- •4.3.6.Численная аппроксимация градиентов
4.2.Метод Хука-Дживса
Данный метод один из наиболее простых прямых методов поиска (1960 г). Метод использует попеременно исследующий (зондирующий) поиск и поиск по образцу (модельный ход).
1. Исследующий поиск позволяет из текущей точки пространства выбрать направление, движение в котором обеспечивает минимизацию целевой функции.
2. После определения направления от точки выполняется поиск по образцу (модельный ход), т.е. используется информация о проведении функции, полученная в исследующем поиске.
Алгоритм Хука-Дживса
1. Ввести начальные значения: - начальная базисная точка; – шаг изменения переменной; - минимальное значение шага; < 1 – константа изменения длины шага
2. Вычислить значение ЦФ в базисной точке
3. Выполнить исследующий поиск в точке , получить новую базисную точку и значение ЦФ в этой точке, .
4. Если (значение ЦФ уменьшилось), перейти на => 8
5. Выполнить поиск по образцу, используя новую базисную точку ,
.
6. Выполнить исследующий поиск в т. , получить точку и значение ЦФ .
7. Если , определить новую базисную точку: присвоить ; ; , перейти на => 5.
8. Если , то уменьшить длину шага, , перейти на => 3.
9. Закончить поиск, печатать результаты.
Окончание поиска происходит при условии, что длина шагов (минимального заданного значения)
Исследующий поиск метода Хука-Дживса содержит такие шаги:
1. Вход: базисная точка , значение ЦФ ;
Задать начальное значение счетчика итераций k = 1 и начальное значение шага переменой h.
2. Увеличить координату на шаг :
(для k =1 будет )
Вычислить значение функции
3. Если , перейти на => 7
4. Уменьшить координату на шаг :
(для k = 1 )
5. Если , перейти на => 7
6. Если не достигнуто уменьшения ЦФ, оставить без изменений, и перейти на => 8.
7. Запомнить новые значения и .
8. Если не все переменные использованы, т.е. , то перейти к следующей переменной, , и перейти на => 2, иначе закончить поиск, перейти на => 9
9. Конец исследующего поиска. Получена новая базисная точка и значение ЦФ .
Достоинства алгоритма Хука-Дживса:
- используются простые операции, не приводящие к запрещенным арифметическим действиям (типа деления на 0);
- не высокие требования к памяти компьютера
Недостатки алгоритма:
- исследующий поиск выполняется только в направлении осей координат, что может привести к прекращению поиска без достижения минимума, если направление «оврага» не параллельно осям координат;
- большое количество вычислений целевой функции.
В этом случае при выполнении условия окончания поиска целесообразно выбрать другую начальную точку и повторить поиск минимума. Решение можно считать найденным при совпадении минимумов.
Окончание поиска по методу Хука-Дживса происходит при длине шагов меньше заданного . Если значение ошибки (целевой функции) не удовлетворяют проектировщика, то можно повторить процесс оптимизации, задав новые значения компонентов или модифицировать принципиальную схему для получения желаемого результата.