Реферат Курсовая Конспект
Динамическое программирование при моделировании в сетях. - раздел Образование, Учебное издание: Моделирование технических систем и процессов При Моделировании Сетевых Структур Помимо Задач, Связанных С ...
|
При моделировании сетевых структур помимо задач, связанных с существованием потоков в транспортных, электрических, телефонных, компьютерных и прочих видах сетей, возникает целый класс задач, сводимых к задаче о кратчайшем пути. Задача о кратчайшем пути в ориентированной сети является типичной задачей динамического программирования.
Понятие динамического программирования тесно связано с многошаговыми процессами принятия решений. Многошаговый процесс принятия решений можно определить, как процесс принятия последовательных решений, направленных на достижение заданной цели. Многошаговые процессы принятия решений постоянно встречаются в самых различных ситуациях, от приготовления обеда до управления космическим аппаратом.
Динамическое программирование можно приблизительно определить, как набор математических процедур, используемых при анализе многошаговых процессов принятия решений. Каждый многошаговый процесс принятия решений представляет собой развитие следующей задачи: найти кратчайший путь в направленной, ациклической сети.
Динамическое программирование можно рассматривать как единую теорию благодаря единому набору идей и приемов, которые используются при математическом анализе различных задач. Эти идеи и приемы и составляют сущность динамического программирования. Беллман одним из первых понял суть принципа оптимальности и стал применять его ко многим оптимизационным задачам, возникающих в математике, технике, исследовании операций и в других областях.
Таким образом, понятие динамического программирования связано с многошаговым процессом принятия решений для достижения определенной цели. Например, перевод летательного аппарата с одной орбиты на другую представляет собой задачу динамического программирования, при условии, если коррекция орбиты осуществляется приложением импульса в дискретные моменты времени, а целью является экономия топлива.
Характеризуя динамическое программирование, как набор математических процедур для оптимального управления дискретной системой, в общем виде задачу оптимального управления можно сформулировать следующим образом. В дискретные моменты времени t = 1, 2,..., N система находится в одном из множеств si состояний, характеризуемых вектором состояния x(t). Переход между последовательными состояниями осуществляется с помощью вектора управления u(t) по закону:
x(t) = g(t) (x(t) , u(t) ) ; t = 1, 2,..., N
Управления u(t) выбираются из множества допустимых управлений и образуют последовательность допустимых управлений u(0),u(1),…,u(N). Последовательность допустимых управлений при заданном начальном состоянии х(0) определяет траекторию системы х(0) ,х(1) ,х(2) ,…,х(N).
Всякой траектории соответствует свое значение критерия оптимальности F , или целевой функции управления, слагающегося из отдельных вкладов на каждом этапе управления:
.
Задачa оптимального управления заключается в нахождении среди множества последовательностей управления такой, которая достигает минимального значения F. Такая последовательность называется оптимальной последовательностью управлений и определяет оптимальную траекторию.
В основе динамического программирования лежит принцип оптимальности Беллмана, который можно сформулировать так. Оптимальная стратегия обладает таким свойством, что каково бы ни было начальное состояние и решение в начальный момент, последующие решения должны формулировать оптимальную стратегию относительно состояния, возникающего после начального решения.
Смысл принципа оптимальности становится ясней, если учесть, что для оптимальной траектории каждый ее участок между конечной точкой и любой промежуточной также является оптимальной траекторией. Принцип оптимальности, или иначе метод динамического программирования, позволяет отыскать оптимальную многошаговую стратегию путем решения совокупности более простых одношаговых оптимизационных задач.
Метод динамического программирования хорошо иллюстрируется на примере поиска кратчайшего пути между крайними узлами ориентированной сети. Рассмотрим некоторую ориентированную сеть, насчитывающую 12 узлов, которую нужно пройти от начального узла (1) до конечного узла (12) за четыре шага, передвигаясь с каждым шагом от узла к узлу.
Числа при дугах (i,j) равны длинам дуг lij между узлами i и j , в условных единицах. Возможные состояния системы si связаны с нахождением в i-м узле, управление u(t) связано с выбором пути на каждом шаге управления. Четыре шага управления u(1),...,u(4) последовательно переводят систему из начального состояния s1 в конечное состояние s12 и таким образом образуют некоторую траекторию. Критерием оптимальности F в данном случае выступает длина траектории, слагающаяся из длин дуг:
.
Если поиски кратчайшего пути, т. е. оптимальной траектории, начинать не с начала, а с конца сети и двигаться в обратном направлении к началу, то в этом случае мы имеем алгоритм «обратной прогонки». В данном случае если реализовать алгоритм обратной прогонки, то движение осуществляется от конечного состояния s12 к начальному состоянию s1.
Вначале поиска кратчайшего пути составляется таблица переходов. Число строк таблицы равно числу шагов управления, число столбцов равно числу состояний минус один. В этой таблице будут храниться шаги управления и соответствующие им значения критерия оптимальности Lt для всех возможных состояний системы после каждого шага.
Таблица 3
i t | s1 | s2 | s3 | s4 | s5 | s6 | s7 | s8 | s9 | s10 | s11 |
12 | 12 6 | ||||||||||
10 | 11 10 | ||||||||||
5 | |||||||||||
1 |
Заполненные клетки таблицы разбиты пополам. В верхнюю часть заполненной клетки заносится управление u(t) , т. е. в данном случае номер узла, в который осуществляется переход. В нижнюю часть заполненной клетки заносится то значение вклада Lt в общее значение критерия оптимальности L , которое было получено при переходеиз соответствующего этой клетке узла в конечный узел.
Заполнение Табл. 3 начинается с первой строки, где хранится информация о последнем шаге пути. Последний, в данном случае четвертый шаг пути определен однозначно при переходе из любого предпоследнего состояния, которым может быть любое из трех возможных: s9, s10, s11. Поэтому оптимальное управление на последнем шаге очевидно. В зависимости от предпоследнего состояния вклад в критерий оптимальности L4(9) = 12, L4(10) = 6, либо L4(11) = 7. Эти значения вклада в L записываются в нижней части клеток первой строки табл. 3.
Перед предпоследним – в данном случае третьим - шагом множество возможных состояний системы есть {s5, s6, s7, s8}. Применим теперь принцип Беллмана для определения траектории на третьем и четвертом шаге. Он заключается в том, что независимо от первых двух шагов управления отрезок траектории на последних двух шагах сам по себе является оптимальной траекторией, т.е. дает минимум вклада L3 в критерий оптимальности.
Если состояние системы перед предпоследним шагом есть состояние s8 , то на последних шагах вклад в L определяется соотношением
L3(s5)=min{}.
Поскольку из s5 возможны переходы в s9 и s11 .т.е.
g(s5,9) = s9; ; L4(s9) = 12,
g(s5,11) = s11; ; L4(s11) = 7,
то
L3(s5) = min{6+12, 4+7} = 11 и u(3) = 11.
Это значит, что если система находится в состоянии s5, то оптимальное управление заключается сначала в переходе в состояние s11, затем в состояние s12 . Длина дуги из s5 в s12 при этом оказывается равна 11 единиц.
Рассчитывая вклад в L аналогично для переходов из состояний s6, s7, s8, получим:
L3(s6)=min{7+12, 6+6)=12 , u(3)=10;
L3(s7)=min{5+6, 3+7)=10, u(3)=11;
L3(s8)=min{10+6, 12+7)=16, u(3)=10;
Полученные четыре пары чисел
записываются во вторую строку Табл. 3.
На втором шаге управления вклад в критерий оптимальности в зависимости от исходного состояния есть
L2(s2) = min{} = min{11+11, 14+10} = 22, u(2) = 5;
L2(s3) = min{} = min{7+11, 9+12} = 18, u(2) = 5;
L2(s4) = min{} = min{2+16, 3+12, 6+10} = 15, u(2) = 6;
Полученные три пары чисел записываются в третью строку Табл.3.
Начальное состояние s1 определено однозначно, поэтому в последней строке таблицы заполняется единственная клетка, куда носятся значения 3 и 24 поскольку:
L1(s1) = min{} = min{5+22, 6+18, 11+15} = 24, u(1) = 3.
Теперь можно окончательно определить оптимальное многошаговое управление. На первом шаге u(1) = 3, т.е. из узла 1 переходим в узел 3, на втором шаге u(2) = 5, т.е. переходим в узел 5, далее после управления u(3) = 11 - в узел 11 и, наконец, в узел 12. Окончательно получаем, что кратчайший путь проходит по последовательности состояний s1→s2→s5→s11→s12 , а его протяженность составляет 24 условных единиц.
Поиск кратчайшего пути можно также осуществлять из начала сети, реализуя при этом алгоритм прямой прогонки, который выполняет в сущности те же операции сложения и сравнения, но в несколько иной последовательности.
В алгоритмах прямой и обратной прогонки, хотя и отличных по существу, предусматривается одно сложение и одно сравнение на каждую дугу. Следовательно, оба алгоритма обладают одинаковым быстродействием. Тем не менее, существует важное различие. В алгоритме прямой прогонки рассматриваются дуги, исходящие из тех узлов, кратчайшие пути li до которых уже известны.
В алгоритме обратной прогонки рассматриваются дуги, входящие в те узлы, кратчайшие пути lj до которых ещё неизвестны. В силу последнего обстоятельства предпочтение чаще отдаётся алгоритму прямой прогонки. Этот алгоритм можно применять при любой структуре множества кратчайших путей.
Решение простой задачи о кратчайшем пути иллюстрирует ряд следующих характерных особенностей, которые присущи значительно более сложным многошаговым процессам принятия решений:
1. Исходная задача погружается во множество оптимизационных задач; при этом для каждого узла решается своя задача.
2. Множество решений оптимизационных задач описывается функциональным уравнением, представляющим собой систему уравнений, которые связывают несколько оптимизационных задач. В такой системе каждое уравнение соответствует одному узлу и содержит обычно операторы типа min, mах или minimax справа от знака равенства, а переменные типа gi, и gj - по обе стороны от него.
3. Решение множества оптимизационных задач можно найти с помощью алгоритма обратной прогонки, который равнозначен упорядоченной процедуре решения последовательности функциональных уравнений.
Динамическое программирование хорошо подходит для решения проблем, связанных с моделированием сетевых систем, не обладающих специальной структурой. Так, алгоритмы прямой и обратной прогонки пригодны для проведения вычислений в ациклических сетях. Алгоритм обратной прогонки можно обобщить и использовать для решения задач, в которых есть элемент случайности. Для алгоритма прямой прогонки это нельзя сделать.
Понятие «состояние» играет центральную роль в динамическом программировании, при этом под состояниями понимается следующее. Переход осуществляется из состояния в состояние, заключающее в себе всю предысторию процесса, т. е. состояние описано с той степенью подробности, которая позволяет провести вычисление (оценку) текущих альтернативных решении.
Для сетевой модели состояниями являются узлы, а дуги, выходящие из некоторого узла, отображают различные решения, которые можно принимать в данном узле (состоянии). При таком толковании можно говорить, что переход происходит из состояния в состояние, а состояния представляют собой точки, в которых принимаются решения. Приведенное утверждение означает, что дуги, выходящие из узла, не имеют никакого отношения к тому, каким путём был достигнут тот или иной узел, т. е. не зависят от входящих дуг.
Элементы состояния часто называют переменными состояния. В моделях динамического программирования состояния иногда группируются в стадии, и переход осуществляется от одной стадии к другой. Например, в задаче о кратчайшем пути имеются состояния, но нет стадий, так как нельзя сгруппировать состояния в множества таким образом, чтобы происходил переход от одного множества к другому.
Погружение во множество оптимизационных задач равносильно введению понятия пространство состояний, которое представляет собой множество состояний. В функциональном уравнении оптимальный отклик рассматривается как функция стартового состояния, а принцип оптимальности устанавливает взаимосвязь между оптимальными откликами для различных стартовых состояний.
Множество S возможных (или наблюдаемых) состояний называется пространством состояний, а элемент s из S определяет конкретное состояние. С каждым состоянием s связано множество D(s) . Элемент d из множества D(s) называется решением. Стратегия d представляет собой правило, согласно которому определяется допустимое решение для каждого состояния.
Фактически стратегия d ставит в соответствие каждому состоянию s некоторый элемент d(s) из множества D(s). Набор всех таких d образует пространство стратегий D. Последнее означает, что выбор решения в некотором состоянии не ограничивает выбор во всех других состояниях. По существу, D представляет собой декартово произведение множеств D(s) по s.
Одна из идей динамического программирования состоит в том, каждой стратегии d должна соответствовать так называемая функция прибыли Vd(s), которую можно получить, исходя из состояния s и используя стратегию d. Понятие функции прибыли, или функции дохода, или функции вознаграждения обобщает понятие вклада Lt в общее значение критерия оптимальности L , рассматриваемое при решении задачи о кратчайшем пути.
Выражение «используя стратегию d» означает, что в состоянии s выбирается решение d(s); затем предполагается, что процесс перешел в состояние s' , т. е. реализуется состояние s', в котором выбирается решение d(s'), и т. д. Функция прибыли имеет довольно сложную структуру, поскольку она зависит от последовательности состояний и решений, от вознаграждений, которые связаны с этими состояниями и решениями, а также от способа агрегирования вознаграждений.
Для марковской модели принятия решений состояние s определяется некоторой парой чисел (n , i) , решением является зависящая от них функция k, а локальная функция дохода определяется выражением типа h[(n, I) , k, v] = Rki(n) + åjPkij(n)v(n+1,j) (n<N). Это выражение представляет собой математическое ожидание, поскольку конечное вознаграждение v (n + 1, j) умножается на вероятность перехода в данное состояние и берется сумма по всем j.
Состояние представляет собой описание предыстории процесса со степенью подробности, позволяющей провести вычисление (оценку) текущих альтернативных решений. Основным свойством состояний является то, что состояние является краткой записью предыстории процесса, причем степень детализации позволяет определить локальную функцию дохода. Иными словами, локальная функция дохода может зависеть лишь от s, d и v.
В Марковской модели принятия решений в условиях неопределенности имеется конечное множество состояний, которые для удобства пронумерованы числами от 1 до т. Для каждого состояния задан конечный набор решений, связанных с данным состоянием. В этой модели локальная функция дохода имеет вид: h( I , k , v) = Rki + c åj=1 m Pkij vj .
В Марковской модели решения принимаются в периоды 0, 1, 2, и т. д. до бесконечности. Периоды представляют собой равные промежутки времени. Если в период n наблюдается состояние I и выбрано решение k , то из локальной функции дохода следует, что вознаграждение Rki получается сразу, а также, что вероятность перехода в состояние j в период (n + 1) равна Рkij . Процесс принятия решений начинается в нулевой (начальный) период и может продолжаться бесконечно, поскольку не имеет того «конца», от которого начинается алгоритм обратной прогонки.
В Марковской модели стратегия d определяет решение d(i) для состояния I . Вознаграждения, получаемые при стратегии d , можно выразить с помощью m - мерного вектора Rd , а вероятности переходов можно записать в виде матрицы переходных вероятностей Рd размера т X т : (Rd)i = Rd(i)I ; (Pd)ij = Pd(i)ij.
Марковские модели принятия решений обобщаются в разных направлениях, в частности, на случай Марковских задач о восстановлении. Наиболее полезное обобщение получается, когда рассматриваются неравные или переменные времена переходов. В простых моделях предполагается, что переход из состояния в состояние и наблюдение состояния осуществляются мгновенно, а отрезок времени между переходами из состояния в состояние может иметь переменную или случайную длину.
Всякий раз, когда наблюдается некоторое состояние, выбирается решение, которое уже нельзя изменять до тех пор, пока процесс не перейдет в новое состояние, где выбирается новое решение, и т. д. Данная модель представляет собой комбинацию теории марковских цепей и теории восстановления; обычно ее называют Марковской задачей о восстановлении.
– Конец работы –
Эта тема принадлежит разделу:
ББК... Рецензент член УМС Си РУМЦ по информатике и вычислительной технике доктор физико математических наук профессор зав кафедрой моделирования и оптимизации...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Динамическое программирование при моделировании в сетях.
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов