Чураков Е.П. Оптимальные и адаптивные системы (1987) (1249286), страница 28
Текст из файла (страница 28)
Схема рсашюацип мего ла (рис 61) со.ссржит>1трЕЩ дд ство определении град>гентш эгед/ '11 г мнон нт льиос устройство и Шпегратьр, охв,чснпые образ НОй СВН.1ЬЮ П1,кажем, жО метод грзди Рис 61 е>жа де .вит лы1о прииг.хи к эк1 трехе>хе> функции С эсоп це. ыо рассмотрим скорость язменРпия аелпчпиы / при реализашш алгоритма (66) Если эга скорость пеотрицательиа, то функция / в процес- 127 се изменения А возрастает п алгоритм приводит к макси. муму функции Если же скорость изменения / неположи)йа..:::.е тельна, то отыскивается минимум / Итак, рассмотрим ЦА1 д (Х> дл ~~зд1 А> дпг дх д' ' дае д1 171 дУ(А) Мэт ~дг(А) С учеточ (6.6) получи1 — — .= Т ь ! — 1 .
Так как суммируются неотрицательные величины, то д/(А)/711)0 при 7>0 и й/(А)/й(<0 при 7-ш О, т. е при 7)0 алгоритм (66) приводит к увеличению функции, а при 7- 0 к уменьшению. Равенства в последних соотношениях достигаются при выполнении (62), что является условием экстремума. Следует иметь в виду, что в общем случае ф>ккция У в области Е может иметь несколько экстремумов, один из которых глобальный, а остальные — локальные.
Во всех этих точках выполняется условие (62) Но при глобальном экстремуме неравенство (61) лш>стиительпо выполняется во всеи области Е, а при ..оьалызом — справедливо лишь в некоторой малои об ласти. включающей точку А Глобальнни минимум являет ся наименьшим локальным миним>мом Алгоритм (66) приводи~ к локальному экстремуму, опре: еленному начальным значением вектора А /(ля достижения глобального экстремума применяют иные метсды, учитывая;шис много экстремальность ситуации [34), или мн.жократно приме няют метод градиента при различных начальных условиях, выбор которых осуществляют так, чтобы с,юстаточно болыпой вероятностью попасть в окрестность глобального экстоси ума Наиболее часто, особенно при машинных способах поиска экстр~ мума, метод градиента реал!жуется в дискре.- ной, яли шагоиои, форме В этом случае параметры А изменяются скачкообразно Пусж, Ао.- значение вектора А на п.м шаге.
Тогда последовательное приближение к экстремуму задается правилолг Л„,. - Л, 1-7нгзб1(дн), и - О, 1, 2... (6 7! х или в развернутой скалярной форме па, -1-78г:г!1!А,), л .. О, 1, 2,; 1 .. 1, и (68) С>щность алгоритма сводится к следующему: задаются некоторым начальным значением А. вектора А; в .той точке вычисляют гралиеит, и каждая составляющая вектора А получает прира|пенис, прппорциоиа. ьн ч части и пр пгз водной функцш. 1 по этой соса звляюсце(г в точке Ао шо ! 72 ь1ь мььоя н*нсноььяшьго спэснь Зададим некоторое начальное аначени вычнслплг в этой точке градным функции изменяем с постоянной скоростью, пропо '!ь,*::-':!; диенту в точке Аи так що г1Лий — 7 агап 1 (Л ) х (!-'*,:",': -'-' нлп в скалярной форме даг д -- у — 1 (Ль,! г .—.
1, пс и да, 7:;:..„".,'.,',ХДЕ, как н в методе граДиевта, 7 — —.сопз(, ,'„,б 7 Поиске максимума и 7" 0 ири поиске м В отличие от предыдущего метода здесь )!!,'', 'ляют лишь в на !альнон точке, дальнеи исходит в направлении, обусловленном и ' .нм градиента. Изменение вектора А п 1-';„'- г (6.12) происходит до тех пор, пока и Ж.„".:~,,'.",~':условие сУ/й(-.=-0, е Ас вектора А и У. Затем вектор А рциональной гра- (6.11) (6! 2) причем 7 0 прн ннимума функции.
градиент выс>исшее движение прозчальиым значенио правилу (6.!!), е будет получено (6.13) >73 Ф»;"., о)йгтр!!водит к точке Ан в этой точке снова вычисляют градн>ент, получают приращение и т. д. Вычисления по прнндниу (6 7) продолжаются до тех пор, !юка при некотором Внзчении л-. й не будут вьшолвечы условия при поиске зд:Ао*;.максимума и минимума соответственно 7(Аь !) (1(Аь); (6 9) 1(А,„,) ~7(дь) (6.10) ~ь„',~':,::;,':.,В рез>шьтазе принимают А=Ах. Следует иметь в виду, '~,".'н йто в отличие от непрерывного алгоритма (6.6), приводя* ';;. щего к экстремуму в условиях теоретической постановки задачи при любых значениях 7, шаговый алгоритм (6.8) ;» ','- чувствителен к величине 7: при малых 7 сходиыость к зкс 1:,3 .тремуму мон.ет оказаться слишком медленной, а при боль ~;.:„х Ших 7 алгоритм может оказаться расходящимся.
Поэтому 1!Д;:,".',в ряде случаев целесообразно использование переменного с'*::.1:-" -коэффициента 7, принимающего на каждом шаге свое значение 7, т. е приходим к нестационарному алгоритму, в структуре которого параметр 7 выбирают из соображений „наиболее быстрого достижения экстремальной точки (34) означающее, что в данном направлении достигнут экст ем ум функции У. Если А« — значение А, соответствующее реусловшо (6 13), то в точке Аг снова вычисляют градиент, и лальп«йшее изменение А наст так: ай ау '(нгааУ(А,).
х Э«от процесс продолжается опшь до выполнения (6 !3), затеи за юво вычисляют гралнент н т. л. до выполнения (621 Метод наискоренше«о спуска является ь ~ огоцикловым, по в пределах одного цикла градиент вычисляется едино.кды в начат е цикла Г!1« «шаганов реализациг«метода, обязанной ЭВМ, даик ение в ирене.,ах цикла осуществляется днскрегно, так что пг г«сохранении прешадущнл обозначений в пределах первого шшла А,, Д« --' '16«ай У А '*. гг'=.
О, 1, 2, (634) х Г(икл прадо,юкается до тех пор, пока не будет выполнено одно из ус.гонг:й (6 9) и,ги (6.10). В точке А, снова вгл гггс гяют грьдиегг;, к второй цикл строится по правилу Л«," А«+ (цгаг)У(Л ), л Уг, д+1, Ь-!.2, . 16.1бг В последующем циклы и двпгкения в их пределах конструируются подобным образом ло тех гор, пока пе сработает лакее-лиоо правило астапова алгоритма, напрем«р, ес гн молуль разности значении функции У в вача.шпон н конечнон точках очерелиого цикла не превосходит )счановг«синоп малов ие.~инины, двигьение прекращается. ««ч оьомдьянмя ммод ньючонь Во многих пракгическнх задачах одним из наибо.се улачпых в огноше»нв с<орости .чосшоьепня экстремума признается алгоритм, гчзвестгч~гп гол названием обоби(энного э«с«ода Ньготоиа и слелуюин,п ич общего соотногпенп«ч (64), если в качестве матрш,ы В использовать отрнца тельную обратную чщтркцу егорыч производных от функции У по А, т е « У 'Лг! Мэтр«:ца вторы~ произволнь:х называется хгатргчгр« "ессе нли гестшаном Ее структура совпалаег со счруг.гу 174 (Ьэачч«мачрицы Г (см.
в !.1), если в последней заменить 6 чф У, а и на а., 1=1, гп. Алгоритм движения к экстреи)ччу чэбобшенным методом Ньютона приобретает впд лл гш У(А)~ нгггбУ(А). ггч (лдь 'Гак, если А:=-а . скаляр и У(а)=--(а -Ь)', получаем :С!~!:,*':;,:.'м='"-а+Ь, т е. в этом случае алгоритм совпадает с мета."«~:,::;:. ";-(йом градиента при 7=-.--'/, и устойчиво приводит к экстгг'.-','"'-'ремальнои точке а= — Ь. В нных ситуациях алгоритм (6.16) ;гу,',:!'.;( обладает большей по сравнению с методом гралиента скоростью схолимости, т.
е. скоростью достижения экстремвльноп тогки, так как более полно учитывае~ профиль функции У(А) благодаря гессиаву. Реализация его, разу«,:";;г."',имеется, оо, ее сложна ггй, Дискретная форма алгоритма имеет вид А.г.::А. — ' — У«А), ''нгас1У(А,,) л.- О. ! 2 .. (6!7) В качестве правила астапова могкво использовать ус„;.;",;,:!,' лсвия (6.9), (6.!0) Прн кпалрачкчпод фунг«ции У(А) ал "11.,"; горптм (6,17) за один шаг сходится к экстремуму. Это наш«яэна внлно нз анализа одномерной сгчтуацгчиг если У(а)---(а - Ь]'ч то при любом начальноьч значении аз сле а«=-ас — (1««2) 2(ас. -Ь) ==Ь==.а, Аналогичное свойство проявляешься и в многомерной кнад ратнчно.'ч задаче 16.!6) ы.«мхчод гюссь-заядьяя В предыдущих алгоритмах при поиске экстремума од«!;.:,=.'ч-.чюврсчсггно изменяются все аргументы функции У.
Это :,",«!:-.:; приводш г усложнению реализации алгорпгмов Поэтому ;;;ь!;,::;:~г, часто процедуру волока экстремума осуществляют следующччм образом Задаются начальным зяачегшем Аь аег;тора параметров А. Зачем изменяют аргумент а„н«меняя знач ния все: й';=';:!!,г остапы«ых аргументов, до тех г ор, гюка за сче: изменения ~«41!:";"„'л 'ач функция У не достигнет экстремал. но.о значения. Из. ~~~!!~.",:- м«еччить а; мо,кно, например, в соотвечств:ш с непрерывной 175 илн дискретной формами метода градиента соответственно — Тд)(а„ав, а„...., аа,),'дад а,ы,г а„удУ(а„„а, а„,...., а„в)'да„а -О, 1, 2 .. Можно также примени~ь специальные алгоритмы понсг а экстремума одномерных функции. После достижения экстремума функции У по ар:умегму иг, что контра.
нр)ется выпоггнснием условии аида (6.2) или (6.9), (6 10), но за писанных относительно только переменной иг, начинают аналоги шое изменение ав при неизлгенныл остальныл аргулгентах аг, ав,, а, до досзи,кения функцией У экстремума по псремеонон а,. Затем изменяют а; н т. д послсдовате.вьно до переменной а . После этого весь цилл поиска повторяют, снова па щиая с а„ и так до тех пор, пока не будут выполнены условия (6 2) прн непрерывном поиске градиента нлн (6.9), (6 10) при шаговом. Прп практгщеском решении экстрема.
ьных задач часто нснользугот комбинацию нсскогшких методов 6.2. МЕТОДЫ ОПРЕДЕЛЕНИЯ ГРАДИЕНТА в.г в имад чнсввннога днаовмнцвваввнив В соответствии с изложенными принципами поиска экстремума необходимо уметь вычислять градиент функции У.
Если конкретныи внд функции У известен, то эти вычис лення осуцгествляют аналитически и зазем результапг используют в структуре алгорит.гов поиска экстремумов. Однако во многих задачал, н частности возникающг;х прн посгроснии СНС, функоия У в явном виде не известна, но могкно намерять ее зна и'г ггя В этих случаях аналитическое вычисление г ра гнснта невозможно и приходится ру. лонгг,,г*воаап си иными погглодамн Обычно меч од чист енкого дифференцирования [19[ применяют при использовании ЭВМ. Пусть имеетсн функция У(а„аь...,а ), аналнгическое выражение которон может быть и неизвестно. Придавим переменной а~ приращекня с б, где б малая неличина, позволяющая зарегнстриронать соответствующие изменения У 1.!змеряют зна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
