Митина_P. Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор. 7730569363023
 Скачать 0.63 Mb.
|
|
http://technomag.edu.ru/doc/363023.html 1 Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор. 77-30569/363023 # 04, апрель 2012 Карпенко А. П., Семенихин А. С., Митина Е. В. УДК.519.6 МГТУ им. Н.Э. Баумана apkarpenko@mail.ru saspost@yandex.ru mitinakaterina@gmail.com Введение Известно большое число методов решения задачи многокритериальной оптимизации (МКО-задачи), из числа которых перспективными являются методы, основанные на предварительном построении аппроксимации множества Парето (а тем самым, и фронта Парето) этой задачи [1, 2]. Простейшим из таких методов является сеточный метод [3]. В ситуации, когда требуется высокая точность аппроксимации множеств Парето и/или когда имеет место высокая вычислительная сложность целевых функций, сеточный метод может требовать неприемлемо высоких вычислительных ресурсов. Поэтому в настоящее время интенсивно развиваются альтернативные методы [4]. Обычно указанные методы строят на основе эволюционных алгоритмов и чаще всего – на основе генетических алгоритмов [5]. При этом соответствующие методы Парето- аппроксимации называют эволюционными. Обзор таких методов представлен, например, в работах [6, 7]. Принципиальным в этих методах является не использование именно эволюционных алгоритмов, а правила формирования фитнесс-функции, обеспечивающие перемещение индивидов популяции, в конечном счете, в направлении множества Парето. Эволюция же этих индивидов может протекать по законам, отличным от законов, используемых в эволюционных алгоритмах, например, по законам миграции частиц в алгоритме роя частиц [8, 9]. Поэтому в качестве общего названия рассматриваемых методов используем термин «популяционные методы Парето-аппроксимации». Для полноты картины, наряду с популяционными методами в работе рассматриваем наиболее известные не популяционные методы. Особенностью обзора является то, что в той его части, которая посвящена популяционным методам, мы концентрируем наше внимание, преимущественно, на правилах формирования фитнесс-функции, используемых в этих методах. 77-30569/363023 , №04 апрель 2012 г. http://technomag.edu.ru 2 Можно выделить следующие основные требования к методам Парето-аппроксимации [7]: - точки найденной аппроксимации расположены достаточно близко к точному множеству Парето; - аппроксимация покрывает все множество Парето; - распределение точек аппроксимации равномерно. В современных методах Парето-аппроксимации для выполнения последнего требования используют специальные механизмы, обеспечивающие приемлемый разброс (spread) точек аппроксимации. Наиболее известным механизмом такого сорта является механизм нишевания (niching) [10]. Самостоятельную проблему представляет разработка критериев оценки качества Парето-аппроксимации, которые отражали бы указанные требования. Примеры таких критериев рассмотрены, например, в работах [11, 12]. Известно несколько классификаций методов Парето-аппроксимации. Используем классификацию, предложенную Гуменниковой А. В. [13], дополнив ее классом «наивных» методов [14] и классом прочих методов. Итого рассматриваем следующие пять классов методов Парето-аппроксимации: - «наивные» методы; - методы переключающихся целевых функций; - методы агрегации целевых функций; - методы на основе ранжирования агентов популяции; - прочие методы. В разделе 1 приведена математическая постановка задачи, разделы 2 - 6 посвящены рассмотрению указанных классов методов Парето-аппроксимации. В заключении сформулированы основные выводы. 1. Постановка задачи и общая схема популяционных алгоритмов ее решения Совокупность частных критериев оптимальности (частных целевых функций) ), ( X f k |] :| [1 F k ∈ образует векторный критерий оптимальности (векторную целевую функцию) } { ) ( F X F ∈ , где } {X X ∈ - вектор варьируемых параметров; } {X , } {F - пространства параметров и критериев соответственно. Здесь и далее запись вида A , где A ─ некоторый вектор или счетное множество, означает размерность этих объектов. Положим, что ставится задача минимизации каждого из частных критериев в одной и той же области допустимых значений n X R D ⊂ Тогда во введенных обозначениях МКО-задачу условно можно записать в виде * * ) ( = ) ( min F X F X F X D X = ∈ , (1) где * * , F X - решения задачи. Полагаем, что частные критерии оптимальности нормализованы, например, по формуле http://technomag.edu.ru/doc/363023.html 3 |], :| [1 , ) ( = ) ( * * * * F k f f f X f X f k k k k k ∈ − − где ), ( min = * X f f k k ) ( max = * * X f f k k , X D X ∈ Векторный критерий оптимальности ) ( X F выполняет отображение области X D в некоторое множество F D , называемое множеством достижимости МКО-задачи (1). Введем на множестве X D отношение предпочтения . Будем говорить, что вектор X D X ∈ 1 предпочтительнее вектора X D X ∈ 2 и писать 2 1 X X , если среди равенств и неравенств ) ( ) ( 2 1 X f X f k k ≤ , |] :| [1 F k ∈ имеется, хотя бы одно строгое неравенство. Аналогично, на множестве F D введем отношение доминирования: будем говорить, что вектор F D X F ∈ ) ( 1 доминирует вектор F D X F ∈ ) ( 2 , и писать ) ( ) ( 2 1 X F X F , если 2 1 X X Выделим из множества F D подмножество * F D точек, среди которых нет доминируемых. Это множество называют фронтом Парето. Множество X X D D ∈ * , соответствующее множеству * F D , называют множеством Парето (переговорным множеством, областью компромисса). Определения множества и фронта Парето иллюстрирует рисунок 1. Поскольку множество F D на этом рисунке является выпуклым, фронт Парето * F D в данном случае представляет собой дугу AB , на которой точка A соответствует * 1 f , а точка B ─ * 2 f . Среди точек ) ( 1 X F , ) ( 2 X F , лежащих на фронте Парето, нет доминируемых, поскольку если ) ( < ) ( 2 1 1 1 X f X f , то обязательно ) ( > ) ( 2 2 1 2 X f X f Рисунок 1 - К определению множества Парето: 2 = X ; 2 = F 77-30569/363023 , №04 апрель 2012 г. http://technomag.edu.ru 4 Ставим задачу приближенного построения множества Парето (а, тем самым, и фронта Парето) в МКО-задаче (1). Называем эту задачу задачей Парето-аппроксимации. Пусть тем или иным образом уже сформировано архивное множество F A , содержащее не доминируемые точки A j F , а также архивное множество X A соответствующих ему точек ] : 1 [ ; A j X A j ∈ Здесь A - мощность множеств F A , X A Суть большинства популяционных методов Парето-аппроксимации состоит в итерационном уточнении множеств точек в архивах F A , X A . Если при этом на итерации t появляется новая точка i F , доминирующая некоторые точки из архива F A , то все доминируемые точки, а также соответствующие точки из архива X A , удаляем. При удовлетворении некоторого критерия останова текущее содержимое архивов F A , X A полагаем искомой аппроксимацией фронта Парето * F D и множества Парето * X D соответственно. В популяционных методах Парето-аппроксимации новые точки для архивов F A , X A «поставляет» популяция агентов i s , текущие координаты которых в пространстве поиска } {X равны i X , а в пространстве } {F - ] : 1 [ ); ( S i X F F i i ∈ = В популяционных оптимизационных алгоритмах миграция агентов в пространстве поиска подчинена задаче минимизации (для определенности) значений фитнесс-функции. Основной проблемой построения популяционных методов Парето-аппроксимации является построение фитнесс-функции ) ( X ϕ , обеспечивающей перемещение агентов популяции i s , ] : 1 [ S i ∈ в направлении множества Парето * X D , а соответствующих точек i F - в направлении фронта Парето * F D В силу, как правило, меньшей размерности критериального пространства } {F по сравнению с размерностью пространства поиска } {X , ответ на вопрос о направлении и шаге перемещения агентов обычно отыскивают в терминах критериального пространства, а не пространства параметров. Важно также, что относительно множества Парето, по сути, нет никой априорной информации, кроме того, что это множество точек, не связанных между собой отношением предпочтения . В то же время по отношению к фронту Парето априорной информации значительно больше. Например, с учетом того, что частные критерии оптимальности нормированы и поэтому ] : 1 [ ], 1 ; 0 [ ) ( F k X f k ∈ ∈ , имеет место Утверждение 1. Любой луч, проведенный из начала системы координат | | 2 1 0 F f f f в неотрицательном направлении осей , 0 1 f 2 0 f ,…, | | 0 F f пересекает фронт Парето не более чем в одной точке. Доказательство проведем от противного. Допустим, что утверждение неверно, и указанный луч пересекает фронт Парето в точках * 1 F , * 2 F В этом случае, по крайней мере, http://technomag.edu.ru/doc/363023.html 5 для одного ] : 1 [ F k ∈ должно быть справедливо неравенство * , 2 * , 1 k k f f < или неравенство * , 2 * , 1 k k f f > , что противоречит условию принадлежности точек * 1 F , * 2 F фронту Парето● Выделяют четыре класса задач Парето-оптимизации, соответствующих следующим четырем типам фронта Парето: выпуклые задачи; вогнутые задачи; выпукло-вогнутые задачи; разрывные задачи (рисунок 2). Рисунок 2 – Типы фронтов Парето ( 2 = F ): а) выпуклый; б) вогнутый; в) выпукло-вогнутый фронт; г) разрывный Одной из проблем популяционных методов Парето-аппроксимации является формирование начальных состояний архивов F A , X A . С этой целью может быть использован сеточный метод, суть которого состоит в следующем. Покрываем область X D некоторой сеткой с узлами i X , ] : [1 n i ∈ . В каждом из этих узлов вычисляем значение вектор-функции i F , среди векторов i F выбираем недоминируемые векторы } { A i j F и находим соответствующее им множество точек } { A i j X , где ) ( = A i A i j j X F F , ] : 1 [ A i j ∈ Множества } { A i j X , } { A i j F представляют собой искомую начальную дискретную аппроксимацию множества Парето и фронта Парето МКО-задачи (1) соответственно. Известным вариантом сеточного метода является метод исследования пространства параметров [15], особенностью которого является использование специальных сеток, построенных на основе так называемых τ ЛП последовательностей, обеспечивающих большую репрезентативность Парето-аппроксимации. 77-30569/363023 , №04 апрель 2012 г. http://technomag.edu.ru 6 2 . «Наивные» методы Данный класс методов выделяет Люк (S. Luke) в своей известной книге [14]. Простейшим методом данного класса является метод на основе лексикографической турнирной селекции (lexicographic tournament selection). Метод исходит из того, что частные критерии ] : 1 [ ), ( F k X f k ∈ упорядочены по важности, так что самым важным является критерий ) ( 1 X f , следующим по важности – критерий ) ( 2 X f и так далее. Рассмотрим правило сравнения приспособленностей агентов, используемое данным методом. Пусть j i S j i s s j i ≠ ∈ ], : 1 [ , , , - два сравниваемых агента в текущих состояниях j i X X , . Лучшего из этих агентов определяем путем последовательного сравнения пар величин ( ) ) ( ), ( j k i k X f X f , F k ...., , 2 , 1 = до тех пор, пока не будет установлено, что, например, ) ( ) ( * * j k i k X f X f < В таком случае полагаем, что агент i s имеет лучшую приспособленность по сравнению с агентом j s Лучшего агента S s best ∈ популяции в ее текущем состоянии ] : 1 [ , S i X i ∈ определяем в результате следующей последовательности шагов. 1) Выбираем случайного агента популяции 1 i s и полагаем его лучшим агентом, т.е. полагаем 1 i best X X = . Выполняем присваивание 2 = j 2) Выбираем другого случайного агента j i s 3) По указанному выше правилу определяем лучшего из агентов j i best s s , и объявляем его новым агентом best s 4) Если m j < (размер турнира m не исчерпан), то полагаем 1 + = j j и возвращаемся к шагу 2. Известен ряд модификаций рассмотренного метода. Так для выбора лучшего агента можно использовать случайный критерий из числа критериев ] : 1 [ , F k f k ∈ Можно использовать процедуру голосования, когда лучшим считается агент, которому соответствуют наименьшие значения наибольшего числа критериев. Наконец, можно использовать многоуровневую турнирную селекцию (в случае 2 > F ), когда основной турнир проводим на основании одного критерия, однако агентов для этого турнира отбираем с использованием турнира по другому критерию, агентов для этого турнира отбираем с использованием турнира по третьему критерию и т.д. 3. Методы переключающихся целевых функций В данных методах выбор лучших агентов популяции производится на основе сравнения соответствующих значений различных частных критериев оптимальности. Наиболее известным алгоритмом Парето-аппроксимации, основанном на методе http://technomag.edu.ru/doc/363023.html 7 переключающихся целевых функций, является алгоритм VEGA (Vector Evaluated Genetic Algorithm ), предложенный Шафером (D. Shaffer) в 1985 г. [16]. Пусть ] : 1 [ , S i X i ∈ текущие положения агентов популяции, где F S > и эти величины кратны. Пригодность агентов в алгоритме VEGA определяют по следующей схеме. 1) В соответствии с принятым правилом селекции, основываясь на фитнесс-функции ) ( ) ( 1 1 X f X = ϕ , выбираем F S лучших агентов, не исключая их из популяции. 2) Аналогично, основываясь на фитнесс-функции ) ( ) ( 2 2 X f X = ϕ , выбираем следующие F S лучших агентов. …. ) F Основываясь на фитнесс-функции ) ( ) ( X f X F F = ϕ , выбираем F S последних лучших агентов. В качестве правила селекции алгоритм VEGA использует правило рулетки, когда вероятность выбора агента i s пропорциональна его относительной приспособленности (если речь идет о максимизации целевых функций): ∑ ∈ j j i S j X X ] : 1 [ ), ( ) ( ϕ ϕ , ] : 1 [ S i ∈ Рассмотренную схему отбора иллюстрирует рисунок 3, на котором представлены проекции точек ] : 1 [ , S i F i ∈ на плоскость 2 1 0 f f пространства критериев } {F . Показаны множества агентов 2 1 , S S , отобранных на основе критериев оптимальности ) ( 1 X f , ) ( 2 X f соответственно (имеются в виду задача многокритериальной максимизации). 77-30569/363023 , №04 апрель 2012 г. http://technomag.edu.ru 8 Рисунок 3 – К схеме алгоритма VEGA |