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

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

5
.2. Метод Парето-силы
Иное правило ранжирования агентов популяции используется в методе Парето силы
(Pareto strength)
. Метод исходит из того, что сила агента
i
s
,
]
:
1
[
S
i
∈
равна числу особей, которых доминирует по Парето данный агент. Определенную указанным способом силу агентов можно использовать для вычисления их приспособленности. Однако такое определение пригодности обладает рядом недостатков [14]. Поэтому в вычислительной практике используют альтернативное понятие слабости (weakness) агента, равной числу особей, его доминирующих. Точнее говоря, используют вариант слабости агента, называемый в работе [14] его хилостью (wimpiness)
i
w
и равный суммарной силе всех особей, доминирующих данного агента. Фитнесс-функция при этом имеет вид
)
1
(
1
i
i
w
+
=
ϕ
,
]
:
1
[
S
i
∈
Метод Парето силы использует известный популяционный алгоритм Парето- аппроксимации SPEA (Strength Pareto Evolutionary Algorithm) [21]. Развитием алгоритма
SPEA является алгоритм SPEA-2, который подобно алгоритму NGSA-II использует оценки равномерности Парето-аппроксимации [23].
Упрощенным вариантом алгоритма SPEA-2 можно считать алгоритм PAES (Pareto
Achieved Evolution Strategy), предложенный Ноулзом (J. Knowles) и Корн (D. Corne) в 1999 г.
[24].
Рангом
i
r
агента
i
s
в алгоритме PAES называется число архивных решений, доминируемых решением
]
:
1
[
;
S
i
X
i
∈
. Схема алгоритма PAES для агента
i
s
имеет следующий вид.
1) По законам используемого популяционного алгоритма (в оригинале – генетического алгоритма) перемещаем агента
i
s
из его текущего положения
i
X
в новое положение
i
X ′

http://technomag.edu.ru/doc/363023.html
17 2) Если одно из решений
i
X
и
i
X ′
доминирует другое решение, то лучшее из них объявляем кандидатом. В противном случае кандидатом объявляем то из решений
i
X
,
i
X ′
, ранг которого выше.
3) Если решение-кандидат доминируется некоторым из архивных решений, то кандидата отвергаем. В противном случае кандидата записываем в архив, но только в том случае, если он находится в той части области поиска, в которой на текущий момент обнаружено мало решений. При записи кандидата в архив все доминируемые им решения из архива удаляем.
4) Если условие окончания итераций не выполнено, возвращаемся к шагу 1.
5.3. Другие методы на основе ранжирования
Метод средневзвешенного ранжирования (Weighted Average Ranking, WAR) предложили Бентли (P. J. Bentley) и Вэйкфилд (J. P. Wakefield) в 1996 г. [25]. Пусть
)
(
k
k
f
v
v
=
- относительная важность частного критерия
]
:
1
[
,
F
k
f
k
∈
Метод WAR
предполагает вычисление текущего ранга агента
]
:
1
[
,
S
i
s
i
∈
по следующей схеме.
1)
Для каждого из критериев
k
f
формируем список
k
L
, содержащий величины
)
(
i
k
X
f
, упорядоченные по их возрастанию.
]
:
1
[
F
k
∈
2)
Ранг агента
i
s
полагаем равным величине
(
)
∑
=
=
F
k
i
k
k
i
X
n
v
r
1
)
(
,
]
:
1
[
S
i
∈
, (7) где
)
(
i
k
X
n
- порядковый номер агента
i
s
в списке
k
L
Метод суммы взвешенных оценок (Sum of Weighted Ratios, SWR) можно считать развитием метода WAR [25]. При вычислении ранга агентов метод использует свертку вида
(7
), в которой вместо относительной важности частных критериев
k
v
используются их особым образом нормализованные значения. Нормализация основана на использовании наихудших и наилучших текущих значений критериев
)
(
max
)
(
]
:
1
[
i
k
F
k
i
worst
X
f
X
f
∈
=
,
)
(
min
)
(
]
:
1
[
i
k
F
k
i
best
X
f
X
f
∈
=
и определяется формулой
|]
:|
[1
,
)
(
)
(
)
(
)
(
=
)
(
F
k
X
f
X
f
X
f
X
f
X
f
i
worst
i
best
i
worst
i
k
i
k
∈
−
−
,
]
:
1
[
S
i
∈
Метод суммы взвешенных глобальных оценок (Sum of Weighted Global Ratios, SWGR)
[25
] близок к предыдущему методу с тем отличием, что наихудшие и наилучшие значения критериев определяют на основе всей предыстории поиска, т.е. на основе всех итераций
]
:
1
[ t
∈
τ
:
)
(
max max
)
(
]
:
1
[
]
:
1
[
τ
τ
i
l
F
l
t
i
worst
X
f
X
f
∈
∈
=
;
)
(
min min
)
(
]
:
1
[
]
:
1
[
τ
τ
l
l
F
l
t
i
best
X
f
X
f
∈
∈
=
;
]
:
1
[
S
i
∈

77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
18
Метод максимального взвешенного ранжирования(Weighted Maximum Ranking, WMR)
[25
] основан на идее рассмотренного выше метода VEGA. Положим, что все критерии нормализованы и заданы их относительные важности
k
v
,
]
:
1
[
F
k
∈
Схему метода определяет следующая последовательно шагов.
1)
Аналогично методу WAR формируем списки
k
L
,
]
:
1
[
F
k
∈
и определяем величины
)
(
i
k
X
n
,
]
:
1
[
S
i
∈
2)
Вычисляем ранги каждого из
S
агентов по всем
F
критериям оптимальности
)
(
)
(
i
k
k
i
k
X
n
v
X
r
=
,
]
:
1
[
S
i
∈
,
]
:
1
[
F
k
∈
3)
В качестве итогового ранга агента
i
s
в его текущем положении
i
X
принимаем величину
)
(
max
]
:
1
[
i
k
F
k
i
X
r
r
∈
=
,
]
:
1
[
S
i
∈
6. Прочие методы
В данном разделе рассматриваем сигма-метод, методы композитных точек, гиперкубов, динамических соседей, а также метод хищник-жертва.
6.1.
Сигма-метод
Сигма-метод (sigma method) предложили Мостагхим (S. Mostaghim) и Тич (J. Teich) в
2003 г. [26].
Для двухкритериальной задачи (
2
|=
| F
) сигма-параметром точки
i
X
или соответствующей ей точки
)
,
(
=
,2
,1
i
i
i
f
f
F
, называется величина
2
,2 2
,1 2
,2 2
,1
=
)
(
=
i
i
i
i
i
i
f
f
f
f
F
+
−
σ
σ
,
]
:
1
[
S
i
∈
Легко видеть, что точки
i
F
, имеющие одно и то же значение сигма-параметра, лежат на одной прямой, проходящей через начало системы координат
2 1
0
f
f
Определение сигма- параметра иллюстрирует рисунок 8, на котором одинаковые значения сигма-параметра имеют пары точек
)
,
(
),
,
(
),
,
(
6 5
4 3
2 1
F
F
F
F
F
F

http://technomag.edu.ru/doc/363023.html
19
Рисунок 8 - К определению сигма-параметра:
2
=
F
В случае, когда размерность критериального пространства больше двух (
2
|>
| F
) сигма-метод использует
|
| F
- мерный вектор сигма-параметров
)
,
,
,
(
=
|
|
2 1
F
σ
σ
σ
σ

Для агента
i
s
этот вектор определяет выражение
)
(
=
)
(
=
2
|
|,
2
,2 2
,1 2
1
,
2
,
2 3
,
2 2
,
2 2
,
2 1
,
F
i
i
i
i
F
i
i
i
i
i
i
i
f
f
f
f
f
f
f
f
f
F
+
+
+
⋅














−
−
−

σ
σ
,
]
:
1
[
S
i
∈
В сигма-методе для точки
i
X
,
]
:
1
[
S
i
∈
лучшая архивная точка
A
j
X
,
]
:
1
[
A
j
∈
определяется по следующей схеме.
1)
Вычисляем значение сигма-параметра точки
)
(
i
X
F
- величину
)
(
=
i
i
F
σ
σ
2)
Находим в архиве
F
A
точку
A
j
F
, у которой значение сигма-параметра наиболее близко к величине
i
σ
:
i
j
i
l
A
l
σ
σ
σ
σ
−
→
−
∈
||
||
min
|]
:|
[1
. (8)
Здесь
||
*
||
- символ евклидовой нормы.
3)
В качестве лучшей для точки
i
X
принимаем точку
A
j
X
такую, что
A
j
A
j
F
X
F
=
)
(
В данном случае в качестве метрики близости точек
i
F
,
A
j
F
используется евклидова

77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
20 норма в сигма-пространстве
}
{
σ
Утверждение 2. Предположим, что для всех архивных частиц
|]
:|
[1
,
A
j
X
A
j
∈
вектор сигма-параметров
|
|
2 1
,
,
,
=
F
σ
σ
σ
σ

уже вычислен. Тогда отыскание для точки
i
X
лучшей архивной точки
A
j
X
сигма-методом требует
|)
|
|
(|
A
F
O
арифметических операций.
Справедливость утверждения вытекает из того факта, что для отыскания точки, которая является лучшей для точки
i
X
, требуется
|
| A
раз вычислить значение нормы вида
(8
) и для каждого такого вычисления необходимо
|)
(| F
O
арифметических операций•
Для двухкритериальной задачи изложенную схему сигма-метода иллюстрирует рисунок 9. Стрелками на рисунке для каждой из точек
i
F
показаны «притягивающие» точки
A
j
F
Рисунок 9 - Схема сигма-метода для двухкритериальной задачи:
•
- архивные точки
A
j
F
;

- точки
i
F
6.2.
Метод композитных точек
Метод композитных точек предложили Филдсенд (J.E. Fieldsend) и Синх (S. Singh) в
2002 г. [27]. Метод использует архив
F
A
недоминируемых точек в виде, так называемого дерева доминирования (dominated tree), представляющего собой список композитных точек
(composite points)
)
,
,
,
(
=
|
|,
,2
,1
F
j
j
j
j
c
c
c
C

,
,
2
,
1
=
j
Для двухкритериальной задачи пример дерева доминирования приведен на рисунке 10.
Координаты первой композитной точки
1
C
определяем по следующей схеме.
1)
В качестве первой координаты
1,1
c
этой композитной точки принимаем первую

http://technomag.edu.ru/doc/363023.html
21 координату той архивной точки
|]
:|
[1
,
1 1
A
j
F
A
j
∈
, у которой значение этой координаты наибольшее, т.е. полагаем
A
j
A
j
A
j
f
f
c
1
,
,1
|]
:|
[1 1,1 1
=
max
=
∈
Исключаем точку
A
j
F
1
из дальнейшего рассмотрения.
2)
Вторую координату
1,2
c
точки
1
C
полагаем равной второй координате той из оставшихся архивных точек
A
j
F
, у которой эта координата имеет наибольшее значение, т.е. принимаем, что
1 2
,
,2
|]
:|
[1 1,2 2
=
max
=
j
j
f
f
c
A
j
A
j
A
j
≠
∈
Точку
A
j
F
2
исключаем из дальнейшего рассмотрения.
3)
Если
2
|>
| F
, то поступаем аналогичным образом для всех остальных координат, так что
1
|
|
2 1
|
|,
|]
:|
[1
|
|
1,
,
,
,
,
=
max
=
,
−
∈
≠
≠
≠
F
A
F
j
A
F
j
A
j
F
j
j
j
j
j
j
f
f
c
F

Рис. 10. Дерево доминирования для двухкритериальной задачи:
•
– архивные точки
A
A
F
F
7 1
−
;
⊗
– композитные точки
3 2
1
,
,
C
C
С

77-30569/363023
, №04 апрель 2012 г. http://technomag.edu.ru
22 4)
По аналогичной схеме вычисляем координаты второй композитной точки
2
C
и так далее до исчерпания всех точек архива
F
A
Рассмотрим схему алгоритма быстрого построения дерева доминирования. Положим, что сформированы списки
|
|
2 1
,
,
,
F
L
L
L

из
|
| A
элементов каждый такие, что в списке
k
L
содержатся точки архива
F
A
, отсортированные в порядке убывания по критерию оптимальности
)
( X
f
k
;
|]
:|
[1 F
k
∈
. При использовании известного алгоритма быстрой сортировки построение таких списков требует, в худшем случае,
)
|
(|
2
A
O
операций сравнения. Элементы списка
k
L
обозначим
j
k
L
,
,
|]
:|
[1
|],
:|
[1
A
j
F
k
∈
∈
1)
В качестве координаты
k
c
1,
точки
1
C
принимаем
k
- ю координату элемента
,1
k
L
и исключаем этот элемент из всех списков.
2)
В качестве координаты
k
c
2,
точки
2
C
принимаем
k
- ю координату элемента
,2
k
L
и исключаем этот элемент из всех списков.
3)
И так далее до исчерпания всех списков
k
L
;
|]
:|
[1 F
k
∈
Легко видеть, что архиву
F
A
соответствует общее число композитных точек, равное






F
A
С =
, где 
* - символ ближайшего целого меньшего.
Архивные точки
A
j
A
j
A
j
F
F
F
F
,
,
,
2 1

, соответствующие композитной точке
j
C
, назовем вершинами точки
]
:
[1
;
C
j
C
j
∈
После того как дерево доминирования построено, лучшую точку для точки
i
X
определяем по следующему правилу.
1)
В списке композитных точек находим точку
j
C
такую, что имеет место хотя бы одно из неравенств
|]
:|
[1 1)],
(
:
[1
,
<
1,
,
,
F
k
C
j
c
f
c
j
j
k
i
k
j
∈
−
∈
≤
+
2)
Из числа вершин
A
j
A
j
A
j
F
F
F
F
,
,
,
2 1

композитной точки
j
C
находим точку
|]
:|
[1
,
F
p
F
A
j
p
∈
, которая строго доминирует точку
i
F
, т.е. такую, что
i
A
j
F
F
p

3)
В качестве лучшей для точки
i
X
принимаем точку
A
j
p
X
, соответствующую вершине
A
j
p
F
4)
Если среди вершин
A
j
A
j
A
j
F
F
F
F
,
,
,
2 1

имеется более одной, которая строго доминирует точку
i
F
, то из них случайным образом выбираем вершину
A
j
p
F
и в качестве

http://technomag.edu.ru/doc/363023.html
23 лучшей для точки
i
X
принимаем соответствующую точку
A
j
p
X
Рассмотренное правило определения лучшей точки иллюстрирует рисунок 11 , на котором стрелками на рисунке показаны соответствующие лучшие точки.
Рисунок 11 – К определению лучшей точки в методе композитных точек:
•
– точки архива
F
A
;
⊗
– композитные точки;

- точки
i
F