Лекция №1 (стр. 6 )

По существу методы прямого поиска простейшего типа заключается в изменении каждый раз одной переменной, тогда как другие остаются постоянными, пока не будет достигнут минимум.

Например, переменная х1 устанавливается постоянной, а х2 изменяется до тех пор, пока не будет получен минимум. Затем, сохраняя новое значение х2 постоянным, изменяют х1 , пока не будет достигнут оптимум при выбранном значении х2 и т. д. Однако такой алгоритм работает плохо, если имеет место взаимодействие между х1 и х2 , т. е. если в выражение для целевой функции входят члены, содержащие произведение х1 · х2.

Хук и Дживс предложили логически простую стратегию поиска. Алгоритм прямого поиска состоит из следующих операций. Задаются начальные значения всех переменных , а также начальное приращение вектора . Чтобы начать "исследующий поиск", вычисляют значение функции f(x1, x2, ..., xn) в базисной точке. Базисная точка - начальный вектор предлагаемых значений независимых переменных (). Затем в циклическом порядке изменяется каждая переменная (каждый раз только одна) на выбранные значения приращений, пока все переменные не будут изменены. Так что и т. д. Если приращение не улучшает целевую функцию, то изменяется на - , т. е. и значение f(x1, x2, ..., xn) проверяется так и ранее. Если значение f(x1, x2, ..., xn) не улучшают ни , ни , то оставляют без изменений.

Процесс итераций повторяют. Затем изменяют на величину и т. д. пока не будут изменены все независимые переменные. На этом "исследующий поиск" завершается. На каждом шаге (или сдвиге по независимой переменной) значение целевой функции сравнивается ее значением на предыдущем шаге (в предыдущей точке). Если целевая функция улучшается на данном шаге, то ее старое значение заменяется на новое при последующих сравнениях. Если произведенное возмущение по неудачно, то сохраняется прежнее значение f(x1, x2, ..., xn). 6. После проведения одного (или более) исследующего поиска применяется стратегия поиска по образцу. Удачное изменение переменных в исследующем поиске [т. е изменение переменных. которое изменили f(x1, x2, ..., xn) ] определяют вектор в Е, указывающий направление минимизации, которое может привести к успеху. Поиск по образцу проводится вдоль этого вектора до тех пор, пока f(x1, x2, ..., xn) уменьшается на каждом шаге. Поиск по образцу проводится в соответствии с правилом акселерации - координаты точки в которой достигнут успех. где - предыдущий базисный вектор . 7. Далее проводится исследующий поиск типа II дают приращение новой базисной точки и xн. б. + x xн. б. + x вычисляют значение функции в этих точках. 8. Если f(x1, x2, ..., xn) не уменьшается в процессе исследующего поиска типа II, говорят что дачный поиск неудачен. 9. Последовательность поисков заканчивается, если значение целевой функции < e. Поиск может быть закончен, если на данном шаге изменение каждой переменой меньше, чем d. Пример максимизировать целевую функцию. f(x1, x2) = 1. Начальный вектор начальное приращение f(2.00;2.80) = 0.059 2. Исследующий поиск типа I = 2.00 + 0.60 = 2.60 f(2.60;2.80) = 0.048 (неудача) = 2.00 - 0.60 = 1.40 f(1.40;2.80) = 0.073 (успех) = 2.80 - 0.84 = 3.64 f(1.40;3.64) = 0.052 (неудача) = 2.80 - 0.84 = 1.96 f(1.40;1.96) = 0.104 (успех) Поиск типа 1 - удачный. 3. Поиск по образцу по правилу акселерации. = 2*1.40 - 2.00 = 0.80 новая базисная точка = 2*1.96 - 2.80 = 1.12 f(0.8;1.12) = 0.22 4. Поиск типа II успех или неудача оценивается путем сравнения с f(0,8; 1, 12) = 0,22

f(1,40;1,12) = 0,14 = 0,80 + 0,60 = 1,40 f(1,40;1,12) = 0,14 неудача = 0,80 - 0,60 = 0,2 f(0,20;1,12) = 0,38 успех = 1,12 + 0,84 = 1,96 f(0,20;1,96) = 0,19 неудача = 1,12 - 0,84 = 0,28 f(0,20;0,28) = 0,67 успех 5. Опредяляют поиск по образцу успешный f(0,20;0,28) = 0,67 > f(1,40;1,96) = 0,104. Запоминают (0,20;0,28) и т. д. xi новое = xi предыд } число неудач в исслед. поисках начиная от последнего успешного исслед. поиска