Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 11
Текст из файла (страница 11)
Результаты сравнения показаны на рис. 3. 10. Здесь МСП вЂ” случайный, а Мà — грздиентный поиск, МНС вЂ” метод наискорейшего спуска. В работе [58) проведено сопоставление алгоритма непрерывного обучения с направляющей сферой с методом наискорейшего спуска на стохастической модели объекта. Под стохастической моделью объекта понимается такая модель, градиентное направление которой меняется от шага к шагу по вероятностному закону: й ба(Х,+,)= йтаб Я(Х;) +пЕ 1йтад Я(Х~) +дЕ ~ ' (3.3,55) где Я вЂ” единичный случайный вектор; я=сопя( (у>0). гг5 2В Щ ав М атз юла мт гв газ с 61 Рас Л.!О.
Подобный алгоритм обучения случайного поиска предлагается И. Матыашем [59, 601: %в+~ = с~%я+ сз (з1ип ЛЯн) ЬХл, (3.3.56) где О~с~(1; с~+гз" 1. (3.3.57) Направление случайного шага ЛХ определяется формулой 5Х =М +тнВ (3.3.58) где ҄— матрица, элементы которой определяются на каждом шаге поиска. Исследованию вопросов сходимости случайного поиска с обучением посвящены работы Ш.
Петраша [61, 62). о7 Изменяя величину д, можно получать различный характер поведения объекта, Результаты сопоставления приведены на рнс. 3.11. Здесь сплошной линией показано быстродействие случайного поиска, а штриховой — случайного спуска. Видно, что для объектов с достаточно медленным изменением градиентного направления более целесообразно с точки зрения быстродействия пользоваться методом случайного поиска с непрерывным обучением.
$ 34. ИОдели«ОВАние сАЯООБучения нА АвтомАтАх Все существенные свойства самообучения в процессе случайного поиска могут быть описаны на языке теории автоматов. Под автоматом понимается некоторая система 3, обладающая некоторым множеством (Чч,...,~р ) внутренних состояний и способная выдавать некоторые выходные сигналы (реакции, выходы, действия) йь )г,...., Рь Выбор автоматом той или иной реакции Й; зависит от внутреннего состояния Ч,, в котором в данный момент находится автомат. Реакция (действне автомата) вызывает какое-то изменение «внешней среды>, которая, поступая па вход автомата, влечет за собой изменение внутреннего состояния автомата. В работе (63) дана классификация автоматов, используемых для моделирования обучения: !) детерминированные автоматы, 2) вероятностные автоматы и 3) автоматы со случайными реакциями.
Автомат называется детерминированным, если каждому внутреннему состоянию автомата соответствует однозначное действие автомата и каждый вход автомата однозначно задает переход автомата из одного состояния в другое. Под стохастическим (марковским) понимается автомат, действие которого однозначно определяется его внутренним состоянием, а переход из одного состояния автомата в другое задается с некоторой вероятностью. Автоматом со случайными реакциями является такой автомат, внутреннее состояние которого определяет распределение вероятностей реакции (действия); переход из одного состояния в другое однозначно определяется входом автомата. Автоматом со случайными реакциями является, например, по алгоритму Буша — Мостеллера, обучающаяся система, если под внутренним состоянием автомата понимать множество вероятностей реакции (рь рь..., р„), под выходом автомата— реакцию испытуемого )т; и под входом автомата -- воздействие операторов Я;.
М. Л. Цетлин в работах (64, 651 предлагает для моделирования процесса обучения объекта, находящегося в случайной среде, применять конечный детерминированный автомат. Пусть конечный автомат А задается своими каноническими уравнениями Ч~((+1) =ОУЬ((), з(1+1В (3.4.1) (3.4.2) где ! — время, принимающее дискретные целочисленные значения; з — входная переменная автомата, принимающая значения О, что соответствует выигрышу автомата, и 1, что соот.
ветствует проигрышу автомата А; !(() — выходная переменная (действие) автомата, принимающая и различных значений !ь )м .,1; ч~(!) — состояние автомата, которое может принимать ш различных значений ~ь ~рь..., ~р; число т — емкость памяти автомата (т>х). Выражение (3.4.1) можно записать в виде матрицы состояний автомата А (з) = ~~пи(з) ~~ (1, 1=1,..., т). Для конечного детерминированного автомата каждая строка матрицы А(з) при любом фиксированном значении з содержит один элемент, равный 1, а остальные элементы являются нулями. Переход автомата из состояния ~; в другое состояние гр., от момента времени ! к моменту времени !+1 определяется равенством а;ф(!+1)]=1. Для стохастического автомата матрица А(з), хотя бы для одного фиксированного з, является стохастической, элементы ац[з(!+1)1 которой определяют вероятности ее перехода из состояния ач в состояние Г;. Автомат А находится в стационарной случайной среде С=С(аь..., а„), если действия автомата и значения его входной переменной связаны следующим образом: действие ( (а= =1,..., х), произведенное автоматом в момент т, влечет за собой в момент г+1 ответ среды з=! с вероятностью Р,„= 1 (1 па), причем !па! ~~1.
Переходы автомата А, находящегося в стационарной случайной среде С (аь...,а„), нз состояния ~р; в состояние <рз описываются простой цепью Маркова, переходные вероятности которой равны Рч'=Ран~!(1) +Чаупо(0). (3.4.3) Математическое ожидание выигрыша Ф'(А, С) для автомата А в среде С выражается следующей формулой: (Р(А, С) = ~ арос,> (ЗА.4) а-! где а — сумма финальных вероятностей таких состояний ~р„ которым соответствует действие ~,„. Автомат Л обладает целесообразным поведением в среде С, если й' (Л, С) ~ — (а, +... + а „), 1 (3.4.5) т. е. если автол<ат А действует лучше автомата, совершающего равновероятные действия независимо от реакции среды.
Последовательность автоматов Аь Аь..., Л„называется асимптотически-оптимальной, если (3.4.6) т. е, автоматы этой последовательности для достаточно большого п производят исключительно то действие, вероятность выигрыша при котором максимальна. М. Л. Бетлиным [64) вводится понятно автомата с линейной тактикой. Этот автомат имеет хп состояний <р<ч (<'=1,...,п; а=1,...,х). Состоянию <р<ч соответствует действие ~,„. Графы состояний и переходы такого автомата для з=0 и з=! показаны на рис.
3.12. Последовательности автоматов с линейной тактикой в стационарных случайных средах, для которых а „)О, являются асимптотически-оптимальными. В работах 166 — 68) предложены конструкции асинптотическпоптимальной последовательности стохастических автоматов. В ряде работ рассматривается поведение конечных детер<иинированиых и вероятностных автоматов в составных средах. Составная среда К=К(Сн<,..., С<"'~) задается цепью Маркова с о состояниями С<н, С<'<,..., С<6 и матрицей переходных вероятностей Л=11б"а11 (а, Д=1,..., о).
Состояние С<м соответствует стационарной случайной среде Са->=С(а<<"<,...,а„<м). Автомат Л находится в составной случайной среде К, если в каждый момент времени он находится в одной из сред С<м. Пусть <р«В< обозначает такое состояние системы «автомат — среда», при котором автомат находится в состоянии <г<, а составная среда -— в состоянии С<В>. Поведение такой системы описывается конечной цепью Маркова, В работе (64) показано, что для автоматов с линейной тактикой, погруженных в составную среду, существует оптимальная величина памяти, прп которой автомат достигает максимального выигрыша.
В работе (69) рассматриваются вопросы синтеза автомата, взаимодействующего оптимальным образом с составной случайной средой. 70 В. И. Варшавский, П. И, Воронцова и М. Л. Цетлин 170 — 731 изучали поведение стохастических автоматов с формируемой структурой. Матрицы состояний для автоматов этого типа изменяются в зависимости от значений входной переменной. Изменение матриц состояний осуществляется следующим образом.
Пусть в момент 1 под воздействием входной переменной з(1) состояние к; переходит в состояние срь а затем (в момент 1+ 1) входная переменная принимает значение з(г+1) =0 (выигрыш) либо з(1+1) =1 (проигрыш). Переходная вероятность а,,(1, з(г)) увеличивается при з(1+1) =0 и уменьшается прп э(1+1) — — 1. Остальные элементы а,х(А з(Г)), ЙФ)', бй строки изменяются таким образом, чтобы сохранилась стохастпчность матрицы. Остальные строки матрицы не изменяются. Поведение автоматов с формируемой структурой в случайных средах описывается неоднородной цепью Маркова. Аналитическое изучение таких автоматов весьма сложно Их исследование проведено при помощи моделирования на ЦВМ, которое показало, что в процессе своего формирования такой автомат приобретает структуру, близкую к структуре автомата с линейной тактикой н оптимальной памятью.
В работе 174) предлагается аналитически обоснованный алгоритм изменепця переходных вероятностей стохастических автоматов, позволяющий автомату вести себя оптимальным образом в стационарных случайных средах. В работах (75, 761 исследуется поведение в случайных средах такой системы, которая обучается по алгоритму Буша — Мостеллера (автомат со случайными реакциями). Показано, что этот алгоритм применим только в ограни ~енных случаях. Конструкция обучающегося автомата со случайнымп реакциями, который оптимально приспосабливается к «медленно» меняющейся внешней среде, Рао Д1Ц предложена в работе [77). Ю.
И. Неймарк, В. П. Григоренко и А. М. Рапопорт предлагают использовать детерминированные и стохастические автоматы для оптимизации функции многих переменных [78]. Структурная схема рассматриваемой системы оптимизации изо- Я'=+! пм йн лр>д мм г О Рис, дт4, бражепа на рнс. 3.!3, где А„..., А„— независимые автоматы, превращающие значения Я в х„...,х . Согласно этой схеме, каждая из входных переменных х; (1=1,..., и) объекта управляется своим автоматом Аь Входной переменной для всех управляющих автоматов является оптимизируемая выходная переменная объекта Я=()(хь...,х„), Все автоматы Аь...,А однотипны Смена внутренних состояний автомата определяется его предыдущим состоянием и приращением величины Я.
Внутреннее состояние каждого из автоматов А, определяет изменение управляемой пм переменной к,. Показано, что система со структурной схемой, изображенной на рис. 3.13, и стохастнческимп автоматами с линейной тактикой может отыскивать минимум функции 9(Х) как при помехе, так и при ее отсутствии, что она может осуществлять поиск глобального минимума и следить за минимумом при медленном изменении функциональной зависимости, Рассмотрена возможность повышения надежности системы путем дублирования управляющих автоматов Аь Иа рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
