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 на плоскости (см. рисунок).







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

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

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

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

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

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

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


 

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

22244. Выбор измерительных средств 43 KB
  При выборе измерительных средств необходимо оценить допускаемую погрешность измерения а также определить положение приемочных границ т. Допускаемая погрешность измерения зависит от допуска на изготовление изделия который связан с номинальным размером. Для линейных размеров до 500 мм СТ СЭВ 303 76 в квалитетах 2 17 устанавливает 16 рядов допускаемых погрешностей измерения. Если допуск на изготовление не совпадает с допуском ЕСДП СЭВ погрешность измерения следует выбирать по ряду погрешностей установленному для ближайшего более...
22245. Характеристика единой системы допусков и посадок 247.5 KB
  Единая система – это есть единая система взаимозаменяемости. Эта система состоит важнейшими, из которых являются допуски и посадки гладких цилиндрических поверхностей. Единая система отличается от прежней системы принципом построения, значениями предельных отклонений, условными значениями допусков и посадок.
22246. Взаимозаменяемость, методы и средства контроля шпоночных и шлицевых соединений 127 KB
  Шпоночные соединения предназначены для передачи вращающегося момента и осевой силы. Шпонка это соединённая деталь предназначенная для передачи вращающегося момента между валом и насаженным на него зубчатым колесом и обеспечивающая их одновременное вращение. Треугольные шлицы применяются для передачи малых нагрузок поэтому наиболее распространёнными являются прямобочные. С точки зрения прочностных и эксплуатационных требований все зубчатые передачи делятся на силовые скоростные передачи.
22247. ВИДЫ ВЗАИМОЗАМЕНЯЕМОСТИ И ТОЧЬНОСТЬ. ВЗАИМОЗАМЕНЯЕМОСТЬ. РАЗМЕРЫ,ОТКЛОНЕНИЯ,ДОПУСКИ, ПОСАДКИ 85.5 KB
  Er = D r D er = d r d Предельные отклонения: Es = D max D верхнее предельное отклонение отверстия; еs = d max d верхнее предельное отклонение вала; ei = d min d нижнее предельное отклонение вала; EI = D min D нижнее предельное отклонение отверстия. TD = D max D min допуск отверстия; Td = d max d min допуск вала. Dm = D max D min Единица допуска является функцией номинального размера. С зазором S min = D min d max = EI es S max = D max d min = ES ei Частным случаем посадки с зазором...
22248. Метод групповой взаимозаменяемости 28.5 KB
  групповой зазор или натяг не обеспечивают однородности соединения так как он меняется при переходе от одной группы к другой при этом усложняются и удорожаются контрольные операции связи с тем что для такого отбора деталей требуется дополнительный измерительный инструмент. Создаются трудности при замене быстроизнашиваемых деталей. Решает следующие задачи: Устанавливает ответственные размеры и параметры деталей и узлов оказывают влияние на эксплуатационные показатели машин и на собираемость узлов. Уточняются номинальные величины...
22249. Расчет допусков размеров, входящих в размерные цепи 39 KB
  Составляющее звено звено размерной цепи изменение которого вызывает изменение исходного или замыкающего звена. Увеличивающие если с увеличением составляющего звена увеличивается размер исходного или замыкающего звена. Уменьшающие если с уменьшением составляющего звена уменьшается размер исходного или замыкающего звена. Компенсирующее звено предварительно выбранное звено размерной цепи изменение размера которого достигается требуемая точность замыкающего звена.
22250. Мониторинг в нейроанестезиологии и нейрореаниматологии 213 KB
  Мониторинг при операциях на стволе мозга Мониторинг при сосудистых операциях. Мониторинг в нейрореаниматологии оценка уровня сознания мониторинг витальных функций контроль ВЧД длительный контроль транскраниальная допплерография оценка метаболизма мозга Обеспечение безопасности больного находящегося в состоянии анестезии является одной из основных обязанностей анестезиолога. В нейрохирургии этот метод часто применяется при вмешательствах н сосудах головного мозга. Нейрофизиологический мониторинг Впервые регистрацию биоэлектрической...
22251. ТАКТИКА ВЕДЕНИЯ НАРУШЕНИЙ МОЗГОВОГО КРОВООБРАЩЕНИЯ 69.5 KB
  Частоту нарушений мозгового кровообращения НМК трудно установить так как определенное количество больных погибает вне клиники или не госпитализируется. Как бы то ни было НМК составляют около 5 объема скоропомощной практики. Сегодня подход к лечению НМК должен быть динамичным коллективным и мультидисциплинарным. Тактикой скоропомощного ведения пациента с подозрением на НМК кроме диагностики причины заболевания и оценки тяжести состояния должно быть срочное обеспече ние максимальной оксигенации головного мозга с целью минимизации...
22252. ОБЩИЕ ПРИНЦИПЫ ИНТЕНСИВНОЙ ТЕРАПИИ ПОСТРАДАВШИХ С СОЧЕТАНОЙ ЧЕРЕПНО-МОЗГОВОЙ ТРАВМОЙ 127 KB
  По данным к примеру клиники Военнополевой хирургии Военномедицинской академии за последние 10 лет частота поступления пострадавших с такой характеристикой повреждений составляет около . Анализ исходов течения травматической болезни у этой категории пострадавших свидетельствует о высокой степени неблагоприятных исходов напрямую коррелирующей с тяжестью ЧМТ степенью полисегментарности повреждения выраженностью шоковой реакции организма в целом. Интенсивная терапия пострадавших III группы нетяжелая ЧМТ и...