Стохастические оптимизационные автоматы с растущей памятью тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Колногоров, Александр Валерианович

• Колногоров, Александр Валерианович
• кандидат физико-математических наук
• 1983

Оглавление диссертации кандидат физико-математических наук Колногоров, Александр Валерианович

ВВЕДЕНИЕ.

ГЛАВА I. ГРАНИЩ ПРЕДЕЛЬНОГО СРЕДНЕГО ВЫИГРЫША. СШМЕТРИЧЕС

КОГО КОНЕЧНОГО АВТОМАТА.

§ 1.1. Определения бинарного ОПНЗ, симметрического авто мата, целей управления.

§ 1.2. Оценки для границ предельного среднего выигрыша симметрического конечного автомата

§ 1.3. Границы предельного среднего выигрыша симметрического конечного автомата с постоянной эргодической матри цей Р.

§ 1.4. Границы предельного среднего выигрыша симметрического конечного автомата с постоянной неэргодической матрицей Р , а также с переменной во времени матрицей А/^

ГЛАВА 2. НЕКОТОРЫЕ СВОЙСТВА АВТОМАТОВ <4 *}^>с/*3 ^

§ 2.1. Определение и некоторые свойства симметрических одновходовых автоматов общего вида

§ 2.2. Оценки вторых моментов случайных величин '¿¿^ ¿ - /¿и автоматов Як. и.

§ 2.3. Оценки вторых моментов случайных величин } ¿-^и автоматов*^ ^

§ 2.4. Оценки вероятностей выхода из цепочек автоматов к,*) 33 зависимости от времени их функционирования

§ 2.5. Обобщение результатов главы на случай слабо неоднородных процессов

ГЛАВА 3. АСШШТОТИЧЕСКИ ОПТИМАЛЬНЫЕ АВТОМАТЫ С РАСТУЩЕЙ ПА

МЯТЫ) ДЛЯ УПРАВЛЕНИЯ МАРКОВСКШИ ЦЕПЯМИ С ДОХОДАМИ.

§ 3.1. Определение управляемых процессов и целей управления

§ 3.2. Конструкции автоматов с растущей памятью и достаточные условия их асимптотической оптимальности

§ 3.3. Доказательство асимптотической оптимальности автомата 2 с растущей памятью на классе марковских цепей с доходами

§ 3.4. Некоторые обобщения

ГЛАВА 4. ОГРАНИЧЕНИЯ НА ФУНКЦИЮ РОСТА ГЛУБИНЫ ПАМЯТИ АВТОМАТА

И ОЦЕНКА СКОРОСТИ СХОДИМОСТИ ЕГО СРЕДНЕГО ДОХОДА

§ 4.1. Ограничения на скорость роста функции глубины памяти

§ 4.2. Оценка скорости сходимости среднего дохода автомата с растущей памятью.

Введение диссертации (часть автореферата) на тему «Стохастические оптимизационные автоматы с растущей памятью»

В работе рассматривается асимптотически оптимальное адаптивное управление посредством стохастических автоматов однородными ко -нечными марковскими цепями с доходами. Задачи, решаемые в работе, состоят в построении дискретных систем, обеспечивающих достижение заданной цели управления, и принадлежат к теоретическим проблемам кибернетики/^/^ М , №1

Класс управляемых однородных конечных марковских цепей/^У за -дается множествами состояний = 3 и управлений переходы между состояниями регулируются матрицами переходных условных вероятностей/^^-, гдеу#./^/-вероятность перейти из состояния в состояние ^ , если в состоянии $1 было применено управление ^ . На множестве ^ определены "доходы" ^"Л^ , которые получает автомат, если в состоянии ^ было применено управление ^ . Доходы могут быть как детерминированными, так и случайными величинами; в последнем случае они могут быть ограниченными или распределенными на всей числовой прямой. Как частный тип однородных марковских цепей с доходами, у которых множество ^ вырождается в одно состояние, могут рассматриваться и однородные процессы с независимыми значениями ( 0Г1НЗ ) [; особо выделяются бинарные ОПНЗ, то есть 0Г1НЗ, доходы которых могут принимать лишь два значения ^ "У ( поощрение и штраф ). Отметим адаптивную постановку задачи: численные значения переходных условных вероятностей^-/^/и функции распределения доходов предполагаются неизвестными.

В качестве цели управления в работе рассматривается традиционная цель максимизации предельного среднего дохода в единицу времени. Если требуется, чтобы предельный средний доход отличался от максимально возможного не более чем на ¿Г , то такая ослабленная цель управления называется £ -оптимальностью; если же требуется, чтобы предельный средний доход в точности равнялся максимальному, то ьта цель управления носит название асимптотической оптимальности [[ .

Выбор класса управляемых процессов определялся с одной стороны требованием достаточной общности описания объекта управления, а с другой стороны тем, что для марковских цепей имеются развитые методы исследования. В значительной части ситуаций, рассматриваемых в управлении, текущее значение процесса зависит от одного или нескольких предшествующих значений процесса и примененных управлений. Все сти ситуации могут быть сведены к рассматриваемым марковским цепям с доходами. Изучение марковских цепей с доходами в случае, если параметры цепи известны, было проведено, например, ъ 4] , где было доказано существование оптимальной управляющей стратегии для таких цепей; в ряде работ, изложение которых имеется в [V] доказано существование оптимальной управляющей стратегии для цепей, параметры которых неизвестны, то есть в адаптивной постановке задачи. Постановка адаптивной задачи управления 01ШЗ и марковскими цепями с доходами восходит к (.№] и в более развитом виде представлена в В качестве примера других подходов к адаптивному управлению укажем

Далее краткий обзор положения дел в теории автоматного оптимизационного управления случайными процессами сопровождается параллельным изложением результатов настоящей диссертации.

Для управления марковскими цепями с доходами в работе используются стохастические автоматы, построенные по аналогии с автоматами типа , описание которых имеется в [. Среди автоматов, используемых в адаптивном управлении, наибольший интерес представляют симметрические автоматы. Симметрический автомат для управления ОШЗ неформально определяется в как автомат, одинаково управляющий процессами, которые описываются одинаковым набором параметров, хотя соответствие этих параметров действиям автомата может быть различным. Ряд симметрических автоматов с описанием их свойств был предложен в работа№1, ЩШ]. Формальное определение симметрического автомата с памятью как суперпозиции автомата, определяющего смену действии и автомата памяти, дается в /Х7 .В главе I настоящей работы симметрический автомат определяется через систему равенств для условных переходных вероятностей автомата и вероятностей начального расцре-деления. Это определение является более общим, чем определение/¿7, так как, во-первых, включает в себя автоматы, условные переходные вероятности которых могут меняться с течением времени, а, во-вторых, включает в себя многовходовые автоматы.

Далее в главе 1 формулируется и решается задача о границах предельного среднего дохода автомата в зависимости от емкости его памяти при управлении простейшим классом процессов - бинарными ОПНЗ. Исследованию вопроса об оптимальном целесообразном поведении автомата, которое может быть переформулировано в терминах его макси -малыюго предельного дохода, были посвящены ранее работы 1ЦЩЩ

В работеА.А.Милютина искалась верхняя оценка суммарного предельного среднего выигрыша автомата с двумя действиями в двух средах, имеющих вероятности получения штрафа за действия у^Д и соответственно. Была получена точная оценка границ предельного среднего дохода автомата в зависимости от емкости его памяти и указана последовательность автоматов, обладающих оптимальным целесообразным поведением. В более поздних работах Хеллмана и Ковера//^//^/, МЯ]^^], а также в работе////7 проводилось исследование границ для предельных вероятностей применения действий управляющим автоматом, но метод, используемый в ьтих работах, отличался от метода работы . Полученные в них оценки описывают зависимость указанных вероятностей от параметров среды и емкости памяти автомата с точностью до некоторого постоянного множитнля. Отметим, что в//^/^/^/^/^/ предполагалось, что условные переходные вероятности автомата не меняются с течением времени, а марковская цепь, порожденная этими вероятностями, эр-годическая. В работе [№] результаты обобщаются на случай, когда условные переходные вероятности автомата порождают неэргодическую марковскую цепь.

В главе I границы цредельного среднего дохода ищутся для симметрических конечных автоматов, условные переходные вероятности которых могут как оставаться постоянными, так и произвольным образом меняться с течением времени. В случае, если переходные условные вероятности автомата остаются постоянными, найдена точная верхняя грань его предельного среднего дохода и показано, что если глубина памяти автомата больше / , то это значение не достигается ни для какого автомата. Точная верхняя грань предельного среднего дохода автомата с постоянной структурой совпадает с максимумом предельного среднего дохода автомата, условные переходные вероятности которого могут меняться с течением времени; описана структура этого оптимального автомата. Таким образом, основной результат главы следующий: симметрические конечные автоматы не могут быть асимптотически оптимальными на классе ОПНЗ, причем этот результат остается в силе и в том случае, если условные переходные вероятности автомата могут меняться с течением времени. Методы доказательства, используемые в главе I, отличны от методов работ [¡¿3,№37, /У2/ . Результаты работ изложены в работе ч .

Примерно в то же времц когда изучались автоматы с памятью, в литературе появилось описание автоматов, которые получили название автоматов с переменной структурой. Эти автоматы меняют веро ятности применения действий в зависимости от полученного на вход значения управляемого процесса /X/ . По-видимому, значительное число исследований цели типа асимптотическая оптимальность и ясная формулировка этой цели были связаны с изучением свойств автоматов с переменной структурой. В работахсихэрмулированы алгоритмы изменения вероятностей применения действий ьтими автоматами. Замечания относительно неверности ряда доказательств асимптотической оптимальности алгоритмов, рассмотренных в работе [I] , высказан в работе[№] . В работе/// асимптотическая оптимальность доказывалась для автомата с непрерывным временем; в ¿<2$] высказано сомнение в том, что это свойство сохранится для автомата с дискретным временем. В имеется также обширный обзор литературы по автоматам с переменной структурой.

Автоматы с переменной структурой в процессе управления не производят оценок параметров управляемого процесса. Были предложены конструкции автоматов, которые производят такие оценки в процессе функционирования, и для которых было доказано свойство асимптотической оптимальности. По-видимому, первой работой, в которой был сформулирован алгоритм, обеспечивающий на основе подсчета статистик управляемого процесса асимптотически оптимальное управление этим процессом, была работа, вышедшая в дальнейшем в русском переводе, /%/ . Этот алгоритм состоял в том, что для каждого из действий автомата июрмировались состоятельные оценки среднего дохода за это действие, причем доля времени, в течение которого применялось действие, соответствовавшее большему значению оценки дохода, стремилась к / по мере увеличения времени функционирования автомата. Сходная задача рассматривалась в работе [к], но предложенный алгоритм отличался от алгоритма тем, что задавалась последовательность вероятностей применения действий, которая также обеспечивала преимущественное применение действия с большим значением оценки дохода. В работе управление случайным процессом велось автоматом с памятью, также производщим подсчет статистик процесса. Отметим далее работу [Ю , в которой использовалась априорная информация об управляемом процессе; и в этом случае были предложены автоматы с бесконечной памятью, обеспечивающие достижение цели типа асимптотическая оптимальность. Асимптотически оптимальные автоматы, производящие подсчет статистик процесса, рассматривались также в

Таким образом, можно констатировать значительный интерес к цели типа асимптотическая оптимальность. Известные конструкции асимптотически оптимальных автоматов в основном охватываются двумя типами: автоматами с переменной структурой и автоматами, вычисляющими в процессе своего функционирования оценки параметров управляемого процесса.

В настоящей работе рассматривается другой подход к построению асимптотически оптимального автомата. Для этого используется известный автомат типа с последовательной сменой ветвей, глубина памяти которого наращивается в процессе его функционирования. Управление разбивается на этапы с номерами . ; отапу управления с номером соответствует глубина памяти автомата После того, как на этапе управления с номером № произойдет выход из последней ветви автомата, производится переход снова в первую ветвь, но номер этапа управления становится равным№+/ , одновременно и глубина памяти автомата принимает значение #

Заме титл, что нельзя просто взять аналоги автоматов </ и $ с бесконечной памятью; как показано в для автомата оС в и том случае с положительной вероятностью имеет место поглощение в каждой из его ветвей; очевидно, что такое же поглощение тлеет место и для автомата ^ . Добавим, что автоматы с растущей памятью не являются частным случаем автоматов с переменной структурой в их традиционном понимании.

В главе 2 подробно изучаются некоторые свойства автоматов типа с конечной памятью: делаются опенки для моментов второго порядка случайных величин, соответствующих временам до смены действий ьтими автоматами и оценки вероятностей того, что автомат сменит действие за время, не превышающее некоторого заданного значения *7 . Эти результаты являются вспомогательными и используются в главах 3 и 4 при доказательстве свойств автоматов с растущей памятью. Следует отметить, что известные доказательства £ -оптимальности автоматов с фиксированной глубиной памяти, для которых требуется только знание математических ожидании случайных величин, соответствующих временам до смены действия этими автоматами, оказываются неприменимыми для автоматов с растущей памятью.

Далее автоматы с растущей памятью применяются для управления однородными конечными марковскими цепями с доходами. Ранее адаптивное управление марковскими цепями с доходами рассматривалось в работах В работах/^//"^/предложен идентификационный подход к управлению, согласно которому в процессе управления производятся состоятельные оценки всех переходных условных вероятностей и всех математических ожиданий ^ , причем стратегия, соответствующая максимальному согласно этим оценкам значению предельного среднего дохода, получает преимущественное применение. В качестве цели управления может выбираться как £ -оптимальность, так и асимптотическая оптимальность. В работе рассматривалось автоматное управление слабо неоднородными марковскими цепями с доходами; в качестве управляющего автомата можно было использовать, в частности, автомат с конечной памятью. Целью управления избиралась £ -оптимальность. Наконец, полное описание идентификационного подхода к управлению конечными однородными марковскими цепями с доходами было сделано в [

В ряде работ рассматривалось управление более сложными процессами. Отметим, здесь управление однородными стационарными процессами [/] , а также игры автоматов, описанные, например, в

В настоящей работе для управления марковскими цепями с доходами предложен следующий способ: управление ведется автоматом 2 с растущей памятью, каждой ветви которого ставится в соответствие одна из марковских стратегий. На вход автомата в выделенные моменты времени подаются значения бинарного процесса , сшотэу — мированного по значениям доходов ^ , принадлежащим отрезку

4'/ , длина которого ^ ~ наращивается с ростом номера этапа управления; также наращивается и глубина памяти . Доказана теорема, указывающая достаточные условия асимптотической оптимальности автомата в виде ограничений на скорости роста функций Лм))^/^] . Оказалось, что эти функции могут меняться в значительных пределах, например, допустимыми оказываются шун-кции //V- С*]+/; [т ^ ш ^ . Результаты главы обобщаются на случай однородных марковских цепей, доходы которых являются случайными величинами, распределенными на всей числовой прямой, а также на случай процессов, пространство управлений которых является компактным подмножеством числовой прямой. В первом случае в зависимости от номера этапа управления меняется способ формирования процесса , во втором случае в зависимости от номера этапа управления меняется число действий автомата. Все полученные результаты являются справедливыми и для автоматов ^ ^ ^ с растущей памятью в области их асимптотической оптимальности. Результаты главы опубликованы в

В главе 4 приводится ограничение на скорость роста функции и даются оценки скорости сходимости среднего дохода автомата. Показано, что если рост глубины памяти автомата является показательным, то автомат теряет свойство асимптотической оптимальности. Объясняется ьто тем, что возникает положительная вероятность достаточно продолжительного применения худшего действия на последнем к текущему моменту времени ьтапе управления.

Далее изучается скорость сходимости среднего дохода автомата на классе связных марковских цепей с доходами, если шункция наращивания глубины памяти имеет степенную зависимость от номера ьтапа управления // в Показано, что сходимость среднего дохода автомата к его предельному значению имеет степенную зависимость от времени, как и в методе стохастической аппроксимации . Б случае ОДНЗ оказалось, что наилучшую сходимость среднего дохода к его предельному значению обеспечивает автомат с линейной функцией роста глубины памяти ^ . При ^^ более медленная скорость сходимости объясняется более медленным наращиванием памяти, в то время как при она объясняется тем, что возникает положительная вероятность достаточно продолжительного применения худшего действия на последнем к текущему моменту времени ытапе управления. Б ьтой же главе делаются оценки требуемой емкости памяти при практической реализации предложенных алгоритмов; оказывается, что если время функционирования вычислительной системы равно

Т , то требуемая емкость памяти имеет порядок У , то есть относительно невелика. Следует отметить простоту предложенных алгоритмов при реализации их с помощью вычислительной техники: требуется, чтобы система выполняла только действия сложения, вычитания и условного перехода. Для сравнения укажем, что автоматы с переменной структурой должны еще выполнять операцию умножения, а автоматы, оценивающие параметры процесса, еще и операцию деления. Результаты главы опубликованы в [$[Л].

Суммируя вышенаписанное, молено сказать, что актуальность работы определяется

- важностью задачи асимптотически оптимального адаптивного управления случайными процессами, в частности, марковскими цепями с доходами;

- интересом к эволюционирующим системам в кибернетике в целом;

- простотой конструкции автоматов, построенных на основе автоматов (I , что важно в случае практической реализации ¿тих автоматов с помощью высислительной техники.

При этом в работе решаются следующие задачи:

1. Исследуются границы предельного среднего дохода симметрического конечного автомата, матрица переходных условных вероятностей которого может произвольным образом меняться с течением времени. Для границ предельного среднего Дохода получены точные оценки; оказывается, что такие автоматы не могут быть асимптотически оптимальными.

2. Исследуются автоматы с растущей памятью, построенные на основе известных автоматов типа </} (/ . Устанавливаются достаточные условия асимптотической оптимальности ьтих автоматов на классе однородных конечных марковских цепей с доходами. Предложенные автоматы не являются частным случаем автоматов с переменной структурой в их традиционном понимании.

3. Исследуется скорость сходимости среднего дохода автомата к его предельному' значению. Показано, что если функция наращивания глубины памяти имеет степенную зависимость от номера ьтапа управления, то скорость сходимости среднего дохода к его предельному значению имеет степенную зависимость от времени. При управлении ОПНЗ показано, что наилучшая сходимость среднего дохода обеспечивается автоматом с линейной шункцием наращивания памяти.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Колногоров, Александр Валерианович

ЗАКЛЮЧЕНИЕ о о

Б работе проведено исследование автоматов с конечной и растущей памятью, управляющими 01ШЗ и однородными марковскими цепями с доходами. При этом решался вопрос о границах предельного среднего выигрыша таких автоматов и, в частности, вопрос о возможности их асимптотической оптимальности. Рассмотренные автоматы являются обобщением и дальнейшим развитием конструкций, описанных в [^ [, таких как и другие. Но если в [пцм , а также других работах по автоматам такого типа структура автоматов предполагалась неизменной, то особенность и новизна задач, рассмотренных в данной работе, состоит в том, что вероятности переходов между состояниями автоматов менялись во времени. Это потребовало нового подхода к решению сформулированных задач.

В работе получены следующие новые результаты.

1. Установлено, что симметрические конечные автоматы не могут быть асимптотически оптимальными на массе ОШЗ даже и в том случае, если матрица их условных переходных вероятностей некоторым образом меняется во времени. Получены точные верхняя и нижняя оценки доходов таких автоматов в зависимости от глубины памяти. Указаны автоматы, обеспечивающие достижение максимального и минимального значений предельного среднего дохода; эти автоматы тлеют матрицы переходных условных вероятностей, меняющиеся во времени. Следствием этого результата является то, что асимптотически оптимальным может быть только автомат с бесконечной, например, растущей памятью.

2. Построены конструкции автоматов с растущей памятью на основе автоматов 31, ^ К $ и доказана их асимптотическая оптимальность на классе однородных конечных марковских цепей с доходами. Множество асимптотически оптимальных автоматов включает в себя автоматы, функции роста периода и глубины памяти которых меняются в значительных пределах, что видно из приведенных примеров. Результаты обобщены на случай цепей, доходы которых являются случайными величинами, распределенными на всей числовой прямой, а также на случай процессов, пространство управлений которых является компактным подмножеством числовой црямой.

3. Для автоматов со степенной функцией роста глубины памяти решен вопрос о скорости сходимости среднего дохода автомата на классе однородных марковских цепей с доходами, которая оказалась степенной функцией времени. На классе 011НЗ установлено, что наилучшая скорость сходимости среднего дохода к его предельному значению обеспечивается автоматом с линейной функцией роста глубины памяти. Сделанные оценки позволяют судить о функционировании автомата с растущей памятью не только на бесконечном, но и на конечном отрезке времени.

4. Получен ряд оценок, которые могут быть далее использованы при изучении автоматов ^ $ , конструкций на их основе, а также при решении задач о случайном блуждании с двумя отражающими экранами.

Достоинство предложенных асимптотически оптимальных автоматов состоит в простоте алгоритмов, лежащих в их основе, так как для их реализации не требуется производить подсчета статистик процесса, а также пересчитывать вероятности применения действий с использованием операции умножения. Поэтому предложенные автоматы могут быть реализованы на простых вычислительных средствах, обладающих высоким быстродействием.

В работе рассматривалось главным образом функционирование автоматов на бесконечном промежутке времени. Б качестве дальнейшего направления исследований можно поставить ряд задач о шункционирова-нии автоматов на конечном промежутке времени. Укажем некоторые из них.

I. Исследовать функционирование автомата с растущей памятью в предположении, что время функционирования является ограниченной случайной величиной с некоторой заданной функцией распределения.

2. Решить вопрос об оптимальной структуре автомата с конечной памятью, функционирующего на заданном конечном промежутке времени.

3. Рассмотреть автоматы с растущей памятью в переключаемых случайных средах.

При решении атих задач, по-видимому, будут полезны оценки, полученные в главе 2. Эти оценки могут быть сделаны более точными.

Кроме того, можно рассмотреть игры автоматов с растущей памятью, а также различные иерархические системы, построенные на их основе.

Список литературы диссертационного исследования кандидат физико-математических наук Колногоров, Александр Валерианович, 1983 год

1. Агасандян Г.А. Адаптивная система для класса однородных последовательностей.- ДАН СССР, 1976, т. 228, 1Ь 2.

2. Буш Р., Мостеллер Ф. Стохастические модели обучаемости.-М.: ^изматгиз, 1962.

3. Вавилов Е.И., озрохи А.И. Синтез автоматов, функционирующих в стационарных случайных средах, максимизирующих среднее количество информации, содержащееся в реакциях среды.- Кибернетика,1977,2.

4. Валах В.Я. О поведении автомата с избирательной тактикой в стационарных случайных средах.- Кибернетика, 1968, № 4.

5. Варшавский В.И. Коллективное поведение автоматов.- М.: Наука, 1973.

6. Варшавский В.И., Воронцова И.II. О поведении стохастических автоматов с переменной структурой.- Автоматика и телемеханика, 1963, т.24, М 3.

7. Винер Н. Кибернетика.- М.: Сов. радио, 1968.

8. Воронцова И.И. Алгоритмы изменения переходных вероятностей стохастических автоматов.- Проблемы передачи информации, 1965, т.1, й 3.

9. Гантмахер С?.Р. Теория матриц.-М.: Гостехиздат, 1953.

10. Гессель М., Срагович В.Г. Адаптивное управление марковскими цепями с доходами.— ДАН СССР, 1980, т.254, й 3.

11. Де Гроот М. Оптимальные статистические решения.: М.-Мир, 1974.12. 1Урвич Е.Т. Адаптивное управление векторными случайными процессами.- В сб.: Исследования по теории адаптивных систем. М.: ВЦ АН СССР, 1976.

12. Засухин В.С.Достаточные условия асимптотической оптимальности одного класса вероятностных автоматов.- Изв. АН СССР. Техническая кибернетика, 1975, JS 5.

13. Засухин B.C. Адаптивное управление марковски?»® процессами.-Автореферат канд. дисс. М.: ВЦ АН СССР, 1976.

14. Зигангиров К.Ш. О многоальтернативном различении гипотез с помощью автоматов с конечным числом состояний.- Проблемы передачи информации, 1977, т. 13, & 3.

15. Канделаки H.H., Церцвадзе Г.Н. Решение задачи локализации характеристических чисел матриц автоматов, обладающих асимптотически оптимальным поведением в стационарных случайных средах.- Труды ВЦ1. АН Г^ССР, 1969, т.9, В 1.1. W 7>. М.£. Tie

16. PrJ&At fitrifil Tcrti'tt fiiuccofv1. U, dovtr 7.J/. а Пой о*1. Шt f. //, л/с /V.

17. Колногоров A.B. Границы предельного среднего выигрыша симметрического конечного автомата, 1980.- Депон. в ВИНИТИ В 2892-80.

18. Колногоров A.B. Асимптотически оптимальный аналог автомата Роб-бинса, 1980.- Депон. в ВИНИТИ М 3521-80.

19. Колногоров A.B. О сходимости среднего выигрыша асимптотически оптимального аналога автомата Роббинса, 1981.- Депон. в ВИНИТИ1391-81.

20. Колногоров A.B. Асимптотически оптимальные автоматы с растущей памятью. ДАН СССР,1983, т. 270, ß I.

21. Коновалов М.Г. Многоуровневые адаптивные системы управления марковскими цепями. Автореферат канд. дисс.- М.: ВЦ АН СССР, 1978.

22. Майн X., Осаки С. Марковские процессы принятия решений.-М.: Наука, 1977.

23. Кринский В.И. Об одной конструкции последовательности автоматов и ее поведение в играх.- ДАН СССР, 1964, т. 156, Ш 6.

24. Крылов В.Ю. Об одном стохастическом автомате, асимптотически оптимальном в случайной среде.- Автоматика и телемеханика, 1963, т. 24, й 9.

25. Милютин А.А. Об автоматах с оптимальным целесообразным поведением в стационарной среде.- Автоматика и телемеханика, 1965,т. 26, № 1.

26. Мухин В.И. О некоторых свойствах одного класса управляющих систем, функционирующих в стационарных случайных средах.- Проблемы передачи информации, 1980, т. 14, $ I.

27. Л, /аг&пс/ы ^клИйсАлл №. Д. /.а №£С Ого«*. М- ?

28. Невельсон М.Б., Хасьминский Р.З. Стохастическая аппроксимация и рекуррентное оценивание.- М.: Наука, 1972.

29. Дж. фон Нейман. Теория самовоспроизводящихся автоматов.-М.: Мир, 1971.

30. Пономарев В.А. Об одной конструкции конечного-автомата, асимптотически оптимального в стационарной среде.- Биофизика, 1964, т. I, й 9.

31. Растригин Л.А. Случайный поиск с линейной тактикой.- Рига.: Зинатне, 1971.

32. Роббинс Г. Некоторые аспекты последовательного построения экспериментов.- Кибернетический сборник. Новая серия. М.: Мир, 1970.

33. Роббинс Г. Построение последовательноетных экспериментов с конечной памятью,- Кибернетический сборник. Новая серия. М.: Мир,

34. Розенблатт <'\ Принципы нейродинамики.- М.: Мир, 1965.

35. Срагович В.Г., клеров Ю.А. Построение класса оптимальных автоматов.- ДАН СССР, 1964, т.159, Ш 6.

36. Срагович В.Г. Теория адаптивных систем.- М.: Наука, 1976.

37. Срагович В.Г. Адаптивное управление.- М.: Наука, 1981.

38. Трахтенброт М.В. Об одной модели обучения с растущей памятью.-Кибернетика, 1972, Je 5.

39. Феллер В. Введение в теорию вероятностей и ее приложения. -М.: Мир, т.1, 1964, т.2, 1967.45. ёельдбаум A.A. Теория дуального управления,- Автоматика и телемеханика, 1960, т.21, J.3 9, JS II.

40. Флеров Ю.А. О некоторых классах многовходовых автоматов.- В сб. Исследования по теории самонастраивающихся систем. М.: ВЦ АН СССР, 1971.

41. Олеров Ю.А. О предельном поведении и асимптотической оптимальности стохастических автоматов.- В сб. Исследования по теории1970,1. JS. /

42. Жгли Рм. /Ь/ ¿W Jb. /^7 /; Цадаптивных систем. М.: ВЦ АН СССР, 1976.48. сомин В.Н., Фрадков А.Л., Якубович В.А. Адаптивное управление динамическими объектами.- М.: Наука, 1980. 6 ¡/¿¿¿мая ^.¿^ ¿ЬтгсА (¿. Л.кплА . г //

43. Хеллман М.Е., Ковер Т.М. По поводу автоматов в случайной среде.- Проблемы передачи информации, 1970, т.6, ДО 2.

44. Церцвадзе Г.Н. Об асимптотических свойствах оптимальных автоматов в стационарной случайной среде.- Автоматика и телемеханика, 1968, т.29, 1Ь 8.

45. Цетлин М.Л. 0 поведении конечных автоматов в случайных средах.-Автоматика и телемеханика, 1961, т.22, й 10.

46. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем.- М.: Наука, 1969.

47. Цыпкин Я.З. Адаптация и обучение в автоматических системах.-М.: Наука, 1968.

48. Эшби У.Р. Конструкция мозга. Происхождение адаптивного поведения.- М.: Изд. иностр. литературы, 1962.

49. ПРШОШЖЕ I ОПИСАНИЕ АВТОМТОВ ^) ^^ Я ^ ) ^/С, У1 ; /С И.

50. Так как в литературе имеются некоторые разногласия в описании автоматов ^ й: л, ' мы ПРИВ°ДИМ описание, котороеиспользуется в работе, а также р.яд свойств этих автоматов.

51. Все рассматриваемые здесь автоматы относятся к классу одновхо-довых ( см. главу 2 ). Это означает, что все множество состояний автомата может быть разбито на (по числу действий ) ветвей.

52. Для автомата справедлива следующая система уравненийсм., например, . )при граничных условиях ~ 0, Е ~ Е^и.

53. Решая эту систему, получим

54. Поэтому для отношений предельных вероятностей справедлива формула£ .11ЙА1 Ч'г^Ь ел»/ ■1/^/

55. Легко видеть, что при условии ^ ^ 7 >/^у имеет место предельное равенство1. Фк.Ь)й1. Л н гхз1ЛЛ --1. Г, 1с, (<)

56. Это равенство не имеет места, если ^^ • Говорят, чтопоследовательность автоматов "асимптотически оптимальна при Я -* оо в области ^ >р

57. Eii CpfL / fPfJE^ '(pq. +q fr) +■ /.при граничных условиях = 0, £ fT^ .

58. Если обозначить P~PP~ P+j Q~pf- » то эта системасовпадает с системой уравнений для автомата ^ ^ » гДе вместостоят Р, (j4. Автомат

59. Изучался В.И. Кринским. В Ш. назван также автоматом Роббинса. Имеет граф при условии полученияштрафаА-о<