Методы Оптимизации Систем Автоматизированного Проектирования

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

Стратегия поиска. Метод представляет собой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу. Цель исследующего поиска – выявление локального поведения целевой функции и определение направления ее убывания. Эта информация используется при поиске по образцу вдоль направления убывания целевой функции.
Исследующий поиск начинается из некоторой начальной точки , называемой старым базисом. В качестве множества направлений поиска выбирается множество координатных направлений. Задается величина шага, которая может быть различной для разных координатных направлений. Фиксируется первое координатное направление и делается шаг в сторону увеличения соответствующей переменной. Если значение исходной функции f(x) в пробной точке меньше значения функции в исходной точке, то шаг считается удачным. В противном случае из исходной точки делается шаг в противоположном направлении с последующей проверкой поведения функции. Если и в этом случае не происходит уменьшения функции, то происходит уменьшение шага и процедура повторяется. Исследующий поиск по данному направлению заканчивается, когда текущая величина шага становится меньше некоторой величины. После перебора всех координат исследующий поиск завершается, полученная точка называется новым базисом.
Поиск по образцу заключается в движении по направлению от старого базиса к новому. Величина ускоряющего шага задается ускоряющим множи-телем . Успех поиска по образцу определяется с помощью исследующего поиска из полученной точки. Если значение функции в наилучшей точке меньше, чем в точке предыдущего базиса, то поиск по образцу удачен, в противном случае происходит возврат в новый базис, где продолжается исследующий поиск с уменьшенным шагом.
Обозначим через – координатные направления:

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

Алгоритм метода.
Шаг 1. Задать начальную точку, число- для остановки алгоритма, начальные значения приращений по координатным приращениям, ускоряющий множитель
Шаг 2. Провести исследующий поиск по выбранному координатному направлению:

Шаг 3. Проверить условия:
а) если i < n, то положить i= i+1 и перейти к шагу 2. (продолжить исследующий поиск по оставшимся направлениям);
б) если i = n, проверить успешность исследующего поиска:
- если, перейти к шагу 4.
- если, перейти к шагу 5.
Шаг 4. Провести поиск по образцу.

В точкепровести исследующий поиск, в результате которого получается точка
Если, то точкастановится точкой нового базиса, а - точкой старого базиса. Перейти к шагу 5. .
Если, то поиск по образцу считается неудачным, точки ,аннулируются, точкаостается точкой нового базиса, а- точкой старого базиса. Перейти к шагу 2.

Стр.: ..., 2