Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 8
Текст из файла (страница 8)
Оператор Я; представляется в следующем виде: где О~а; = 1, а Л; является неподвижной точкой для оператора Яь т. е. Я;Л;=Ль (3.2.8) Если р равно Ль то оператор Я.; не изменяет величины р. Геометрическая интер! л претацпя введенных параметров показана на рис. 3.3. Для $р=! — Я;р имеем: Я,р=-а,д+ (! — а,) (1 — Л,). (3.2.9) л, Повторно применяя оператор 9» имеем: > Я,лр=--а ну+(1 — а,")Ль Ю( (3.2. 10) При Л'- сю получаем: ( 1пп 91нр=Л,.
(3.2.11) а Рис, дЗ. Тогда (3.2.13) Я„ь „р = а„„р+ (1 — а„, 1;) Л», „, где (3,2.14) а, — азиате. аз" (1 — а,")Л~+ (1 — аз )Лз Ли, ю= а и<~Р (3.2.15) Различаются события, контролируемые экспериментатором, и события, контролируемые испытуемым субъектом. Под собы- Следовательно, Л; является предельной точкой оператора Яь т. е. для достаточно большого М при применении только оператора Я; вероятность р стабилизируется на некоторой фиксированной величине Ль Пусть имеются два события Я~ и Яз (например, наличие награды н отсутствие награды), которые представлены математической последовательностью Д: Яз'Я1" = 9, (3.2, ! 2) тпем, контролируемым экспериментатором, понимается тот случаи, когда последовательность воздействия операторов Я; задается экспериментатором.
Под событием, контролируемым испытуемым субъектом, понимается случай, когда воздействие операторов Яг определяется реакцией, выбранной субъектом. Рассматривается и случай событий, контролируемых как экспериментатором, так и субъектом. Для событий, контролируемых экспериментатором, среднее значение вероятности р на Ж-и испытании определяется форму- лой дРм —— оамР+ (1 — аи) Х, (3.2.16) Где (3.2.17) а = л1а ~ + лгаг', а=л1а~+лгаг, а;= (1 — а,)Х;; (3,2.18) (3.2.19) (3.2.20) Для событий, контролируемых экспериментатором, предельная дисперсия величины р выражается в явном виде: сг+~~Х 1 — сг (3.2.22) где со=-л,аР+лгаг', с~ =2(л~а1а~+лгагаг); сг=л~аР+лгагг (3.2.23) Для событий, контролируемых субъектом, и событий, контролируемых экспериментатором и субъектом, явные выражения для определения предельного среднего значения и дисперсии величины р не получены, хотя и доказано, что они сугцествукзт (13, 15, 16].
л~ и лг — вероятности применения экспериментатором операторов Я~ н Яг, аь Хг (1=-1,2) — параметры операторов Я1 и ()г (3.2.7]. При М вЂ” ~ос р =-1- Обобщенная модель обучения, частным случаем которой является модель Буша — Мостеллера, построена М, Иосифеску и Р. Теодореску (17 — 19) при помощи понятий и определений цепей с полными связями (20, 21). Аксноматическая теория линейной модели обучения разработана В. К. Истпзом и П. Сапсом (22). Согласно этой теории, каждый опыт прп обучении характеризуется стимулом 5, ответом субъекта 1с' и подкреплением А— действием экспериментатора, которое может быть поощрением или наказанием. Количество возможных событий в одном опыте равно произведению числа различных стимулов, возможных ответов на каждый стимул, а также количества воздействий экспериментатора.
Количество возможных последовательностей при А' опытах равно йн, где й — количество возможных событий на одном опыте. Пространство выборок Х определяется как множество всех возможных последовательностей йм. В. К. Истца и П. Санс предполагают, что вероятность любого события определяется конечным числом опытов, не превосходящим некоторое число %". Поэтому любое событие отнесено к бесконечному количеству последовательностей, которые совпадают на й7' опытах и различны на всех прочих.
Множество таких сооытий обозначается через В(Х). Пусть Рс к — множество всех последовательностей, имеющих реакцию 1с; на Ж-м испытании; Ак,н — множество всех по. следовательпостей, имеющих подкрепление Ах на Л'-и испытании; Хн — множество всех последовательностей, имеющих ге же самые реакции и подкрепления, что и данная последовательность Х на первых Ж испытаниях. Обозначим Рь и = Р(й', и) ' Рхг, ч =Р(гсот/Хм ~); Р» э =Р(Хн): пмн=Р(Ах н); пм, н=Р(Ам ч(йс и), (3.2.24) чг где Р(йсн) — вероятность появления реакции 1т; па испытании М или вероятностная мера на множестве 8(Х); 0 — параметр, определяющий скорость обучения (0<0<1).
Предполагается, что О=сонэ(. Упорядоченное множество т=(Х, Р, О, г) является линейной моделью простого обучения тогда и только тогда, если Х является пространством выборок, Р -- вероятностной мерой иа В(Х), 0<9 '-1 и если для любого кенХ, имеющего Р„, м>0, для любого 1 н й, удовлетворяющих неравенства 1 1-г и 0 . й~г, выполняются следующие аксиомы: 1-я аксиома Если хенА; х, то (3.2.25) Рхьлы=(1 0)Р.
',и+0 2-я аксиома Если хенАм к, то (3.2.2б) р~ ь н+ ~ = (1 — О) Ры, н. 3-я аксиома Если х~Ак х, то Р ь мы =Р.',н (3.2.27) Эти три аксиомы выражают предположения о том, что если появляется подкрепляющее событие, то вероятность соответствующей реакции увеличивается, а других реакций — уменьшается. При практическом приложении рассмотренной модели ры, и можно интерпретировать как вероятность реакции )т', отдельного сУбъекта на Ж-м испытании, а Рс л — как сРедние значе- ниЯ величин Ры, к. Ряд работ [23 — 29) посвящен теоретическому и экспериментальному исследованию моделей обучения с континуальньв| множеством реакций испытуемого.
Показано, что если ввести дельта-функцию, то модели обучения с дискретным множеством реакций получаются как частный случай моделей с контпнуальным множеством реакций [30). Другим классом моделей, не зависящих от пути, являются коммутативные модели обучения, исследованные Р. Д. Льюсом в работе [31). Эти модели математически представляются ввиде (3.2.28) где [ — вещественное строго монотонное преобразование единичного интервала; р — константа, зависящая от реакции испытуемого и от результата на Ф-м испытании (р>0), Такие операторы исследуются прн помощи функциональных уравнений [32 — 341. Изложенный линейный алгоритм обучения Буша — Мостеллера применим к обучению системы случайного поиска по формуле (З.Е6). Перед тем как в следующем параграфе показать его применение, коротко рассмотрим использование алгоритмон обучения при решении других задач.
Широкое применение изложенные алгоритмы обучения находят при решении технических и других задач. При помощи зтих алгоритмов можно, например, предсказать протекание случайного процесса без предварительных сведений о нем, произвести оценку неизвестных параметров объекта, выделить полезный сигнал из шумового фона (35 — 38], распознать образ (39 — 4Ц. В виде примера рассмотрим применение линейного алгоритма при обучении системы автоматического управления (42 — 44).
Пусть управляемая система описывается дифференциальным уравнением (3.2.29) Х=ф(Х, и, У, Е, (), где Х= (хь..., х„) — вектор состояния объекта, определенный в пространстве состояния Ы,,; и — управляющее воздействие; У= (оь..., о ) -- вектор окружающей среды, определенный в пространстве й,; Е= (еь..., е ) — вектор помех, действующих на выход системы, определенный в пространстве й,. Функция качества системы (3.2.30) где а=сова(; гТ вЂ” момент времени, Состояние объекта в любой момент времени полностью определяется вектором измерения М= (хь ..., х„ оь ..., о,„) в пространстве йм. Выбор управления и осуществляется из конечного множества допустимых управляющих воздействий Я„= (иь..., их). Предполагается, что воздействие вектора помехи Е отсутствует, ф — неизвестная функция, функция качества Я(Х) задана.
Через промежуток времени Т определяется значение вектора измерения М и производится новый выбор управления и. Управляющее устройство обучается переводить вектор состояния Х из произвольной начальной точки в окрестность б Ри((г+1) Т) =Т.ДРо(ГТ))=-ОРО(гт) + (! — О), (3 2 31) 0«.О 1; РО((г+1)Т) =$~РО(гт))=ОРО(гт), (3232) где величина Π— параметр, определяющий скорость обучения; оператор Е+ — положительное подкрепление; оператор Е отрицательное подкрепление. Положительно подкрепляется то управление и; (для фиксированного ,), которое обеспечивает максимум по 1 величины Л;; (1 — фйкспровано, 1=1,..., А), где т (с г(гт) 1)лн(( 1)т) +Л с,,(гТ) (3.2.33) если и((г — 1) Т) =и;; и и (Гт) =Ли((г — !) т).
если и((г — 1) Т) Фи;; (г'((г — 1) Т) — Я(гт) шах [(1((г — 1) Т), Я(ГТ)) ' < -н г,~г (3.2.34) (3.2.35) со(гТ) — число применений выбора управления и; для множества 5~ на протяжении интервала (О, гТ) при условии, что с,,(гТ) меньше плп равно заранее заданному числу Х. Когда величина со(гТ) достигает У, она считается равнон У.
начала координат пространства состояний. Первый этап обучения сводится к разбивке пространства 11»г на классы 5, (1= =-1,...,э), называемые «ситуациями управления». Выбор управления из множества 12, считается одинаковым дли всех элементов данного класса 5» Следующий этап сводится к определению при помощи линейного алгоритма обучения наилучшего выбора управления для каждой ситуации управления. Пусть РО обозначает вероятность того, что Рй элемент и~ пз класса Й является выбором оптимального управления для 1 ситуации управления 5ь Первоначально все Р;,= —, 1=1,..., й; /=1,..., э.
В ходе процесса обучения вероятность Рм для каждого 1' приближается к единице при каком-то определенном иь Изменение вероятностей РО осуществляется формулами: Изменение скорости обучения 0 при каждом новом выборе управления и, определяется формулой 0=1 — ат, (3.2.36) где а=Ь ппп [АΠ— А;,[; (3.2.37) ь г ~! 1 ЬΠ— максимальное Ж,; Ь=сопаг, у=сонэ!; (0<Ь» — ). Сходпмость изложенной процедуры обучения систем автоматического управления доказывается в работе [45). В работах [46 — 48) исследуется применение линейного алгоритма обучения к описанию действий в игровых ситуациях, а в работах [49, 50) — к описанию процесса накопления информации. В раооте [5!) изломсепо применение этого алгоритма в диагностических системах.
В ЗЗ. АЛГОРИТМЫ ОБУЧЕНИЯ ПРИ СЛУЧАЙНОМ ПОИСКЕ Из рассмотренных выше алгоритмов наиболее подходящим для обучения при случайном поиске является линейный алгоритм Буша — Мостеллера. Схема применения этого алгоритма для обучения случайного поиска изложена Л. А. Растригиным в работе [1). Пусть движение оптимизируемой системы в пространстве параметров происходит только вдоль направлений, определяемых следуюшей системой уравнений: [ х! [ = [ хз [ = ° ° ° = [ ха ! . (3.3.1) Число таких направлений равно 2". Пусть состояние обученности системы на М-м шаге поиска описывается и-мерным вектором Р (р !и! р РО) (3.3.2) где р,<к> — вероятность выбора положительного направления шага по Ьй координате на М-м шаге. В первоначальный момент, когда нет никакой информации об объекте, система делает шаг равновероятно во всех возможных направлениях: (3.3,3) О— 50 где а; и ).; — параметры, определяющие предыдущий опыт работы системы; |=-1, 2....,л.
Величина Х«должна быть такой, чтобы вероятность шага в благоприятном направлении увеличивалась, а вероятность шага в неблагоприятном — уменьшалась. Следовательно, нужно установить два значения параметра Х«, соответствующие двум неподвижным точкам, и предлагать системе двигаться к одной или к другой, в зависимости от того, нужно ли уменьшать или увеличивать вероятность шага в положительном направлении по «'-й координате. У штывая равноправность координат в процессе поиска, естсствсшю положить, что (3.3.5) а«=а; !.~! !'«| ~««=кы «=1,..., и. Значения й«п )а определим следующим образом: Х« =-с, если а|пи [Лх««юЛ(,«и)~0; ««=1 — с, если з!нп [Лх««к«ЛЯл1»О, Ьх;«х' =-х«««ч — х««м -««; АД =Р(Х ) — «',«(Хл ); (3.3.2) (3.3.8) О =с» —, | (3.3.9) Подобное выражение для Л реализует обучение системы, т. е.