Стохастические оптимизационные автоматы с растущей памятью

• Автор: Колногоров, Александр Валерианович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1983
• Место защиты: Москва
• Количество страниц: 134 c. : ил

ОГЛАВЛЕНИЕ Стр>

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

§ 1.1. Определения бинарного ОГШЗ, симметрического авто

мата, целей управления

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

симметрического конечного автомата

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

ГЛАВА 2. НЕКОТОРЫЕ СВОЙСТВА АВТОМАТОВ Я,*, “4• •

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

одновходовых автоматов общего вида
§ 2.2. Оценки вторых моментов случайных величин
автоматов Яи
§ 2.3. Оценки вторых моментов случайных величин Т}1
автоматов 4.«, 4«
§ 2.4. Оценки вероятностей выхода из цепочек автоматов Р-ки. Р/га. Рк и. 33 зависимости от времени их гоункционирования
§ 2.5. Обобщение результатов главы на случай слабо неоднородных процессов
ГЛАВА 3. АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫЕ АВТОМАТЫ С РАСТУЩЕЙ ПА
МЯТЫ) ДЛЯ УПРАВЛЕНИЯ МАРКОВСКИМИ ЦЕПЯМ С ДОХОДАМИ
§ 3.1. Определение управляемых процессов и целей управления

§ 3.2. Конструкции автоматов с растущей памятью и достаточные
условия их асимптотической оптимальности
§ 3.3. Доказательство асимптотической оптимальности автомата ^ с растущей памятью на классе марковских цепей с доходами
§ 3.4. Некоторые обобщения
ГЛАВА 4. ОГРАНИЧЕНИЯ НА ©УНКЦШ РОСТА ГЛУБИНЫ ПАМЯТИ АВТОМАТА
И ОЦЕНКА СКОРОСТИ СХОДИМОСТИ ЕГО СРЕДНЕГО ДОХОДА
§ 4.1. Ограничения на скорость роста функции глубины памяти 88 § 4.2. Оценка скорости сходимости среднего дохода автомата с растущей памятью
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ I. ОПИСАНИЕ АВТОМАТОВ *4
ПРИЛОЖЕНИЕ 2. СХЕМА ДОКАЗАТЕЛЬСТВА ТЕОРЕМЫ 1.3 Ю9
ПРИЛОЖЕНИЕ 3. ДОКАЗАТЕЛЬСТВА НЕКОТОРЫХ РЕЗУЛЬТАТОВ ГЛАВЫ 3 п9
ПРИЛОЖЕНИЕ 4. ДОКАЗАТЕЛЬСТВА НЕКОТОРЫХ РЕЗУЛЬТАТОВ ИЗ ГЛАВЫ 4

В работе рассматривается асимптотически оптимальное адаптивное управление посредством стохастических автоматов однородными ко -нечными марковскими цепями с доходами. Задачи, решаемые в работе, состоят в построении дискретных систем, обеспечивающих достижение заданной цели управления, и принадлежат к теоретическим проблемам кибернетики/?^ А/ [22]) №~]3 [2/].
Класс управляемых однородных конечных марковских цепей[41] за -дается множествами состояний } и управлений
; переходы между состояниями регулируются матрицами переходных условных вероятностей(^Ц , где^Я.^/-вероятность перейти ИЗ СОСТОЯНИЯ в состояние Лу , если в состоянии было применено управление ^ . На множестве * У
определены "доходы" , которые получает автомат, если в состоянии чГ было применено управление У . Доходы Щ) могут быть как детерминированными, так и случайными величинами; в последнем случае они могут быть ограниченными или распределенными на всей числовой прямой. Как частный тип однородных марковских цепей с доходами, у которых множество вырождается в одно состояние, могут рассматриваться и однородные процессы с независимыми значениями ( ОПНЗ ) [42] ; особо выделяются бинарные ОШЗ, то есть ОПНЗ, доходы которых могут принимать лишь два значения ^ ~/ ( поощрение и штраф ). Отметим адаптивную постановку задачи: численные значения переходных условных вероятностейи функции распределения доходов предполагаются неизвестными.
В качестве цели управления в работе рассматривается традиционная цель максимизации предельного среднего дохода в единицу времени. Если требуется, чтобы предельный средний доход отличался от максимально возможного не более чем на <£ , то такая ослабленная цель управления называется с£ -оптимальностью; если же требует-

можЗамечанне. Для случая У оо методом, описанным в т но получить более точные оценки для вероятностей [р^ І-Нам для дальнейшего потребуется следующий результат, установленный [<м] . При у >р вероятность выхода из ветви автомата /,С)П

равна
Отсюда, так как
р (<*>)• рЁрТР).
получим
£>-=> л
5 Гт- і ■
Перейдем к рассмотрению случая конечной глубины памяти. Если глубина памяти равна У , то через ^ [р обозначим вероятность
нахождения автомата в момент времени £ в состоянии с глубиной і . Переходы между состояниши одной ветви автомата ^ можно рассматривать как одномерное случайное блуждание с отражающим экраном 1^1 . При этом множество траекторий, по которым автомат к моменту времени / попадает в С -ое состояние можно разбить на два класса.
В первый класс, который мы обозначим как событие $/ • £ ,
попадают траектории, которые не изменились бы при увеличении глубины памяти, то есть остались бы неизменными при бесконечной глубине памяти. Это те траектории, которые не задерживались более чем на один такт подряд в самом глубоком состоянии ветви. Очевидно, что верна оценка
ри„,<) рГіу.
(2.4.7)
Во второй класс попадают траектории, которые задерживались по крайней мере на два такта подряд в самом глубоком состоянии ветви