9901

Динамическое программирование

Реферат

Информатика, кибернетика и программирование

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

Русский

2013-03-18

224 KB

112 чел.

Динамическое программирование

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

=  + F(x1, t1), x' = f(x(t), u(t), t),

x(t0) = x0, x(t1) = x1, {u(t)}U.      (1)

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

Вслед за этим, как частный случай, определяется и решение данной конкретной задачи.


Принцип оптимальности и уравнение Беллмана

Формулировка принципа оптимальности:

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

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

  x (фазовая координата)

x(t1)        x*(t)

    2

x()

    1

x(t0)

    t0                t1  t (время)

На рисунке дана иллюстрация принципа на примере задачи с одной фазовой координатой. Кривая x*(t) (t0tt1) – это фазовая траектория, соответствующая оптимальному управлению, начальное и конечное состояния – фиксированы. Вся траектория поделена на две части относительно момента времени . Согласно принципу оптимальности, траектория 2, определенная при tt1, должна представлять собой оптимальную траекторию по отношению к начальному состоянию x(). Следовательно, вторая часть оптимальной траектории сама по себе должна быть оптимальной траекторией, вне зависимости от того, что происходило с системой до того, как она пришла к состоянию, являющемуся начальным для второй части траектории.

Предположим, что общая задача управления (1) имеет решение.

Максимальное значение целевого функционала задачи с начальным состоянием  x  и начальным временем t 

J*(x, t)

назовем функцией оптимального поведения.

Отметим, что в то время как J представляет собой функционал, зависящий от {u(t)}, J* является функцией, зависящей от n+1 параметров x и t.

Таким образом, задача оказывается "погруженной" в более широкий класс задач, характеризуемых значениями n+1 начальных параметров. Оптимальной значение целевой функции исходной задачи (1) имеет, таким образом, вид

J* = J*(x0, t0).

Если J*(x, t) является функцией оптимального поведения для задачи с начальным состоянием x в момент t, то, согласно принципу оптимальности J*(x+x, t+t) является функцией оптимального поведения для второй части оптимальной траектории с начальным моментом времени t+t и начальным состоянием x+x. Поскольку прирост функции оптимального поведения на протяжении всего промежутка времени между t и t+t может происходить только за счет изменения подынтегральной функции, то он равен I(x,u,t)t. Значения функции оптимального поведения на всем интервале времени, начавшимся в момент t, представляют собой оптимальную сумму вкладов двух частей этого интервала времени. Таким образом, приходим к основному рекуррентному соотношению

J*(x, t) = {I(x, u, t)t  + J*(x+x, t+t)} (2)

В динамическом программировании существенную роль играет предположение, что функция оптимального поведения J*(x, t) представляет собой однозначную и непрерывно дифференцируемую функцию от n+1 переменных. Иначе говоря, решения задач более широкого класса являются однозначными и непрерывными функциями относительно изменений начальных параметров. (Отметим, что во многих задачах эти предположения о гладкости не выполняются, кроме того, заранее вообще неизвестно, будут ли они выполнены в данной конкретной задаче).

Благодаря этому предположению можно разложить J*(x+x, t+t) в точке (x, t) по формуле Тейлора:

J*(x+x, t+t) = J*(x, t) + x + t + …  (3)

где  - это вектор-строка

= (, , …, ).

Подставляя (3) в (2) и проводя элементарные преобразования, получаем

0 = {I(x, u, t) +   +  + … }.

Переходя к пределу при t  0 с учетом того, что

= x' = f(x, u, t),

получаем

-  = {I(x, u, t) + f(x, u, t)}. (4)

Уравнение (4) называется уравнением Беллмана и является основным дифференциальным уравнением в частных производных, используемых в динамическом программировании.

Так как второе слагаемое в (4) представляет собой скалярное произведение вектора-строки  и вектора-столбца f(x, u, t), то уравнение Беллмана можно записать как

-  = {I(x, u, t) +fj(x, u, t)}.

С уравнением Беллмана связано в качестве граничного условия ограничение, налагаемое на конечное состояние:

J*(x(t1), t1) = F(x1, t1).

Это условие показывает, что значение функции оптимального поведения для задачи, начальным моментом и начальным состоянием которой являются соответственно конечный момент и конечное состояние, равно значению функции F, рассчитанному в данный момент времени при данном состоянии.

Если бы уравнение Беллмана было решено, то мы получили бы функцию оптимального поведения и, следовательно, оптимальное значение целевой функции для исходной задачи можно было бы определить как частное значение этой функции при указанных в формулировке задачи конкретных начальных условиях. Однако в общем случае это уравнение в частных производных первого порядка, как правило, нелинейное, не имеет аналитического решения. В принципе можно решать уравнения Беллмана, представленные в виде разностных схем, на ЭВМ с большим быстродействием. Однако даже современные ЭВМ, работающие с высокой скоростью счета, не обладают такой машинной памятью, которая позволяла бы найти достаточно хорошее приближение к решению даже при не очень больших размерностях. Беллман назвал это препятствие "проклятьем размерности" ("curse of dimensionality").


Решение многошаговых задач оптимизации методом

динамического программирования

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

Рассмотрим некоторую динамическую систему S.

Пусть на k-м шаге (k = 1, 2, ..., n) состояние системы определяется совокупностью чисел (фазовыми координатами)  X =( ), которые получены в результате реализации управления Uk, обеспечивающего переход системы S из состояния X в состояние X . Будем полагать, что X зависит от X и Uk и не зависит от того, как система пришла в состояние X (свойство отсутствия последействия).

Пусть Wk(X , Uk) есть доход (выигрыш), полученный в результате реализации k-го шага. Тогда общий выигрыш полагаем равным

 F = Wk(X , Uk)

(свойство аддитивности целевой функции).

Совокупность управлений U = ( , , ... , ), в результате реализации которых система S переходит за n шагов из начального состояния X0 в конечное X и при этом функция F принимает наибольшее значение, будем называть оптимальной стратегией управления.

Принцип оптимальности Беллмана.

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

Оптимальную стратегию можно получить, если сначала найти оптимальную стратегию управления на последнем n-м шаге, за тем на двух последних шагах и т.д. вплоть до первого шага.

Таким образом, решение задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем n-м шаге.

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

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

Обозначим через Fn(X0) максимальный доход, получаемый за n шагов при переходе системы S из начального состояния X0 в конечное состояние X , а через Fn-k (X ) - то же при переходе из X  в X  и оптимальном управлении на последних n-k шагах.

Тогда  

Fn(X0) = [W1(X0, U1) + W2(X1, U2) + ... + Wn(X , Un)],

Fn-k(X0) = [Wk+1(X , Uk+1) + Fn-k-1(X )],

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

Положим  k = n - 1. Тогда

 

F1(X ) = [Wn(X , Un) + F0(X )],   (*)

где F0(X ) считаем известным.

Используя (*) и рассматривая всевозможные допустимые состояния X , X , ... , X , ... , системы на (n-1)-м шаге находим условно-оптимальные управления (X ), (X ), ... , (X ), ... , и соответствующие значения функции (*):

(X ), (X ),..., (X ), ... .

Таким образом, на n-м шаге находим условно-оптимальное управление при любом допустимом состоянии системы после (n-1)-го шага. Т.е., в каком бы состоянии система не оказалась после (n+1)-го шага, нам уже известно, какое следует принять решение на n-м шаге. Известно и соответствующее значение функции (*).

Переходим к рассмотрению функционального уравнения при k = n - 2.

F2(X ) = [Wn-1(X , Un-1) + F1(X )],  (**)

Для того, чтобы найти значение F2 для всех допустимых значений X , очевидно, необходимо знать Wn-1(X , Un-1) и F1(X ). Но F1(X ) мы уже определили на предыдущем шаге. Поэтому нужно произвести вычисления для Wn-1(X , Un-1) при некотором наборе допустимых значений X  и соответствующих управлений Un-2. Эти вычисления позволят определить условно оптимальное управление U для каждого X . Каждое из таких управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах.

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

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

Чтобы найти оптимальную стратегию управления, то есть определить искомое решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. А именно - на первом шаге в качестве оптимального управления возьмем найденное условно оптимальное управление U . На втором шаге найдем состояние X , в которое переводит систему управление . Это состояние определяет условно оптимальное управление U (X ), которое теперь будем считать оптимальным ( ). Зная , находим X  = (X ), а значит - определяем = U (X ), и т.д. В результате этого находим решение задачи, то есть максимально возможный доход и оптимальную стратегию управления U*, включающую оптимальные управления на отдельных шагах ( , , ... , ).

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


Задача о минимизации расхода горючего самолетом

при наборе высоты и скорости 

Пусть самолет, находящийся на высоте Н0 и имеющий скорость V0 должен подняться на высоту Нk н иметь скорость Vk. Известен расход горючего при подъеме самолета с любой высоты H1 на любую высоту Н2 > Н1 при постоянной скорости, а также расход горючего при увеличении скорости от любого значения V1 до любого значения V2 > V1 при неизменной высоте.

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

Из условия следует, что состояние физической системы S (самолета) характеризуется двумя параметрами: скоростью V и высотой Н. Поэтому решение будем искать на плоскости VOH, а точнее на ограниченном прямыми V=V0, V=Vk и Н=Н0, Н=Hk прямоугольнике, который и является областью допустимых состояний. Начальное S0(V0, Н0) и конечное Sk(Vk, Hk) состояния вполне определены, как две точки S0 и Sk на плоскости (см. рисунок).







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

Классическая задача вариационного исчисления является частным случаем задачи динамического программирования, в которой управляющими параметрами являются скорости изменения фазовых координат во времени, причем на значения управляющих параметров не накладывается никаких ограничений. Из необходимого условия динамического программирования – выполнения уравнения Беллмана – выводятся необходимые условия вариационного исчисления – уравнения Эйлера, Лежандра, условие Вейерштрасса и условия Вейерштрасса-Эрдмана для точки излома.

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

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

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

Кроме того, при численном определении оптимальных управлений эти два метода представляют собой весьма различные подходы к динамической задаче оптимизации: динамическое программирование приводит к нелинейному дифференциальному уравнению в частных производных, а принцип максимума – к двум системам обыкновенных дифференциальных уравнений.

Принцип максимума оказывается часто более плодотворным, поскольку он, по существу, разбивает решение уравнения Беллмана на два шага: на первом шаге оптимальные управления определяются как функции сопряженных переменных, а на втором сопряженные переменные определяются как функции времени. Первый шаг обычно не вызывает затруднений; он часто позволяет увидеть свойства решения, а это может подсказать и способ решения задачи. Второй шаг оказывается более трудным, так как приходится решать двухточечную граничную задачу. С другой стороны, в динамическом программировании оба эти шага требуется осуществить одновременно, решая уравнение Беллмана. Поэтому при аналитическом решении подход принципа максимума обычно более полезен, чем подход динамического программирования. Однако при численном решении оба метода приводят к сходным компьютерным программам и к тем же проблемам, связанным с объемом памяти ЭВМ ("проклятье размерности"), поскольку в динамическом программировании требуется найти приближенное решение нелинейного дифференциального уравнения в частных производных, а метод принципа максимума требует определения приближенного решения двухточечной граничной задачи.


 

А также другие работы, которые могут Вас заинтересовать

25687. Яичники 58.5 KB
  Около половины овогоний с 3го месяца развития начинает дифференцироваться в овоцит первого порядка период малого роста находящийся в профазе мейоза. К моменту рождения число овогоний прогрессивно уменьшается и составляет около 45 большая часть клеток подвергается атрезии основные клетки представляют собой вступившие в период роста овоциты 1го порядка. 2 стадия период роста протекает в функционирующем яичнике и состоит в превращении овоцита 1го порядка первичного фолликула в овоцит 1го порядка в зрелом фолликуле. 3 стадия ...
25688. Мужские половые клетки 40 KB
  Скорость их движения у человека 3050мкм с Целенаправленному движению способствуют хемотаксис движение к химическому раздражителю или от него и реотаксис движение против тока жидкости. Мужские половые клетки человека сперматозоиды или спермии длиной 70мкм имеют головку и хвост. В ядре сперматозоида человека содержится 23 хромосомы одна из которых является половой X или У остальные аутосомами.
25689. Понятие о системе крови. Эритроциты 47 KB
  Система крови включает в себя кровь органы кроветворения красный костный мозг тимус селезенку лимфатические узлы лимфоидную ткань некроветворных органов. Элементы системы крови имеют общее происхождение из мезенхимы и структурнофункциональные особенности подчиняются общим законам нейрогуморальной регуляции объединены тесным взаимодействием всех звеньев. Так постоянный состав периферической крови поддерживается сбалансированными процессами новообразования гемопоэза и разрушения клеток крови.
25690. МОЧЕВЫДЕЛИТЕЛЬНАЯ СИСТЕМА 41 KB
  Длина его канальцев до 50мм а всех нефронов в среднем около 100 км. Остальные 15 нефронов располагаются в почке так что их почечные тельца извитые проксимальные и дистальные отделы лежат в корковом веществе на границе с мозговым веществом. Таким образом корковое и мозговое вещества почек образованы различными отделами трех разновидностей нефронов. Корковое вещество составляют почечные тельца извитые проксимальные и дистальные канальцы всех типов нефронов.
25691. Устойчивость работы электропривода 281 KB
  Устойчивое, неустойчивое и безразличное состояния электродвигателей. Статическая устойчивость электропривода Совмещенные механические характеристики электродвигателя и механизмов. Влияние эксплуатационных характеристик электродвигателяышечные клетки. Клетки узла проводящей системы. Формирование импульса происходит в синусном узле центральную часть которого занимают клетки первого типа водители ритма или пейсмекерные клетки Рклетки способные к самопроизвольным сокращениям.
25692. Прямая кишка 31 KB
  В тазовой части прямой кишки ее слизистая оболочка имеет три поперечные складки. В анальной части кишки различают три зоны: столбчатую промежуточную и кожную. Слизистая оболочка прямой кишки состоит из эпителия собственной и мышечной пластинок.
25693. Сердце 42.5 KB
  Стенка сердца состоит из трех оболочек: внутренней эндокарда средней миокарда и наружной эпикарда. Первая закладка сердца появляется в начале 3й недели развития у эмбриона длиной 15 мм в виде парного скопления мезенхимных клеток которые расположены в задней части головного отдела зародышевого щитка по сторонам от средней линии под висцеральным листком мезодермы. К 4му месяцу заканчивается образование всех отделов проводящей системы сердца. Клапаны сердца: предсердножелудочковые и желудочковососудистые развиваются в основном...
25694. Развитие нервной ткани 35.5 KB
  Часть клеток нервной пластинки не входит в состав нервной трубки и эпидермальной эктодермы и образует скопления по бокам от нервной трубки которые сливаются в рыхлый тяж располагающийся между нервной трубкой и эпидермальной эктодермой нервный гребень ганглиозная пластинка. Нервная трубка на ранних стадиях эмбриогенеза представляет собой многорядный нейроэпителий состоящий из вентрикулярных или нейроэпителиальных клеток. Вентрикулярная эпендимная зона состоит из делящихся клеток цилиндрической формы. Клетки делятся и после деления...
25695. НЕРВНАЯ СИСТЕМА. Развитие. Нервы. Узлы. Оболочки 34 KB
  Оболочки. Клетки этой оболочки отличаются овальной формой ядер. На поперечном срезе нерва видны сечения осевых цилиндров нервных волокон и одевающие их глиальные оболочки. Соединительнотканные оболочки нерва содержат кровеносные и лимфатические сосуды и нервные окончания.