И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 16
Текст из файла (страница 16)
В. Алгоритм, исиольауиеиий усредиеииые аиечеиил фуиимии В этом пункте приводится алгоритм, в котором вектор вероятностей р (/с) преобразуется по информации о средних значениях функции /е на соответствующих подынтервалах. Алгоритле 2 Н а ч а л о. 1. Разбить интервал [а„Ье! на и подынтервалов 1, равной длины в = (Ь, — ае)/и, и поставить в соответствие каждому 1,, 1 = 1, ..., гп, единственное состояние стохастического автомата П. Положить р, (О) = 1/т, 1 = 1, ..., и. П1. Выбрать константу е ) 0 (а — заданная точность выполнения условия оптимальности стохастического автомата в случайной стационарной среде).
1Ч. Выбрать параметр алгоритма у ) О. Ч. Вычислить массив средних значений г;(О) =(/ (ш(1 — '/,))) ~, 1=1, ..., т. Ч1. Положить Ь = О. Ос н о в н о й ц и к л. ЧП. С помощью вектора вероятностей р (Ь) = (р1 (Ь) " р„(Ь)) сгенерировать случайное состояние автомата Я (Ь) = 5с,, /„Е 11: т!. Выбрать выход автомата х,„(Ь) принадлежащий интервалу Ь (/е — 1), аи'„! (считается, что случайная величина х;, (Ь) равномерно распределена на интервале [в ([е — 1), ай„!). ЧП1. Вычислить значение /е (х~ ). 1Х.
Вычислить значение з~е (/с+ 1) = Уе Фе)) Х, Вычислить массив средних значений г, (Ь + 1), 1 = 1, ..., гп 70 по правилам: ге»(й+ 1) = Хг~ (й) +(1 — Л)ге„(й+ 1), 0(Л(1; г1(й+ 1) = Лг1(й), 1= 1, ..., т; 1чь 1». Х1. Вычислить вектор вероятностей р (1е + 1) = (р, (й + 1), ... ..., р (й + 1)) по формулам ре(й + 1) = ге(й + 1)l ~~ г~ (й + 1), 1 = 1, ..., т. 1=! ХП.
Если с заданной точностью е выполняются условия оптимальности (1.7), (1.8) поведения автомата в случайной стационарной среде, то прекратить вычисления; иначе положить й = й + 1 и перейти к шагу ЧП. Алгоритм 2 обеспечивает выполнение условий (1.7), (1.8), если произведено удачное разбиение интервала [аа, Ье) на подыитервалы 1н 1 = 1, ..., т, и выбран подходящий параметр алгоритма у. Библиографические указания. Прн написании параграфа нсполъзоаалнсь работы !17, 181. 1.13. Адаптивные методы 1. Алгоритмы Кнфора — Вольфоанна 3 а да ч а 1. Найти агн шах 1»(х) для заданной функции куя' 1~; Д' и'. ПРедположение 1.
ФУнкциЯ 1е Унимодальна. Метод Кифера — Вольфовица применяется для минимизации унимодальных функций, вычисление которых проводится со случайными помехами. Алгоритм 1 Н а ч а л о. 1. Выбрать произвольное начальное приближение х' Е 11'. П. Положить й = О. О с н о в н о й ц н к л. П1. Вычислить значения шагового множителя р, и смещения 6», удовлетворяющие условиям теоремы 1. 1Ч. Найти величину г (х»+ 6 ) — результат вычисления со случайными помехами значения функции 1» в точке х»+ 6». Ч. Найти величину г (х» — 6») — результат вычислении со случайными помехами значения фуйкции )а в точке х» — 6„.
Ч1. Вычислить следующее приближение х"+' = х»+ (р„/6,) (г(х'+ 6„) — г(х» — 6,)). ЧП. Положить й = й + ! и перейти к шагу 1П. Теорема 1. Пусть. функции 1е являапся унилгодальной и удовлетворяет условию ! Ро (х) — 1а (У) / ~ сс, ! х — х»1+ аа ( оо, где хо — ре~иение задачи 1; ао а — некоторые постоянные. 71 Тогда, если в алгоритме'! ошибка вычислений функцииГ» равномерно ограничена и имеет нулевое ма»пематическое ожидание, т. е. Е (г (х» ~ 6») — 1» (х» й= 6»)) = 0' Е Е (г (х" ~ 6») — 1» (х» ~ 6»))' ( ' и если шаговые множители р, и смещения 6» такие, что р»)0; 1!(пр» 0; !пп6,=0; » ОО Ю «« Х р = к Х,(р»16»)' =. пю последовательность (х»)».»ь порожденная алгоритмом 1, сходится к точке максимума х* функции (о в среднекладршпическом и в вероятностью 1, т.
е. 1пп Е(х» — хе)о = 0; Р (!ип х» = хо) = !. Замечание 1. Если приближение х»+' на шаге Ч1 алгоритма 1 вычислять по формуле х = р»зяп! »+~ х»+ 1 ( г(«»+6»! — г(㻠— 6»! ! 26» то получится нормализованный вариант метода Кифера — Вольфовица. 2. Простой перебор Зада ч а 2. Найти агд пип 1»(х) для заданной функции «с(о«'»Л го. Е' -» Е' и заданного отрезка (ао Ьо). Предположение 2. Функция 1» такова, что на отрезке [а, Ь„) точка ее локального минимума хо является точкой абсолютного минимума До на отрезке (ао Ьо). Алгоритм 2 Н а ч а л о. 1.
Задать: число е ) 0 — точность вычисления точки минимума функции 1» на отрезке (ао, Ь»1; натуральное число У (рекомендуется выбирать число М из отрезка (!О', 10'!); положить й = О. Основной цикл. П. Положить( О. 111. Положить х»о а„вычислить (о (а») и положить(о (х»,о) = 1» (а»). 1Ч. Вычислить смещение Ь» = (Ь» — а»)/М. Ч.
Вычислить точку х»,„.~ = х»л+ П» и вычиолить 1» (х»,~+~). 72 Ч1. Если 1е (хь» ~) ) ге (хьл), то перейти к шагу Ч11; иначе перейти к шагу Ч111. ЧП. Если / = О, то положить аа»л = а,. Ььы = хьл н перейти к шагу !Х; иначе положить аа+~ = ха,7 ь Ьа+~ = ха,.г+~ и перейти к шагу 1Х. Ч(П. Если 1 ( й7 — 1, то положить 1 = 1+ 1 и перейти к шагу Ч; иначе положить аа.ы — — хан ь Ьа~ы = Ь„и перейти к шагу 1Х. 1Х.
Если Ьа» ~ — аа»л ) е, то перейти к шагу Х; иначе положить х*= (а»+~+ Ьь»»)/2 и прекратить вычисления. Х. Положить й = й + ) и перейти к шагу 11. Теорелш 2. Если выполнено предположение 2, то для произвольного е ) О алгоритм 2 за конечное число игпераций приводит в точку хе такую, что (хе — хе)(е. Занечание 2. Недостатком метода простого перебора является то, что во многих «лишних» точках приходится вычислять значение фУнкции г„что нежелательно в слУчае, когда 1» опРеделЯетсЯ в Результате эксперимента или когда для вычисления значения функции ге в точке тРебУетсЯ значительное машинное вРемЯ. Библиографические рказанил.
При иаписаиии параграфа использовались работы 1194, 358, 5021. Глава 2 МЕТОДЫ ОПТИМИЗАЦИИ ДИФФЕРЕНЦИРУЕМЫЕ ФУНКЦИИ 2.1. Градиентные методы 3 а да ч а 1. Найти агд ппп 7 (х) для заданной функции «яаа ге Предположение 1. Функция ге дифференцируема в В". В градиентных методах минимизации за направление движения в й-й итерации выбирается вектор, обратный градиенту функции 7е в точке хг.
Различные ваРианты гРаДиентного метоДа отличаютсЯ друг от друга способом выбора шагового множителя в й-й итерации, а также теми нли иными способами (разностной) аппроксимации градиентов. 1. Метод иаисворевшего спуска В методе наискорейшего спуска шаговый множитель ра (гг = = О, 1, ...) вычисляется из условия минимума функции 1е в направлении антиградиента — Ч)'е(ха), т. е. р„=- атя ППП1е (Х" — рЧ1» (Х')). о»о 73 Алгоритм 1 Н а ч а л о. !. Выбрать произвольную начальную точку ха Е ~ В" и положить /а = О, Оси о в ной ни к л. 1!.
Вычислить Ч/а(ха). Ш. Если Ч/е (ха) = О, то положить х*= ха и прекратить вы- числения; иначе перейти к шагу !Ч. 1Ч. Вычислить шаговый множитель р из условия /а(ха — р„Ч/ (ха)) = пйп/а(ха — рЧ/ (хе)). рва Ч. Вычислить следующее приближение ха+' = ха — РаЧ/е (ха). 'Ч1. Положить й = й + 1 и перейти к шагу П. Теорема 1.
Если выполнено предположение 1 и (!) — функция1 а ограничена снизу в В"; (й) — градиент функции /а удовлетворяет условию Липшица '1Ч/а(х) — Ч/а(У))(а(х — У1 Ух, УСВ", а(оо, то для бесконечной последовательности (ха)~ а, порожденной ал- горитмом 1, справедливо соотношение 1,Ч/а (ха) 1-» О при й -» оо. Теорема 1'. Если выполнены условия: (1) — функция /а дважды не- прерывно дифференцируема в В"; (И) — матрица вторых производе ных Ч„„/а (х) функции /а удовлетворяет условиям ~)У)е((Ч,',/а(х)У, У)(У(У(е, У~~)О, при любых х, у Е В", то бесконечная последовательность (ха) а-о порожденная алгоритмом 1, сходится к точке минимума х* со скоростью геометрической прогрессии со знаменшпелем ц = = (у — р)/(у + р), т.
е. ! х"+' — х* ! ~ (~/у) и ! ха — х' ! д'+'. Алгоритм 1 на практике используют редко. Это связано, в част- ности, с невозможностью реализовать шаг 1Ч в большинстве прак- тических случаев. Поэтому на практике чаще применяют модифи- цированные методы наискорейшего спуска. В. МоднФннвроаавнмй метод навекорейшего антака Алгоритм 2 Шаги 1 — 111 такие, как в алгоритме 1. 1Ч.
Определить число рм удовлетворяющее равенству ~а = пип /а (ха — ~)Ч/а (х')). а а Ч. Вычислить параметр Лм удовлетворяющий условию ((В) теоремы 2. Ч1. Вычислить шаговый множитель р„из условияйа(х раЧ/а(х )) ~~(1 Ле)/а(х ) +М» (2. 1) И1. Вычислить следуюшее приближение х»+' = х» — р»Ч/ (х»).
ЧШ. Положить я = я + 1 и перейти к шагу П. Теорема 2. Если выполнено предположение 1 и (1) — градиент Функции Д» удовлетворяет условию /1ипшица 5Ч/о(х) — Ч/ь(у)»»(и!! х — у), Чх, ус В", а(оо; (й) — начальное приближение хь таково, что зпр )х' — х" 5 = с$! аш Х, = т) ( ьь, *, -сх, где Х, = (х / /«(х) ( Д> (хь), х Е В"); ((В) — параметры Л», й = = О, 1, ..., удовлетворяют неравенств м Л ( Л» ( 1, где Л вЂ” про- извольная константа из полуинтервала (О, 1); (1о) — функция /ь выпукла в В", то для бесконечной последова- тельности (х»)» ь, порожденной алгоритмом 2, справедлива оценка скорости сходимости по функционалу /»-1 ~-1 /о(х») /о (2ат)«~ ~ Л;) (2ац»/Л/«, й = 1, 2, »=о С й»п(г» /,( ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
