Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 7
Текст из файла (страница 7)
Были проведены некоторые эксперименты применения случайного поиска для решения практических вопросов ~2~. Надо будет основательнее изучить возможности использования этой теории на практике, главным образом при помаши специальных автоматов, работакзщпх на основе вышеприведенной теории. ГЛАВА !и ПРОЦЕССЫ САМООБУЧЕНИЯ ПРИ СЛУЧАЙНОМ ПОИСКЕ 5 ЗЛ. ПОСТАНОВКА ЗАДАЧИ Самообучение и процессе оптимизации многопараметрических систем методом случайного поиска сводится к перестройке вероятностных характеристик генераторов случайности с тем, чтобы увеличить вероятность благоприятных шагов и уменьшить вероятность неблагоприятных (! — 3].
Пусть состояние некоторого объекта определяется и параметрами хь хь..,,х„. В декартовом пространстве этих параметров каждому состоянию объекта соответствует некоторая точка. Пусть в этом пространстве определена скалярная функция качества как функция координат: Я=Я(хь..., х,). (33, П Задача оптимизации заключается в отыскании одной из точек пространства параметров, называемой целью, соответствующей минимальному значению функции качества. Состояние объекта после М-го шага поиска будет определяться вектором (3.!.2) Хн = (х~<ю,..., х„<">) .
Этому вектору соответствует значение функции качества д =а(х .). (33.3) Приращение функции качества Мн=(Ь вЂ” Я -ь (3.!.4) вычисленное после Л'-го шага (3.1.5) ЛХ =Хи — Х, — ь определяет степень успеха па этом шаге по сравнению с предыдущим состоянием. Общая схема системы оптимизации с самообучением показана на рис. 3.1. В этой системе обучающимся элементом является генератор случайного 0 процесса (ГС), вероятностные характеристики которого изменяются по определенному алгоритму в соответствии с накапливаемым опытом работы сн.
стем ы. Процесс самообучения описывается следующей рекуррентной формулой: Рх(Б) =Ф(Рк-ч.' Бх-и Ьав. ~), (3.1.6) где Л(Ь, — изменение функции качества на У вЂ” 1-м шаге поиска; Я вЂ” слу- Рис. в,л чайный вектор в пространстве оптимизируемых параметров; Рм-~(Е) распределение вероятностей случайного вектора Б на Л' — 1-и шаге поиска. Эта зависимость показывает, что распределение вероятностей определяется результатом предыдущего шага и распределением вероятностей на предыдущем шаге. Следовательно, самообучение происходит за счет целенаправленного изменения закона распределения случайного вектора шага в процессе поиска. Теория обучения до последнего времени в основном развивалась по двум направлениям, Первое направление — разработка стохастических алгоритмов обучения, моделирующих обучение биологических систем, второе — моделирование процесса обучения прн помощи детерминированных н вероятностных автоматов.
Перед тем как перейти к изложению алгоритмов самообучения случайного поиска, рассмотрим описанные в литературе модели и алгоритмы обучения. 39 азлк СТОХАСТИЧЕСКИЕ АЛГОРИТМЫ ОБУЧЕНИЯ БИОЛОГИЧЕСКИХ СИСТЕМ Впервые стохастические алгоритмы обучения были развиты и применены в связи с описанием и исследованием обучения биологических систем [4, 5). Классификация стохастических моделей обучения, применяемых для обучения биологических систем, дана в работах [6, 71.
Первый класс моделей — так называемая теория опробовании стимулов — предложен В. К. Истнзом в работе [4) и развит в работах [8 — 11). По этой теории существует конечное число так называемых раздражителей, или стимулов, каждый из которых в любой фиксированный момент времени связан с одной из реакций испытуемого. Решающее правило подсказывает, как испытуемому на основе воспринятых стимулов выбрать ответную реакцию. В зависимости от исхода эксперимента связь стимулов с реакциями испытуемого систематически меняется. Такой механизм изменения связей приводит к применению цепей Маркова, используемых для описания изменения реакции испытуемого.
Поясним эту тсоршо более подробно на одном из простейших се вариантов. Пусть имеются два раздражителя (стимула) г н з, вероятность воздействия каждого из которых на испытуемого равна 0 и не зависит от реакции испытуемого и от того, какое действие выбрал экспериментатор. Пусть испытуемый может ответить реакцией Ра или реакцией )сь Иа реакцию испытуемого экспериментатор отвечает действием Ао (например, вознаграждение) или действием А, (например, певознагражденпе) с вероятностямн, расположенными в следующей матрице; (3.2.1) где а — вероятность действия А~ экспериментатора после реакции испытуемого Рм Ь вЂ” вероятность действия А, после реакции )ть Пусть любой из стимулов г и з связан с одной из реакций )га или Й~ и пусть вероятность появления реакций Кг ((=- =0; 1) в эксперименте пропорциональна числу стимулов, связанных с реакцией Рь Если на испытуемого не воздействует ни один стимул, то он выбирает любую из реакций с одинаковой 40 вероятностью.
Будем считать, что действие А, зксперпментатора подкрепляет реакцию Ям а действие А~ — реакцию Кь Такая схема обучения изображена на рис. 3,2, причем в начале эксперимента стимул г связан с реакцией Я, (верхний индекс у г Нмеь. ВЬР гази 1г', з') ~ в'ге~~ 1г,'т'~ яб зла К у'У 1 ',г'1 ~в'а ~ в'гье 1т', г'1 1г', г'У Вй-~)з 1г', з'3 Рп-а)гья' 1г~ 8~3 81ьн)л-а) 1г', з') а 1ьв)а 1г', з') й- в)' а 4 л,— к ') г-а. 4„— ао а 4 амм ме кмеююиса Рис. 82. равен 1) и стимул з — - с реакцией )та (верхний индекс у з равен О). Такая схема ооучення описывается простой однородной цепью Маркова, если под состоянием цепи Маркова понимать число стимулов, связанных с одной из реакций испытуемого. например с реакцией Йь В рассмотренном случае цепь Маркова состоит нз трет состояний: О, 1 н 2. Используя рнс.
(3.2), для этой цепи полу- чаем следующую матрицу переходных вероятностей: 1 20(! — 0)ьц 2 О'а, (! — 9)з+ +0(1 — О) (1 — а) + +о(1 — е) (1-ь); 20(1 — 0) Ь; 2, Оэь; По этой матрице находятся предельные вероятности Рм Р1 и Р2: 69+2ьэ(1 — О) = (а+Ь) Е+2(а+Ь) э(! — Е) ' 4аь(1-О) Р1 = (а+Ь)0+2(а+Ь)э(1 — 8) ' ае+2аэ (1 — 8) Рг= — —— (а+Ь)9+2(а+6)э(1 — О) ' Легко найти предельные вероятности реакций Йа и Р,: Ь а Р(Ю Я) (3.2.4) что соответствует предельным вероятностям выбора экспериментатором действий А, и Аь Если предположить, что экспериментатор делает выбор Ао с вероятностью Р, не зависящей от выбора испытуемого, то испытуемый может максимизировать среднее значение числа пра- 1 вильных Реакций, РеагиРУЯ всегда посРедством !га, если Р) —, 2' 1 и посРедством Йь если Р< —.
2' 0 0 (1 — О) 'а+1 — а; 1 — 0'(1-а) + 2 ц=! + — 0(2 — 0)Ь; 2 02(1 6) ! 2 -4- — 0(2 — 8) а. ! 2 (1-ет)Ь+(!-Ь). ! (3.2.2) Вслн экспериментатор всегда выбирает воздействие Ам матрица вероятностей перехода имеет следующий внд: 1)1 0 0 и=' О 1 — Е О ; е' 2о(1 — о) (1-о),,: (3.2.5) В этом случае нулевое состояние является поглощающим. Это значит, что через некоторое число испытаний обучаемый научится выбирать правильную реакцию )см Подробное исследование этого случая проведено в работе [12). Исследования показывают, что аналитические оценки, полученные при помощи модели апробования стимулов, хорошо согласуются с экспериментальными данными. Однако эту модель неудобно применять для обучения случайного поиска. Второй класс моделей обучения, наиболее подробно разработанный Р. Бушем н Ф.
Мостеллером 15), предполагает, что вероятности реакции обучаемого объекта меняются на каждом испытании. Пусть рх(й) обозначает вероятность выбора реакции Й на г1-и испытании. Тогда постулируется, что Рл+,(й) = (1 — 0) Р'()1) + 6)., (3.2.6) (3.2.7) где () и Х вЂ” константы.
зависящие от частной реакции испытуемого и от результата на Л"-м испытании. Предполагается, что вероятность рл ы ()с) зависит только от вероятности рл(1с) и от результата на А'-м испытании. Такой иестационарный случайный процесс является относительно сложным, и только несколько его простейших случаев хорошо изучены 113 — 16). Далее коротко изложим основные результаты исследования этой модели. Для простоты изложения примем,,что испытуемый на каждом опыте может прореагировать одной из двух реакций — й~ или )7з с вероятностями р и о=1 — р, соответственно. Вероятности р и д изменяются операторами Яь которые соответствуют событиям Аь наступающим после выбора испытуемым определенной реакции.