Первый этап реализуется путем выполнения пробных шагов в положительном или отрицательном направлении каждой из координатных осей относительно некоторой базовой (базисной) точки и подсчете значений ЦФ в этих точках. Сравнение полученных значений определяет последовательность изменений положения базовой точки. Последнее из таких положений (полученное после вариации всех переменных) определяет направление вектора, задающего направление основного поиска.
Второй этап реализуется путем выполнения рабочего шага.
Рассмотрим несколько начальных шагов процесса поиска точки экстремума методом Хука-Дживса для функции двух переменных. Используем при этом рис. 4.11.
 |
Рис. 4.11
Пусть X0 – некоторая начальная точка. Принимаем ее за начальную базовую точку X0б (НБТ). Пусть h – длина пробного шага.
Осуществляем пробный шаг в положительном направлении оси x1. Получаем точку X0б1+ . Определяем значение z(X0б1+ ). Если z(X0б1+) < z(X0б), то считаем шаг успешным и перемещаем исходную базовую точку в точку X0б1+ , которую называем текущей базовой точкой
Если перемещение из исходной точки в точку X0б1+ не вызвало уменьшения значения ЦФ то признаем выполненный шаг неудачным (неуспешным). (Именно такой случай приведен на рис. 4.11). Тогда выполняем пробный шаг в направлении, обратном направлению оси x1. Получаем точку X0б1- Определяем значение z(X0б1- ). Если выполняется условие z(X0б1-) < z(X0б), то считаем выполненный шаг удачным (успешным) и перемещаем исходную базовую точку в точку X0б1- , которую называем текущей базовой точкой. (Этот случай приведен на рис. 4.11).
Если шаги в обоих направлениях оси x1 оказались неудачными, то ИБТ остается без изменений и считается текущей базовой точкой. Будем обозначать текущую базовую точку, полученную в результате варьирования переменной x1, единым символом X0б1. (На рис. 4.11 X0б1 = X0б1-)
После выполнения пробных шагов в направлении оси x1 должно быть произведено аналогичное варьирование переменной x2 , осуществляемое вдоль соответствующей оси.. При этом в зависимости от особенностей ЦФ возможны перемещения текущей базовой точки X0б1 в точку X0б2+ или в точку X0б2- Возможен также вариант того, что при неудачных перемещениях предыдущая текущая базовая точка не изменит своего положения. Таким образом, в результате выполнения пробных шагов в прямом или обратном направлениях оси x2 будет получена некоторая текущая базовая точка X0б2 . (В роли такой точки на рис. 4.11 выступает точка X0б2- ).
Полученная в результате предварительного поиска по двум переменным базовая точка X0б2 определяет конец вектора S0 , в направлении которого далее будет осуществляться основной поиск. Началом такого вектора будет НБТ X0б .
Далее осуществляется основной поиск в выбранном направлении. Вектор направления основного поиска определяется по формуле:
S0 = X0б2 - X0б.
Положение новой точки для функции двух переменных (при k=0) определяется по формуле
X1 = X0б2 + (X0б2 - X0б) = X0б2 + S0 .
После этого полученная точка X1 принимается за новую начальную базовую точку X1б и процедура повторяется.
В общем случае предварительный поиск будет необходимо последовательно осуществить по n переменным оптимизации. Поэтому для сохранения общности будем называть точку, полученную в результате варьирования всех переменных ЦФ на k-ой итерации, последней базовой точкой k-ой итерации (ПБТ) и обозначать ее символом Xkб* . На рис. 4.11 Xkб* = X0б2.
В общем случае формулы для определения направления основного поиска и точки основного поиска имеют вид
Sk = Xkб* - Xkб , (4.19)
Xk+1 = Xkб* + (Xkб* - Xkб) = Xkб* + S0 . (4.20)
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.