Автоматика и телемеханика, № 6, 2014
Системный анализ и исследование
операций
© 2014 г. Ю.Г. ЕВТУШЕНКО, акад. РАН (evt@ccas.ru) (Вычислительный центр им. А.А. Дородницына РАН, Москва), М.А. ПОСЫПКИН, канд. физ.-мат. наук (mposypkin@gmail.com) (Институт проблем передачи информации им. А.А. Харкевича РАН, Москва, Вычислительный центр им. А.А. Дородницына РАН, Москва)
МЕТОД НЕРАВНОМЕРНЫХ ПОКРЫТИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ С ЗАДАННОЙ ТОЧНОСТЬЮ1
Работа посвящена применению метода неравномерных покрытий для решения задач многокритериальной оптимизации. Определяется множество е-Парето и исследуются его свойства. Описан алгоритм построения множества е-Парето с гарантированной заданной точностью е. Обсуждаются вопросы эффективной реализации данного подхода и приводятся результаты экспериментов.
1. Введение
В настоящее время опубликовано большое число работ по многокритериальной оптимизации. Общую информацию по методам решения таких задач можно найти в монографиях [1—3]. Подробный обзор современного состояния исследований по этой теме можно найти в [4]. Одним из важных направлений в многокритериальной оптимизации являются методы, основанные на аппроксимации множества Парето [2, 5-10]. Есть также и другие подходы к решению задач многокритериальной оптимизации, представленные в работах [12-15].
В данной работе рассматривается подход к аппроксимации множества Парето, основанный на методе неравномерных покрытий. Этот метод успешно использовался для поиска глобального экстремума функций многих переменных. Его развитию, обобщению и эффективной реализации посвящено большое число публикаций. Укажем первую из них [11] и некоторые из последних [16-20]. В [8] метод был перенесен на многокритериальные задачи, благодаря удачному определению понятия множества е-Парето.
Метод неравномерных покрытий позволяет получать множество е-Парето для заданного е, т.е. гарантирует е-оптимальность получаемой аппроксима-
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты №№ 11-01-12136-офи-м 10-07-00700-а, 10-07-00640-а).
ции. Эта особенность метода неравномерных покрытий является уникальной и отсутствует в других подходах к решению задач многокритериальной оптимизации. Для некоторых применений задач многокритериальной оптимизации иметь гарантированную точность решения очень важно. К такому классу относится, например, задача построения границы области достижимости робота-манипулятора [21].
В данной работе доказываются новые свойства множества е-Парето, показана его связь с оболочкой Эджворта-Парето. Первоначальный вариант метода, предложенный в [8], применялся в предположении, что функции критериев удовлетворяют условию Липшица. В данной работе метод неравномерных покрытий для многокритериальных задач обобщен на случай произвольных минорант. Проведен сравнительный анализ численных расчетов двух простейших задач, показывающий эффективность предложенного подхода.
В работе используются следующие обозначения. Компоненты n-мерного вектора x обозначаются верхним индексом, заключенным в круглые скобки: х = (ж^, ... Через ||ж|| обозначается евклидова норма в пространстве R": ||ж|| = 'Ya=i(x^)2• Запись |ж| обозначает вектор |,..., |), составленный из абсолютных величин компонент x. Векторные неравенства выполняются покомпонентно.
2. Определение Парето-оптимального решения многокритериальной задачи
Задача многокритериальной минимизации условно записывается в виде
(1) min F (x),
x€X
где X - допустимое множество параметров, а вектор-функция F(■) : Rn — Rm определяет векторный критерий, компоненты которого f (1)(-),..., f (m)(-) составляют набор из m скалярных критериев. Образ Y = F(X) допустимого множества X при отображении F назовем множеством достижимых критериальных векторов. Всюду далее вектор-функция F(■) предполагается непрерывной, а множество X - непустым компактом. При сделанных предположениях множество Y также будет непустым компактом.
Для произвольной точки z € Rm определим юго-западное SW(z) и северовосточное NE(z) множества следующим образом:
SW(z) = {y € Rm : y < z}, NE(z) = {y € Rm : y ^ z}.
Для произвольного множества Q С Rm определим его множество Парето P(Q) следующим образом:
(2) P(Q) = {ш € Q : Q П SW(w) = ш}.
Если в качестве Q взять множество достижимых критериальных векторов Y, то данное определение совпадает со стандартным определением множества Парето, принятым в работах по многокритериальной оптимизации.
Для определенного таким образом отображения Р : ^ 2кт справедливо следующее соотношение, выполняющееся для любого О С Мт:
(3) Р (Р(О)) = Р(О) С О.
Расширим определения SW(z), КЕ(^) на случай произвольного множества О С Мт:
SW(О) = Ц,е^(у), КЕ(О) = иуепКЕ(у).
Множество КЕ(О) называют оболочкой Эджворта-Парето множества О. Несложно показать справедливость следующего свойства, верного для любого непустого компактного множества О в пространстве Мт:
(4) О С КЕ (Р(О)) = КЕ(О).
Решение задачи (1) состоит в нахождении множества Р (У) и его прообраза при отображении ^. Приведенные определения не накладывают ограничений на мощность множества X. Оно может быть континуальным, счетным или конечным. Так как множество У является непустым компактом, то Р(У) не пусто [3].
3. Понятие множества е-Парето
Следуя [8], определим понятие приближенного решения задачи (1). Для е ^ 0 дискретный набор точек Уе СУ будем называть множеством е-Парето, если:
(5)
для любой точки у* € Р(У) существует такая точка уе € Уе, что уе - е ■ ет ^ у*,
(6) Р (Уе) = Уе.
Здесь вектор ет обозначает вектор из пространства Мт, все компоненты которого равны 1.
Соотношения (5), (6) будем называть первым и вторым условиями е-оп-тимальности по Парето соответственно. Второе условие позволяет отбросить излишние точки из дискретного набора точек Уе. Множество Ае С X такое, что ^(Ае) = Уе, называется е-оптимальным решением задачи (1).
Считаем, что задача (1) решена с заданной точностью е, если найдено множество е-Парето Уе и его прообраз Ае.
Лемма 1. Если построено множество е-Парето Уе, то для любой точки у из оболочки Эджворта-Парето КЕ(У) найдется такая точка уе € Уе, что
и
(7)
уе - еет ^ у.
Доказательство. Пусть y € NE(Y). Согласно (4) найдется точка y* € € P(Y) такая, что y* ^ y. Согласно (5) для точки y* найдется такая точка y£, что y£ — еет ^ y*. Таким образом, y£ — еет ^ y* ^ y и, следовательно, неравенство (7) имеет место.
Из (5) следует, что множество е-Парето является одновременно множеством ё-Парето для любого е, е ^ е. В частности, V(Y) является множеством е-Парето для любого е ^ 0. Следовательно, при сделанных предположениях о компактности и непустоте Y при любом е ^ 0 всегда существует хотя бы одно множество е-Парето. Множество е-Парето определяется однозначно только при е = 0. В этом случае оно совпадает с P(Y). При е > 0, вообще говоря, может быть сколь угодно много множеств, удовлетворяющих введенному определению.
Обозначим через d(NE(Y)) границу множества NE(Y). Рассмотрим множество
S£(Y) = Y П UyeS(NE(Y))SW(y + еет), которое будем называть е-полосой множества Y.
Утверждение 1. Для любого множества е-Парето Y£ справедливо включение
(8) Y£ С S£(Y).
Доказательство. Пусть включение (8) не выполняется. Это означает, что существует е-Парето множество Y£, содержащее точку y£, не принадлежащую е-полосе. Несложно показать, что в этом случае точка y = y£ — еет является внутренней точкой множества NE(Y). Согласно (4) найдется такая точка y* из P (Y), что y* ^ y. Так как y* - граничная точка Y, а y - внутренняя, то y* = y. По определению множества е-Парето найдется такая точка v € Y£, что
v — еет ^ y* ^ y = y£ — еет.
Отсюда следует, что v ^ y£. При этом v = y£. Получили противоречие со вторым условием оптимальности P(Y^) = Y£.
Для любой точки u € Rm и множества V С Rm определим расстояние от точки u до множества V следующим образом: p(u, V) = infvey ||u — v||.
Отклонением непустого множества U С Rm от непустого множества V С Rm назовем величину
d(U, V) = sup p(u, V). ueu
Отклонение d(U, V) не является симметричным относительно перестановки аргументов, так как величины d(U, V) и d(V, U), вообще говоря, отличаются. Введем симметричное расстояние Хаусдорфа между двумя непустыми подмножествами U и V пространства Rm:
dn(U, V) = max (d(U, V),d(U,V)).
Рис. 1. Иллюстрация теоремы 1.
Теорема 1. При сделанных предположениях относительно множества Y справедливы следующие утверждения, связывающие оболочки Эджворта-Парето2 множества е-Парето и множества достижимых критериальных векторов:
(9) NE(Y£) С NE(P(Y)) = NE(Y) С NE(Y£ - е ■ em),
(10) dH(NE(Y£), NE(Y)) < dH(NE(Y£), NE(Y£ - е ■ em)) < е,
(11) dH(NE(Y), NE(Y£ - е ■ em)) < dH(NE(Y£), NE(Y£ - е ■ em)) < е.
Доказательство этих утверждений, проиллюстрированных на рис. 1, очевидно.
Содержательно теорема 1 означает, что при стремлении е к нулю, множества NE(Y) и NE(Y - е ■ em) стремятся (в метрике Хаусдорфа) к оболочке Эджворта-Парето NE(Y) множества достижимых критериальных векторов изнутри и снаружи множества Y (рис. 1). При этом множество P(Y) заключено между множествами NE(Y - е • em) и NE(Y), т.е.
P(Y) € (NE(Y£ - е ■ em) \ NE(Y£)) U Y£.
Установим теперь связь между е-Парето множеством и множеством Паре-то для задачи (1).
Лемма 2. Пусть y* € P(Y). Тогда для любого ö > 0 найдется такое е > 0, что для множества е-Парето Y£ выполняется неравенство
(12) p(y* ,Y£) < ö.
2 Идея использования оболочки Эджворта-Парето при решении многокритериальных задач принадлежит А.В. Лотову [22].
Доказательство. Рассмотрим стремящуюся к нулю монотонно убывающую последовательность (ек}, ек > 0, Нш^^ ек = 0. Предположим, что утверждение леммы неверно. Тогда для любого к существует множество ек-Парето Уек, такое что р(у*,Уек) > 5. По определению множества е-Парето найдется точка у к € У^к такая, что у к — ек ет ^ у*. В силу компактности множества У без ограничения общности можно считать, что последовательность (у к} сходится к точке у € У. Так как Иш^^, ек = 0 и у к — ек ет ^ у*, то у ^ у*. Так как р(у*, ) > 5 для каждого к, то р
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.