Митина_P. Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор. 7730569363023
 Скачать 0.63 Mb.
|
|
4. Методы агрегации целевых функций В данном случае целевые функции агрегируют (сворачивают) в один параметризованный скалярный критерий, который выступает в роли фитнесс-функции. Рассматриваем следующие методы данного класса: метод взвешенных критериев; метод идеальной точки; адаптивный метод взвешенных сумм. 4 .1. Метод взвешенных критериев Теоретической основой метода взвешенных критериев (Sum of Weighted Objectives, SWO) является следующая известная теорема [1, 2]. Теорема 1. Если для некоторых весовых множителей 0 > k λ , ] : 1 [ F k ∈ имеет место равенство ( ) ∑ ∑ = = ∈ = F k k k F k k k D X X f X f X 1 * 1 ) ( λ λ min , (2) где X D X ∈ * , то вектор * X оптимален по Парето. Доказательство. Пусть вектор * X не оптимален по Парето. Тогда существует такой вектор X D X ∈ , что ) ( ) * X f X f k k ≤ , ] : 1 [ F k ∈ , причем хотя бы одно из неравенств является строгим. Умножая каждое из последних неравенств на 0 > k λ и складывая, получим http://technomag.edu.ru/doc/363023.html 9 ( ) ( ) ∑ ∑ < = = F k k k F k k k X f X f 1 * 1 λ λ , что противоречит условию теоремы● Теорема 1 показывает, что выбор определенной точки из множества Парето эквивалентен указанию весов для каждого из частных критериев оптимальности. Важно, что теорема задает лишь необходимое условие оптимальности по Парето вектора X D X ∈ * . Т.е. из того факта, что точка * X принадлежит множеству Парето, не следует, что эта точка обязательно удовлетворяет условию (2) – случай невыпуклого множества * F D ( рисунок 4). Рисунок 4 – Невыпуклый фронт Парето: 2 = F ; дуга AB - фронт Парето * F D В качестве фитнесс-функции в методе взвешенных критериев используем функцию ∑ = = Λ = F k k k X f F X 1 ) ( ) , ( ) ( λ ϕ ϕ , где ) 1 ( × F - вектор ) ..., , , ( 2 1 F λ λ λ = Λ Основным недостатком метода является невозможность с его помощью локализовать точки фронта Парето, принадлежащие его невыпуклой части (дуга CD на рисунке 4). Метод широко используется для построения не популяционных алгоритмов Парето- аппроксимации, схема которых состоит из двух следующих основных шагов. 77-30569/363023 , №04 апрель 2012 г. http://technomag.edu.ru 10 1) Множество ]) : 1 [ , 1 0 | ( F i D i ∈ ≤ ≤ Λ = Λ λ допустимых значений вектора весовых множителей ) ,..., , ( 2 1 F λ λ λ = Λ покрываем некоторой сеткой с узлами ) ,..., , ( , , 2 , 1 j F j j j λ λ λ = Λ , ,... 2 , 1 = j 2) При каждом j Λ решаем задачу глобальной условной оптимизации (2) – получают точку * * X j D X ∈ 4 .2. Метод идеальной точки Идеальной называют точку в пространстве критериев ) ,..., , ( * * 2 * 1 * * F f f f F = , где ) ( min ) ( * * X f X f f k D X k k k X ∈ = = , ] : 1 [ F k ∈ В качестве фитнесс-функции в этом случае используют функцию ) , ( ) ( * * F F X ρ ϕ = , (3) где ) , ( ⋅ ⋅ ρ - некоторая метрика пространства } {F , например, чебышевская метрика [17] ( ) ) ( max ) , ( * ] : 1 [ * * k k k F k f f abs F F − = ∈ λ ρ , 0 > k λ Здесь ) ( ⋅ abs - символ абсолютного значения числа. Метод идеальной точки иллюстрирует рисунок 5, показывающий, что, в отличие от метода взвешенных критериев, данный метод позволяет отыскивать точки, лежащие на невыпуклой части фронта Парето. Заметим, что свертка на основе идеальной точки (3) близка к свертке Гермейера [17]. http://technomag.edu.ru/doc/363023.html 11 Рисунок 5 – К методу идеальной точки: 2 = F ; дуга AB - фронт Парето Метод может быть использован для построения не популяционных алгоритмов Парето-аппроксимации. Задачу Парето-аппроксимации в этом случае сводят к многократному решению задачи глобальной оптимизации ) , ( ) , ( min * * * * * F F F F X D X ρ ρ = ∈ при различных допустимых значениях компонентов вектора весов ) ,..., , ( 2 1 F λ λ λ = Λ по схеме, близкой к схеме, приведенной в предыдущем пункте. 4 .3. Адаптивный метод взвешенных сумм Адаптивный метод взвешенных сумм (Adaptive Weighted Sum Method, AWSM) предложили Рю, Ким и Ван (J-H. Ryu, S. Kim, H. Wan) в 2009 г. [18]. Целью разработки метода было преодоление указанного выше ограничения метода взвешенных критериев, заключающегося в невозможности отыскания точек, принадлежащих невыпуклым частям фронта Парето. Метод не является популяционным. Мы включаем его в обзор вследствие новизны и высокого потенциала развития. Метод разработан для двухкритериальной задачи ( 2 = F ) и включает в себя три следующие основные процедуры: • определение центральной точки; • формирование метамоделей частных критериев; • решение полученных оптимизационных задач. Рассмотрим суть указанных процедур. 77-30569/363023 , №04 апрель 2012 г. http://technomag.edu.ru 12 Определение центральной точки. На этапе инициализации центральная точка 0 C X выбирается случайным образом в области X D . На этом же этапе должны быть определены следующие свободные параметры метода: δ δ = 0 - начальный радиус области доверия (trust region radius); ) 1 ; 0 ( ∈ ρ - коэффициент сужения области доверия; min δ - минимальная величина радиуса области доверия. На итерации 1 + t центральная точка С X ′ отыскивается среди точек текущей Парето- аппроксимации t X X A A = , построенной на предыдущей итерации t Отсортируем элементы архивных множеств F X A A , по возрастанию первого частного критерия оптимальности ) ( 1 X f и представим в виде линейных списков с прежними наименованиями. Определим расстояние j d архивной точки A j F до ближайших к ней в списке F A точек формулой | || || =|| 1 1 A j A j A j A j j F F F F d + − − + − , A j < < 1 , (4) где || || ⋅ - символ евклидовой нормы. Метод использует следующее правило определения центральной точки C X ′ 1) Если 2 > A , то полагаем A j C X X * = ′ , где [ ] ∉ = − ∈ T A j j A j X X d j | max arg ) 1 ( : 2 * Здесь T X - множество точек, использованных в качестве центральных на всех предыдущих итерациях ] : 0 [ t Иными словами, за центральную точку принимаем точку, во-первых, наиболее удаленную от других точек множества X A в смысле расстояния (4), и, во-вторых, не использованную на предшествующих итерациях. 2) Если 2 = A , то с равной вероятностью полагаем A C X X 1 = ′ или A C X X 2 = ′ 3) Если 1 = A , то принимаем A C X X 1 = ′ Формирование метамоделей. Метамодели представляют собой квадратичные аппроксимации ) ( 1 X m′ , ) ( 2 X m′ функций ) ( 1 X f , ) ( 2 X f в окрестности точки C X ′ : ) ( ) ( ) ( 2 1 ) ( ) ( ) ( = ) ( ; ) ( ) ( ) ( 2 1 ) ( ) ( ) ( = ) ( 2 2 2 2 1 1 1 1 C C T C C C T C C C T C C C T C X X X H X X X X X G X f X m X X X H X X X X X T G X f X m ′ − ′ ′ − + ′ − ′ + ′ ′ ′ − ′ ′ − + ′ − ′ + ′ ′ Здесь T - символ транспонирования; ) ( ), ( 2 1 C C X G X G ′ ′ - градиенты функций ) ( 1 X f , http://technomag.edu.ru/doc/363023.html 13 ) ( 2 X f в точке C X ′ соответственно; ) ( ), ( 2 1 C C X H X H ′ ′ - матрицы Гессе этих функций. Если 2 > A , то дополнительно строим метамодели ) ( ) ( ) ( 2 2 1 1 X m X m X m p p p ′ + ′ = ′ λ λ , ) ( ) ( ) ( 2 2 1 1 X m X m X m q q q ′ + ′ = ′ λ λ , а если 2 = A или 1 = A - метамодель ) ( ) ( ) ( 2 2 1 1 X m X m X m p p p ′ + ′ = ′ λ λ В первом случае ( 2 > A ) весовые множители p p p Λ = ) , ( 2 1 λ λ , q q q Λ = ) , ( 2 1 λ λ определяем по правилу ( ) )) ( ) ( ( )), ( ) ( ( 1 1 1 1 2 2 * * A j A C A j A C p p X f X f X f X f c − − − + − = Λ , ( ) )) ( ) ( ( )), ( ) ( ( 1 1 1 2 1 2 * A C A j A C A j q q X f X f X f X f c − + − = Λ + + ∗ ; во втором случае ( 2 = A ) – по правилу ( ) )) ( ) ( ( )), ( ) ( ( 1 1 2 1 1 2 2 2 A A A A p p X f X f X f X f c − + − = Λ ; в третьем случае (когда 1 = A ) – по правилу ( ) 5 , 0 , 5 , 0 = Λ p Константы p c , q c выбираем таким образом, чтобы обеспечить выполнение условий нормировки 1 = = 2 1 2 1 q q p p λ λ λ λ + + Отметим, что при построении метамоделей ) ( 1 X m′ , ) ( 2 X m′ речь может идти не о градиентах и матрице Гессе функций ) ( 1 X f , ) ( 2 X f , а об их оценках, полученных, например, численными методами (путем соответствующих конечно-разностных аппроксимаций указанных функций). Решение оптимизационных задач. Данная процедура предполагает решение задач оптимизации ), ˆ ( ) ( min 1 1 1 X m X m C D X ′ ′ = ′ ′ ∈ ), ˆ ( ) ( min 2 2 2 X m X m C D X ′ ′ = ′ ′ ∈ (5) где текущая область доверия C D′ определяет формула } , | { δ ≤ ′ − ∈ = ′ C X C X X D X X D Если 2 > A , то решения 2 1 ˆ , ˆ X X ′ ′ задач (5) позволяют отыскать приближенно 77-30569/363023 , №04 апрель 2012 г. http://technomag.edu.ru 14 оптимальные по Парето точки q p X X ′ ′ ˆ , ˆ , принадлежащие области доверия C D′ , путем решения оптимизационных задач ), ˆ ( ) ( min p p p D X X m X m C ′ ′ = ′ ′ ∈ ) ˆ ( ) ( min q q q D X X m X m C ′ ′ = ′ ′ ∈ . (6) Данный этап метода AWSM иллюстрирует рисунок 6, на котором принято что ) ( C C X F F ′ = ′ , ) ( 1 1 * * A j A j X F F − − = , ) ( 1 1 * * A j A j X F F + + = Отметим, что задачи (5), (6) представляют собой задачи оптимизации квадратичных функций, для решения которых известны высокоэффективные методы, алгоритмы и соответствующее программное обеспечение. Рисунок 6 – К схеме адаптивного метода взвешенных сумм: результаты решения задач (6) В процессе итераций текущий радиус области доверия уменьшают по правилу δ ρ δ = до достижения минимально допустимой его величины min δ Новое состояние архивного множества X A′ получаем путем добавления в текущее множество X A точек 1 ˆ X ′ , 2 ˆ X ′ , p X ′ ˆ , q X ′ ˆ и исключения из полученного набора доминируемых решений. Множество F D′ образуют точки, соответствующие построенному множеству X A′ 5. Методы на основе ранжирования агентов популяции Основным понятием методов данного класса является понятие ранга агента популяции. Известно несколько правил вычисления рангов. Ниже рассмотрены основные из http://technomag.edu.ru/doc/363023.html 15 этих правил, используемые в методе недоминируемой сортировки, методе Парето-силы, а также в некоторых других методах. 5.1. Недоминируемая сортировка Метод недоминируемой сортировки (Non-Dominated Sorting, NDS) впервые был опубликован в работе Шриниваса (N. Srinivas) и Деба (K. Deb) в 1994 г. [19]. Метод лежит в основе широко известного генетического алгоритма Парето-аппроксимации NGSA (Non- Dominated Sorting Genetic Algorithm) [21]. Положим, что все частные критерии оптимальности являются одинаково важными. Ранг агента i s , ] : 1 [ S i ∈ в его текущем положении i X обозначаем i r . В методе NDS используется простейшее из правил вычисления рангов, имеющее следующий вид (рисунок 7). 1) Выбираем среди всех агентов популяции недоминируемых, присваиваем им ранг, равный единице, и исключаем из дальнейшего рассмотрения. 2) Среди оставшихся агентов выбираем недоминируемых, присваиваем им ранг, равный двум, и исключаем из дальнейшего рассмотрения. И так далее до исчерпания популяции. Ранг индивида легко использовать для вычисления его приспособленности, например, по формуле вида i i r X + = 1 1 ) ( ϕ , ] : 1 [ S i ∈ Рисунок 7 – К определению понятия ранга агента: 2 = F Предтечей метода недоминируемой сортировки можно, вероятно, считать метод MOGA (Multi-Objective Genetic Algorithm ), предложенный Фонсека (C. M. Fonseca) и 77-30569/363023 , №04 апрель 2012 г. http://technomag.edu.ru 16 Флемингом (P. J. Fleming) в 1993 г. [10]. В методе предполагается, что ранг агента равен числу агентов в популяции, которые его доминирует. Заслуживает также упоминания Парето генетический алгоритм с нишеванием (Niched-Pareto Genetic Algorithm, NPGA), предложенный Хорном (J. Horn) c соавторами в 1994 г. [20]. Как отмечалось выше, важнейшим требованием к методам и алгоритмам Парето- аппроксимации является требование обеспечения равномерности покрытия множества и фронта Парето. Для оценки равномерности покрытия может быть использована величина, называемая разреженностью (scarcity), имеющая смысл минимального расстояния между решениями, принадлежащими Парето-аппроксимации. Указанное расстояние может быть измерено с помощью различных метрик, например, с помощью известного манхеттеновского расстояния (Manhattan distance). Развитием метода недоминируемой сортировки является метод, в котором при формировании архивов F X A A , отвергают агентов, расстояние которых до других агентов в архиве не превышает заданной величины. Такой модифицированный метод положен в основу генетического алгоритма Парето- аппроксимации NGSA-II (Non-Dominated Sorting Genetic Algorithm II) [21]. |