Динамическое программирование с использованием множеств Парето

В данном разделе излагается модификация метода Р. Веллмана «динамическое программирование с использованием множеств Парето» [25,33,35], которая для широкого круга задач более эффективна, чем оригинальный метод. Приводятся практические задачи из различных областей, которые решаются с использованием множеств Парето.

Однокритериальная задача распределения ресурса

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

Выше ( разд. 3.4) мы уже рассматривали численный пример распределения капитала, который и был ресурсом, по четырём инвестиционным проектам при оценке эффективности по одному критерию. Рассмотрим теперь более общий случай.

Задача сводится к следующему [3]:

Найти шах при где с есть

распределяемый объём ресурса, a Xi>0 -его количество, выделенное для i-oro потребителя (объекта).

Для решения задачи Р. Веллман использовал принцип оптимальности, который в [3] сформулирован так : «Оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальные состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения». Мы уже приводили практически ту же формулировку: если в каждом из состояний дальнейшее поведение системы не зависит от того, как она попала в это состояние, то дальнейшая траектория должна быть оптимальной.

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

Рис. 4.1. Схема многошагового процесса распределения ресурса

Предполагается, что распределение ресурса происходит дискретно с постоянным шагом, так что На первом шаге (вертикаль 1

на рис. 4.1) первому объекту может быть выделено единиц ресурса, что отражено соответствующей стрелкой на вертикали 1. Для каждой из этих возможностей вычисляется оценка эффективности fi(xi). Далее, на втором шаге второму объекту может быть выделено любое количество ресурса Х2 (с той же дискретностью), но не более, чем с- xi (это всё что осталось). Суммарное количество xi + хг даёт состояние системы после второго шага. Этим состояниям соответствуют точки на вертикали 2. В одно и то же состояние можно перейти различными путями, так как одно и то же значение суммы xi + хг может быть получено при различных значениях слагаемых. При этом и оценка эффективности fi(xi) + f2(x2) может принимать различные значения. Обозначим её оптимальное (в данной задаче максимальное) значение как F2(r). Здесь r=xi+X2 -это распределённый ресурс, который и определяет состояние системы после двух шагов. И вообще Fi(r) - максимальная эффективность за i шагов при распределённом ресурсе г. При i=n это и есть максимальная эффективность распределения всего ресурса по всем объектам. Естественно предположить, что все функции fi(xi) неубывающие и в конечном итоге г равно с. Исходя из принципа оптимальности, Р. Веллман получил уравнение

Это уравнение устанавливает рекуррентную связь между Fi(r) и Fi-i(r). Его смысл в том, что при любом г (то есть состоянии системы после i-ro шага) величину Xi надо выбирать так, чтобы суммарная эффективность перехода в это состояние из начальной точки была максимальной. Для схемы рис. 4.1 выбор Xi означает переход из состояния r-Xi на i-1-ой вертикали к состоянию г на i-ой вертикали, то есть выбор из всех путей, сходящихся в одной точке i-ой вертикали, определяемой г. На первом шаге при любом г нет выбора, есть только один путь из точки О в любую точку (состояние, определяемое г). Но на всех дальнейших шагах из всех путей, сходящихся в одной точке (на рис. 4.1 точки А,В,С), остаётся только один, запоминается максимальное значение Fi(r) и то значение Xj, которое соответствует переходу с i-1 вертикали в точку с координатой г на i-ой вертикали. Именно сравнение путей, сходящихся в одной точке, и отбраковка бесперспективных путей и всех их продолжений, обеспечивает высокую эффективность динамического программирования. Однако при большой размерности задачи (мелкой сетке) даже этот метод требует больших затрат машинного времени, т.е. действует «проклятие размерности».

Зададимся вопросом, а нельзя ли, хотя бы в некоторых задачах, отбраковывать не только пути, сходящиеся в одной точке, но и сами состояния. Особенно актуальным этот вопрос становится в тех задачах, где требование регулярной сетки (постоянного шага 5) становится обременительным, так как приводит к необходимости использования малых дискретов и требует больших объёмов памяти и времени счёта.

Обратившись к рис. 4.1, рассмотрим вопрос, а что если на некотором шаге состояние с большим г (точка В) после сравнения всех приводящих в него путей и отбраковки бесперспективных вариантов, оказывается менее эффективным, чем состояние с меньшим г(точка А) после сравнения всех приводящих в него путей? Другими словами, может ли быть Fi(n) гг? Казалось бы это невозможно. Действительно, если это так, то на предыдущем шаге (i-1- ая вертикаль) вместо наилучшего состояния, из которого переходим в п (точка М рис.4.1) возьмём состояние (точка К), из которого переходим в гг(точку А). Теперь на предпоследнем шаге (i-1 вертикаль) мы имеем состояние (точка К), из которого на i-ую вертикаль в состояние n переходим при большем Xi, чем в состояние гг. Так как функция fi(xi) не убывающая, то получим по этому пути Fi(n)> Fi(r₂). Получается, что, если действовать оптимальным образом, то в данной задаче большему растраченному ресурсу соответствует и большая эффективность, что вполне естественно. Однако не следует спешить с отрицательным ответом на поставленный выше вопрос о возможности отбраковки состояний, а не только путей, приводящих в одно и то же состояние.

Казалось бы очевидное предположение о возможности перехода из точки К в состояние гi (точка В) может и не выполняться в более сложных случаях, чем рассматриваемый. Примером может служить такая классическая задача целочисленного линейного программирования, как задача о рюкзаке, которая в переменных 0 и 1 имеет вид:

Найти при

Эту задачу можно рассматривать как задачу распределения ресурса b по п объектам, каждый из которых получает ai или не получает ничего.

В общем виде этот тип задач может быть описан следующим образом: имеется п объектов, каждый из которых можно выбрать (xi=l) или не выбрать (xi=0). Выбор i-oro объекта требует затрат ресурса в количестве ai. Общее количество ресурса равно Ь. Эффективность выбора i-oro объекта равна сь Следует выбрать объекты так, чтобы суммарные затраты ресурса не превосходили Ь, а суммарный эффект был максимальный.

Аналогичная задача получается при наличии нескольких (ki>2) экземпляров объектов. При этом Как будет показано на конкретных примерах, именно в подобных задачах появляется возможность отбраковки не только путей, приводящих систему в некоторое состояние, но и самих не эффективных состояний из-за наличия на том же шаге одного или нескольких состояний, которые не уступают данному как по ресурсу (он не больше), так и по эффективности (она не меньше). Такое не эффективное состояние может быть исключено из дальнейшего рассмотрения вместе со всеми его продолжениями, так как при оптимальном выборе в дальнейшем, двигаясь из этого состояния нет шансов «наверстать упущенное».

Сформулируем принцип отбраковки состояний. Состояние (А) может быть исключено из дальнейшего рассмотрения, если на том же шаге имеется состояние (В), такое что :

• 1. Оценка эффективности (значение целевой функции) для состояния А при максимизации меньше, а при минимизации больше, чем для состояния В;
• 2. Существует путь из состояния В в конечное состояние, который не менее эффективен, чем наилучший путь из состояния А в конечное состояние.

Если эти условия выполнены, то очевидно, нет никакого смысла сохранять состояние А, так как оно проигрывает состоянию В на рассматриваемом шаге и не может наверстать этот проигрыш на оставшихся шагах. Условие пункта 2 всегда выполнены, если возможности выбора и соответствующие затраты на оставшихся шагах одинаковы для всех состояний, то есть существуют «параллельные траектории».

Более того, сформулированный принцип отбраковки состояний может быть усилен. Даже если на оставшихся шагах, двигаясь из состояния А в конечную точку наилучшим образом, можно что-то наверстать по сравнению с движением из состояния В, но не более, чем имеющаяся разность в эффективности этих состояний, то всё равно состояние А можно исключить из дальнейшего рассмотрения (принцип отбраковки состояний «отставших навсегда»).

Если рассматривать задачу как двухкритериальную: первый критерий - эффективность (нужен максимум), а второй критерий - суммарный использованный ресурс (нужен минимум), то новый принцип отбраковки требует оставлять на каждом шаге только паретовское множество состояний. По этой причине он назван программированием с использованием множеств Парето [25]. Ясно, что остаётся отбраковка путей, приводящих систему в некоторое состояние, (как в классическом динамическом программировании), поэтому каждому состоянию из паретовского множества соответствует только один, приводящий в него путь. Если в классическом динамическом программировании требовалось отсутствие влияния предыстории, то для применения динамического программирования с использованием множеств Парето требуется ещё и сохранение возможностей принятия одних и тех же решений на последующих шагах независимо от достигнутых состояний, причём с теми же последствиями, то есть существование «параллельных траекторий».

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

При задании регулярной сетки состояний их число на каждом шаге фиксировано и в случае не попадания реальных состояний на узлы сетки «привязка» к узлам делается за счёт округления соответствующих величин. Если отказаться от регулярной сетки, ничего не округлять и оставлять только множества Парето, то при большом числе шагов количество состояний может стать чрезмерно велико. Однако как только число состояний на некотором шаге превысит заданное предельное значение, можно ввести допускаемую погрешность (аналог шага сетки), то есть не включать в множество Парето эффективное состояние, если оно попадает между двумя близкими состояниями из множества Парето. Предельное значение числа состояний и величина допускаемой погрешности определяется условиями конкретной задачи и мощностью используемых вычислительных средств.

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

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