Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 55
Текст из файла (страница 55)
Вместо того чтобы пытаться изучать информацию как «улыбку чеширского кота»*), мы рассмотрим действительный физический процесс, в котором информация используется для выработки решений. Величина информации может быть тогда измерена через эффективность решений. Таким обрззом, полезность информации зависит от ее применения — это наиболее разумная концепция! Рассмотрим процесс передачи сообщений как совокупность трех элементов: источника сигналов, канала связи, который преобразует сигналы, исходящие из источника, в другие сигналы, и приемника, ко~орый интерпретирует сигналы для наблюдателя. Наблюдатель делает выводы на основании сигналов, ко~орые он приннмаег.
Эти решения определяют состояние другой системы о. Для того чтобы свести схему к точной математической задаче, проделаем следующее. В любой частный момент времени источник испускает одни из К различных сигналов, которые мы обозначим символами 1= 1, 2, ..., К. Канал связи в силу различных внутренних несовершенств и внешних воздействий преобразует сигнал 1 в сигнал )'(1' = 1, 2, ...,А4) с вероятностью рп, Первоначально мы будем считать ее известной. От наблюдателя после получения этого сигнала требуется принять решение, которое действует на подсистему о.
Это решение основывается на знании им вероятности гп с которой может быть передан 1-й сигнал, заранее указанного набора вероятностей искажений в канале р;, и вектора состояний системы х. Результат решения состоит ") Улыбка чеширского кота, по сказке Л. Кэррола »Алиса в стране чудес», существовала отдельно от упомянутого кота. (Приап редд заз 28) воямглявовка задачи в преобразовании к в случайный вектор л, распределение которого определяется исходным сигналом, полученным сигналом, нынешним состоянием системы и решением.
27. ПОЛЕЗНОСТЬ КАК ФУНКЦИЯ ИСПОЛЬЗОВАНИЯ Для того чтобы сравнить различные конструкции, мы должны иметь возможность оценивать свойства системы связи. Эта оценка наиболее естественно нырзжается через ее использование. Хотя в некоторых специальных случаях возможно приписать сравнительные числовые характеристики передатчикам, приемникам или каналам связи безотносительно к другим кол~понентам системы, но, вообще говоря, для реалистичных и важных процессов необходимо рассматривать полную систему как одно целое. Как мы увидим, такое описание проблемы полезно не только для разъяснения наших идей; оно указывае~ нам и тот математический аппарат, который мы будем использовать.
28. ФОРМУЛИРОВКА В ТЕРМИНАХ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Предположим, что мы имеем дело с лшогошаговым процессом, на каждом шаге которого сигнал испускается источником, преобразуется в канале связи, принимается наблюдателем, который на этой основе вырабатывает решение. Этот процесс продолжается Аг шагов, в конце которых процесс оцениваетсЯ с помощью заданной фУнкции Р(лж) от конечного состояния л . системы Я.
Мы введем последовательность функций ум(л) — равных математическому ожиданию 7(лл), полученному в результате АГ-ша~ового процесса, начинающегося, когда 5 находится в состоянии .к, нри использовании оптимальной политики, для М = ),2 и всех допустимых .к. (8.7о) Пусть 0(8 7', к, д; г) означает функцию распределения для л, где смысл индексов 8 / и х указан выше, а д означает выбор решения. Тогда в этих терминах мы имеем: ~,(х)=шах~~~',г;~~рг ~ 7(г)ЫО(г,/, х,д; л)~1 (8.76) я[1 /1-чл 344 пвоцвссы гвгглиговлния с овватной связью (гл. ош к ж г ?д (х)=тах [~г, [ф р;, ) 1,,(г)цО(1, г', х, ?; з)[) (8.1?) о ;=~ ?=~ для Аг= 2, 3,.
29. ПРОЦЕСС С АДАПТАЦИЕЙ рассмотрим теперь следующий процесс — относительно простой вариант ситуации, в которой мы не имеем полкой информации о свойствах канала связи. Предположим, что источник испускает два типа сигналов, нули и единицы. При прохождении через канал связи имеется вероятность р точной передачи, т. е. О преобразуется в О или 1 в 1.
Наблюдатель после получения сигнала О или 1 держит пари на некоторую сумму денег (любую от нуля до полной суммы, имеюшейся в его распоряжении), что сигнал, который им получен, совпадает с посланным. Предположим, что имеются равные шансы — обстоятельство, несущественное для этого рассмотрения. Предполагая, что этот процесс повторяется А? раз, мы хотим найги политику, которая максимизирует математическое ожидание заданной функции о от конечной суммы денег. Имеешься много способов сформулировать задачи этого типа.
Мы начнем следующим образом. Основываясь на какой-то доступной информации, мы предположим, что априорное распределение р есть 0(р), которая не являегся ступенчатой функцией с единственным скачком в точке р,. Мы далее предположим, что успешно споряшнй игрок 1 преобразует оценку для р от НО(р) к рЫО(р)/')рг?0(р), а нео удачно споряший — от г(0(р) к (1 — р) Ю(р)( ~(1 — р) с(6 (р) о При этих предположениях мы хотим определить политику, которая максимизирует математическое ожидание заданной функции от конечной суммы денег.
31) ствпинпой закон 30.ФОРМУЛИРОВКА В ТЕРМИНАХ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Пусть х — исходная наличная сумма денег. Введем функзтию у (х, ль л) — математическое ожидание з (лл), где г, — количество денег после М шагов пр» пачальнол~ количестве х и использовании оптимальной политики. При этом задана информация, что произошло а удачных и л иеудаэиыл пари. (8.
78) Введем обозначение ! ра.! (! р)л гтгэ '7ал = \ ') ра (! )л,1Ц ~7ал = 1 Рал (8.79) /,(х, т, л)= шах (д л р(х+у)+дахр(х — у)1. (8.8!) Здесь у — ставка в пари. 31. СТЕПЕННОЙ ЗАКОН Задача может быть решена в явном виде, если ф(л) = =аль, а, Ь) О, или в предельном случае Е(г)=!она. Рассмотрим сначала случай степенной функции. Для а = 1 мы имеем; т, (х; т, л)= шах ~д „(х+у)а+ пал(х — у)э) = а«л х =х шах (д „(1+у) +д „(1 — у)"). (8.82) а и Лвгко теперь доказзть по индукпии, что Г .(х; лп л)= С (т, л)хл, (8.83) Тогда мы получим следуюшие рекуррентные соотношения: Уч(х, и,л)= шак (7 „Уч,(х+у; т+ 1; л)+ 0 г х + г1' х~л, (х — У, т, л + ! )), (А1 = 2, 3, ...) (8.80) пяоггессы гпггливования с оввхтнон связью где последовательность (С (т, л)) определяегся соотношением Сп(т, п)=д „С,(т+1, п)+г)' С,(т, а+1)+ + !пах !с) „1оЕ(1+У)+!7мп!оЕ(1 — У)).
(884) о х 32. ЛОГАРИФМИЧЕСКИЙ ЗАКОН Сходным образом в логзрифмическом случзе мы можем показать, что Тп(х; т, п)=1о8х+Сл(гп, л), (8.85) где С (т, л) = 11 „С,, (т и- 1, и) + д' „С,, (лг, л + 1) -л + шах ~д „!оп(1+у)+д„,„!оп(1 — у)1. (8.86) а > Хотя явно оценить (С (т, л)) нелегко, нетрудно определить оптимальную политику.
Мы видим, что 1 при а „) —, 1 при г) „(; —. (2гу „— 1) х у= 0 ВЗ. ДАЛЬНЕЙШИЕ УПРОЩЕНИЯ И ЧИСЛЕННЫЕ РЕЗУЛЬТАТЫ рвэ а(! Р)л ьа — ~ а В(т+ а+ 1, и+ Ь) аа В(т+и, и+Ь) и~а-~11 р я~а-~ф а а+и аг + а -(- и л- Ь ' Если начальное распределение задано в форме г(О(р) в( ~ Ыр; а, Ь) О, (8.87) где В (а, Ь) — бета-функция (этот выбор позволяет с большоп гибкостью описывать начальную кривую распределения), то мы можем получить; 1 СЬ И ~~ Н б СО О х о зз1 УПРОЩЕНИЯ И ЧИОЛГННЫЕ РЕЗУЛЬТЛТЫ Н ~К К а 1 к Кк к 1 ЕОЧ» ЯТЛ Лижи' Й Ф х к 2 о о с с х к х 4 к $ з Зля пяоцвссы еагхлияовлпия с. оягатноп связью [гл.
щп Для логарифмического случая эго означает, что оптимальная полигика (после лг выигрышей и л проигрышей) состоит в том, чтобы поставить долю от имеющеяся суммы, равную м+ и — (в+ Ь) (8.89) гл+а+л+Ь 1 при условии, что л „),;, или не сгавигь ничего, если 1 д„„ =- †,, Зто приводит к очень простому способу изменения априорной вероятности успеха от попытки к попытке. -гМ а ~п гь ю 42г И Ь27 И Ю ВС угЮ ~/лаю лари Рис. 82. Численный эксперимент был проведен для значении а=4, Ь=1/2, которые дают кривую бр(р), имеющую форму, показанную на рис.
80. (!редполагалось, что канал имеет вероятность точной передачи р = 0,78. Тогда с помощью таблиц случайных чисел была имитирована последовательность 100 пари двумя способами: при первом было известно, что р = 0,78, так что половина наличного капитала ставилась при коммвнтлиии и ьивлиогвлвия каждой возможное~и, яо втором этих сведений не было и использовалась описанная выше схемз. Результаты показаны на рис. 81, по которому можно судить об удовлетворигельности политики. На рис. 82 показано изменение доли капитала на ставку при каждом пари; после 100 пари только 68 было выиграно, так чго ставилось приблизителы<о 40»,Г« наличного капитала, что совсем ненамного ниже оптимального значения 50«,гь. КОММЕНТАРИИ И БИБЛИОГРА<ВИЯ б !. Детальное рассмотрение понятия регулирования с обратной связью может быть найдено в книге: В. В е11в а п, Адар!!се Соп!<о1 Ргосеььеь: А Оибед Товг, Рппсе1оп, Сп!четв<у Ргеьь, Рг!псе!оп, Хся Зегьеу, 1961 )русский перевод: Р.
Б е а.т м а н, Адаптивные процессы управления, Изд-во «Наука», !964). В ней имеются исчерпывающие ссылки на современную литературу. Ь 2. Дальнейшее обсуждение и библиография имеются в Н. Ва1евап, Оп йе сон<го! о1 ап с!аз<к 11и!й Вип. Авег. Ма1Ь, Бос., чо1. 51, !945, рр. 601 — 646.
9 4. См. монографию: В.Ве!!вап апб 3. М. Туапь«<п, А Бигчеуо1 йе Ма<Ьева!ка! ТЬсогу о1 Типе $.ай, ))е!а<бед Соп<го< айд НегегВ!агу Ргосемеь, ТЬс ))АХ)у Согрогьиоп, !)ерог< )7-256,!954, и недавно вышедш<ю книгу; В. В е11 в а и ап<1 К. 1.. С о о 1< е, 0<1!егеп!!а1-б!1)егепсе Еоиа<гопь, Асад«в!с Ргеьь, 1пс., Хея< Уой, 1962. Ь 9.
См. В. В с 11 в а п, !. 01! с и ь Ь е г я апд О. О г о ь ь, Оп йе ЬапяЬапя сои<го! ргоЫев, О. Арр<. Май., чо1. 14, 1956, рр. 11 — 18; й Р. Ь а 8 а!!с Оп <!гпеор<<ва! соп!го! ьуь!евь Ргос. Ха1. Асад. Бек НБА, чо!. 45, 1959, рр. 573 — 577, где можно найти дааьнейшую библиографию б 10. См. М. Аь Ь, )7. В с<< в а п апб В. К а!а Ь а, Оп соп!го! оу геастог ьйи<бо<чп !пчо!Нпд пнп!ва! аепоп ро<ьоп!пе, Хяс!еаг Вс!. апб Епяг» чо1. б, 1959, рр. 152 — 156. 350 пРОннссы РВГулнРОВлш|я с ОБРлтной сВязью !Гл. ви 11. Слг. К.
Вс|1шап, Ыо!еь оп сои|го| ргосевьел.— оп йе в|пинию о1 шах|шиш дел!а!1оп, Г;|. АРР1. Май., чо|. 14, 19о7, рр. 419 — 423. 6 12. Слг. К. Ве1|и! а п, Еипсйопа! сг!иаг!опь апй вах|пшв гап8е, !|. Арр|. Май., то|. !7, 1959, рр. 316 — 318. ф !4. См. К, В с11в а и, Зове пели !еснп|г!иеь !и йе дупапт|с ргойгавш|пи во|и!юп о1 час|виспа! ргоЫсвь, 1,|. АРР1. Май., чо|. 16, 1958, рр. 295 — 305. К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
