Хайкин С. - Нейронные сети (778923), страница 155
Текст из файла (страница 155)
Имея в распоряжении понятия (1-фактора и жадной стратегии, можно описать алгоритм итерации по стратегиям (ройсу йегайоп а!йопйпп). Этот алгоритм включает следующие шаги (125]. 772 Глава 12. Нейродинамическое программирование Рис. 12.2. Два возможных перехода: переход из состояния (х, о) в состояние 1 является веро- ятностным, а переход из состояния е в состоя- ние (ь, о) является детерминистским Стоимость перехода хх Рис.
12ль Блочная диаграмма алгоритма итерации по стратегиям 2. Шаг улучшения стратегии (ро1(су (шргочешепг мер), в котором текущая стратегия корректируется и становится жадной по отношению к функции стоимости перехода, полученной на шаге 1. Эти два шага показаны на рис. 12.3. Для большей конкретизации начнем с некоторой исходной стратегии р, после чего сгенерируем последовательность новых стратегий р„р,....
Для данной стратегии р„реализуем шаг вычисления стратегии, получив функцию стоимости перехода У'-(з) в качестве решения линейной системы уравнений (12.22): У'-(т) = с(т,р„(т))+т ьг р ((ь ),У""(у), з = 1, 2, ..., Аг (12.26) Ян" (з,а) = с(т,а) +у~р,,(а)Ух" (1'), а Е А, и т = 1,2,...,Аг. (12.27) 7=1 Далее выполняем шаг улучшения стратегии, вычисляя новую стратегию р„+г следующим образом (см. (12.24)): )г„„,(т) = агйш(пЯР" (т',а), т = 1,2,...,Аг.
оЕА, (12.28) опюсительно неизвестных У'- (1), У" (2), ..., У' (Ю). Используя полученные результаты, можно вычислить 9-фактор для пары состояние-действие (т, а) (см. (12.23)): 12.5. Итерация по значениям 773 ТАБЛИЦА 12.1. Алгоритм итерации по стратегиям Начинаем с произвольной исходной стратегии (з . Для п = О, 1, 2,... вычисляем У' (1) и Я" (з, а) для всех состояний 1 Е Х и действий а Е А,. Для каждого из состояний 1 вычисляем р«ы(1) = агйш)пЯ" (1,а). «еА, Повторяем действия 2, 3, пока )г„,, не перестанет улучшать 1з„. В этой точке алгоритм останавливается, а 1г„считается искомой стратегией. 1. 2.
3. Затем описанный выше двухшаговый процесс повторяется для стратегии р„„ пока мы не получим У'"+ (1) = У' (1) для всех 1. 12.5. Итерация по значениям В алгоритме итерации по стратегиям функция стоимости перехода должна была заново вычисляться на каждом шаге алгоритма. С точки зрения вычислений зто слишком затратный подход. Даже если функция стоимости перехода для новой стратегии является идентичной соответствующей функции для старой стратегии, данные вычисления не уменьшаются. Однако существует другой метод нахождения оптимальной стратегии, в котором обременительное действие постоянного вычисления функции стоимости перехода отсутствует.
Этот альтернативный метод, основанный на последовательных аппроксимациях, называется алгоритмом итерации по значениям. Алгоритм итерации по значениям (на1пе йегабол а1йопбпп) подразумевает решение уравнения оптимальности Беллмана (12.22) для последовательности задач с конечным горизонтом. При устремлении количества итераций алгоритма к бесконечности функция стоимости перехода задачи с конечным горизонтом равномерно сходится по состояниям к соответствующей функции стоимости задачи с бесконечным горизонтом [125], [905]. В этом случае алгоритм завершает работу со стратегией 1г„.
Если 7"-«< У'- (см. задачу 12.5), то можно сказать, что алгоритм итерации по стратегиям завершится после конечного количества итераций, так как соответствующий Марковский нроцесс нринятия решений (Магкон(ап бес(з)оп ргосеав) имеет конечное количество состояний. В табл. 12.1 в сжатом виде представлен алгоритм итерации по стратегиям, основанный на выражениях (12.26Н12.28). 274 Глава 12. Нейродннамическое программирование Пусть У„(т) — функция стоимости перехода для состояния з на шаге гз алгоритма итерации по значениям.
Этот алгоритм начинается с произвольного решения,4(г) для з = 1, 2, ..., Ж. Единственным ограничением, налагаемым на Уо(т), является ее ограниченность. Это условие автоматически выполняется в задачах с конечным числом состояний. Если доступна некоторая оценка оптимальной функции стоимости перехода,7*(г), то ее можно использовать в качестве начального значения .Уо(з). Как только выбрана функция .Уо(з), можно вычислить последовательность функций Уг(т), Уз(т),..., используя алгоритм итерации по значениям: .У„.ьт(з) = ппп с(т,а) + Тару(а)У„(У'), з' = 1,2,..., Л.
(12 29) 1=1 Применение модификации функции стоимости перехода, описываемой выражением (12.29) для состояния з, называется резервированием затрат (ЬасЫпя ир о( й'з созг). Это резервирование является прямой реализацией уравнения оптимальности Беллмана (12.22). Обратите внимание, что значения функции стоимости перехода (12.29) для состояний з = 1, 2,..., Х резервируются одновременно на каждой итерации алгоритма. Этот метод реализации представляет собой традиционную синхронную форму алгоритма итерации по значениямз. Таким образом, начиная с произвольных исходных значений,Уо(1),,Уо(2),...,,Уо(Х), алгоритм (12.29) сходится к оптимальным значениям .У'(1),У*(2), ...
„У*(М) при стремлении количества итераций к бесконечности (125], [905]. В отличие от алгоритма итерации по стратегиям в алгоритме итерации по значениям оптимальная стратегия не вычисляется напрямую. Вместо этого сначала с помощью (12.29) вычисляются оптимальные значения,У*(1)„У'(2),... „У'(]1[). Затем по этому оптимальному множеству вычисляется жадная стратегия, т.е. ]г'(з) = агбш[пЯ'(т',а), т = 1,2,...,Х, (12.30) аЕА, где и Я'(т',а) = с(з,а)+у~> рг,(а).У*(2), т =1,2,...,Х.
(12.31) 1=1 В табл. 12.2 приведено пошаговое описание алгоритма итерации по значениям, основанное на формулах (12.29)-(12.31). В это описание включен критерий останова алгоритма. з Итерация по стратегиям и итерация по значениям — два основных метода динамическою программирования, Существуют еще два метода динамическопз программирования, которые нельзя не упомянуть, — метод Гаусса-Зейделя и асинхронное динамическое программирование [99], [125].
В методе Гаусса-Зейделя функция стоимости перехода корректируется в каждый момент времени только для одного состояния; при зтом все остальные состояния разворачиваются (вжеер). Конкуренция основыввщся на самых последних значениях состояний. Асинхронное динамическое программирование отличается от метода Гаусса-Зейделя тем, что оно не организовано в терминах систематических последовательных рвзверток множества состояний. 12.б.
Итерация по значениям гУб ТАБЛИЦА 12.2. Алгоритм итерации ло значениям 1. Начинаем с произвольного начального значения,7с(з) для состояний з = 1, 2, ..., Аг. 2. Для п = 0,1,2,... вычисляем ,Т„ь, (1) = пцп ~ с(т, а) + Т 2; р„(а) 1„(у), а б А„( = 1, 2,..., Аг. Эти вычисления продолжаются, пока не выполнится следующее неравенство: ~.)„ь,(з) —,У„(г) ~ ( 8 для всех состояний з, где е — некоторый наперед заданный параметр допуска. Для того чтобы функция 1„(з) хорошо приближала оптимальную функцию стоимости перехода,У'(г), значение е должно быть достаточно малым.
Таким образом, можно положить: 1„(з) = 1'(() для всех состояний 1. 3. Вычисляем Я-фактор: (~*(г,а) = с(з,а) +ТЯРгз(а)3*Я, а Е Аг, ( = 1,2,...,зч'. з=т Тогда в качестве оптимальной можно выбрать жадную стратегию для Т*(г): )г*(з) = агйгп(п(,) (з,а). аЕА, Пример 12.1 Задача дилижанса Для того чтобы проиллюстрировать полезность О-фактора в динамическом программировании, рассмотрим задачу дилижанса (згабесоасЬ ргомеш). В середине Х1Х века, когда Калифорнию охватила зшютая лихорадка, некий авантюрист отправляется на запад Америки (456). Это путешествие предполагает переезд на дилижансах по неосвоенным землям, где велика опасность нападений бандитов. Исходный пункт путешествия (Миссури) и пункт назначения (Калифорния) фиксированы, однако предстоит выбор маршрута путешествия по восьми промежуточным штатам (рис.
12.4). На зтом рисунке показано следующее. ° Общее количество штатов (10); каждый штат представлен соответствующей буквой. ° Направление движения — слева направо. ° В пути от исходного штата А (Миссури) в штат назначения з (Калифорния) нужно сменить четыре дилижанса. ° При перемещении из одного штата в следующий путник может выбрать одно из следующих направлений: вверх, прямо и вниз. ° Существует 18 возможных маршрутов перемещения из штата А в штат з. На рис.
12.4 также показаны затраты, связанные с соответствующими стратегиями страхования жизни при перемещении на определенных дилижансах, основанные на оценке риска подобной поездки. Требуется найти маршрут из штата А в штат .У с самой дешевой стратегией страхования.
776 Глава 12. Нейродинамическое программирование Рис. 12.4. Граф передачи сигнала для задачи дилижанса Для того чтобы найти оптимальный маршрут, рассмотрим последовательность задач с конечным горизонтом, начинающихся в конечной точке ) и продвигающихся в направлении, обратном направлению маршрута. Это соответствует принципу оптимальности Беллмана, описанному в разделе 12.3. На рис. 12.5, а видно, что Я-факторы для последнего переезда к пункту назначения равны: Я(Н, вниз) = 3, О(1, вверх) = 4. Эти числа на рис.
12.5, а можно увидеть над условным обозначением штатов Н и 1. Далее, перемещаясь на один шаг назад и используя значения из рис. 12.5, а, находим следующие Я-факторьк Г,)(Е, прямо) = 1+ 3 = 4, Я(Е, вниз) = 4+ 4 = 8, Я(К, вверх) = 6 + 3 = 9, ЩЕ, вниз) = 3+ 4 = 7, ЩС, вверх) = 3+ 3 = 6, < >(С, примо) = 3 + 4 = 7. Так как требуется найти маршрут с наименьшей стратегией страхования, то по значениям Г;)-факторов видно, что необходимо оставить только следующие маршруты Е ч Н,Š— 1 и С вЂ” Н, а остальные отбросить (рис. 12.5, 6). Переместившись назад еше на один пункт, повторив вычисления Я-факторов для состояний В, С, Р и оставив только значения, соответствующие наименьшим стратегиям страхования, получим рис.
12.5, в. В заключение, переместившись еще на один шаг и действуя аналогичным способом, получим граф, показанный на рис. 12.5, а На зтом рисунке показано, что существуют три оптимальных маршрута: А — ~ С вЂ” ~ Š— ~ Н ч,г, А- Р- Е Н- 7, А- РчŠ— ~1- Х Все они предполагают затраты, равные 11 условным единицам. 12.5. Итерация по значениям а) б) в) Рис. 12.5. Шаги вычисления 0-факторов в рассматриваемой задаче дилижанса Т78 Глава 12. Нейродинамическое программирование 12.6. Нейродинамическое программирование Основной целью динамического программирования является поиск оптимальной стратегии, т.е. оптимальной последовательности действий, которые должны быть предприняты обучаемой системой в каждом из ее состояний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
