И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 15
Текст из файла (страница 15)
Прн написании параграфа нспольоовапись работы !343 — 34б!. 1.11 Методы поиска интервала наибольших значений многозкстремальных функций 3 а д а ч а !. Найти агд шах /о (х) для заданной функции лб[ав,ьа] /о: й' - 11' и заданного отрезка (а„бо). Определении 1. Зафиксируем число 6) О и определим класо Ко функций, удовлетворяющих условию: для любой <р (х) из Ко существует отрезок Л длиной 6 из [а„бо) такой, что из х Е 6, х' Я Л следует ф (х) ) ф (х'). Определение класса функций йо вытекает из определения класса Ко, если положить 6 = (Ьо — ао)/2. Предположение 1.
Функция /о непрерывна на (а„Ьо! и принад.лежит классу Ка. Ниже приводится метод для отыскания отрезка 6 для функции /о (х), принадлежащей к классу Ка. Если вычислить значения функции /о (х) из класса Ко в точках по+ б, по + 26, ..., по + гпб, где (Ь,— ао)/6 — 1, если (Ьо-ао)/6 — целое число; Еп!((Ь,— ао)/6), если (Ь,— ао)/6 — нецелое число, и среди этих точек выбрать точку г(с наибольшим значением функции /о (б), то точка с( принадлежит /ь, а область /а следует искать на отрезке Ы вЂ” 6, г(+ 6!. Таким образом, задача отыскания области 6 наибольших значений функции /о (х) из класса Ко сводится к задаче отыскания области Л для функции из класса 1.о. Если наибольшее значение достигается в двух соседних точках по+ !б, ао+ (! + + !) 6, то искомая область 6 совпадаетс интервалом (ао+ /б, ао + + (!+ 1) б!.
Приводимый ниже алгоритм для функции /о (х), принадлежащей классу 1.о на отрезке Ы вЂ” 6, 6 + г!), за (и — 1) итераций находит 6 отрезок в заданной погрешностью н ) О за наименьшее воз- бб можное число итераций. Для начала работы алгоритма необходимо знать некоторый интервал [а~О, р»»[, принадлежащий отрезку Л и содержащий точку А Алгория»м 1 Н а ч а л о. 1. Выбрать число е ) Π— погрешность вычисления области»».
П. Задать отрезок Л» — — [и~+, й~+[, который содержит точку д н принадлежащий области»». П1. Вычислить натуральное число п, удовлетворяющее условию Л-! (( — 0) — » (~" ! где Р„ь Є— числа Фибоначчи (т. е. такие, что Р» = Р, = 1, Р, = Р~ ~+ Р~ м 1 = 2, 3, ...); б»= р» — а» ° + + 1Ч. Положить й = О, 6,= 8 (т. е. 6,— пустое множество). 0 с н о в но й ци к л.
Ч. Вычислить Ỡ— длину интервала [а»», р+~[, принадлежащего отрезку»», и величину ч»= 6 — б». Ч1. Найти точку и„лежащую слева от точки [!+а на расстоянии 6, и найти точку б», лежащую справа от точки а+~ на расстоянии б. ЧП. Если оба полуинтервалы Ь», а») и ([1», р»1 не содержат точек, в которых функция 1» вычислялась на предыдущих итерациях, то вычислить значения функции 1» (х) в точках х~ = с»~+ к»Р» — » — »(Рл» х» ~~+ [ у»Рп» вЂ” 2!Р» — м положить 6»+~ = 6»[) [х») [) [х») и перейти к шагу ЧП1; если полуинтервал Ь», с»»') содержит точку у», в которой функция вычислялась на предыдущих итерациях, и полуинтервал ([)Ц, [)»! не содержит точек, в которых функция ~, вычислялась на предыдущих итерациях, то вычислить функцию )» в точке х» = р» — (у»вЂ” — с»»), положить 6».»~ — — 6»[) (х»! и перейти к шагу ЧШ; если полуинтервал (р»", р»! содержит точку у», в которой функция 1» вычислялась на предыдущих итерациях, а полуинтервал Ь», а») не содержит таких точек, то вычислить функцию 1» в точке х» = = а»+ (р» — у»), положить 6»ч~ = 6 [) (х»! и перейти к шагу Ч1П.
ЧП1. Используя имеющееся на й-й итерации множество точек 6».»ь значения функции г» в точках множества 6»+~ и интервал Ь», [)» 1, принадлежащий отрезку Л, вычислить наибольший интервал Ь»+~ и Ц+~.~]; принадлежащий отрезку Ь, с помощью следующих пяти правил: П если х, х'~ Л и к ( г «( х', то з с й' 2) если х~Л и ):»(х')~1»(х), то х'сц; 3) если х [» Ь н 1» (х') ~~ 1» (х), то х'К Ж 4) если х Е Л и [ к — х' [ ) б, то х' [С Л; 5) если х Е Ы вЂ” б, й! и х'Е Ы, с[ + 6[, то нз !й (х): !й (х') и [х — х' ! (6 следует хр б, а нз [й(х) ) !й(х') н ! х — х' ! > 6 следует х'Я Л. 1Х. Если /г и — 2, то положить й = й + ! и перейти к шагу У; иначе прекратить вычисления. Теорема !. Если функция !й (х) принадлежит классу!.ь на интервале Ы вЂ” б, й + 6[, то алгоритм 1 за (и — 1) итераций находит интервал [а+ и []+ ~), принадлежащий отрезку Л, такой, что []ч ~ — а„~ ) б — а, причем алгоритм ! является оптимальным алгоритмом поиска области б с погрешностью а, т.
е. находит область б с погрешностью а за наименьшее возможное число шпераций. Замечание !. Если в алгоритме 1 на шаге ЧИ точки хй и хй вычнслять по формулам хй = Яй + ч»»рй — й — а!» и — й хй — р» чйрп» вЂ” 2!Рй — й то для этого алгоритма теорема 1 остается в силе. Библиографические укаеания. Параграф написан на сено»анна рабат [350, 35]1. 1.12. Методы поиска глобального минимума, испольвутощие стохастичесиие автоматы 3 а д а ч а О. Найти агу гп[п !о (х) для заданной функции »Я]й,,»»] !а .
Л' -»- Вй и заданного интервала [а„ Ьо!. Лредположенив О. Функция !й непрерывна на [а„Ь,! н имеет единственный глобальный минимум на [ай, Ь,!. В начальной стадии метода интервал [а„Ь,! разбивается на т (достаточно большое число) подынтервалов 1;, ! = 1, ..., т, равной длины ш = (Ь,— а,)/т и каждому подынтервалу 1], ! = 1, ..., т, ставится в соответствие состояние 5], ! = 1, ..., т, стохастнческого автомата. Стохастнческнй автомат задается вектором вероятностей Р (й) = (р» (Й), ..., р (й)), каждая 1-я компонента которого характернзует вероятность р] (й) перехода автомата в состояние 5].
На й-й итерации по заданному вектору р ([е) генерируется состояние автомата 5,, 1» Е И: т!. Выход стохастнческого автомата прннадлежит интервалу [ш (1» — 1), ип»! с равномерным распределением вероятностей. Вектор вероятностей р (й) прн переходе от одной нтерации к другой преобразуется таким образом, что вероятность р, (й), соответствующая интервалу 1„который содержит точку глобального минимума, возрастает, а все вероятности р] (и), ! = 1, ..., т, ! Ф 1, уменьшаются. Приводимые ниже алгоритмы находят интервал 16е 1» Е [1: т), в котором с вероятностью, достаточно близкой к единице, находится точка глобального минимума функции !й на Ый Ь»1 ба Методы поиска глобального минимума, использующие стохастические автоматы, целесообразно применять тогда, когда вычисление функции /е (х) сопровождается сильнымн помехами.
1. Алгорптм, пепольеуюпгпй модель Буша — Моетеллере В алгоритме ! вектор вероятностей р (й) на каждой итерации преобразуется по формулам Буша — Мостеллера. Алгоритлг ! Н а ч а л о. 1. Разбить интервал (а„Ь,! на т подынтервалов /, равной длины га = (Ь, — ае)/т и поставить в соответствие каждому !„г = 1, ..., т, единственное состояние автомата Яо / = 1, ..., т. П. Положить р, (0) = 1/т, г = 1, ..., т. П1. Положить Яг — — а, г' = 1, ..., т, где а — достаточно большое положительное число. 1Ч. Выбрать константу е ) 0 (з — заданная точность выполнения условия оптимальности автомата в случайной среде).
Ч. Положить й = О. Ос н о ни о й ци к л. Ч!. С помощью вектора вероятностей Р (/г) = (Рг (/г) Рг (/г)..., р (/г)) сгенерировать случайное состояние автомата 5 (/г) = 3;», ге Е 11: т). Выбрать выход автомата хг„(Й), принадлежащий интервалу (гп (г,— 1), гп!е) (считается, что случайная величина хг, (/г) равномерно распределена на этом интервале). ЧП. Вычислить значение !е (хг„). ЧП1.
Вычислить Я" ш = пни Яг". ьягмм 1Х. Определить вход автомата у (й + 1) по правилам О, если Ц'и(/е(хг,); 1, если Я*м»!е(х, ). Х. Положить 9,, = !о (хг„) (остальные значения г./г, г = 1, ... ..., т, г' Ф г„не меняются). Х1. Вычислить вектор а (/г) = (а, (л), ..., а (й)), определяющий структуру автомата на /г-й итерации, по правилам: если у (й + 1) = 1, то а, (/г) = ! и а; (л) = 0 для ! = 1, 2, ... т /'чь /е' если у (й + 1) = О, то а; (й) = р; (й), / = 1, ..., т. ХП. Преобразовать вектор вероятностей р (/г) по формуле Буша — Мостеллера р(/г ! !) (Х!+(1 Х)А(й))Р(/г), где / — единичная матрица размера т Х т; Х вЂ” постоянная вели- чина, принадлежащая интервалу 10, 1); А (й) — т Х т-матрица, состоящая из т одинаковых столбцов а (й). 69 ХП1. Если с заданной точностью е выполняются следующие условия оптимальности поведения автомата в случайной стационарной среде: [р;„„,(Ь+ 1) — 1[(е, если 9;.
„,(Я,". для всех /~/е+~, '<!л) рг(Ь+ 1)(е для всех /= 1, ..., и, /~/и+и (ьа) то прекратить вычисления (в этом случае точка глобального мини* мума с вероятностью, близкой к единице, принадлежит интервалу 1~а+,); иначе положить Й = /г + 1 и перейти к шагу Ч1. При удачном разбиении интервала [ос, Ье! на подынтервалы //, / = 1, ..., т, алгоритм 1 приводит к интервалу [ае+ (/е+1 — 1) в, ае+ /е.ь1 в), в котором с вероятностью, достаточно близкой к единице (за счет выбора з), находится точка глобального минимума функции /е (х) на интервале [а„Ье!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
