Читать книгу Портфельная теория и методы оптимизации. NSGA, POWER BI - - Страница 4

Для фронта размером с целями:

– Для каждой цели: отсортировать индивиды по возрастанию (пусть индексы после сортировки – , где имеет минимальное, – максимальное). [71] [73]

– Инициализировать массив для всех индивидов и целей; граничные индивиды получают (или очень большое число). [71] [74]

Формула расчета по цели

Для каждой цели, для внутренних индивидов :

где или аналогичное малое число предотвращает деление на ноль при совпадении границ. Нормализация диапазоном цели обеспечивает сравнимость между целями разного масштаба. [71] [72] [75]

Агрегация и итоговое значение

Итоговый crowding distance для индивида :

Индивиды фронта сортируются по убыванию (большее расстояние предпочтительнее). При равенстве рангов в турнире или отборе побеждает больший. [71] [73] [76]

Псевдокод расчета

def crowding_distance (F, M, f): # F – список индивидов, f – их цели (l x M)

l = len (F)

if l <= 2: return [inf] * l # Граничные случаи

d = [^3_0] * l

for m in range (M):

# Сортировка по m-й цели

sorted_idx = argsort ([f [j] [m] for j in range (l)])

d [sorted_idx [^3_0]] = inf

d [sorted_idx [l-1]] = inf

fmin, fmax = f [sorted_idx [^3_0]] [m], f [sorted_idx [l-1]] [m]

for k in range (1, l-1):

i = sorted_idx [k]

d [i] += (f [sorted_idx [k+1]] [m] – f [sorted_idx [k-1]] [m]) / (fmax – fmin +1e-6)

return d

Этот подход обеспечивает на фронт за счет сортировок. [71] [77] [74]

⁂

Пошаговый пример расчёта crowding distance для 3 точек в 2D

Рассмотрим фронт Парето из 3 точек в 2D-пространстве целей (минимизация обеих): A (1, 4), B (2, 3), C (4, 1). Crowding distance стимулирует выбор граничных точек A и C, средняя B получит конечное значение. [86] [87]

Шаг 1: Сортировка по первой цели

Сортировка по: A (1), B (2), C (4) → индексы I = [A, B, C].

Границы:,.

Для B (внутренняя):. [86] [88]

Шаг 2: Сортировка по второй цели

Сортировка по: C (1), B (3), A (4) → индексы I = [C, B, A].

Границы:,.

Для B:. [86] [89]

Шаг 3: Агрегация расстояний

Итоговые:

,

,

.

При отборе предпочтение: A и C (∞)> B (2). В турнире A/C побеждают B. [86] [87]

Визуализация фронта

Этот пример иллюстрирует, как crowding distance расширяет «кубoid» вокруг точек, предпочитая края фронта для равномерного покрытия. [86] [90]

⁂

Пошаговый пример расчёта crowding distance с числами и пояснениями

Расчет crowding distance демонстрируется на фронте из 4 точек в 2D (минимизация): A (1,5), B (2,3), C (3,4), D (5,1). Границы получат ∞, внутренние – нормализованные расстояния по соседям. [99] [100]

Границы:,. Диапазон: 5—1=4.

– B: →.

– C: →. [99] [101]

По цели: сортировка D (1), B (3), C (4), A (5)

Границы:,. Диапазон: 5—1=4.

– B: →.

– C: →. [99] [102]

Итоговые расстояния

При равенстве B и C (1.25) турнир решает случайно; предпочтение границам A/D обеспечивает разнообразие. [100] [103]

⁂

Как нормировать цели перед расчётом crowding distance

В оригинальном NSGA-II нормировка целей встроена в формулу crowding distance и выполняется динамически на основе текущего фронта, без предварительной глобальной нормализации. Это обеспечивает адаптивность к разным масштабам целей внутри поколения. [112] [113]