Нахождение Парето-лексикографически оптимальных траекторий в дискретных динамических системах



Скачать 136.17 Kb.
Дата16.11.2016
Размер136.17 Kb.
Нахождение Парето-лексикографически оптимальных траекторий в дискретных динамических системах
Автор: Парфёнов Андрей Павлович, преподаватель факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета.
Рассмотрены динамические задачи многокритериальной оптимизации с дискретным временем и обобщенными интегральными выигрышами, принимающими значения из произвольных упорядоченных полугрупп. Эти задачи исследованы на динамическую устойчивость и позиционную динамическую устойчивость. На основе обобщения метода динамического программирования построены алгоритмы нахождения парето-оптимальных дискретных управлений относительно некоторых лексикографических порядков на подмножествах множества критериев.
Ключевые слова: динамическая оптимизация, оптимумы Парето, многокритериальная оптимизация, лексикографическая оптимизация, упорядоченные полугруппы.
При оптимизации управляемых динамических систем с дискретным временем во многих случаях целесообразно применять рекуррентные соотношения динамического программирования, введенные Беллманом [2]. Но в задачах многокритериальной оптимизации, как и в игровых задачах, эти соотношения не всегда выполняются [3]. Их, обычно, связывают с принципом динамической устойчивости, согласно которому конечный участок оптимальной траектории также оптимален, хотя, как будет показано дальше, в общем случае применимость метода динамического программирования может не следовать из динамической устойчивости, и обратное следование также может быть неверно.

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

Пусть дана управляемая динамическая система D : X T 2X с пространством состояний X, с дискретным временем T = {1, …, m}, множествами позиционных (программно-адаптивных) управлений U(x, t), заданных для каждого состояния системы в каждый момент времени, и функцией перехода π : X T U(X, T) X, определяющей состояние системы h(t+1) = π(h(t), t, u(h(t), t)) в момент времени t+1, если в момент t в позиции h(t) было выбрано управление u.

Рассмотрим задачу выбора траектории h (или программного управления u) управляемой динамической системы, начинающейся в заданной точке x1 и удовлетворяющей некоторому набору критериев оптимальности f1, ..., fn:



(1),

где P(x, t) - множество траекторий, начинающихся в точке x в момент t, а критерии f1, ..., fn принимают значения в некотором упорядоченном множестве (R, <). То есть рассматривается самый общий случай оптимизационной задачи, соответствующий выбору из некоторого упорядоченного множества альтернатив. Это эквивалентно тому, что (R, *, <) - упорядоченная полугруппа. Действительно, любое упорядоченное множество можно представить как упорядоченную правосингулярную полугруппу, в которой операция * задается соотношением a * b = b.

Частные случаи критериев оптимальности f1, ..., fn:

1. Терминальная полезность (терминальный выигрыш):



fi(h1, ..., hm) = fi(hm) (2);

2. Обобщенная интегральная полезность (обобщенный интегральный выигрыш):



f(h1, ..., hm) = fi1(h1) * ... * fim(hm) (3)

где (R, *, <) - упорядоченная полугруппа - включает в себя (2) как частный случай при правосингулярной полугруппе R.

Динамическая устойчивость [3] определяется не для одной оптимизационной задачи, а для целого семейства задач, заданных в разные моменты времени в разных начальных условиях. Да и метод динамического программирования [2] решает не одну задачу, а семейство задач. Дадим строгое определение:

Определение 1. Пусть дана управляемая динамическая система D с дискретным временем на множестве состояний X и соответствующая ей динамическая многокритериальная оптимизационная задача (P(x1, 1), f1, ..., fn), где x0 - начальная позиция, (f1, …, fn )- критерии оптимальности на множестве траекторий. Тогда семейство задач, соответствующих системе D - это множества траекторий, соответствующих моменту t, начинающихся в точке x. и критерии оптимальности (P(x, t), (f1)(x, t), ..., (fn)(x, t)), заданные на этом множестве траекторий.

То есть семейство динамических оптимизационных задач (СДОЗ) означает, что для каждой подсистемы задана оптимизационная задача на множестве траекторий, что позволяет определить, как меняются цели системы в зависимости от текущего момента времени. Поскольку семейство задач задается произвольным образом, отнюдь не каждое семейство задач можно решить методом динамического программирования.



Определение 2. Пусть задана управляемая динамическая система D с обобщенным интегральным выигрышем fi(x1, x2, ..., xm) = fi1(x1) * fi2(x2) * ... * fim(xm). Тогда естественное семейство задач - это СДОЗ, определяемое так: (fi)(x, t)(x, xt+1, ..., xm) = fit(x) * fit+1(xt+1) * ... * fim(xm).

В частности, если в основной задаче задана терминальная полезность fi(xm), то в каждой задаче семейства также задана терминальная полезность fi(xm). Таким образом, мы формализовали рассуждения о том, что выигрыш «выплачивается в разные моменты времени» [3].

Пусть задан принцип оптимальности в задаче многокритериальной оптимизации, который каждому набору критериев f = (f1, ..., fn) и множеству возможных решений X сопоставляет множество оптимальных решений X' X. Будем рассматривать принципы оптимальности -паретовские множества относительно лексикографических порядков на подмножествах множества критериев. Эти принципы удовлетворяют аксиоме независимости от посторонних альтернатив: если x* оптимально для множества X и x* X' X, то x* оптимально и для множества X'.

Напомним теперь основные понятия, связанные с динамической устойчивостью по аналогии с теорией позиционных игр [3]. Свойства динамической устойчивости имеют место для семейства оптимизационных задач (P(x), (f1, ..., fn)) и их оптимальных траекторий - то есть таких траекторий, на которых достигается оптимум по критериям f1, ..., fn.



Определение 3. Оптимальная траектория h называется (слабо) динамически устойчивой в СДОЗ, если любая ее конечная подтраектория (h(t), h(t+1), h(t+2), ..., h(m)) является оптимальной в задаче для подсистемы, определяемой позицией (t, h(t)).

Будем говорить, что для СДОЗ выполняется принцип оптимальности Беллмана или что оно является (слабо) динамически устойчивым, если все его оптимальные траектории являются динамически устойчивыми.



Определение 4. Будем называть позиционное (программно-адаптивное) управление s позиционно динамически устойчивым [4] в СДОЗ, если оно также является оптимальным в задаче для каждой подсистемы D(x, t).

Замечание. Из определения следует, что оно также является позиционно динамически устойчивым в задаче для каждой подсистемы.

Определение 5. Пусть дано некоторое СДОЗ на пространстве X с временем T. Тогда рекуррентное управление, соответствующее принципу оптимальности Sel - это позиционное управление u(x, t), удовлетворяющее следующим рекуррентным соотношениям:



(4).

Иначе говоря, на каждом шаге мы решаем одномерную подзадачу исходной многомерной задачи. Например для обычной оптимизационной задачи нужно заменить Self на оператор максимизации arg max.

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

Теорема 1 (о связи принципов динамической устойчивости).


  1. Если позиционное управление позиционно динамически устойчиво, оно порождает динамически устойчивые (но не обязательно динамически совместимые) траектории.

  2. Если позиционное управление позиционно динамически устойчиво и выполняется аксиома независимости от посторонних альтернатив, то оно рекуррентно.

Доказательство. 1. Следует из того, что оптимальное управление порождает оптимальную траекторию. А позиционно динамически устойчивое управление оптимально для всех подсистем.

2. Действительно, позиционно динамически устойчивое управление на каждом шаге доставляет оптимум для оптимизационной задачи из позиции (x, t). При этом оно принадлежит области определения одномерной подзадачи, а значит, по независимости от посторонних альтернатив, доставляет оптимум и для одномерной подзадачи.



Замечание. Даже для оптимизационной задачи с одним критерием можно привести простейшие контрпримеры СДОЗ с принципом оптимальности Беллмана, в которых не все рекуррентные управления оптимальны.

Пример. Рассмотрим управляемую динамическую систему с X = {1, 2, 3, 4}, T = {1, 2}, D(1) = 2, D(2) = {3, 4}, а целевой критерий (полезность) для основной задачи определяется так: f(1, 2, 3) = 1, f(1, 2, 4) = 2, а целевой критерий для подзадачи так: f(2, 3) = f(2, 4) = 1. В основной задаче оптимальна траектория (1, 2, 4), а в задаче для подсистемы оптимальны обе траектории. Это значит, что выполняется принцип Беллмана. Управление u(1, 1) = 2, u(2, 2) = 3 рекуррентно, но оно не является оптимальным, поскольку порождает неоптимальную траекторию (1, 2, 3). Причина - семейство задач не является естественным.

Теорема 2 (о динамической устойчивости обобщенного интегрального выигрыша).

Пусть R - строго слева линейно лево-упорядоченная полугруппа и любой критерий f(x) = f1(x1) * ... * fm(xm) - обобщенный интегральный выигрыш. Пусть принцип оптимальности – оптимумы Парето относительно лексикографических порядков для некоторых подмножеств множества критериев. Тогда для естественного семейства задач выполняется принцип оптимальности Беллмана.



Доказательство. Прежде всего, заметим, что полугруппа R для любого натурального n вкладывается в полугруппу Rn лексикографически упорядоченных векторов с покомпонентными операциями. При этом, если первая полугруппа была лево-упорядочена строго слева, то же верно и для второй полугруппы. А произведение линейно упорядоченных слева полугрупп - частично упорядоченная слева (покомпонентно) полугруппа с покомпонентными операциями, причем строгость порядка слева для произведения сохраняется. Таким образом, мы сводим задачу нахождения оптимума Парето относительно лексикографических порядков для некоторых подмножеств множества критериев к задаче нахождения максимальных элементов в строго слева упорядоченной полугруппе. Осталось доказать утверждение для такой полугруппы.

Рассмотрим произвольную оптимальную траекторию h = (x'1, x'2, ..., x'm). Ее оптимальность означает, что на ней достигается максимум выражения f1(x1) * f2(x2) * ... * fm(xm), т.е. оно недоминируемо в полугруппе Rk. Рассмотрим теперь любую ее подтраекторию (x't, x't+1, ... x'm) и докажем, что на ней достигается максимум целевой функции подзадачи ft(xt) * ... * fm(xm). Действительно, если бы существовала иная подтраектория (x't, x''t+1, ... x''m), на которой достигалось бы значение ft(x't) * ft+1(x''t+1)* ... * fm(x''m) > ft(x't) * ft+1 (x't+1) * ... * fm(x'm), это, по строгой слева лево-упорядоченности, означало бы, что f1(x'1) * ... * ft(x't) * ft+1(x''t+1) * ... * fm(x''m) > f1(x'1) * ... * ft(x't) * ft+1(x't+1) * ... * fm(x'm), что противоречит максимальности траектории (x'1, …, x'm).



Теорема 3 (о динамическом программировании для обобщенного интегрального выигрыша).

Пусть f(x) = f1(x1) *... * fm(xm) - обобщенный интегральный выигрыш.

1. Пусть R - лево-упорядоченная полугруппа, а принцип оптимальности - оптимум Парето. Тогда рекуррентные управления оптимальны и позиционно динамически устойчивы.

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



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

Дальше утверждение следует рекуррентных соотношений динамического программирования для упорядоченных полугрупп [1].

Для произвольных упорядоченных полугрупп без свойства строгости слева даже для одного критерия не выполняется принцип оптимальности Беллмана: существуют оптимальные траектории, конечные участки которых неоптимальны.

Пример 1. Рассмотрим управляемую динамическую систему на множестве X = {1, 2, 3, 4} с временем T = {1, 2, 3}, определяемую так: D(1) = 4, D(4) = {2, 3}. Пусть начальная вершина x1 = 1 и следует максимизировать минимальное значение на траектории: f(x1, x2, x3) = min(x1, x2, x3). Это обобщенный интегральный выигрыш на упорядоченной полугруппе (диоиде) (, min), который определяет естественное семейство функций выигрыша для подсистем: f(x2, x3) = min(x2, x3), f(x3) = x3. Существует всего 2 траектории основной системы: (1, 4, 2), (1, 4, 3) и на обеих достигается одинаковое (а значит, оптимальное) значение f = 1.

Но в подсистеме, начинающейся в точке 4, оптимальной будет только одна подтраектория (4, 3), вторая - (4, 2) - неоптимальна. Следовательно первая траектория является динамически устойчивой, а вторая нет. Принцип Беллмана не выполняется.

Однако и для произвольной упорядоченной полугруппы всегда существует хотя бы одна динамически устойчивая траектория, которую, как следует из [1], можно найти рекуррентными соотношениями динамического программирования (РСДП). Таким образом, для интегрального выигрыша на упорядоченных полугруппах, если порядок - не строгий слева, выполняются рекуррентные соотношения динамического программирования, но может не выполняться принцип оптимальности Беллмана.

Пример 2. Пусть имеется 3 критерия A, B, C, и нужно найти по ним оптимумы Парето.

Пусть задана управляемая динамическая система на множестве X = {0, 1, 2, 3} с временем T = {0, 1, 2}, определяемая так: D(x) = {x-1, x, x+1}. Пусть начальная позиция x0 = 0 и следует максимизировать максимальное значение критерия на траектории: fi(x0, x1, x2) = max(gi(x0), gi(x1), gi(x2)) (то есть важен наилучший результат, достигнутый системой за время ее действия). Значит, принцип оптимальности Беллмана не выполняется, но все же оптимальные элементы можно найти динамическим программированием.

Пусть критерии таковы: gA(x) = 1/|x-1.5|, gB(x) = 1/|x-0.1|, gC(x) = 1/|x-4|. Будем искать оптимум методом динамического программирования. В момент времени t=2 позиции x = 0, 1, 2, 3 доставляют, соответственно, значения критериев

(gA, gB, gC)(0) = (2/3, 10, 1/4) (5)

(gA, gB, gC)(1) = (2, 10/9, 1/3)

(gA, gB, gC)(2) = (2, 10/11, 1/2)

(gA, gB, gC)(3) = (2/3, 10/21, 1).

Рассмотрим теперь момент времени t = 1. В позиции x = 0 наиболее выгодно сдвинуться в позицию x = 1, получив вектор (gA, gB, gC) = (2, 10, 1/3). В позиции x = 1 - либо в позицию x = 0, получив (gA, gB, gC) = (2, 10, 1/3), либо в позицию x = 2, получив (gA, gB, gC) = (2, 10/9, 1/2). В позиции x = 2 - либо в позицию x = 1, получив (gA, gB, gC) = (2, 10/9, 1/2), либо в позицию x = 3, получив (gA, gB, gC) = (2, 10/11, 1). Наконец, в позиции x=3 наиболее выгодно сдвинуться в x = 2, получив (gA, gB, gC) = (2, 10/11, 1).

Рассмотрим, наконец, момент времени t=0. В позиции x = 0 наиболее выгодно сдвинуться в x = 1, а оттуда - в x = 2, получив на последнем шаге (gA, gB, gC) = (2, 10, 1/2). В позиции x = 1 - либо вернуться в x = 0, получив в итоге (gA, gB, gC) = (2, 10, 1/3), либо - в x = 2, а оттуда - в x = 3, получив в итоге (2, 10/9, 1). В позиции x = 2 - либо перейти в x = 1, а оттуда - в x = 0, получив в итоге все те же (gA, gB, gC) = (2, 10, 1/2), либо - в x = 3, получив (gA, gB, gC) = (2, 10/11, 1). Наконец, в позиции x = 3 наиболее выгодно переместиться в x = 2, а оттуда - в x = 1, получив в итоге (gA, gB, gC) = (2, 10/9, 1).

Итак, траектории, оптимальные по Парето - (0, 1, 2), (1, 0, 1), (1, 0, 0), (1, 2, 3), (2, 1, 0), (2, 3, 2), (2, 3, 3), (3, 2, 1) - всего 8 траекторий из 26 возможных.



Пример 3. Пусть имеется 3 критерия A, B, C, причем A важнее B, A важнее C, но B и C несравнимы. Можно интерпретировать эти критерии как, допустим, способность некой фирмы расплатиться с долгами и выйти на два рынка. Отсутствие долгов всегда приоритетнее выхода на рынок, но у фирмы нет данных, позволяющих решить, какой из двух рынков важнее. Тогда оптимум - это оптимум Парето относительно лексикографически упорядоченных критериев (fA, fB) и (fA, fC).

Пусть задана та же управляемая динамическая система и те же критерии gA, gB, gC, что и в предыдущем примере (x можно интерпретировать, например, как количество товара для 2-го рынка, производимого фирмой). Пусть следует максимизировать сумму критериев на траектории. Вещественные числа относительно суммы образуют группу, т.е. сильно упорядоченную полугруппу, а потому лексикографические оптимумы можно искать методом динамического программирования.

Будем искать оптимум методом динамического программирования. В момент времени t=2 позиции x = 1, x = 2, доставляющие, соответственно, вектора ((2, 10/9), (2, 1/3)) и ((2, 10/19),(2, 1/2)), между собой несравнимы, но оба доминируют позицию x = 0, доставляющую вектор ((2/3, 10), (2/3, 1/4)), и позицию x = 3, доставляющую вектор ((2/3, 10/29), (2/3, 1)).

В момент времени t=1 в позиции x=0 наиболее выгодно перейти в позицию x=1, получив ((8/3, 100/9), (8/3, 7/12)); в позиции x=1 — либо остаться в x=1, получив ((4, 20/9), (4, 2/3)), либо перейти в x=2, получив ((4, 280/171), (4, 5/6)); в позиции x=2 — перейти в 1, получив ((4, 280/171), (4, 5/6)), либо остаться в 2, получив ((4, 20/19), (4, 1)); в позиции x=3 — перейти в x=2, получив ((8/3, 480/551), (8/3, 3/2)). Опять же, выигрыши в позициях 1 и 2 доминируют выигрыши в позициях 0 и 3, но не доминируют друг друга. Следовательно, по динамической устойчивости, и в момент времени t=0 наиболее выгодно переходить в позиции 1 и 2, причем неважно, в какую из них. Следовательно, оптимальные траектории — (0, 1, 1), (0, 1, 2), (1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2), (3, 2, 1), (3, 2, 2) — 12 траекторий из 26 возможных.



Пример 4. Пусть имеются 3 критерия A, B, C, которые сравниваются так же, как и в предыдущем примере. Но пусть при этом следует максимизировать максимальное значение на траектории. Полугруппа (ℝ, max) не является сильно упорядоченной, поэтому оптимум Парето относительно лексикографически упорядоченных критериев нельзя найти динамическим программированием. Но любой оптимум Парето относительно лексикографически упорядоченных критериев является оптимумом Парето относительно всех критериев, поэтому можно найти нужные оптимумы, перебирая 8 оптимумов по Парето, найденных в примере 2. Но, поскольку максимальное значение первого критерия x = 2 достигается на всех оптимальных траекториях, получается, что они все оптимальны и относительно указанного лексикографического порядка на критериях.

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

Список литературы.

1. Авдошин С.М., Белов В.В. Обобщенный метод «волны» для решения экстремальных задач на графах. - ЖВМ и МФ, АН СССР, 1979, т. 19, № 3, с. 739—755.

2. Беллман Р. Динамическое программирование. Пер. с англ. И.М. Андреева, А.А. Корбут И. В. Романовский, И. Н. Соколова, под ред. Н. Н. Воробьева. - М.: Издательство иностранной литературы, 1960.- 399 c.

3. Петросян Л.А, Кузютин Д.В. Игры в развернутой форме: оптимальность и устойчивость. - Изд.-во Санкт-Петербургского университета, 2002.



4. Смолин Е.А. Принцип позиционной динамической устойчивости и его применение в системах со многими управлениями. // Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. - Красноярск, 2007.


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница