научная статья по теме ДЕКОМПОЗИЦИЯ ЗАДАЧИ АППРОКСИМАЦИИ ОБОЛОЧКИ ЭДЖВОРТА–ПАРЕТО Математика

Текст научной статьи на тему «ДЕКОМПОЗИЦИЯ ЗАДАЧИ АППРОКСИМАЦИИ ОБОЛОЧКИ ЭДЖВОРТА–ПАРЕТО»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 10, с. 1681-1693

удк 519.642.8

ДЕКОМПОЗИЦИЯ ЗАДАЧИ АППРОКСИМАЦИИ ОБОЛОЧКИ

ЭДЖВОРТА—ПАРЕТО1)

© 2015 г. А. В. Лотов

(119333 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: avlotov@mail.ru Поступила в редакцию 12.03.2015 г.

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

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

DOI: 10.7868/S0044466915100166

1. ВВЕДЕНИЕ

Рассматриваются задачи многокритериальной оптимизации (МКО), имеющие блочную структуру. Методы решения задач МКО на основе их декомпозиции были рассмотрены, например, в [1], [2]. Декомпозиция имеет смысл в том случае, когда система описывается большим числом подсистем, слабо связанных между собой. В данной статье предлагается метод декомпозиции, упрощающий задачу построения аппроксимации оболочки Эджворта—Парето (ОЭП), т.е. максимального (по включению) множества, имеющего ту же границу Парето, что и множество достижимых критериальных векторов задачи МКО. Впервые вопрос о декомпозиции при аппроксимации ОЭП был рассмотрен в [3] для линейных систем.

Введем основные понятия и обозначения. Как обычно в задачах МКО (см. [4], [5]), обозначим через X множество допустимых решений х е К", а векторы критериев выбора у, связанные с решениями соотношением y = f (х), будем считать элементами Кm. Пусть рассматривается задача многокритериальной максимизации, т.е. считается, что желательно увеличение значения каждого из критериев в отдельности (при равных значениях остальных критериев). В этом случае для точной формулировки задачи МКО можно использовать бинарное отношение Парето, в рамках которого критериальная точка y' более предпочтительна, чем точка у (говорят, что y' доминирует у по Парето), тогда и только тогда, когда y > y и y' Ф y. Тогда задача МКО записывается в условном виде

y = f(x) ^ max, х е X , (1.1)

а ее решением считаются недоминируемая граница (граница Парето) множества Y=f(X), определяемая как

P(7) = {y е Y : {y е Y : y' > y, y ф y} = 0}, (1.2)

1) Работа выполнена при финансовой поддержке РНФ (грант № 14-11-00432).

4

1681

1682

ЛОТОВ

и множество Р (X) с X, точки которого порождают Р (7) (множество решений, оптимальных по Парето). Под оболочкой Эджворта—Парето для задачи (1.1) имеется в виду множество

7р = {у е К™ : у < /(х), х е X}. (1.3)

Известно (см. [4], [5]), что Р (7р) = Р (7).

Вопрос об аппроксимации многомерной ОЭП возникает в методах МКО, использующих визуализацию многомерной границы Парето, в частности, в методе диалоговых карт решений/достижимых целей (ДКР/МДЦ) (см. [6], [7]). В ДКР/МДЦ визуализация границы Парето осуществляется в виде карт решений — наложенных одно на другое двумерных сечений ОЭП. При этом границы сечений 7р дают информацию о сечениях Р(У) (подробнее этот вопрос рассмотрен в [5]). Знание аппроксимации ОЭП позволяет быстро рассчитывать и изображать на дисплее всевозможные карты решений по требованию пользователя, а также анимировать карты решений. Карта решений дает наглядное представление о границе Парето для трех критериев, а быстрое изображение различных карт решений и их анимация позволяют оценить влияние остальных критериев. Пользователь получает представление о потенциальных возможностях выбора и о так называемых критериальных (или эффективных) замещениях, т.е. о связи величин критериев на границе Парето (разнообразные приложения описаны в книгах [6], [7]).

Преимущество аппроксимации 7р или У по сравнению с непосредственной аппроксимацией Р(У) состоит в том, что задача аппроксимации 7р (или У) обычно является корректной, в то время как граница Парето Р(У) часто бывает неустойчивой по отношению к возмущениям (см. [8]), что приводит к некорректности задачи ее непосредственной аппроксимации. Сравнивая подход на основе аппроксимации множества 7 с подходом на основе аппроксимации 7р, можно заметить, что структура границы ОЭП проще, чем структура границы множества 7 (это становится сразу ясно, если заметить, что 7р = 7 + К™, где К ™ — неположительный ортант). Благодаря этому факту, построение аппроксимации множества 7р и его визуализация являются более простыми задачами, чем те же задачи для У, и, что самое главное, доминируемые границы У, мешающие восприятию сечений У, накладываемых одно на другое, исчезают при переходе от У к 7р.

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

на N групп {х1,1}, где х' е X' с К"', г' е К", I = 1, ..., N. Множество X' допустимых значений переменных 1-й группы нижнего уровня х задается некоторыми ограничениями, которые составляют описание подсистемы нижнего уровня, I = 1, ..., N. Переменные 1-й группы верхнего уровня г'

связаны с переменными нижнего уровня заданными соотношениями г = ), I = 1, ..., N. Заданы координирующие соотношения верхнего уровня, которые можно представить в виде

£

N

I е 2, где 2 с К". Таким образом, соотношения модели имеют вид

и=1

N

х' е X', I = Е(х1), '' = 1,..., N, а также £г е 2. (1.4)

'■=1

Векторы критериев многокритериального выбора у связаны с переменными верхнего уровня заданным соотношением

у = /(г1,..., (1.5)

и являются элементами линейного пространства К ™. Обозначим через Умножество достижимых критериальных векторов (1.5) для модели (1.4), т.е.

7 = |у е К™ : у = / (г1,..., ^), где г'' = Я'(х'), х' е Г,1 = 1,..., N £ г' е (1.6)

Тогда граница Парето Р (7) задается тем же соотношением (1.2). Совокупность векторов нижне-

го уровня {х1,..., х1^}, порождающая такую совокупность векторов верхнего уровня {г\ ...,

N1

г }

что она порождает критериальную точку из Р (7), является оптимальным по Парето решением нижнего уровня. Множество таких решений, как принято, обозначим через Р (X) и будем называть множеством решений, оптимальных по Парето.

В рассматриваемой задаче многокритериальной максимизации (1.4), (1.5) множество Ур задается на основе множества достижимых критериальных векторов (1.6) таким же образом, как и в обычном случае, т.е. Ур = 7 + М", и может быть представлено более подробно в виде

7р = |у 6 К" : У < /(г\ ..., ^), где г1' = Е(х1), X е X', ' = 1,..., N £г' е (1.7) Введя обозначение

? = {г' е К" : г'' = gi(xi), X е X''}, (1.8) множество 7 р можно представить в виде

7р = |у 6 К" : У < /(г1,..., ^), где г' 6 г', ' = 1, ..., N £г' 6 г|. (1.9)

Отметим, что математические модели, использующиеся при формулировке задачи МКО (1.1), т.е. при описании множества X и вектор-функции у = / (х), могут быть заданы весьма различными способами. С одной стороны, они могут быть заданы в явном виде некоторыми формулами. В этом случае при аппроксимации ОЭП можно использовать методы, основанные на использовании каких-либо свойств этих соотношений, например, их постоянных Липшица и т.д. Другой край спектра возможных моделей (1.1) составляют математические модели типа черного ящика, для которых единственным доступным способом анализа является расчет выходного сигнала (в нашем случае — значение критериального вектора) по входному воздействию на него (в нашем случае — по варианту решения). В случае блочной модели (1.4), (1.5) черными ящиками могут оказаться несколько блоков модели (может быть, все блоки), а также модель расчета критериев. Методы аппроксимации ОЭП зависят от типа используемой математической модели.

Существующие методы аппроксимации ОЭП для задачи (1.1) естественно разбить на две большие группы в зависимости от того, выпукло ли множество Ур. В выпуклом случае используются методы полиэдральной аппроксимации ОЭП, основанные на расчете опорной функции. Способ расчета опорной функции при этом зависит от типа модели — для линейных моделей, например, при этом обычно решается задача линейного программирования, в которой в качестве единственного критерия оптимизации взята соответствующая скалярная функция (свертка) критериев. При этом могут использоваться два основных подхода к построению сверток — адаптивный и неадаптивный. Адаптивные методы из [6], [7], [9] состоят из итераций, на каждой из которых не только уточняется аппроксимация ОЭП, но и вырабатываются новые направления для расчета опорной функции Ур на следующей итерации. Одним из таких методов является метод уточнения оценок (УО), который пригоден как для аппроксимации многомерных выпуклых компактных тел, так и (в несколько измененном виде) при аппроксимации ОЭП. Метод был реализован в виде программного обеспечения, которое с успехом использовалось на практике в ряде прикладных систем поддержки принятия решений при нескольких критериях (см. [6], [7]). При аппроксимации компактных выпуклых тел метод УО оказался оптимальным по порядку скорости сходимости (см. [9]). Метод имеет и другие важные свойства: например, была показана его эффективность — были даны априорные оценки констант сходимости, которые оказались достаточно близки к оптимальным (см. [9]). В то же время, правильно построенные неадаптивные методы также имеют свои преимущества (см. [10]).

В невыпуклом случае ОЭП аппроксимируется множеством Тр = ^{у + : у е Т}, где Т —

конечное число точек множества У, называемых базой аппроксимации. Таким образ

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком