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







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

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

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

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

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

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

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


 

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

30315. Предложение как синтаксическая единица. Его признаки и свойства. Понятие структурной схемы и парадигмы предложения 35.5 KB
  Понятие структурной схемы и парадигмы предложения. Универсальный признак предложения – предикативность вслед за Шахматовым и Пешковским сформулировал Виноградов – соотнесенность содержания предложения с действительностью. Существует широкое предикативность присуща всем предложениям и узкое понимание только те предложения в которых есть предикат предикативности. Универсальное свойство предложения позволяющее совокупности словоформ стать предложением – интонационная оформленность.
30316. Понятие семантической структуры предложения, ее соотношение с формальной структурой 46 KB
  Эти отношения выражает предикат который организует положение дел и задаёт определённые места для предметов – участников ситуации актантов определяя их количество и роли. Актанты это предметные распространители предиката актант субъектного типа актант объектного типа орудийный актант и т. В структуре пропозиции имеются также непредметные распространители предиката – сирконстанты локатив темпоратив и др. Таким образом каждая пропозиция являясь моделью ситуации имеет свою структуру вершиной которой выступает предикат.
30317. Основы описания простого предложения. Типы предложений 29 KB
  Основы описания простого предложения. коммуникативную задачу выражающуюся интонацией и порядком слов Актуальное членение предложения. структура; порядок слов и интонация; члены предложения как компоненты предикативной основы П. По характеру выражаемого в них отношения к действительности различаются предложения реальной и ирреальной модальности с разнообразными оттенками модальных значений: реальности и ирреальности предположения сомнения уверенности возможности невозможности и т.
30318. Современный русский литературный язык как предмет научного изучения. Русский язык в современном мире 45.5 KB
  Русский язык в современном мире. Русский язык в современном мире. Языки имеют национальные границы каждый из языков своеобразен.
30319. Понятие о стилях ЛЯ. Принципы их классификации 198.5 KB
  ЛИТЕРАТУРНЫЙ ЯЗЫК наддиалектная подсистема форма существования национального языка которая характеризуется такими чертами как нормативность кодифицированность полифункциональность стилистическая дифференцированность высокий социальный престиж в среде носителей данного национального языка. Литературный язык является основным средством обслуживающим коммуникативные потребности общества; он противопоставлен некодифицированным подсистемам национального языка – территориальным диалектам городским койне городскому просторечию...
30320. Проблема нормативности литературной речи. Классификация речевых ошибок 53 KB
  Нормы: 1. Ожегов дал такое определение языковой нормы: Норма это совокупность наиболее пригодных для обслуживания общества средств языка складывающихся как результат отбора языковых элементов из числа сосуществующих наличествующих образуемых вновь или извлекаемых из пассивного запаса прошлого в процессе социальной в широком смысле оценки этих элементов. Искусственные нормы устанавливаются в результате нормотворческой деятельности языковедов путем подготовки и издания авторитетных словарей и справочников и даже законодательных актов ...
30323. Физико-химические основы технологических процессов 59.5 KB
  Физикохимические основы технологических процессов Этилбензол на нефтехимических предприятиях Украины и в ведущих капиталистических странах получают по каталитической реакции алкилирования бензола этиленом: С6Н6 С2Н4→С6Н5СН2СН3 2 Реакция алкилирования бензола этиленом можно классифицировать как: по зоне протекания химической реакции гетерогенная ; по использованию в ходе реакции катализатора...