Хайкин С. - Нейронные сети (778923), страница 154
Текст из файла (страница 154)
Здесь под термином "решение" понимается один из вариантов управления в коикретиый момент времени, а под термином "стратегия" — вся управляющая последовательиость или функция. Для того чтобы сформулировать принцип оптимальности в математических терминах, рассмотрим задачу с конечным горизоитом, для которой функция стоимости перехода имеет следующий вид: к — г .Т,(Х,) = К дк(Хк)+ ~'д„(Х„,ц„(Х„),Х„„), (12.8) я=0 где К вЂ” горизонт (Ьопгоп) (те. количество шагов); дк(Хк) — терминаль- наЯ стоимость (геппша1 совг). Дла данного Хе магематичеспзе ожидание (12.8) формулируется относительно оставшихся состояний Хы ..., Хк г. С помощью этой терминологии можно формально определить принцип оптимальности Беллмаиа в следующем виде (125).
ПУсть П' = (1Гь, ц~,..., ц~ г) — оптимальнаЯ стРатегиЯ длл задачи с конечным горизонтом. Предполагается, что при использовании оптимальной стратегии и" заданное состояние Х„наступает с ненулевой вероятностью. Рассмотрим подзадачу, в которой система в момент времени и находится в состоянии Х„, и предпсаоясим, что необходимо минимизировать соответствующую функцию стоимости перехода к-г .У„(Х„) = Е дк(Хк)+ у д„(хь,ць(Х„),хи+,) (12.9) для п = О, 1,..., К вЂ” 1. Тогда усеченная стратегия ()г*„, ц„'+г,..., йк г) будет оптимальной для этой подзадачи. 12.3. Критерий оптимальности Беллмана 767 ° После этого оптимизация расширяется на предыдущую ступень и строится оптимальное решение для последних двух ступеней системы. ° Так продолжается до тех пор, пока вся система не будет охвачена оптимальным решением.
Алгоритм динамического программирования На основе описанной процедуры можно сформулировать алгоритм динамического программирования, который реализуется в обратном времени, от 1'т' — 1 до О. Пусть л =()1„)гз,..., )гк 1) обозначает некоторую допустимую стратегию. Для каждого п =О, 1,..., К вЂ” 1 обозначим л" =(11„,)1„+1, ..., )гк 1). Пусть 1„'(Х„) определяет оптимальные затраты на (К вЂ” л)-м шаге задачи, который начинается в момент времени и с состояния Х„и завершается в момент времени К, т.е. К вЂ” 1 1„'(Х„) = ппп Е дк(Хк) + ~1 дь(Х„, Р (Хь ), Хь+1) . (12.10) а" 1х.
„...,х,1 1ь Это выражение представляет собой оптимальную форму (12.9). Зная, что к" = (р„,я"+1), и частично раскрывая сумму в правой части выражения (12.10), можно записать следующее: 1„'(Х„) = пйп Е [д„(Х„,)1„(Х„), Х„ь1) + дк(ХК) + 1и„,я-+Ч 1х. ь...,х,1 К-1 + ~ д„(Х„,рь(Х„),Х„,)[ = 1=и+1 = ппп Е (д„(Х„,)1„(Х„),Х„.~1)+ П„Х.1, (12. 11) К-1 +ппп Е дк(Хк)+ ~1 дь(Хь )гь(Хь) Хь~1) ) = Я" 1х..1„...,х,) ~ Ь= а-1-1 = ппп Е [д„(Х„, )з„(Х„), Х„. 1) + 1„' 1(Х„.„1)1, п.
х.„ Интуитивно можно понять истинность этого принципа оптимальности. Если бы усеченная стратегия ()1'„, и„'„1„..., 1г 1) не была оптимальной, то после достижения в момент времени п состояния Х„можно было бы уменьшить функцию стоимости перехода 1„(Х„), перейдя к стратегии, оптимальной для данной подзадачи. Приведенный подход к оптимальности основывается на инженерном принципе "разделяй и властвуй". По существу, оптимальная стратегия сложного многоступенчатого планирования или задачи управления строится согласно следующей процедуре. ° Вначале строится оптимальная стратегия для последней подзадачи, включающей в себя только последнюю ступень системы. 768 Глава 12.
Нейродннамнческое программирование где в последней строке используется определение (12.10), в котором вместо п под- ставлено гз + 1. Теперь предположим, что для нежзгорого п и всех Х„ь„ ,У„*„(Х„„) = У„+,(Х„+,). (12.12) Тогда выражение (12.11) можно переписать в следующем виде: о„'(Х„) = ппп Е [д„(Х„, р„(Х„), Х„ьг) +,У„ьг(Хь ы)] . (12.13) и. х„„ Если соотношение (12.12) выполняется для всех Х„ь„то равенство .У„"(Х„) =,У„(Х„) также выполняется для всех Х„. Следовательно, из (12.13) можно заключить, что .У„(Х„) = пцп Е ]д„(Х„,п„(Х„),Х„+г) +,У„.ьг(Х„ьг)].
и„х.ь, Таким образом, можно формально записать алгоритм динамического программирования в следующем виде [125]. Для любого исходного состояния Хо оптимальное значение функции сгяоимости .1'(Хо) равно Уо(Хо), где функция Уо вычисляется начиная с последнего шага следующего алгоритма: ,У„(Х„) =ппп Е ]д„(Х„,р„(Х„),Х„ьг)+,У„„г(Х„+г)], (12.14) и„х„е, который "перемещается" по оси времени в обратном направлении, при этом ,Ук(Хк) = дк(Хк). Более того, если значение р„' минимизирует правую часть (12.14) для всех Х„и и, тогда стРатегин П* = (Рс, Рг,..., П~~ ) Явлаетса оптимальной. Уравнение оптимальности Беллмана Основная форма алгоритма динамического программирования связана с решением задачи с конечным горизонтом. Однако этот алгоритм можно расширить для решения задач с бесконечным горизонтом, юторые описываются функцией стоимости (12.5) при стационарной стратегии и = ()г, и, р,...).
Для достижения этой цели нам нужно сделать следующее. з 2.3. Критерий оптимапьности Беллмена 769 ° Изменить индекс времени в алгоритме так, чтобы он соответствовал задаче. ° Определить стоимость д„(Х„, )з(Х„), Х„ь, ) как д„(Х„, р(Х„), Х„.ь, ) = 17'д(Х„, )г(Х„), Х„ь, ). (12.15) Теперь алгоритм динамического программирования можно переформулировать в следующем виде (см. задачу 12.4): .7„ь,(Хс) = ппп Е [д(Хс, )г(Хс ),Х1) + 7,7„(Х,)] . (12.16) а х, Этот алгоритм начинается с исходного условия ,7в(Х) = 0 для всех Х. ,7"(1) = 1пп .7к(1) для всех 1.
К ~ю (12.17) Это соотношение является связующим звеном между дисконтированными задачами с конечным и бесюнечным горизонтами. Принимая п+ 1 = К и Хв — — ю' в (12.16), а затем применяя (12.17), получим: ,7'(т) = пйп Е [д(т,)г(1), Хз) + 7,7'(Х,)] . а х, (12. 18) Для оценки оптимальных затрат,7*(1) в задаче с бесконечным горизонтом выполняются следующие действия. 1. Вычисляем математическое ожидание стоимости д(1, )г(1), Х1) по Хз.
Е[д(т),п(1),Х„] = ~) р,"д(т',(г(1),2), (12.19) где Х вЂ” юличество состояний среды; р;, — вероятность перехода из начального состояния Хс — — 1 в новое состояние Х, = з'. Величина, определяемая выражением (12.19), называется мгновенной ожидаемой стоимостью (пшпегйа1е ехрес1ед Итак, алгоритм начинается с неюторого исходного состояния Хс, новое состояние Х, получается в результате применения стратегии р, а у в (2.15) представляет собой дисконтный множитель.
Пусть 7*(т) означает оптимальную стоимость в задаче с бесконечным горизонтом и начальным состоянием Хс — — 1. Тогда 7*(1) можно рассматривать как предел соответствующей оптимальной стоимости 7к(т) на К-м шаге при К, стремящемся к бесконечности: 770 Глава 12. Нейродинамическое программирование соз!) в состоянии (, при выполнении действия, рекомендованного стратегией )г. Обозначая эти затраты как с((, р(!)), можно записать, что с(1,)г(1)) = ~~~ рчд((,!г(!),2).
з=ь (12.20) 2. Оцениваем ожидание 7'(Х,) по отношению к Х,. Отсюда можно заключить, что в системе с конечным числом состояний, если известна стоимость перехода ,У'(Хз) для всех состояний Хы можно наверняка определить ожидание д'(Х~) в терминах вероятностей перехода соответствующей цепи Маркова, записав: Е~.! (Х,)) ",'~ р„д (2). (12.21) Таким образом, подставляя выражения (12.19) — (12.21) в (12.16), получим искомый результат: .7'(!) = ппп с((,ц(!)) +7~) р„()г),Г(2),! = 1,2,...,Х.
(12.22) я ~=1 Равенство (12.22) называется уравнением оптимальности Беллмана (Ве!!пзап'з ор1ппа(йу еоцаг!оп). Его нельзя рассматривать как алгоритм — оно представляет собой систему 1У уравнений, в которой для каждого состояния отводится одна переменная. Решение этой системы уравнений определяет оптимальные значения функции стоимости перехода (созЬГо-яо бзпс1!оп) для всех 11! состояний внешней среды. Существуют два основных метода вычисления оптимальной стратегии: итерация по стратегиям и итерация по значениям. Зти два метода описываются в разделах 12.4 и 12.5. 12.4. Итерация по стратегиям ь Я" (1, а) = с(1, а) + 7 Я р„(а) Р(Я, 1=1 (12.23) Чтобы подготовить основу для описания алгоритма итерации по стратегиям, введем понятие Я-фактора !1115).
Рассмотрим существующую стратегию )г, для которой функция стоимости перехода У'(!) известна для всех состояний !. Д-фактор (О-Тасгог) каждой пары состояния ! Е Х и действия а Е А, определяется как мгновеннал стоимость плюс сумма дисконтированных стоимостей всех последующих состояний согласно стратегии р, т.е. 12.4. Итерация по стратегиям 771 где действие а = и(().
Заметим, что Я-факторы Я" (з, а) содержат больше информации, чем функция стоимости перехода 1" ((). Например, действия можно упорядочить только на основании Я-фактора, в то время как упорядочивание на основе функции стоимости перехода требует знания вероятностей и стоимости перехода между состояниями. Для более глубокого изучения Я-фактора рассмотрим новую систему, состояния которой образованы на основе исходных состояний 1, 2, ..., Аг и всех возможных пар ((, а) (рис. 12.2). Здесь возможны две ситуации. ° Система находится в состоянии ((, а), в котором не предпринимается никаких действий.
Переход автоматически выполняется в состояние 1 с вероятностью, скажем, р,, (а), при этом автоматически вычисляется стоимость д((, а, 1). ° Система находится, к примеру, в состоянии 1, в котором предпринимается действие а е А,. Следующее состояние предопределено как ((, а). Стратегия и называется жадной (ягееду) по отношению к функции стоимости перехода У'(1), если для всех состояний и(!) представляет собой действие, удовлетворяющее следующему условию: Я" (1, !г(()) = ппп Я" (1, а) для всех (. аЕА. Здесь важно обратить внимание на следующие моменты. (12.24) ° В некоторых состояниях возможно несколько действий, которые минимизируют множество Я-факторов. В этом случае может существовать более одной жадной стратегии по отношению к соответствующей функции стоимости перехода.
° Некоторая стратегия может оказаться жадной по отношению к нескольким различным функциям стоимости перехода. Более того, следующий факт является основой всех методов динамического программирования: Я" ((, )г'(()) = ппп Я"*((, а), аЕА, (12.25) 1. Шаг вычисления стратегии (ройсу еиа1пайоп мер), на котором определяются функция стоимости перехода для некоторой текущей стратегии и соответствующий Я-фактор. где )г* — оптимальная стратегия; 7' — соответствующая функция стоимости перехода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
