Митина_P. Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор. 7730569363023

• Название: Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор. 7730569363023
• Дата: 30.04.2021
• Размер: 0.63 Mb.
• Имя файла: Митина_P.pdf
• Тип: Документы; #200474
• страница: 4 из 5

Утверждение 3. Предположим, что дерево доминирования предварительно тем или иным образом построено. Тогда поиск в архиве
X
A
точки, которая является лучшей для точки
i
X
, требует
)
|
|
(
2
F
C
O
⋅
сравнений.
Справедливость утверждения вытекает из того факта, что в изложенной схеме определения лучшей точки поиск композитной точки
j
C
требует
|)
|
(
F
C
O
⋅
, а выбор точки
A
j
p
F
- не более
|)
(| F
O
сравнений
•
6.3.
Метод гиперкубов
В основе метода гиперкубов, предложенного Коэлло (C.A. Coello) и Лечунга (M.S.
Lechunga) в 2002 г. [28], лежит процедура покрытия области достижимости
F
D
некоторой совокупностью гиперкубов и процедура назначения каждому из этих гиперкубов коэффициента пригодности. Рассмотрим данные процедуры.
Положим частные критерии оптимальности
)
(
,
),
(
),
(
|
|
2 1
X
f
X
f
X
f
F

нормированными, так что
]
:
1
[
],
1
;
0
[
)
(
F
k
X
f
k
∈
∈
,
X
D
X
∈
∀
Искомые гиперкубы строим путем разделения
|
| F
- мерного единичного гиперкуба
1]
;
[0 1]
;
[0 1]
;
[0 0
×
×
×
=
H
на
|
|F
n
гиперкубов с длиной ребра, равной
n
1
(рисунок 12),

77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
24 где натуральное число
n
- свободный параметр метода.
Пусть некоторый гиперкуб
]
:
[1
,
|
|
1
F
j
n
j
H
∈
включает в себя
j
m
архивных точек.
Пригодность этого гиперкуба принимаем равной величине
j
j
m
10
=
ϕ
. Если выбранный гиперкуб вообще не содержит точек архива, то происходит расширение области поиска, т.е. вводится в рассмотрение гиперкуб, который включает в себя гиперкуб
1
j
H
. Таким образом, пригодность каждого из построенных гиперкубов полагаем обратно пропорциональной числу архивных точек, которые находятся в нем, и гиперкуб, содержащий меньшее число этих точек, оказывается более пригодным (рисунок 12). Такое определение пригодности направлено на обеспечение более равномерной Парето-аппроксимации.
Рисунок 12 – Покрытие области
F
D
гиперкубами для двухкритериальной задачи:
4
=
n
;
•
– архивные точки
A
j
F
Если по рассмотренному правилу множество достижимости
F
D
покрыто гиперкубами и для каждого из гиперкубов определены их пригодности, то отыскание в архиве
X
A
точки, которая является лучшей для точки
i
X
, производится по следующей схеме.
1)
Если в гиперкубе
1
j
H
, в котором находится точка
i
X
, имеются архивные точки, то случайным образом с равной вероятностью выбираем одну из этих точек
A
j
i
F
2)
В противном случае выполняем следующие действия:

http://technomag.edu.ru/doc/363023.html
25
- расширяем зону поиска - рассматриваем все возможные гиперкубы
2
j
H
с длиной ребра равной
n
2
, которые включают в себя гиперкуб
1
j
H
;
- определяем пригодность гиперкубов
2
j
H
, как сумму пригодностей входящих в них гиперкубов
1
j
H
;
- из числа всех найденных гиперкубов
2
j
H
по правилу рулетки выбираем один из гиперкубов
2
*
j
H
;
- случайным образом с равной вероятностью выбираем одну из точек
A
j
i
F
этого гиперкуба.
3)
В качестве искомой лучшей точки принимаем соответствующую точку
A
j
i
F
Приведенную схему выбора лучшей точки иллюстрирует рисунок 12. Точка
i
F
на рисунке находится в гиперкубе
ABCD
. В этом гиперкубе нет ни одной архивной точки.
Поэтому в рассмотрение вводим гиперкубы
DMNP
CHKL
BEFG
,
,
. Пригодности этих гиперкубов равны 2; 2,3; 0,4 соответственно. По правилу рулетки выбираем, например, гиперкуб
BEFG
. В этом гиперкубе с равной вероятностью выбираем одну из архивных точек, например, точку, на которую на рисунке указывает стрелка.
6.4.
Метод динамических соседей
Метод динамических соседей предложили Хью (X. Hu) и Эберхарт (R. Eberhart) в 2002 г. [29]. Схему метода можно представить в следующем виде.
1)
Фиксируем все критерии оптимальности, кроме критерия
)
(
1
X
f
- полагаем этот критерий динамическим.
2)
Вычисляем в пространстве критериев
F
f
f
f
,...,
,
3 2
расстояния (например, евклидовы) от точки
i
F
,
]
:
1
[
S
i
∈
до всех архивных точек
]
:
1
[
,
A
j
F
A
j
∈
3)
Выбираем на этой основе
m
ближайших архивных соседей точки
i
F
, где
m
- свободный параметр метода.
4)
Из числа выделенных точек выбираем лучшую по критерию
)
(
1
X
f
5)
На следующей итерации полагаем динамическим критерий
)
(
2
X
f
, а все остальные критерии фиксируем. И так далее.
Авторы метода отмечают, что остается открытым вопрос об оптимальной величине числа
m
6.5.
Метод хищник-жертва
Метод хищник-жертва (predator-prey) предложил Лауманс (M. Laumanns) с соавторами в 1998 г. [30]. Рассматриваем оригинальный метод Лауманса и его основные модификации последних лет. Полагаем, что областью допустимых значений вектора

77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
26 варьируемых параметров является гиперпараллелепипед
])
:
1
[
,
|
(
X
i
x
x
x
X
D
i
i
i
X
∈
≤
≤
=
+
−
Каждая из жертв представляет собой один вектор решений, а каждый хищник - один критерий оптимальности. Популяция эволюционирует на тороидальной сетке (рисунок 13), в узлах которой случайным образом инициализируем жертв и хищников. Каждый хищник рассматривает все жертвы в своей окрестности и удаляет жертву с худшим значением соответствующего критерия оптимальности. Затем в той же окрестности выбираем и модифицируем случайную жертву. Измененное решение помещаем на место удаленной жертвы. Хищника случайным образом перемещаем в один из соседних с ним узлов сетки.
Процесс итерационно повторяем до выполнения условий окончания.
Рисунок 13 – Пример размещения хищников (квадратики) и жертв (кружки) на тороидальной сетке
Приведем схему метода в более формализованном виде.
1)
В гиперпараллелепипеде
X
D
случайным образом инициализируем популяцию жертв – решения
]
:
1
[
,
S
i
X
i
∈
2)
Ставим в соответствие жертвам вершины ненаправленного связного графа в виде тороидальной решетки.
3)
Случайным образом помещаем хищников в вершины указанного графа.
4)
Ставим в соответствие каждому из хищников один из критериев оптимальности
]
:
1
[
),
(
F
k
X
f
k
∈
таким образом, чтобы каждый из критериев был представлен, по меньшей мере, одним хищником.

http://technomag.edu.ru/doc/363023.html
27 5)
Вычисляем значения соответствующего критерия для всех жертв в окрестности каждого из хищников и выбираем худшие жертвы.
6)
Полагаем, что выбранные жертвы поглощены хищниками, и удаляем их из популяции.
7)
Взамен каждого из удаленных агентов создаем новую жертву путем изменения случайно выбранной жертвы в окрестности удаленного агента.
8)
Случайным образом перемещаем хищников из их текущих положений в соседние вершины графа.
9)
Если условие окончания итераций не выполнено, возвращаемся к шагу 5.
Экспериментально показано, что с ростом числа поколений популяция жертв стремится к фронту Парето, т.е. представляет собой искомую Парето-аппроксимацию.
Недостатком рассмотренного канонического метода хищник-жертва является возможная потеря лучших (ближайших к множеству Парето решений).
Деб (K. Deb) в 2001 г. предложил улучшения метода [31], суть которых заключается в следующем:
- хищникам ставят в соответствие не частные критерии оптимальности, а векторы их весов;
- вместо удаленной жертвы новую жертву создают путем модификации не случайного, но лучшего агента в окрестности удаленной жертвы;
- хищника перемещают не случайным образом, а в направлении позиции лучшей жертвы в его окрестности.
Исследования авторов метода показывают, что он обеспечивает по сравнению с каноническим методом более высокую скорость сходимости, однако, как и канонический метод, может терять найденные лучшие решения.
В работе [32] рассмотрена модификация канонического метода, предложенная Ли
(X. Li)
, в которой жертв и хищников помещают не во все узлы графа, представленного на рисунке 13. Жертвы и хищники выполняют случайные перемещения в направлении соседних пустых узлов графа, причем хищники движутся быстрее жертв. При каждом перемещении жертвы создается ее потомок. Вычислительные эксперименты показали недостаточно высокую скорость сходимости соответствующего алгоритма.
В той же работе [32] Дебом (K. Deb) и Рао (U. Rao) предложена глубокая модификация канонического метода, основу которой составляют следующие три механизма:
- механизм сохранения лучших решений;
- механизм рекомбинации решений;
- механизм получения равномерной Парето-аппроксимации.
Механизм сохранения лучших решений(элитизм) предполагает сравнения приспособленности худших жертв с приспособленностью созданных агентов (потомков).
Меру приспособленности агентов строим на основе Парето доминирования. Если данный потомок слабо доминирует всех жертв популяции (лучше их, по крайней мере, по одному из частных критериев оптимальности), то заменяем этим потомком соответствующую худшую жертву. В противном случае потомка объявляем неподходящим, худшую жертву оставляем в популяции, а хищник для обеспечения разнообразия популяции случайным образом

77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
28 перемещаем в направлении худшей жертвы.
Механизм рекомбинации решений строим на основе операторов скрещивания и мутации агентов (так что, в целом, метод оказывается вариантом генетического алгоритма). В окрестности худшей жертвы создаем двух потомков путем скрещивания лучшего и второго лучшего решений. Затем случайным образом выбираем одного из этих потомков и выполняем его мутацию. Если полученный таким образом потомок оказывается хуже худшей жертвы, то по рассмотренной схеме создаем нового потомка и опять сравниваем его приспособленность с приспособленностью худшей жертвы. Процесс повторяем не более некоторого фиксированного числа раз.
Механизм обеспечения равномерности покрытия. Полагаем, что каждая жертва имеет
область влияния (influencing region) в виде гиперкуба в критериальном пространстве, в центре которого находится данная жертва. Потомка полагаем не подходящим, если он создан в области влияния любой из существующих жертв. Заметим, что аналогичный механизм используется в методе
ε
- доминирования [33]. Размеры области влияния назначаем, исходя из требуемой равномерности покрытия.
Для того чтобы предотвратить ситуацию, когда хищники полностью уничтожают популяцию, используем следующий прием. Число перемещений
P
t
, которые выполняют хищники перед тем, как жертвы могут сделать свои перемещения, объявляем динамической переменной, определяемой формулой








−
=
P
p
p
P
S
S
S
t
*
, где
 
•
- символ ближайшего меньшего,
p
S
,
*
p
S
- текущее и желаемое числа жертв,
P
S
- текущее число хищников. В результате при уменьшении числа жертв уменьшается величина
P
t
, т.е. хищники начинают двигаться медленнее, шансы жертв на выживание повышаются, и популяция жертв расширяется. При этом хищники становятся более быстрыми, и их популяция начинает сокращаться. И так далее.
Авторы рассматриваемой модификации метода выполнили широкое экспериментальное исследование его эффективности на ряде трудных задач известного тестового набора двух- и трехцелевых задач многокритериальной оптимизации [31].
Показано, что алгоритм обеспечивает высокие скорость сходимости и равномерность покрытия фронта-Парето.
Заключение
Многообразие методов построения Парето-аппроксимации указывает на актуальность данной задачи. Представляются перспективными следующие направления развития этих методов.
Вычислительная сложность частных критериев оптимальности, вообще говоря, различна в различных частях области варьируемых параметров
X
D
. Рассмотренные и иные

http://technomag.edu.ru/doc/363023.html
29 известные методы Парето-аппроксимации не учитывают этого обстоятельства. Поэтому актуальной, на наш взгляд, является разработка адаптивных и самоадаптивных методов
Парето-аппроксимации, учитывающих данный факт.
Практически значимые задачи многокритериальной оптимизации имеют высокую вычислительную сложность и требуют для своего решения использования параллельных вычислительных систем. Поэтому необходима разработка параллельных методов Парето- аппроксимации, ориентированных на различные классы таких систем (кластерные системы, графические процессорные устройства и т.д.) [34].
Важным с практической точки зрения является класс задач Парето-аппроксимации, в которых требуется построить аппроксимацию не всего фронта Парето, но лишь той части его, которая ближе всего к заданной пользователем «предпочтительной» точке пространства критериев. Поэтому представляется актуальной задача разработки методов решения задач данного класса. Известна модификация метода хищник-жертва, предназначенная для решения таких задач [32]. Можно также считать, что метод идеальной точки является частным случаем этих методов.
Задачу Парето-аппроксимации можно считать одной из широкого класса задач приближенного построения границ множеств различной природы. Поэтому значительный интерес представляет адаптация рассмотренных методов и разработка новых методов, предназначенных для решения задач указанного класса. Пример такого подхода демонстрирует работа [35], в которой один из методов Парето-аппроксимации использован для приближенного построения границы области достижимости многосекционного манипулятора параллельной кинематики типа хобот.
Отметим, наконец, перспективность гибридизации рассмотренных и иных методов
Парето-аппроксимации.
Авторы благодарят Бушневского А.В. и Савелова А.С. за помощь в подготовке некоторых материалов для данной работы.
Литература
1.
Подиновский
В.В.,
Ногин
В.Д.
Парето-оптимальные решения многокритериальных задач.- М.: Физматлит, 2007.- 256 с.
2.
Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход.- М.: Физматлит, 2005.- 176 с.
3.
Ларичев О.И. Теория и методы принятия решений: Учебник для ВУЗов.- М.:
Университетская книга, Логос, 2006.- 392 с.
4.
Курейчик В.М. Генетические алгоритмы и их применение.- Таганрог: Изд-во
Таганрогского РТУ, 2002. -244 с.
5.
Ashlock D. Evolutionary Computation for Modeling and Optimization.- Springer,
2006.- 571 pp.
6.
Guliashki V., Toshev H., Korsemov Ch. Survey of Evolutionary Algorithms Used in
Multiobjective Optimization // Problems of Engineering Cybernetics and Robotics, 2009, Vol. 60, pp. 42 – 54.

77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
30 7.
Zitzler E., Deb K., Thiele L. Comparison of Multiobjective Evolutionary Algorithms:
Empirical Results // Evolutionary Computation, 2000, Vol. 8(2), pp. 173-195.
8.
Карпенко А. П., Селиверстов Е. Ю. Глобальная оптимизация методом роя частиц. Обзор // Информационные технологии, 2010, №2, c. 25-34.
9.
Карпенко А. П., Селиверстов Е. Ю. Обзор методов роя частиц для задачи глобальной оптимизации // Наука и образование: электронное научно-техническое издание,
2009, №3. (http://technomag.edu.ru/doc/116072.html).
10.
Fonseca C. M., Fleming P. J. Genetic Algorithms for Multiobjective Optimization:
Formulation, Discussion and Generalization / Proc. of the 5th International Conference on Genetic
Algorithms, San Mateo, California, 1993, pp. 416-423.
11.
Zitzler E., Thiele L., Marco Laumanns M., Fonseca C. M., da Fonseca V. G.
Performance Assessment of Multiobjective Optimizers: An Analysis and Review // IEEE
Transactions of Evolutionary Computation, 2003, Vol. 7(2), pp. 117-132.
12.
Knowles J.D., Corne D.W. On Metrics for Comparing Non-Dominated Sets // Proc. of the 2002 IEEE Congress on Evolutionary Computation (CEC '02), New Jersey, Piscataway, May
2002, IEEE Service Center, 2002, Vol. 1, pp. 711-716.
13.
Гуменникова А. В. Адаптивные поисковые алгоритмы для решения сложных задач многокритериальной оптимизации. Диссертация на соискание ученой степени к. т. н.-
Красноярск, 2006, 129 с.
14.
Luke S. Essentials of Metaheuristics. A Set of Undergraduate Lecture Notes.
Department of Computer Science George Mason University, Online Version 1.3 February, 2012.
(http://cs.gmu.edu/

sean/book/metaheuristics/Essentials.pdf).
15.
Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями: Учебное пособие для ВУЗов.- М.: Дрофа, 2006.- 175 с.
16.
Schaffer J.D. Multiple Objective Optimization with Vector Evaluated Genetic
Algorithms / In: Genetic Algorithms and Their Applications. Proceedings of the First International
Conference on Genetic Algorithms, 1985, Lawrence Erlbaum, pp. 93-100.
17.
Моор Д.А., Мухлисуллина Д. Т. Анализ эффективности различных сверток критериев оптимальности в задаче многокритериальной оптимизации // Наука и образование: электронное научно-техническое издание, 2010, №4. (http://technomag.edu.ru/doc/141623.html).
18.
Ryu J.-H., Kim S., Wan H. Pareto front approximation with adaptive weighted sum method in multiobjective simulation optimization / Proceedings of the 2009 Winter Simulation
Conference (WSC), 2009, Austin, pp. 623-633. (http://www.informs-sim.org/wsc09papers/060.pdf).
19.
Srinivas N., Deb K. Multiobjective optimization using nondominated sorting in genetic algorithms // Evolutionary Computation, 1994, vol. 2, p. 221–248.
20.
Horn J., Nafpliotis N., Goldberg D.E. A Niched Pareto Genetic Algorithm for
Multiobjective Optimization / Proc. of the First IEEE Conference on Evolutionary Computation,
IEEE World Congress on Computational Intelligence, New Jersey, 1994, Vol. 1, pp. 82-87.
21.
Deb K., Pratap A., Agarwal S., Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation, 2002, Vol. 6, Issue 2, pp.
182 – 197.

http://technomag.edu.ru/doc/363023.html
31 22.
Zitzler E., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 1999,
Vol. 3(4), pp. 257–271.
23.
Zitzler E., Laumanns M., Thiele L. SPEA2: Improving the Strength Pareto
Evolutionary Algorithm for Multiobjective Optimization / In K.C. Giannakoglou and al., editors.
Evolutionary Methods for Design, Optimization and Control with Application to Industrial
Problems (EUROGEN 2001), International Center for Numerical Methods in Engineering
(CIMNE), 2002, pp. 95-100.
24.
Knowles J., Corne D. The Pareto achieved evolution strategy: A new baseline algorithm for Pareto multiobjective optimization / Proceedings of the Congress on Evolutionary
Computation (CEC99), 1999,
Washington, Vol. 1, pp. 98–105.
25.
Bentley P. J., Wakefield J. P. An Analysis of Multiobjective Optimization within
Genetic Algorithms / Technical Report ENGPJB96, University of Huddersfield, UK, 1996. P. 19.
26.
Mostaghim S., Teich J. Strategies for Finding Good Local Guides in Multi-objective
Particle Swarm Optimization (MOPSO) / In: Swarm Intelligence Symposium, 2003. SIS '03.
Proceedings of the 2003 IEEE, pp. 26 – 33.
27.
Fieldsend J.E., Singh S. A multi-objective algorithm based upon particle swarm optimization, an efficient data structure and turbulence (2002).
(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.6959).
28.
Coello C.A., Lechuga M.S. MOPSO: A proposal for multiple objective particle swarm optimization / In IEEE Proceedings, World Congress on Evolutionary Computation
(CEC2002), 2002, pp. 1051-1056.
29.
Hu X., Eberhart R. Multiobjective Optimization Using Dynamic Neighborhood
Particle Swarm Optimization / In: Evolutionary Computation, 2002. CEC '02. Proceedings of the
2002 Congress on, Honolulu, HI, USA, 12 – 17 May 2002, pp. 1677 – 1681.
30.
Laumanns M., Rudolph G., Schwefel H.P. A spatial predator-prey approach to multi- objective optimization: A preliminary study / In Proceedings of the Parallel Problem Solving from
Nature, 1998, Vol. V, pp. 241-249.
31.
Deb K. Multi-objective optimization using evolutionary algorithms.- Chichester, UK:
Wiley, 2001, P. 518.
32.
Deb K., Rao U. B. Investigating Predator-Prey Algorithms for Multi-Objective
Optimization / Kanpur Genetic Algorithms Laboratory (KanGAL), Department of Mechanical
Engineering Indian Institute of Technology Kanpur, India, KanGAL Report Number 2005010
(http://www.iitk.ac.in/kangal/).
33.
Deb K., Mohan M., Mishra S. Evaluating the
ε
-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions // Evolutionary
Computation Journal, 2005, Vol. 13(4), pp. 501-525.
34.
Антух А.Э., Карпенко А.П., Семенихин А.С., Хасанова Р.В. Построение множества Парето методом роя частиц на графических процессорах архитектуры CUDA //
Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды
Международной суперкомпьютерной конференции (20-25 сентября 2010 г., г. Новороссийск).
М.: Изд-во МГУ, 2010. C. 274-280.

77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
32 35.
Карпенко А.П., Семенихин А.С., Червяцова М.Н. Метод приближенного построения границы области достижимости многосекционного манипулятора типа «хобот» //
Наука и образование: электронное научно-техническое издание, 2011, № 1.
(
http://technomag.edu.ru/doc/165078.html
).

http://technomag.edu.ru/doc/363023.html
33