Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 9
Текст из файла (страница 9)
перестройку вероятностных характеристик поиска в целесообразном направлении. Подставляя выражение (3.3.6) в (3.3.4), получаем рекуррентную формулу для вероятности выбора шага в положительном направлении для «-й координаты: р««и+«! = ар««и>+ — ((1- с) [!в 2 — абпп(Лт«к«Л!«к))+с[1+а!пп(йх««и«Л««к)5. (33.10) 5! Алгоритм обучения Буша — Мостеллера определяет выражение для координаты векгора Рл„.«в виде следующеи рекуррентной зависимости: р««««"««= а«р,«и«+ (1-а;) Хь (3.3.4) Точка р, в процессе обучения колеблется между двумя неподвнжнымн (стационарными) точками с -р;~1 — с, (зл.11) что препятствует детерминировапию систем.
так как в любом случае значение р, стремится либо к с, либо к 1 — с. Недостатком алгоритма обучения Буша-.Мостеллера является то, что он очень чувствителен к ошибкам. В результате одной ошибки (это легко показать) может «сбрасываться» память, накопленная за несколько шагов поиска. Другим недостатком этого алгоритма является его относительно неудобная аппаратурная реализация, Поэтому предлагаются другие более общие алгоритмы обучения случайного поиска (52, 53).
Эти алгоритмы можно разделить на два класса: 1) алгоритмы покоординатного обучения, частным примером которых является вышеизложенный алгоритм обучения Буша-- Мостеллера; 2) алгоритмы непрерывного обучения. Сначала .рассмотрим алгоритмы покоордпнатного обучения. Пусть вероятность выбора положительного шага вдоль ~'-й переменной является определенной функцией некоторого параметра шРо, который назовем параметром памяти (нли «памятью») по 1-й координате на М-м шаге поиска: (3.3.! 2) рсь '=р(ш;о ~), причем должно выполняться условие: О(р(в;) (!.
(3.3.13) если ш~ — 1; если — 1~а(1; если 1<в. О, ! р( ) = — (1т.ш) 2 1, (3.3.14) Вид функции р(ш) может быть достаточно произвольный, но всегда монотонный и неубывающий, т. е, прп возрастании параметра ш значение вероятности шага в положительном направлении йй оси должно возрастать. Различные зависимости р(ш) предложены в работах [1, 54). В дальнейшем рассматривается следующая линейная зависимосттс ш,''-ч"Н=-гн,~к~ — Ь з1йп(бх;ОоЛ(Ь), (3.3. 15) где б — кшаг по памятия; (6>О) — величина, определяющая скорость обучения. Чем больше б, тем быстрее обучается система поиска. Формула (3.3.15) обеспечивает перестройку вероятностных характеристик поиска, необходимую для целенаправленного самообучения в процессе оптимизации многопараметрических систем, работающих по методу случайного поиска.
Этот алгоритм уже не так чувствителен к ошибкам поиска, как алгоритм Буша — Мостеллера. В случае ошибки параметр ш изменится на величину 6 в неправильном направлении, что исправляется на следующем же шаге поиска, Этот алгоритм удобно реализуем аппаратурно, а поэтому он осуществлен в автоматических оптимизаторах, работающих по методу случайного поиска с обучением, разработанных в Институте электроники и вычислительной техники АН Латв. ССР (1). Однако при работе по этому алгоритму могут получаться слишком большие значения 1ш;! ()ы;1»!).
В этом случае система детерминируется (так как при этом р(пЧ) =.О или 1), и перестройка шг в случае необходимости будет связана сбольшими затратами времени, что делает алгоритм медлительным и немобильным. Этот недостаток алгоритма можно преодолеть, если ограничить зону изменения параметра шь например; — с, если ш( — с; шь если (ш;) =с; с, е«ли ш;)с. (3.3.15) Значения границы с устанавливаются в зависимости от характера оптимизируемой системы. С учетом этих ограничений алгоритм обучения приобретает необходимую подвижность при перестройке.
Другие возможные алгоритмы покоординатного обучения приводятся в работе [11. Теория покоординатного обучения, разработанная при по- моши методов теории цепей Маркова, изложена в работах 155 — 571. Приведем краткий обзор основных положений. Алгоритмы обучения реализуются путем соответствующего из- менения параметра памяти, например при помощи следующей рекуррентной зависимости (21: 1 — с вероятностью р,; ~а 1 — с вероятностью 1-р,. Уп (3.3.17) Этим условием в пространстве параметров Х определяется 2" направлений В; (1=1,..., 2"), по которым может двигаться си- стема.
Пусть функция качества оптимизируемой системы явля- ется линейной: Ю(хь, х ) =- Яч+ (йтай Я, Х), (3.3,18) где (), — исходное значение функции качества в точке Ха= =(О, О,...,О); Х=(хь...,х„) — вектор состояшгя системы; пгвд Я =сопз1. В процессе обучения вектор памяти % переходит из одного состояния в другое в соответствии с алгоритмом обучения (3.3.15) и ограничениями (3.3,16). Пусть общее число возможных состояний этого вектора конечно н равно гл.
Пусть также вероятность перехода из (-го состояния в 1'-е определяется числом рп. Тогда изменение вектора % в процессе обучения — %л-~- %к- %к+~- (3.3,19) рассматриваются два пространства: пространство параметров оптимизируемой системы Х= (хь..., х„) и пространство обучения %= (щь..., гв„), в котором вектор памяти % определяет направление преимущественного движения системы. Предполагается, что модуль смещения в пространстве параметров Х постоянен н равен единице, а координаты вектора ооразует простую цепь Маркова.
Для линеинои функции качества эта цепь является однородной. Таким образом, задание матрицы переходных вероятностей р;; определяет обучение. Рассмотрим динамику обучения двумерной системы при б=-э2с, когда по каждой координате имеются два уровня памяти: — с и с, т. е.
вектор памяти Ф на плоскости обучения может находиться в одном из четырех состояний. Этп состояния на плоскости обучения н возможные направления смещения системы в пространстве параметров Х показаны на рис. 3,4. Матрица переходных вероятностей вектора % Следует различать два случая: !) 0<с<! н 2) с=1. Первый случай соответствует тому, что не допускается детерминирование системы поиска.
В этом случае цспь Маркова является зргодической. Во втором случае допускается детерминнрование поиска по некоторому нз возможных направлений. Вэтом случае цепь Маркова является незргодической, т. е, предельное распределение вектора % по состояниям на плоскости обучения зависит от его начального распределения. Получены формулы для определенна пошаговых н предельной характеристик обучения н средних приращений функции качества. Для случая 0<с< ! предельное распределение вектора % =р =О,б; Ра=ра=-О, (3.3.2!) а предельное среднее прирашение функции качества на одном шаге л1(АЯ) == саь 1 ~'2 (3.3.22) —,'(+с); , .— (1 — с'); ! ! — (1 — сз); 2 1 2 !! — (1+ оа); — (1 — с'); 0 ! 2 — (1 -)- сз) О ! 2 — (1+ сз); 0 1 2 — (! — сз) .
О 1 2 О! 0 !! (3.3.20) 0 й ! М (Л!'>) 1 2 - с )>2 ' (3.3,23) Для с=1 ,':1 0 0 О! :~0 ! О 0 ;,о ! о о,' 1 О 0 0,> (3.3.24) Предельное распределение вектора % ..<о> 4 , <о>. Р2 РУ >+РЗ~ > Рз=рх=-О, (3.3.25) предельное среднее приращение функции качества >)4(>!ф (п>4 па(Р><о> ! Р <а> Рз<о> Р >о>)) (33.2б) 1 )>2 Когда направление градиента оптимизируемой системы совпадает с одной из биссектрис пространства Х, то система в пределе (Л'-~ос) обучается идеально и предельное среднее прира. щенне функции качества в эргодическом случае равно единице.
Рассмотрим динамику обучения двумерной системы для с б.= — (й — целое число). А По каждой координате имеются (21+1) уровней памяти. Вектор памяти % может находиться в одном пз (2й+1)т состояний. Состояние вектора памяти % иа плоскости обучения и его переходы из одного ~остояния в другое показаны на рис. 3.5. Матрица переходных вероятностей вектора % имеет следующий блочный вид: где а; (1=1, 2) — направляющие косинусы градиентного направ- ления. Предельное среднее приращение функции качества в за- висимости от направления градиента изменяется в следующих пределах: (2лИ) 4к +Ух Ь~ Яе+Ф Рас.
8Х о,........, о~~ и=- ( ' зг' ' ' ' ' ',1. (3,3.27) ~О,..., О, Рео з.-о О, 0;' (.' О,...,, О, Рм,,е„и, О, где 0 - — блоки, элементы которых равны кулки Ро — матрицы Якоби, иаиример: ! О, ......,,, О" О,......, О,~ Р з . Рзъ Рзо...., О, (3.3.28) !.,',..., 0 ° ° ° Ргь и — и 0 Рта гз+~ Из матрицы н следует, что состояния от (21+2) до (21+1)' являются невозвратными, а состояния от 1 до 2й+1 — возвратными (для эргоднческого случая 0<с<1). Поэтому предельные вероятности Ртд~.х =... = Рохас = О. (3,3.29) Решая систему алгеоранческнх уравнений Р'нР=Р, (3.3.30) где Р'и — транспонированная матрица Ри, р= (Рь, Рныч)— вектор предельных вероятностей по состояниям от 1 до 21+1, находим: гт Рз-ь,~ Р '=Рзхч-з- =! 1 ' ' Рб ) --' Рхю-~ а=2,3,...,1+1; Р + =Р =2 1+ Х П - ' "+ — П --'='-'-~ , т;-е рь„~ 2 ~-.
р~,; ~ 1(( (3.3.31) Предельные вероятности (3.3.31) определяют дискретное распределение блуждания системы в процессе поиска по состояниям от 1 до 2Й+1. На рис. 3.6 показано дискретное распределение, рассчитанное по формулам (3.3.31) для с=05, й=1, 2, 4, 8, !6. Р,. и Характерно отпоситсльяое увеличение вероятности по крайним состояниям. В неэргодическом случае (с=-1) предельное распределение р; (1= 1,..., (2Й+ 1)') сосредоточено в крайнем состоянии (= 1 и 1=-2й+1. Отсюда следует вывод, что перестройка вектора памяти Чг в процессе покоордпнатного обучения затруднительна, т.
с. поиск при увеличении й становится немобильиым. Предельное среднее приращение функции качества для эргодического случая Ч(ЛЯ) == саь 1 ]~2 (З.З.З2) М(ЛЯ) == саь ! ун (З.З.ЗЗ) Отсюда видно, что эффективность обучения падает с увеличением размерности оптимизируемой системы. Теоретические результаты в основном были получены на примере линейной функции качества оптимизируемой системы. Свойства алгоритма покоординатного обучения при оптимирацип объекта с центральной функцией качества исследовано с применением ЦВМ. В раооте [2] показано, что в этом случае выявленные недостатки алгоритма покоординатного обучения сохраняются. В работах [56, 57] исследуется динамика покоордииатпого обучения при оптимизации в обстановке аддитивных нормальных помех, накладываемых на функцию качества.
В работе [56] рассматривается случай, когда 6~2с. Здесь, как и прн оптимизации в обстановке без помех, следует различать два случая: 1) 0<с< 1 (эргодическая цепь); 2) с= 1 т. е. для линейной функции качества оно пе зависит от величины параметра скорости обучения б. Исследование динамики покоординатного обучения прп оптимизации в трехмерном пространстве параметров показывает, что и здесь справедливы основные результаты, полученные для двумерного случая, Для л-мерного случая получено предельное среднее приращение функции качества (неэргодическая цепь). В первом случае предельное распределение вектора % р;= — Фь >'=1,...,4, 1 2 ь (3.3.34) где Ф; — [1<-Ф[ ')1; Ф(х) — функция Лапласа; А>,>> — приращение функции качества по направлению В; пространства параметров Х=- (х>,..., х„) на единичном ц>аге; оз — дисперсия помехи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
