Динамическое программирование при моделировании в сетях.

 

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

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

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

Динамическое программирование можно рассматривать как единую теорию благодаря единому набору идей и приемов, которые используются при математическом анализе различных задач. Эти идеи и приемы и составляют сущность динамического программи­рования. Беллман одним из первых понял суть принципа оптимальности и стал применять его ко многим оптимизационным задачам, возникающих в математике, технике, исследовании операций и в других областях.

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

Характеризуя динамическое программирование, как набор математических процедур для оптимального управления дискретной системой, в общем виде задачу оптимального управления можно сформулировать следующим образом. В дискретные моменты времени t = 1, 2,..., N система находится в одном из множеств s_i состояний, характеризуемых вектором состояния x^(t). Переход между последовательными состояниями осуществляется с помощью вектора управления u^(t) по закону:

 

x^(t) = g^(t) (x^(t) , u^(t) ) ; t = 1, 2,..., N

 

Управления u^(t) выбираются из множества допустимых управлений и образуют последовательность допустимых управлений u⁽⁰⁾,u⁽¹⁾,…,u^(N). Последовательность допустимых управлений при заданном начальном состоянии х⁽⁰⁾ определяет траекторию системы х⁽⁰⁾ ,х⁽¹⁾ ,х⁽²⁾ ,…,х^(N).

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

 

.

 

Задачa оптимального управления заключается в нахождении среди множества последовательностей управления такой, которая достигает минимального значения F. Такая последовательность называется оптимальной последовательностью управлений и определяет оптимальную траекторию.

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

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

Метод динамического программирования хорошо иллюстрируется на примере поиска кратчайшего пути между крайними узлами ориентированной сети. Рассмотрим некоторую ориентированную сеть, насчитывающую 12 узлов, которую нужно пройти от начального узла (1) до конечного узла (12) за четыре шага, передвигаясь с каждым шагом от узла к узлу.

 

 

 

 

Числа при дугах (i,j) равны длинам дуг l_ij между узлами i и j , в условных единицах. Возможные состояния системы s_i связаны с нахождением в i-м узле, управление u^(t) связано с выбором пути на каждом шаге управления. Четыре шага управления u⁽¹⁾,...,u⁽⁴⁾ последовательно переводят систему из начального состояния s₁ в конечное состояние s₁₂ и таким образом образуют некоторую траекторию. Критерием оптимальности F в данном случае выступает длина траектории, слагающаяся из длин дуг:

 

.

 

Если поиски кратчайшего пути, т. е. оптимальной траектории, начинать не с начала, а с конца сети и двигаться в обратном направлении к началу, то в этом случае мы имеем алгоритм «обратной прогонки». В данном случае если реализовать алгоритм обратной прогонки, то движение осуществляется от конечного состояния s₁₂ к начальному состоянию s₁.

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

 

Таблица 3

i t	s1	s2	s3	s4	s5	s6	s7	s8	s9	s10	s11
									12	12 6
						10	11 10
			5
1

 

Заполненные клетки таблицы разбиты пополам. В верхнюю часть заполненной клетки заносится управление u^(t) , т. е. в данном случае номер узла, в который осуществляется переход. В нижнюю часть заполненной клетки заносится то значение вклада L_t в общее значение критерия оптимальности L , которое было получено при переходеиз соответствующего этой клетке узла в конечный узел.

Заполнение Табл. 3 начинается с первой строки, где хранится информация о последнем шаге пути. Последний, в данном случае четвертый шаг пути определен однозначно при переходе из любого предпоследнего состояния, которым может быть любое из трех возможных: s₉, s₁₀, s₁₁. Поэтому оптимальное управление на последнем шаге очевидно. В зависимости от предпоследнего состояния вклад в критерий оптимальности L₄(9) = 12, L₄(10) = 6, либо L₄(11) = 7. Эти значения вклада в L записываются в нижней части клеток первой строки табл. 3.

Перед предпоследним – в данном случае третьим - шагом множество возможных состояний системы есть {s₅, s₆, s₇, s₈}. Применим теперь принцип Беллмана для определения траектории на третьем и четвертом шаге. Он заключается в том, что независимо от первых двух шагов управления отрезок траектории на последних двух шагах сам по себе является оптимальной траекторией, т.е. дает минимум вклада L₃ в критерий оптимальности.

Если состояние системы перед предпоследним шагом есть состояние s₈ , то на последних шагах вклад в L определяется соотношением

 

L₃(s₅)=min{}.

 

Поскольку из s₅ возможны переходы в s₉ и s₁₁ .т.е.

 

g(s₅,9) = s₉; ; L₄(s₉) = 12,

g(s₅,11) = s₁₁; ; L₄(s₁₁) = 7,

то

L₃(s₅) = min{6+12, 4+7} = 11 и u⁽³⁾ = 11.

 

Это значит, что если система находится в состоянии s₅, то оптимальное управление заключается сначала в переходе в состояние s₁₁, затем в состояние s₁₂ . Длина дуги из s₅ в s₁₂ при этом оказывается равна 11 единиц.

Рассчитывая вклад в L аналогично для переходов из состояний s₆, s₇, s₈, получим:

 

L₃(s₆)=min{7+12, 6+6)=12 , u⁽³⁾=10;

L₃(s₇)=min{5+6, 3+7)=10, u⁽³⁾=11;

L₃(s₈)=min{10+6, 12+7)=16, u⁽³⁾=10;

 

 

Полученные четыре пары чисел

записываются во вторую строку Табл. 3.

На втором шаге управления вклад в критерий оптимальности в зависимости от исходного состояния есть

 

L₂(s₂) = min{} = min{11+11, 14+10} = 22, u⁽²⁾ = 5;

L₂(s₃) = min{} = min{7+11, 9+12} = 18, u⁽²⁾ = 5;

L₂(s₄) = min{} = min{2+16, 3+12, 6+10} = 15, u⁽²⁾ = 6;

 

Полученные три пары чисел записываются в третью строку Табл.3.

Начальное состояние s₁ определено однозначно, поэтому в последней строке таблицы заполняется единственная клетка, куда носятся значения 3 и 24 поскольку:

 

L₁(s₁) = min{} = min{5+22, 6+18, 11+15} = 24, u⁽¹⁾ = 3.

 

Теперь можно окончательно определить оптимальное многошаговое управление. На первом шаге u⁽¹⁾ = 3, т.е. из узла 1 переходим в узел 3, на втором шаге u⁽²⁾ = 5, т.е. переходим в узел 5, далее после управления u⁽³⁾ = 11 - в узел 11 и, наконец, в узел 12. Окончательно получаем, что кратчайший путь проходит по последовательности состояний s₁→s₂→s₅→s₁₁→s₁₂ , а его протяженность составляет 24 условных единиц.

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

В алгоритмах прямой и обратной прогонки, хотя и отличных по существу, предусматривается одно сложение и одно сравнение на каждую дугу. Следовательно, оба алгоритма обладают одина­ковым быстродействием. Тем не менее, существует важное различие. В алгоритме прямой прогонки рассматри­ваются дуги, исходящие из тех узлов, кратчайшие пути l_i до которых уже известны.

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

Решение простой задачи о кратчайшем пути иллюстрирует ряд следующих характерных особенностей, которые присущи значительно более сложным мно­гошаговым процессам принятия решений:

1. Исходная задача погружается во множество оптимизационных задач; при этом для каждого узла решается своя задача.

2. Множество решений оптимизационных задач описывается функциональным уравнением, представляющим собой систему уравнений, которые связывают несколько оптимизационных задач. В такой системе каждое уравнение соответствует одному узлу и содержит обычно операторы типа min, mах или minimax справа от знака равенства, а переменные типа g_i, и g_j - по обе стороны от него.

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

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

Понятие «состояние» играет центральную роль в динамическом программировании, при этом под состояниями пони­мается следующее. Переход осуществляется из состояния в состояние, заключающее в себе всю предысторию процесса, т. е. состояние описано с той степенью подробности, которая позволяет провести вычисление (оценку) текущих альтернативных решении.

Для сетевой модели состояниями являются узлы, а дуги, выходящие из некоторого узла, отображают различные решения, которые можно принимать в данном узле (состоянии). При таком толковании можно говорить, что переход происходит из состояния в состояние, а состояния представляют собой точки, в которых принимаются решения. Приведенное утверждение означает, что дуги, выходя­щие из узла, не имеют никакого отношения к тому, каким путём был достигнут тот или иной узел, т. е. не зависят от входящих дуг.

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

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

Множество S возможных (или наблюдаемых) состояний назы­вается пространством состояний, а элемент s из S определяет конкретное состояние. С каждым состоянием s связано множество D(s) . Элемент d из множества D(s) называется решением. Стратегия d представляет собой правило, согласно которому определяется допустимое решение для каждого состояния.

Фактически страте­гия d ставит в соответствие каждому состоянию s некоторый эле­мент d(s) из множества D(s). Набор всех таких d образует про­странство стратегий D. Последнее означает, что выбор решения в некотором состоянии не ограничивает выбор во всех других состояниях. По существу, D представляет собой декартово произведение множеств D(s) по s.

Одна из идей динамического программирования состоит в том, каждой стратегии d должна соответствовать так называемая функция прибы­ли V^d(s), которую можно получить, исходя из состояния s и используя стратегию d. Понятие функции прибы­ли, или функции дохода, или функции вознаграждения обобщает понятие вклада L_t в общее значение критерия оптимальности L , рассматриваемое при решении задачи о кратчайшем пути.

Выражение «используя стратегию d» означает, что в состоянии s выбирается решение d(s); затем предполагается, что процесс перешел в состояние s' , т. е. реализуется состояние s', в котором выбирается решение d(s'), и т. д. Функция прибыли имеет доволь­но сложную структуру, поскольку она зависит от последователь­ности состояний и решений, от вознаграждений, которые связаны с этими состояниями и решениями, а также от способа агрегиро­вания вознаграждений.

Для марковской модели принятия решений состояние s определяется некоторой парой чисел (n , i) , решением является зависящая от них функция k, а локальная функция дохода определяется выражением типа h[(n, I) , k, v] = R^k_i(n) + å_jP^k_ij(n)v(n+1,j) (n<N). Это выражение представляет собой математическое ожидание, поскольку конечное вознаграждение v (n + 1, j) умно­жается на вероятность перехода в данное состояние и берется сумма по всем j.

Состояние представляет собой описание предыстории процесса со степенью подробности, позволяющей провести вычисление (оценку) текущих альтернативных решений. Основным свойством состояний является то, что состояние является краткой записью предыстории процесса, причем степень детализации позволяет определить локальную функцию дохода. Иными словами, локальная функция дохода может зависеть лишь от s, d и v.

В Марковской модели принятия решений в условиях неопределен­ности имеется конечное множество состояний, которые для удобства пронумерованы числами от 1 до т. Для каждого состояния задан конечный набор решений, связанных с данным состоянием. В этой модели локальная функция дохода имеет вид: h( I , k , v) = R^k_i + c å_j=1 ^m P^k_ij v_j .

В Марковской модели решения принимаются в периоды 0, 1, 2, и т. д. до бесконечности. Периоды представляют собой равные промежутки времени. Если в период n наблюдается состояние I и выбрано решение k , то из локальной функции дохода следу­ет, что вознаграждение R^k_i получается сразу, а также, что вероят­ность перехода в состояние j в период (n + 1) равна Р^k_ij . Процесс принятия решений начинается в нулевой (начальный) период и может продолжаться бесконечно, поскольку не имеет того «конца», от которого начинается алгоритм обратной прогонки.

В Марковской модели стратегия d определяет решение d(i) для состояния I . Воз­награждения, получаемые при стратегии d , можно выразить с помощью m - мерного вектора R^d , а вероятности переходов можно записать в виде матрицы переходных вероятностей Р^d размера т X т : (R^d)_i = R^d(i)_{I ;} (P^d)_ij = P^d(i)_ij.

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

Всякий раз, когда наблюдается некоторое состояние, выбирается реше­ние, которое уже нельзя изменять до тех пор, пока процесс не перейдет в новое состояние, где выбирается новое решение, и т. д. Данная модель представляет собой комбинацию теории марков­ских цепей и теории восстановления; обычно ее называют Мар­ковской задачей о восстановлении.