Skip to content
Назад к результатам поиска

Многокритериальная динамическая программа — Парето-оптимальные стратегии при последовательных решениях

Автор метода
Extension of Bellman (1957); formalized by multiple authors from 1970s onward
Год
1957-1975
Тип
Exact optimization — recursive multi-objective decomposition
Семейство
Simulation / optimization

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Вместо одной оптимальной стратегии она производит Парето-оптимальное множество стратегий — каждая из которых представляет собой различный профиль компромисса — путем распространения векторных функций ценности назад по пространству состояний.

Интуиция метода

В однокритериальной динамической программе каждое состояние несет одно лучшее значение и одно лучшее действие. Многокритериальная динамическая программа обобщает это, храня в каждом состоянии весь Парето-фронт доминирующих векторов суммарного вознаграждения. По мере того как алгоритм движется назад по этапам принятия решений, он объединяет и отсекает эти Парето-множества, так что только действительно недоминируемые стратегии выживают до финального этапа. Результатом является не один ответ, а полная поверхность компромисса, из которой лицо, принимающее решения, может выбрать стратегию, наилучшим образом соответствующую его предпочтениям, без необходимости заранее указывать веса.

История

Многокритериальная динамическая программа строится на основе основополагающей структуры динамического программирования Ричарда Беллмана, опубликованной в 1957 году. Расширения на векторные цели появились в литературе по исследованию операций в 1970-х и 1980-х годах, обусловленные приложениями в управлении водными ресурсами, военном планировании и экономической политике. Область созрела вместе с теорией многокритериальной оптимизации, с ключевыми вкладами в формализацию рекурсии Парето-функции ценности и алгоритмов отсечения. Она остается активной областью исследований, особенно в контексте марковских процессов принятия решений с множественными сигналами вознаграждения.

Когда применять

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

Ограничения и замечания

  • Сильно страдает от проклятия размерности: вычислительная стоимость и память растут экспоненциально с числом переменных состояния и целей.
  • Требует дискретного или дискретизированного пространства состояний, что может привести к ошибке аппроксимации для непрерывных задач.
  • Число недоминируемых стратегий, хранящихся в каждом состоянии, может очень сильно расти, делая точные методы непрактичными для задач с более чем тремя или четырьмя целями.
  • Предполагает марковское свойство — оптимальное будущее действие зависит только от текущего состояния, а не от истории прошлых решений.
  • Реализация значительно сложнее однокритериальной динамической программы, требуя эффективных проверок Парето-доминирования и управления множествами в каждом состоянии.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Предоставляет полный Парето-фронт оптимальных стратегий, давая лицам, принимающим решения, полное представление о компромиссах между целями без принудительного предварительного указания весов.
  • Гарантирует точную Парето-оптимальность в рамках модели — отсутствие эвристических приближений для задач управляемого размера.
  • Естественно обрабатывает последовательные и поэтапные структуры принятия решений, где большинство других многокритериальных методов требуют искусственного переформулирования задачи.
  • Разделяет фазу оптимизации и фазу выявления предпочтений, позволяя применять предпочтения заинтересованных сторон после вычисления фронта.
  • Естественно расширяется на стохастические сценарии путем хранения Парето-множеств ожидаемых векторных значений в каждом состоянии.

Применение

  • Многоэтапное управление водохранилищем, балансирующее контроль над наводнениями, ирригационное снабжение и гидроэлектрогенерацию одновременно.
  • Последовательное планирование лечения рака, оптимизирующее контроль над опухолью, токсичность и качество жизни в течение циклов лечения.
  • Многопериодная оптимизация портфеля, балансирующая доходность, риск и ограничения ликвидности на разных инвестиционных горизонтах.
  • Оценка экологической политики для мер, которые должны балансировать экономические затраты, сокращение выбросов углерода и воздействие на биоразнообразие с течением времени.
  • Многокритериальная маршрутизация и планирование в логистических сетях с конкурирующими целями по стоимости, времени и надежности.
  • Последовательное распределение ресурсов в портфелях НИОКР, балансирующее эффективность бюджета, потенциал инноваций и время выхода на рынок.

Как это работает

Как это работает

1

Определить многоэтапную задачу принятия решений: множество этапов t = 1, ..., T, пространство состояний S, пространство действий A, функцию перехода и векторную функцию вознаграждения r(s, a) = (r1, r2, ..., rk) с k целями. На этом этапе скалярные веса не требуются.

2

Перечислить или дискретизировать пространство состояний. Для каждого терминального состояния на этапе T инициализировать Парето-множество как синглетон, содержащий вектор терминального вознаграждения. Эти граничные значения закрепляют рекурсию назад.

3

На каждом состоянии s и этапе t определить векторную функцию ценности V(s, t) как множество всех недоминируемых векторов суммарного вознаграждения, достижимых из (s, t) до терминального этапа. Заменить скалярную оптимальность Беллмана на Парето-недоминируемость: вектор v доминирует v', если v как минимум так же хорош по каждой цели и строго лучше по крайней мере по одной.

4

Двигаться назад от этапа T к этапу 1. На каждом (s, t) вычислить кандидатные векторные значения для каждого допустимого действия a, комбинируя непосредственное вознаграждение r(s, a) с каждым элементом V(s', t+1) для следующего состояния s'. Взять объединение по всем действиям и отсечь доминируемые векторы, чтобы сохранить только Парето-фронт для V(s, t).

5

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

Частые ошибки

  • Путаница многокритериальной ДП с простым многократным запуском динамической программы с различными весами — такой подход упускает невыпуклые области Парето-фронта.
  • Неспособность проверить, что пространство состояний действительно марковское, перед применением метода — скрытые переменные состояния сделают рекурсию недействительной.
  • Недооценка размера Парето-множества в каждом состоянии, что приводит к исчерпанию памяти для задач с большим числом целей или длинными горизонтами.
  • Применение МКДП к непрерывным или высокоразмерным пространствам состояний без схемы аппроксимации с гарантией сходимости, что приводит к ненадежным результатам.
  • Представление полного Парето-фронта лицам, принимающим решения, без вспомогательных инструментов для выявления предпочтений, перегружая их слишком большим количеством вариантов стратегий.

Часто задаваемые вопросы

Чем многокритериальная динамическая программа отличается от простого запуска динамической программы отдельно для каждой цели?

Запуск ДП отдельно для каждой цели дает индивидуальные однокритериальные оптимумы, которые, как правило, невозможно достичь одновременно и полностью упускают структуру компромисса. МКДП распространяет векторные Парето-множества через пространство состояний, захватывая все недоминируемые комбинации значений целей, достижимые любой отдельной стратегией — включая решения в невыпуклых областях Парето-фронта, которые подходы со взвешенной суммой не могут найти.

Когда проклятие размерности делает МКДП непрактичной?

МКДП становится невыполнимой, когда пространство состояний имеет более нескольких дискретных переменных, когда горизонт планирования очень длинный, или когда существует более трех или четырех целей (что приводит к экспоненциальному росту Парето-фронта в каждом состоянии). В таких случаях предпочтительны приближенные методы, такие как многокритериальное обучение с подкреплением или эвристический поиск Парето.

Может ли МКДП справляться с неопределенностью в переходах или вознаграждениях?

Да. В стохастическом сценарии векторная функция ценности хранит ожидаемые Парето-оптимальные векторы вознаграждений, вычисленные с использованием взвешенной по вероятности суммы по следующим состояниям. Это естественным образом распространяется на многокритериальные марковские процессы принятия решений (МКМП), хотя стохастичность еще больше увеличивает вычислительные требования.

Нужно ли указывать веса целей перед запуском МКДП?

Нет — это одно из ключевых преимуществ МКДП. Веса или информация о предпочтениях не требуются во время фазы оптимизации. Алгоритм вычисляет полный Парето-фронт, а лицо, принимающее решения, применяет свои предпочтения после этого для выбора конкретной стратегии.

Какой вывод производит МКДП и как его следует интерпретировать?

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

Похожие методы

Источники

  1. Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.

    ISBN: 9780691079516
    Скопировано.
  2. Daellenbach, H. G., & Flood, R. L. (1992). Multi-objective dynamic programming. European Journal of Operational Research, 56(2), 215-225.

    Открыть ссылку на публикацию
    Скопировано.