Детерминированное динамическое программирование — точная последовательная оптимизация при известных параметрах
- Автор метода
- Richard E. Bellman
- Год
- 1957
- Тип
- Exact sequential optimization algorithm
- Семейство
- Simulation / optimization
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Детерминированное динамическое программирование (ДДП) — это метод математической оптимизации, который раскладывает многоэтапную задачу принятия решений на последовательность более простых подзадач, решая их точно, когда все параметры системы — функции переходов, затраты и вознаграждения — известны с определённостью.
Он гарантирует глобально оптимальную политику посредством принципа оптимальности Беллмана.
Интуиция метода
Представьте планирование самого дешёвого маршрута через сеть городов, где все стоимости дорог известны заранее. Вместо того чтобы оценивать каждый возможный полный путь, динамическое программирование работает в обратном направлении: в каждом городе оно записывает минимальную стоимость достижения пункта назначения оттуда. Как только каждый город помечен, проследить оптимальный путь вперёд тривиально. Это обратное рассуждение — принцип оптимальности Беллмана — является сердцем детерминированного ДП: любая подчасть оптимального пути сама по себе должна быть оптимальной.
История
Ричард Беллман формализовал динамическое программирование в своей монографии 1957 года в Принстоне, выведя принцип оптимальности, который лежит в основе всех методов ДП. Детерминированный случай — когда переходы и вознаграждения известны — был первоначальной формулировкой. Он вырос из исследовательской работы Беллмана во время войны и стал основополагающим в теории управления, экономике и комбинаторной оптимизации. Позже Берцекас расширил и систематизировал теорию в нескольких томах.
Когда применять
Используйте детерминированное динамическое программирование, когда система имеет чётко определённые последовательные этапы, все затраты и результаты переходов известны с определённостью, и принцип оптимальности применим (оптимальная подструктура). Оно превосходно подходит для управления запасами, распределения ресурсов во времени, поиска кратчайшего пути и планирования производства с фиксированными параметрами. НЕ используйте его, когда параметры неопределённы или случайны — вместо этого переключитесь на стохастическое динамическое программирование. Также избегайте ДДП, когда пространство состояний очень велико или непрерывно без аналитической структуры, поскольку проклятие размерности делает его вычислительно невыполнимым. Оно не подходит для задач без последовательной или рекурсивной структуры.
Ограничения и замечания
- Сильно страдает от проклятия размерности: вычислительные требования и требования к памяти растут экспоненциально с числом переменных состояния. Это делает точное ДП невыполнимым для задач высокой размерности, мотивируя приближенные методы, такие как приближенное ДП или обучение с подкреплением.
- Требует полного и точного знания функции перехода и структуры вознаграждений; любая неопределённость параметров делает детерминированную модель недействительной.
- Дискретизация непрерывных пространств состояний или действий вносит погрешности аппроксимации и может пропустить истинный оптимум.
- Предполагает марковскую структуру — оптимальное решение на каждом этапе зависит только от текущего состояния, а не от истории того, как это состояние было достигнуто.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Гарантирует глобально оптимальное решение, когда задача удовлетворяет принципу оптимальности и параметры известны.
- Естественным образом обрабатывает многоэтапные последовательные решения, которые были бы неразрешимы как единая большая задача оптимизации.
- После вычисления функции цен оптимальные решения для всех состояний доступны одновременно, что позволяет проводить анализ чувствительности по начальным условиям.
- Применимо как к дискретным, так и к непрерывным пространствам состояний-действий (при соответствующей дискретизации или аналитической обработке).
- Концептуально прозрачно: процедура обратной индукции легко проверяется и верифицируется шаг за шагом.
Применение
- Оптимальные политики пополнения запасов с известными графиками спроса на конечный горизонт планирования.
- Задачи поиска кратчайшего пути и сетевой маршрутизации (например, алгоритм Дейкстры как частный случай ДП).
- Планирование производства и определение размера партии в производстве с детерминированным спросом и ограничениями по мощности.
- Добыча ресурсов и планирование капитальных вложений в экономике при определённости.
- Выравнивание последовательностей и биоинформатика (например, алгоритм Нидлмана-Вунша).
- Планирование замены и технического обслуживания оборудования с известными функциями затрат и деградации.
Как это работает
Как это работает
Определите цель оптимизации, горизонт планирования (конечный или бесконечный) и последовательность решений. Определите, что составляет этап, состояние, действие, непосредственное вознаграждение или стоимость r(s, a) и детерминированную функцию перехода s' = f(s, a), которая отображает пары состояние-действие в следующие состояния с определённостью.
Перечислите или параметризуйте все допустимые состояния S и все допустимые действия A(s) для каждого состояния. Для дискретных задач это даёт конечную таблицу состояний-действий; для непрерывных задач используются дискретизация или аналитические формы решения. Требования к памяти масштабируются с размером этого пространства — ключевое вычислительное узкое место.
Запишите уравнение оптимальности Беллмана: V_t(s) = max по a из A(s) [r(s,a) + V_{t+1}(f(s,a))]. Для задачи с конечным горизонтом инициализируйте V_T(s) терминальными значениями и рекурсивно двигайтесь назад от этапа T-1 к этапу 0. Для бесконечных горизонтов итерируйте обновления значений до сходимости (итерация по значениям).
Формула
V_t(s) = \max_{a \in A(s)} \bigl[ r(s, a) + V_{t+1}(f(s, a)) \bigr]Решите рекурсию этап за этапом от последнего периода к начальному (обратная индукция). На каждом этапе каждому состоянию присваивается его оптимальное значение, и записывается действие, которое его достигает. Это гарантирует, что решения подзадач согласованы и глобально оптимальны в рамках детерминированной модели переходов.
Постройте оптимальную политику путём прямого прохода: начиная с начального состояния s_0, применяйте pi*(s) = argmax_a [r(s,a) + V*(f(s,a))] на каждом этапе, следуя записанным оптимальным действиям. Полученная последовательность решений является глобально оптимальным планом при известных, фиксированных параметрах.
Формула
\pi^*(s) = \arg\max_{a \in A(s)} \bigl[ r(s, a) + V^*(f(s, a)) \bigr]Частые ошибки
- Смешение детерминированного ДП со стохастическим ДП: если какой-либо параметр системы неопределён, результаты детерминированной модели будут излишне оптимистичными и потенциально вводящими в заблуждение.
- Выбор представления состояния, которое слишком грубое (теряет оптимальность) или слишком тонкое (взрывает пространство состояний); тщательный дизайн пространства состояний имеет решающее значение.
- Игнорирование граничных условий: некорректные значения в конечном этапе V_T(s) распространяют ошибки по всей обратной рекурсии.
- Применение ДП к задачам, которым не хватает оптимальной подструктуры, где локальная оптимальность не гарантирует глобальную оптимальность.
- Предположение о конечном горизонте, когда задача на самом деле бесконечна, или наоборот, что приводит к некорректной формулировке рекурсии.
Часто задаваемые вопросы
Чем детерминированное ДП отличается от стохастического ДП?
В детерминированном ДП следующее состояние s' = f(s, a) является известной функцией — нет случайности. Стохастическое ДП заменяет f на распределение вероятностей P(s'|s, a) и максимизирует ожидаемое значение. Детерминированное ДП проще и точнее; стохастическое ДП подходит, когда исходы неопределённы.
Что такое проклятие размерности и почему оно важно?
Беллман ввёл этот термин, чтобы описать, как пространство состояний растёт экспоненциально с числом переменных состояния. Например, 10 переменных состояния, каждая с 100 дискретными уровнями, дают 10^20 состояний — далеко за пределами памяти любого компьютера. Это делает точное ДП невыполнимым для задач высокой размерности, мотивируя приближенные методы, такие как приближенное ДП или обучение с подкреплением.
Когда следует использовать линейное программирование вместо ДП?
Используйте линейное программирование, когда задачу можно выразить как оптимизацию одного периода с линейными ограничениями и целями. ДП предпочтительнее, когда решение разворачивается на несколько этапов, и оптимальное действие на каждом этапе зависит от состояния системы в это время.
Является ли детерминированное ДП тем же, что и обратная индукция в теории игр?
Они разделяют ту же рекурсивную логику — решение с конца назад — но обратная индукция в теории игр включает в себя нескольких игроков и стратегическое взаимодействие. Детерминированное ДП — это задача оптимизации одного агента без стратегических противников.
Может ли детерминированное ДП обрабатывать непрерывные пространства состояний и действий?
Да, когда существуют аналитические решения (например, линейно-квадратичные задачи) или когда функция цен имеет известные функциональные формы. В противном случае непрерывные пространства должны быть дискретизированы, что вносит погрешность аппроксимации и значительно увеличивает вычислительную нагрузку.
Похожие методы
Источники
Bellman, R. E. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.
ISBN: 9780691079516Скопировано.Bertsekas, D. P. (2017). Dynamic Programming and Optimal Control (4th ed., Vol. 1). Athena Scientific, Belmont, MA.
Открыть ссылку на публикациюСкопировано.