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







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

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

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

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

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

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

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


 

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

6427. Печатная электроника для дешевых электронных систем. Состояние технологии и развитие оборудования. 21.59 KB
  Печатная электроника для дешевых электронных систем. Состояние технологии и развитие оборудования. Аннотация. В последние годы печать стала сильно интересна как метод получения дешевых и массовых электронных систем. Печать допускает использование це...
6428. РЕАБИЛИТАЦИЯ ЖЕРТВ ПРЕСТУПЛЕНИЙ КАК ПРАВОВАЯ ПРОБЛЕМА 22.21 KB
  Статья посвящена анализу правового института реабилитации в уголовном процессе Российской Федерации, а также кругу участников судопроизводства, которые, по мнению автора, должны обладать правом н...
6429. Зигмунд Фрейд. Влечения и их судьба 116 KB
  З. Фрейд. Влечения и их судьба Нам часто приходилось слышать, что наука должна строиться на основании ясных и точно определенных исходных положений. В действительности никакая, даже самая точная, наука не начинает с таких определений. Настоящее нача...
6430. Проблема обучения и умственного развития в школьном возрасте 118.5 KB
  Проблема обучения и умственного развития в школьном возрасте Вопрос об отношении обучения и развития ребенка в школьном возрасте представляет собой самый центральный и основной вопрос, без которого проблемы педагогической психологии и педагогическог...
6431. Манипулятивные технологии в системе массовых коммуникаций 167.5 KB
  Манипулятивные технологии в системе массовых коммуникаций. Введение. Определение манипуляции. Признаки манипуляции. Психология манипуляции. Манипуляция на уровне психических процессов. Манипуляция на уровне психологиче...
6432. Проверка гипотезы совпадения экспериментального закона с теоретическим по критерию Колмогорова 25.47 KB
  Проверка гипотезы совпадения экспериментального закона с теоретическим по критерию Колмогорова Этапы задания и результаты их реализации. Задание 1. Разобраться в теоретическом материале Задание 2. Проверить с помощью критерия Колмогорова, подч...
6433. Новейшая история стран Латинской Америки 2.19 MB
  Предисловие Проблемы новейшей истории стран Латинской Америки занимают видное место в отечественной исторической науке. Начиная с 50-х годов было опубликовано много работ по тем или иным вопросам истории региона и отдельных латиноамерикански...
6434. Американская стратегия для ХХI века 152 KB
  Введение Всегда непредсказуемая, мировая история сделала в 1990-е годы нашего века удивительный поворот. После полустолетия биполярного противостояния мир потерял прежнее равновесие и новую систему международных отношений возглавили Соединенные Штат...
6435. Исламская экономика: универсальная теория развития или одна из моделей третьего пути 151.5 KB
  Исламская экономика: универсальная теория развития или одна из моделей третьего пути? Статья посвящена различным теориям развития в мусульманском мире во второй половине XX - начале XXI в., среди них - арабский социализм, исламский социали...