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

министерство высшего и среднего специального образования рсфср

московский ордена твдового красного знамен» фпзнко-техшиесшы институт

Нп правах рукопиои

лебедев василил николаевич удк 519.777

ллг0р1ггм!! оптимизации стационарных управлений

в дискретных динамических системах

0I.0I.U9 - ^атрматическяп кибернетика

Апторсфорат

диссертации на соискание ученой степени кандидата физико-матекятических наук

Моекпа - lü'Ju

/

г? Y

/

Раоита выполнена на кафедре Ор-аниваиии и .проектирования (лю-геы Московского физико-техническох'о института

Научпие руководители : д.ф.-(»;.н. Хачичн Л.Г. ,

д.т.п., профессор Орлих А.И.

)

Офш шальные оппоненты : д.ф.-м.н. Леонтьов В.К.,

к.ф.-м.н. Гришухин В.И.

И^иущал организация: ШШ1СИ АН СССР

Защита состоится "......"............. 19У1) г на заседании

специализированного совет;! Г K063.9I.U3 Московского физико-технического института

С диссертацией люжно ознакомиться в библиотеке Московского физико-технического института

АШЛ .Ж'АТ разослш) "....."............. 1990 Г.

.Учений секретарь специализированного совета:

I.ОБЩАЯ ХАРАКТЕРИСТИКА ГАБОТН

Актуальность теш

В диссертационной работе проводится изучешю вычислительной сложности поиска оптимвлмшх стационарных стратегия в динамических конфликтах двух лиц с полной информацией и пределышм во вроумш платежом. Частным Случаем рассматриваемой задачи является известная из комбш 13торной оптимизации проблема отнсгсш'чя экстремальных средних цитслов в ориентированных графах. Этот частный случай соответствует внрождетгой постановке, в ггаторой конфликт отсутствует и речь идет о чистой оптимизации функционала по траектории.

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

Таким образом, цельп работы является построение г, анализ срчислит'1."! нгх алгоритмов поиска огггамальных попедшшй в антагонистических ш-рах с полной информацияй и предельным во гремепи платежом.

Ноучппл новизна

По.пученшо в работе результат! ( дагаше без ссылок на другие источники ) являются новыми.

Практическая значимость

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

I. Р.Белгман ДинямиЧиСкое програмиропашю.

- М : ИЛ, 19602. Р.Беллман Пршслпдше задачи динамического програмирования.

- М. 1965

3. Р.Ховард Динамическое'програмирование и марковские процэсси.

- М, 1964

Апробация работы

Результаты дисспртационноП работи докладовались на научных конфорпшшях Московского аизико-техничоского института, на научном семинаре но дискретной математике в институте Проблем Управления АН ССОР

Публикации

Результата диссертационной работи опублнковони в четнрех печтннх работах ( 1-4 )

2.СОДЕРЖАНИЕ РАБОТЫ

Рассматривалась следу гадая задача: Динамическая система с конечным множеством состояний существует в дискретном времени ^ ~ . находясь в

каждый момент времени в одном из состояв.Л ¡с г 1-1 ¿г"V .

Динамика систеш описывается ориентированным графхэм б-СУ^Е) , ребро (и-) которого означпет возможность парохода из состояния в состояние 1С (-¿) в момент £

функционирования системы. При этом лероходе возможен сбой или отказ и число отказов в состоянии с определяется

целочисленной функцией : о л (< !£:(<•■''/- / ,

где £: (- множество робер с началом в в

графе С . Исходя из концепции гарантированного результата, будем считать, что отказ в состоянии ¿-'"^ "И" определяется противоборствующей стороной, то есть имеется второй игрок наш противник, и он в текущей вершине отсекает некоторое

множество ребор :

е С с) с: Е(1Г) : /Р. (ал < юсе)

а первий переводит систему по одному из оставшихся ребер <=г Е I г (¡г} в очередное состоящте с с ¿г V" , после чего все отсеченные ребра восстанавливаются.

При фиксированной паре стратегий поведения первого и второго игроков , и некотором начальном состоя!ШИ ¿.т^

возникнет бесконечная траектория последовательных переходов системы 7"; 1г(о) ... М)... .Тогда ценой за выбор пори _ лг^ ( и тто есть платок второго первому

у ) является опредйлешшн стоимостная функция возникающей траектории.

В глава I рассматривается средний предельней плате» :

( Здесь функция , стоящая под знаком суммы - есть

локалышй платок заданный на ребрах £ ' графа переходов )

Тогда первш! игрок стремится максимизировать, а второй минимизировать величину с згл) 1 Оказывается для любой начальной вершины ¡гсо) справедливо следущое дискретное

тождество мшшмакса;

/■_/ ) /пах /ти'.т. <г С-^л -51.) - лг^-х. сС-^^в)

^А 2Я.

В главе I дается конструктивное доказательство сформулированного выше утверждения с помощью следуюцего метода.

Рассмотрим потенциальное преобразование стоимостной функции :

( ¿с с: ¿и. ^ -I £ Си.)

для произвольных вещаствешшх £( ^ заданных на вершинах "У" графа О . Это преобразование не меняет стоимостей траекторий ^И поэтому сохраняет нормальную форму игры. В параграфе 4 показало,что существует потенциальное преобразование с: с' приводящее систему ,к следующему тривиальному виду.

Рассмотрим ,все .возможнее значения екстремумов вершин :

Р; . . <Р<п.

(,гюд эксрх^у^едл ^.в^рвдю 1Г иошшается значение

цтоилости моглл - дгр ,ре(|ра ,в порядке убывашш

стмостер ¡ребер, ^сходящих ,113 .в^ршща ,<г ,) ,]иразобьем множество ьарщ>ш,ра блркр :

- У1-- ■ к

где в /-ий блрк попадают вершшш с значением

¡■)Г(;тр"мума ранним р,- . Тогда ребра ведущие из блока Ту' гв блоки I / , / < ^ имеют стоимость строго большую чем ,]?; .

о ребро ведущие из блока в блога! Л^ ; [

юле ют стоимость строго меньшую чем р!

Поэтому, если игра начиналось в вершит иеЛ^ , то первый обеспечит виигршо не меньший цгх-А (си) , если он будет переводить систему по ребру максимальной стоимости из оставшихся после отсечений второго, но и второй имеет возможность проиграть но более го , если он будет отсекать

первые л(<г) ребер в порлдко убывания их стоимостей с началом в текущей вершине ^ Таким образом, из

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

Как уже указывалось, доказательство утверждения о миниматссе носит конструктивный характер и в параграфе 2 изложен конечный алгоритм приведишя системы к такому тривиальному виду. В алгоритме применяется метод дихотомического сокращения разброса экстремумов вершин предложении!! Гурвичем В.Л., Карзаповнм Л.П., Хачияном Л.Г. и распространенный для решения общего случая циклических игр с отказами в работе ( 4 )

В параграфе Б рассмотрены частные случаи представленной выше проблемы. И это есть :

I. Поиск . экстремального ( максимального ) среднего ' цикла дости;химого из вершины о-е°) в ориентированном графе с целочисленной стоимостной функцией с на ребрах.

Пусть во всех состояниях "У" система полностью

управляема, и гювтому /с*''*;— о для любого сьтУ"

Тогда задача оптимального поведения при начальном состоянии и&У и есть задача поиска максималвного среднего цикла достижимого из вершинн "

Предложенный в работе алгоритм найдет потен шальное ггреобразовшше с с стоимостной функции ( и это

преобразование не меняет длин циклов ) такое, что рассмотрев все возмоюше значения экстремумов вершин : /><... ... ^ рп где под экстрэмумом в воршшю (Г понимается значение максимального по стоимости ребра исходящего из V и разбить все вершшш на блоки :

\/ .. . - Т'/" . . . ,

где к / -нй блок попадут вершины с /' -ым значенном экстремума, то для кьэдой вершины / -ого блока во-порЕих будут отсутствовать переходы в вершшш блоков с бопьшим значенном скстромукя, и во-вторых все экстремальные ребра водут в / -ый блок. Тогда для ¡секций начальной вершины и I -ого блока значение максимального средаого цикла достикимого из нее есть о'»°г,идмо г, . Число арифметических операций (+, сравно?те

двоичны* чисел) необходимых для приведения стоимостной функции к тригч''\'1!>нпму гиду огрпчи'?р?1о полиномом от длины входных данных.

^. Ррг'-днчесс.ие расширения матричных игр.

Пусть имеется матричная игра тдавяомая матрицей С(п * т) Т»т одическим рчеп'и-^нн^м матричных игр называют носледователыше выборы /* ¿1 ■ . . первым, вторым игроком соответственно '■трок ... , столбп'ч» ¿¡^___ при известной информации

о предшествующих выборах. Тогда каждой бесконечной партии соответствует последовательность платежей ],) ¿Y'j i,)... , и стоимость такой партш1 (и это есть платеж второго игрока первому) принимают к ale значение среднего предельного платежа. Тогда первый стремится максимизировать, а второй минимичщювпть стоимость о)И1даемой партии.

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

3. Циклические игры.

Пусть дан ориентированный граф Q-CV.tz) с

целочисленной стоимостной с функцией на ребрах, который описывает динамику системы и локальный платеж. Состояния разбиты на два непересекающихся множества А и & Если система находится в состоянии d , то переводит систему в очередное состояние первый игрок, а в состояниях fa? £> переводит систему второй игрок. Тогда в результата бесконечно долго длящейся игры будет пройдена некоторая траектория последовательных состояний ir ... и; . , и плату

второго первому пршшмаыт как среднюю предельную стоимость на етой траектории.

Тогда предложенный в работе алгоритм найдет потенциальное преобразование отсииосткоН Функции с с ' ( ц ато

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

а

если рассмотреть все возможные значения экстремумов вершин рл ^ ,.. < р, ^ ... + р,п ( здесь под вкстремумом в вершине тгА понимается максимальное значение стоимостей ребер с началом , а в вершине ¿/-¿г В - минимальное значение стоимостей ребер о началом С ) и разбить все вершины на блоки

• - • ■ • • ~Ут по значения^ этих экстремумов, то

будут выполнены следующие условия :

1. Для каждой вершины ~У[ ее экстремальные ребра ведут в I -ый блок.

2. Для каждой вершины ¿/¿гТ^'Я А ( VЛ В ) отсутствуют ребра (и-и.^ с концами в блоках с большими ( меньшими ) номерами.

Тогда первый и второй игроки имеют оптимальные стационарные стратегии и , по которым в каждом текущем состоянии

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

Если игра состоит из одного блока " "V" , то ость

цена игры не зависит от начального состояния системы, то такую игру, как было сказано, называют эргодической. Если игра оргодична для любой стоимостной функции на ребрах, то граф такой игры называют структурно эргодическим. ( Структурно эргодичен , например, иодшй двудольный граф {Л , Р>, Е ) с долями А и

В соответствующий эргодическим расширениям матричных игр ) Оказывается, и это доказано в параграфе 8 , что задача распознавания структурной эргодичности графа л/я -трудна.

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

Во-перЕЫХ, удается указать примеры задач, для которых число итераций этого алгоритма оказывается экспоненциальным но числу состояний системы JV

Во-вторых, мокно надеяться - и это подтверждает тот ограниченный опыт, который был собран в экспериментальном исследовании при решении конкретных задач - среднее число итераций алгоритма оказывается существенно меньше и, по-видимому, линейным по числу состояний системы. ( Алгоритм тестировался на модельной задаче преследования одного игрока другим по среднему расстоянию мекду ними на ограниченном отрезке с десятью позициями. И число итераций не превосходило /V/ - '¿0 ° - числа вершин в

графе переходов этой системы. Время работы программы нв превышало двух минут. )

3 гласе 2 рассматривается гарантированный платеж по траектории Т : С'(. , . Cs~(-t). . . , то есть стоимость траектории с с V) определяется так : с с Y'i t'cni- с l'ifw) (s~c-n<))

Необходимость рассмотрения такого случая возникает, когда вахнэ, чтобы значение стоимости перехода не превышало заданного порога для всех переходов системы. Например, в случае когда ■величина ■=•/<>'<0 интерпретируйтся как^вероятность сбоя при переходе из состояния V' в состояние и. , рассмотрение средней в расчете на один ход вероятности сбоя является менее приемлемым гарантированного критерия, так Лш в первом случае допускаются траектории, на некоторых переходах которых можэт возникать большая, в принципе равная единице, вероятность сбоя системы, в то время как во втором можем гарантировать, что ата величина не превысит некоторого небольшого порогового значения на всех переходах.

При етом опять оказывается справедливым дискретное тождество минимакса : (X ) дглх /72 Сп. ) — Пих пгчзс.

■^"л ^ л -5л

для любой начальной вершины .

Доказательство атого утверадения также является конструктивным, но в отличии от случая в главе I потенциальные првобразования существенно изменяют выигрыши игроков, и поэтому ми год потенциальных преобразований здесь не приемлем. В втой главе д'д :тся полшю.лиалышй алгоритм поиска оптимальных стационарных стратегий обоих тороков в описанной выше игре. Алгоритм имеет полиномиальную вычислительную сложность О С /~У>2 У ^N) ( число сравнений двоичных чисел ), где М -максимальная по модулю стоимость переходов системы. Основную идею доказательства покажем на примере игры, в которой при всех начальных состояниях цень одна и таже и равна р

Тогда алгоритм получит два представления игры. По первому представлению будет видно, что первый игрок имеет стратегию, дащую ему выигрыш не меньший р , а по второму

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

Порвое представление такое : Псе вершины графа С разбита на непересекающиеся множества :

. . . т-7 . . .

Т01Ш9, что при любых отсечениях второго игрока первый всегда тлеет возможность перевести систему из текущего состояния V I -ого блока в некоторое очередное состояние и. блока со строго меньшим номером, а осли такой возможности нет, то п состоите

и блока с номером большим либо равным с по ребру со стоимостью . Тогда, так как любой возникающий

цикл должен содержать ребро с началом из одного блока и концом в блоке с большим либо равным помором, а такое ребро в силу построения имоет стоимость с/¿-и)? р , то перга/Л действительно ¡¿моет возможность выиграть не меньше р

Второе представление такое : В кввдой вершине ^«ег'Т7- отсекают некоторое множество ребер : л С сг ■■ /ее¡г)! лг (с-) Так, что все вершины графа можно разбить на неЪоросекопяиеся множество: Л^ ... Л-/: .. . ллГп

такие, что любое оставшееся ребро либо обоими концами лежит в некотором блоке "V/ , и его стоимость тогда удовлетворяет

неравенству: ¿г с <-1, р .

либо ведет из некоторою блока в блок со строго

меньшим номером. Тогда любой цикл в графе с выкинутыми так

ребрами проходит через вершщш одного блока и стоимости есэх ребер такого цик^а удовлетворяют неравенстяву {е-и.) ^ р ,

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

В третьей главе имеем Стохастический случай. Динамика системы описывается тройкой ( (5 Р, с ) , где :

— £) _ ориентированный пол!шй двудольный граф с доля™ А и /3 • и множеством ориентированных ребер £ ( Считаем, что все вершины каждой из долей А н 3 занумерованы числами /,.. . ,/А! . //V соответственно )

»

с • ^ "" ^ ' - целочисленная стоимостная

Функция, заданная на ребрах граф«.

^ '■ —"" ^ ( - функция, ставящая в соответствие

каждой вершине с ¿г Л ( ¡?~ег &) некоторую стохастическую матрицу размером ; в/* пкы (/М * "г У'-ч) ,

столбцы которой интерпретируются как чистые стратегии игрока один ( дна ). ( (- есть вероятность перехода из

состояния ('¿гЛ в / -ое состояние В , если первый игрок в вершине выбрал /с -ую стратегию )

Причем, матриц

предполагается, что все эломенты всех стохастических строго положительные рациональные числа л? , п. / - / , с] ^о

поэтому С -управляемая эргодическая марковсквя

цепь с доходами.

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

А , первый игрок выбирает какой-то столбец Р

матрицы РС^с-") , после чего в соответствии с вероятностями этого столбца возникнет очередное состояние , в

котором процесс разыгрывания повторяется с тем только отличием, что переводом системы занимается второй игрок. После -А -шагов будет пройдена некоторая траектория Т7-* ^ ... ,

будем обозначать вероятность ее при фиксированных стратегиях

и первого И второго игроков как )

Тогда критерий игры естествегага определить как предельное значение математического ожидания среднего выигрыша за 4 - шагов.

То есть первый ( второй ) стремится максимизировать ( минимизировать ) величину

: с Г7) ^=>{"77^ £ГЛ )

у — —

где сумма берется по всем траекториям из -6 переходов с начальной вершиной ( Г^тр - средняя дл!ша

траектории "У^ ).

Для решения таких игр оказывается эффективным применение потенциальных преобразований :

¿> V ¿Гц ) — С С с."и.) ^ ¿'("'у) - ¿¿и)

В силу того, что данное преобразование не меняет предельных средних значений о ^ т' ) , то нормальная

форма игры но меняется от этого преобразования. Оказывается существует £ преобразование, при котором экстремальные значения ( максимальные значения по чистим стратегиям для первого игрока с

минимальные для второго ) математических ожиданий выигрышей за один ход для всех состояний V" системы равны некоторой величине р

Тогда для этой приведенной игры, первый игрок обеспечит себе выигрыш не меньший р , если в каждой верш1ше ^ он будет выбирать столбец матрицы Рс^> дающей максимальное значение ожидаемой стоимости за один ход, но и второй обеспечит себе проигрыш не больший р , если в каадой вершине е~ег & ои будет выбирать столбец матрицы Рс^) дающий минимальное значение ожидаемой стоимости за один ход. Поэтому и в начальной игре значение цены равно р и стратегии, о которых шла речь выше являются оптимальными стационарными стратегиями в нашей игре.

В этой главе дается алгоритм приведения игры к тривиальному виду, идея которого заключается в следующем. Разобьем вершины ~У на два непересекающихся мнажества и ~\Г'Г , так что в попадают все вершины с значением

экстремальных ожидаемых выигрышей за один.ход строго меньше некоторого порога р' , а в мнохество ~у* - все остальные вершины, тогда, если на вершинах ~У~~ увеличивать потенциал , а на вершинах оставлять его нулевым, то экстремальные

значения вершин будут увеличиваться, а вершин

уменьшаться и при этом можно сократить разброс экстремальных значений в раз, что позволяет в пределе полностью

сравнять экстремальные значения выигрышей за один ход всех вершин нашей сети. Общее число элементарных операций ( -г , х , сравнение двоичных чисел ) есть - О (¡У:"1, Здесь Л - некоторый числовой параметр исходной задачи.

Заключение

Основные результаты диссертационной работы состоят в следующем.

1. Предложен эффективный - полиномиальный алгоритм поиска оптимальных стационарных поведений в циклических играх с отказами и гарантированным платежом на траектории.

2. Метод потенциальных, преобразований дашгый' Гурвичем В.А., Карзановнм A.B., Хачияном Л.Г. обобщен на случай циклических игр с отказами и средним, предельным платежом. Проведены вычислительные эксперимента показавшие практическую эффективность этого метода.

3. Предложен метод потенциалышх преобразований для нахождения равновесных стационарных поведений в эргоднческом случае стохастических игр с полной информацией. Алгоритм оказался полгаюмиалышм по числу состояний ■ системы и длине двоичного представления стоимостной фуш'цш.

Результаты диссертации опубликованы в работах :

1. Гурвич В.А., Лебедев В.И. Критерий и проверка эргодичности

шаровых форм / Успехи Математических Наук 1989, » I

2. Лебедев В.Н. Полиномиальный алгоритм нахождения оптимальных стратегий в одной игре двух лиц с полной информацией и предельным во времени платежом // Моделирование процессов управления и обработки информации, - М, - 1989

3, Конечный алгоритм определения цен в циклических ьгрях с отказами / Лейядоп П.Н., МФТИ - М, 19ЭО - Дои. в ВИНИТИ, 13.08.90 * 4 Г, 30 П 30

■1. KerraiDv л.V., I.ebodev V.N. Cyclical game в with prohibitions // Поп. Пер., шло ARTEMIS, Grenoble, 1990

'ViV.." . i'ZTiVtl..... гхи г ;; /iffJ.... Тираж.