Многокритериальная оптимизация: Парето, NSGA-II, SPEA2

В предыдущих статьях трека фитнес-функция всегда возвращала одно число. Это удобно, но почти всегда — ложь. Реальные инженерные задачи звучат иначе:

• Отбор тестов для pre-merge: максимум покрытия, минимум времени прогона — цели прямо конфликтуют.
• Планирование релиза (Next Release Problem): максимум ценности для клиентов, минимум стоимости разработки.
• Автоматическое исправление программ: максимум пройденных тестов, минимум размера патча (большой патч почти всегда — переобучение под тесты).
• Рефакторинг модульной структуры: максимум связности внутри модулей, минимум зацепления между ними, плюс «не наплодить 200 микромодулей».
• Подбор конфигурации сервиса: минимум p99-латентности, минимум стоимости инфраструктуры, максимум надёжности.

Во всех случаях у задачи нет единственного правильного ответа. Есть семейство компромиссов, и выбор между ними — управленческое решение, а не математическое. Задача поиска — не выбрать компромисс за человека, а показать ему весь спектр разумных компромиссов и не тратить его время на заведомо плохие варианты. Этим и занимается многокритериальная оптимизация (Multi-Objective Optimisation, MOO), а в эволюционном варианте — MOEA (Multi-Objective Evolutionary Algorithm).

Формальная постановка

Пусть решение $x$ принадлежит пространству поиска $X$, а качество измеряется вектором из $m$ целей:

$$ F(x) = \big(f_1(x), f_2(x), \dots, f_m(x)\big) $$

Договоримся, что все цели минимизируются — это стандартное соглашение. Если цель на максимум (покрытие, ценность), берём $-f$ или 1 $ - f$. Смешивать min и max в одном коде — источник классических ошибок со знаком.

Доминирование по Парето

Решение $a$ доминирует решение $b$ (пишут $a \prec b$), если: (1) $a$ не хуже $b$ по всем целям, $\forall i:\ f_i(a) \le f_i(b)$; и (2) $a$ строго лучше хотя бы по одной, $\exists j:\ f_j(a) < f_j(b)$.

По-человечески: «$a$ — бесплатное улучшение $b$». Никакой разумный заказчик не выберет $b$, если доступно $a$. Если ни $a \prec b$, ни $b \prec a$ — решения несравнимы (incomparable). И вот главное свойство: доминирование — это строгий частичный порядок, а не линейный. Он транзитивен и антисимметричен, но не полон. Именно неполнота порядка порождает всю специфику MOO: отсортировать популяцию «по возрастанию качества» нельзя в принципе.

Парето-оптимальное множество $P^\ast = {x \in X \mid \nexists y \in X: y \prec x}$ — все недоминируемые решения. Его образ в пространстве целей $PF^\ast = F(P^\ast )$ — фронт Парето.

На панели A видно, что доминирование делит пространство целей вокруг точки $p$ на четыре зоны, и только две из них дают определённый ответ. Чем больше целей $m$, тем больше «серых» зон — к этому вернёмся в разделе про many-objective.

$\varepsilon$-доминирование (Laumanns et al., 2002) — практически полезный трюк: оно «огрубляет» сетку в пространстве целей, благодаря чему архив недоминируемых решений имеет доказуемо ограниченный размер и не разрастается до миллиона точек на непрерывных фронтах.

Почему нельзя просто сложить цели с весами

Первый инстинкт инженера — скаляризация: $f = w_1 f_1 + w_2 f_2$. Иногда это правильный ответ, но чаще — ловушка.

1. Веса нужно знать до того, как вы поняли задачу. Чтобы утверждать «покрытие в 3 раза важнее времени», надо уже представлять форму компромисса. На старте её не представляет никто, включая заказчика.
2. Цели в разных единицах. Покрытие — в долях, время — в секундах, стоимость — в рублях. Сумма без нормировки физически бессмысленна и молча вырождается в однокритериальную задачу по самой «крупной» цели.
3. Взвешенная сумма принципиально не достаёт вогнутые участки фронта. Это не баг реализации, а геометрия: минимизация $w^\top F$ — скольжение гиперплоскости с нормалью $w$ до касания с множеством достижимых точек, а касание всегда происходит на выпуклой оболочке фронта. Точки в «провале» невыпуклого фронта не оптимальны ни при каком $w \ge 0$ — их нельзя получить в принципе.

Если скаляризация всё-таки нужна, берите не взвешенную сумму, а взвешенную метрику Чебышёва $g^{tch}(x \mid w, z^\ast ) = \max_i w_i \cdot | f_i(x) - z_i^\ast |$, где $z^\ast $ — идеальная точка: она достаёт и невыпуклые участки. На этом свойстве построен MOEA/D (Zhang & Li, 2007), где задача с $m$ целями раскладывается на $N$ скалярных подзадач с разными весами, решаемых совместно.

Для SBSE в подавляющем большинстве случаев правильный выбор — a posteriori: показать фронт продакт-менеджеру или тимлиду и дать выбрать. Это дешевле, чем пытаться вытащить из него числовые веса.

Недоминируемая сортировка

Первый строительный блок NSGA-II. Задача: разбить популяцию на фронты $F_1, F_2, \dots$ — $F_1$ недоминируемые вообще, $F_2$ недоминируемые после удаления $F_1$, и так далее. Номер фронта = ранг особи, он и есть «первичный фитнес».

Наивный алгоритм — для каждого фронта проходить по всем оставшимся, $O(m N^3)$. Деб предложил хитрость: считаем для каждой особи счётчик $n_p$ (сколько её доминирует) и список $S_p$ (кого доминирует она), затем «снимаем слои», как в топологической сортировке. Получается $O(m N^2)$ по времени и $O(N^2)$ по памяти.

from math import inf

def dominates(a, b):
    """a доминирует b. Обе цели минимизируются."""
    return all(x <= y for x, y in zip(a, b)) and any(x < y for x, y in zip(a, b))

def fast_non_dominated_sort(objs):
    """objs — список векторов целей. Возвращает (фронты как списки индексов, ранги).
    Время O(m*N^2), память O(N^2) в худшем случае (списки S)."""
    n = len(objs)
    dominated_by = [[] for _ in range(n)]   # S_p: кого доминирует p
    dom_count = [0] * n                     # n_p: сколько особей доминируют p
    rank, fronts = [0] * n, [[]]
    for p in range(n):
        for q in range(p + 1, n):           # каждую пару смотрим ровно один раз
            if dominates(objs[p], objs[q]):
                dominated_by[p].append(q); dom_count[q] += 1
            elif dominates(objs[q], objs[p]):
                dominated_by[q].append(p); dom_count[p] += 1
    for p in range(n):
        if dom_count[p] == 0:
            rank[p] = 0
            fronts[0].append(p)
    i = 0
    while fronts[i]:
        nxt = []
        for p in fronts[i]:
            for q in dominated_by[p]:
                dom_count[q] -= 1
                if dom_count[q] == 0:       # все доминаторы сняты слоями выше
                    rank[q] = i + 1
                    nxt.append(q)
        i += 1
        fronts.append(nxt)
    fronts.pop()                            # последний всегда пустой
    return fronts, rank

Для больших популяций и малого $m$ есть быстрее: divide-and-conquer сортировка Йенсена (Jensen, 2003) даёт $O(N \log^{m-1} N)$, а Efficient Non-dominated Sort на практике сильно обгоняет наивную на тысячах особей. Но для типичных SBSE-задач ($N \le 200$) узкое место — не сортировка, а вычисление фитнеса: один прогон тестового набора стоит на порядки дороже, чем $N^2$ сравнений векторов.

Crowding distance: как сохранить разнообразие фронта

Ранга недостаточно. Внутри $F_1$ все особи равны по рангу, и если не следить за разнообразием, популяция схлопнется в один кластер на фронте — получите десять почти одинаковых компромиссов вместо равномерного спектра.

Crowding distance $d_i$ — оценка «просторности» вокруг особи: полупериметр минимального прямоугольника (кубоида в $m$ измерениях), построенного на ближайших соседях по каждой цели. Чем больше $d_i$, тем уникальнее компромисс.

def crowding_distance(objs, front):
    """Crowding distance для одного фронта. O(m * |F| * log|F|) из-за сортировок."""
    dist = {i: 0.0 for i in front}
    size = len(front)
    if size <= 2:
        return {i: inf for i in front}              # крайние точки неприкосновенны
    for k in range(len(objs[front[0]])):
        order = sorted(front, key=lambda idx: objs[idx][k])
        f_min, f_max = objs[order[0]][k], objs[order[-1]][k]
        dist[order[0]] = dist[order[-1]] = inf      # границы фронта всегда выживают
        span = f_max - f_min
        if span < 1e-12:                            # цель константна на фронте — вклада нет
            continue
        for j in range(1, size - 1):
            prev_v, next_v = objs[order[j - 1]][k], objs[order[j + 1]][k]
            dist[order[j]] += (next_v - prev_v) / span   # НОРМИРОВКА обязательна
    return dist

Два места, где обычно ошибаются. Нормировка на размах цели (/ span): без неё цель с большим числовым диапазоном (время в миллисекундах) полностью съест цель в долях единицы, и разнообразие будет поддерживаться только по одной оси. Бесконечность на границах: крайние точки фронта — это лучшие решения по отдельным целям, потеряв их, фронт «съёживается» к середине за десяток поколений.

Crowding distance быстрая ($O(mN\log N)$), но грубая: при $m \ge 4$ она плохо коррелирует с реальной плотностью, потому что кубоид в многомерии почти всегда пустой. Это одна из причин появления NSGA-III.

NSGA-II целиком

NSGA-II (Deb, Pratap, Agarwal, Meyarivan, IEEE TEC 2002) — самая цитируемая работа во всей эволюционной оптимизации и де-факто базовая линия, с которой сравнивают всё остальное. Три её идеи: быстрая недоминируемая сортировка вместо $O(mN^3)$; crowding distance вместо sharing-функции с ручным параметром $\sigma_{share}$ (никаких магических констант); элитизм через объединение $R_t = P_t \cup Q_t$, где родители конкурируют с потомками и хорошие решения не теряются.

Оператор сравнения (crowded-comparison $\prec_n$): $i \prec_n j$, если $rank_i < rank_j$, либо $rank_i = rank_j$ и $d_i > d_j$. Он превращает частичный порядок в полный и позволяет проводить обычный бинарный турнир.

Рабочая реализация: отбор регрессионных тестов

Классическая SBSE-задача (Yoo & Harman, «Pareto efficient multi-objective test case selection», ISSTA 2007): выбрать подмножество тестов, максимизируя покрытие требований и минимизируя время прогона.

import random
random.seed(7)

N_TESTS, N_REQS = 60, 120
# Синтетическая модель проекта: у каждого теста своё покрытие и своя длительность.
COVERAGE = [set(random.sample(range(N_REQS), random.randint(3, 22))) for _ in range(N_TESTS)]
DURATION = [round(random.uniform(0.4, 30.0), 2) for _ in range(N_TESTS)]
TOTAL_TIME = sum(DURATION)

def evaluate(mask):
    """Обе цели МИНИМИЗИРУЮТСЯ и нормированы в [0, 1]."""
    covered, time = set(), 0.0
    for i, bit in enumerate(mask):
        if bit:
            covered |= COVERAGE[i]
            time += DURATION[i]
    return (1.0 - len(covered) / N_REQS, time / TOTAL_TIME)

def tournament(pop, rank, crowd):
    a, b = random.randrange(len(pop)), random.randrange(len(pop))
    if rank[a] != rank[b]:
        return pop[a] if rank[a] < rank[b] else pop[b]
    return pop[a] if crowd[a] >= crowd[b] else pop[b]   # при равном ранге — кто просторнее

def crossover(p1, p2):
    """Равномерный кроссовер: для битовых масок работает лучше одноточечного."""
    return [x if random.random() < 0.5 else y for x, y in zip(p1, p2)]

def mutate(ind, pm=1.0 / N_TESTS):
    return [1 - b if random.random() < pm else b for b in ind]

def nsga2(pop_size=100, generations=150):
    pop = [[random.randint(0, 1) for _ in range(N_TESTS)] for _ in range(pop_size)]
    objs = [evaluate(x) for x in pop]
    for _ in range(generations):
        fronts, rank = fast_non_dominated_sort(objs)
        crowd = [0.0] * len(pop)
        for f in fronts:
            for idx, d in crowding_distance(objs, f).items():
                crowd[idx] = d
        offspring = []                                  # порождаем Q_t
        while len(offspring) < pop_size:
            offspring.append(mutate(crossover(tournament(pop, rank, crowd),
                                              tournament(pop, rank, crowd))))
        pop = pop + offspring                           # R_t = P_t ∪ Q_t
        objs = objs + [evaluate(x) for x in offspring]
        fronts, _ = fast_non_dominated_sort(objs)
        new_idx = []                                    # элитарный отбор N из 2N
        for f in fronts:
            if len(new_idx) + len(f) <= pop_size:
                new_idx.extend(f)
            else:
                d = crowding_distance(objs, f)
                new_idx.extend(sorted(f, key=lambda i: d[i], reverse=True)[:pop_size - len(new_idx)])
                break
        pop = [pop[i] for i in new_idx]
        objs = [objs[i] for i in new_idx]
    fronts, _ = fast_non_dominated_sort(objs)
    return [(pop[i], objs[i]) for i in fronts[0]]

if __name__ == "__main__":
    print(f"{'тестов':>7} {'покрытие':>10} {'время, с':>10}")
    for mask, (inv_cov, rel_time) in sorted(nsga2(), key=lambda r: r[1][1]):
        print(f"{sum(mask):>7} {(1 - inv_cov) * 100:>9.1f}% {rel_time * TOTAL_TIME:>10.1f}")

На выходе — не один набор тестов, а лесенка: «7 тестов, 61 % покрытия, 42 с» … «31 тест, 100 % покрытия, 310 с». Дальше тимлид сам решает, что влезает в бюджет CI. Это и есть практическая ценность MOO: разговор с заказчиком идёт не о весах, а о конкретных вариантах.

Сложность одного поколения: $O(mN^2)$ на сортировку, $O(mN\log N)$ на crowding, $N$ вычислений фитнеса; память $O(N^2)$ из-за списков доминируемых. Для $N=100$ накладные расходы — микросекунды, доминирует стоимость evaluate.

SPEA2

SPEA2 (Zitzler, Laumanns, Thiele, TIK-Report 103, 2001) — второй классический алгоритм, разработанный независимо и почти одновременно с NSGA-II. Он решает те же задачи другими средствами и до сих пор остаётся сильной базовой линией. Ключевое отличие: SPEA2 держит явный внешний архив $\bar{P}$ фиксированного размера $\bar{N}$, а фитнес считает не рангом фронта, а более тонкой величиной — учитывающей, сколько решений доминирует особь и насколько сильные это решения.

1. Strength $S(i)$ — количество решений (в популяции ∪ архиве), которые доминирует $i$.
2. Raw fitness $R(i) = \sum_{j \prec i} S(j)$ — сумма «сил» всех, кто доминирует $i$. Меньше — лучше; $R(i) = 0$ ровно у недоминируемых.
3. Density $D(i) = 1 / (\sigma_i^k + 2)$, где $\sigma_i^k$ — расстояние до $k$-го ближайшего соседа, $k = \sqrt{N + \bar{N}}$. Значение всегда в $(0, 1)$ — плотность никогда не перебивает raw fitness.

Итоговый фитнес $\mathit{Fit}(i) = R(i) + D(i)$, минимизируется.

from math import sqrt

def spea2_fitness(objs):
    """Фитнес SPEA2, меньше — лучше. Время O(m*N^2 + N^2 log N)."""
    n = len(objs)
    dom = [[i != j and dominates(objs[i], objs[j]) for j in range(n)] for i in range(n)]
    strength = [sum(row) for row in dom]                       # S(i)
    raw = [sum(strength[j] for j in range(n) if dom[j][i]) for i in range(n)]   # R(i)
    k = int(sqrt(n))                                           # в оригинале k = sqrt(N + N̄)
    fit = []
    for i in range(n):
        dists = sorted(sqrt(sum((a - b) ** 2 for a, b in zip(objs[i], objs[j])))
                       for j in range(n) if j != i)
        sigma_k = dists[min(k, len(dists)) - 1]
        fit.append(raw[i] + 1.0 / (sigma_k + 2.0))             # R(i) + D(i)
    return fit

Усечение архива (environmental selection) — самая дорогая и самая аккуратная часть SPEA2. Когда недоминируемых больше $\bar{N}$, итеративно удаляется особь с минимальным расстоянием до ближайшего соседа; при равенстве сравниваются вторые, третьи соседи и так далее. Это гарантирует, что крайние точки фронта не будут удалены — свойство, которого не было у наивной кластеризации в первом SPEA. Стоимость: $O(\bar{N}^2 \log \bar{N})$ на поколение.

Эмпирически на 2–3 целях они близки: SPEA2 чуть лучше держит равномерность фронта, NSGA-II заметно дешевле. В SBSE-статьях чаще берут NSGA-II — там фитнес (прогон тестов, компиляция патча) стоит на порядки дороже, чем накладные расходы алгоритма, и экономия на архиве не окупает сложность реализации.

Как измерять качество фронта

Сравнить два однокритериальных запуска легко: у кого фитнес меньше. Сравнить два множества точек — нетривиально, и здесь регулярно допускают методологические ошибки. Считать «средний фитнес по фронту» бессмысленно.

Hypervolume (HV) — объём области в пространстве целей, доминируемой найденным фронтом и ограниченной опорной точкой (reference point). Это единственный широко используемый индикатор, строго совместимый с доминированием по Парето: если множество $A$ лучше $B$ в смысле доминирования, то $HV(A) > HV(B)$ всегда (Zitzler et al., TEC 2003). Плюс — не требует знания истинного фронта, что критично для реальных задач, где его никто не знает. Минус — цена: точное вычисление растёт экспоненциально с числом целей. Для $m=2$ хватает развёртки за $O(N\log N)$:

def hypervolume_2d(front, ref):
    """HV для двух минимизируемых целей. ref должна доминироваться всеми точками."""
    pts = sorted(p for p in front if p[0] < ref[0] and p[1] < ref[1])
    hv, prev_y = 0.0, ref[1]
    for x, y in pts:                 # идём по возрастанию f1
        if y < prev_y:               # точка не доминируется предыдущими
            hv += (ref[0] - x) * (prev_y - y)
            prev_y = y
    return hv

Для $m \ge 5$ используют WFG-алгоритм (While et al., 2006) или Монте-Карло-оценку (HypE). В pymoo и jMetal это уже реализовано — не пишите сами. Практические правила:

• Опорную точку HV фиксируйте один раз для всего эксперимента (например, надир по объединению всех запусков ×1.1). Разные опорные точки делают числа несравнимыми.
• Всегда нормируйте цели в $[0,1]$ перед вычислением HV — иначе цель с большим диапазоном определит весь результат.
• Сравнивайте алгоритмы статистически: не менее 30 независимых запусков, критерий Манна—Уитни и величина эффекта Варга—Дилейни $\hat{A}_ {12}$ — методологический стандарт SBSE (Arcuri & Briand, STVR 2014). Один запуск не доказывает ничего: алгоритмы стохастические.

Проблема many-objective: когда целей становится много

При $m \ge 4$ Парето-доминирование теряет разрешающую способность. Прикинем: если цели независимы и случайны, вероятность, что решение $a$ доминирует $b$, равна $2^{-m}$, а ожидаемое число доминаторов у случайной особи в популяции из $N$ решений — примерно $(N-1)/2^m$.

Когда весь $R_t$ оказывается в $F_1$, NSGA-II фактически превращается в случайный поиск с отбором по разнообразию — селективное давление в сторону фронта исчезает. Известные лечения:

• NSGA-III (Deb & Jain, TEC 2014) — заменяет crowding distance на ассоциацию с равномерно распределёнными опорными направлениями (reference points) и нишевую процедуру.
• MOEA/D — декомпозиция на скалярные подзадачи; давление к фронту создаёт сама скаляризация.
• Indicator-based: IBEA, HypE, SMS-EMOA — фитнес прямо равен вкладу особи в индикатор (обычно HV или $\varepsilon$). IBEA (Zitzler & Künzli, PPSN 2004) популярен в SBSE: на задаче конфигурирования линеек продуктов SATIBEA (Henard et al., ICSE 2015) показал, что indicator-based подход масштабируется там, где NSGA-II сдувается.
• Objective reduction — иногда цели просто скоррелированы и их честно можно склеить. Посчитайте корреляцию Спирмена между целями до того, как городить NSGA-III.

Ограничения (constraints)

В SBSE ограничения встречаются постоянно: «набор тестов обязан покрывать все smoke-требования», «релиз не должен превышать бюджет», «патч обязан компилироваться». Скармливать их штрафом в цель — плохая практика: штраф превращается в ещё одну неявную скаляризацию с волшебным весом. Правильный способ — constrained-domination principle Деба: $a$ доминирует $b$, если (1) $a$ допустимо, а $b$ — нет; или (2) оба недопустимы, но суммарное нарушение ограничений у $a$ меньше; или (3) оба допустимы и $a \prec b$ в обычном смысле. Это обёртка над dominates(), не требующая ни одного дополнительного параметра. Важная деталь: суммарное нарушение считается по нормированным нарушениям, иначе одно ограничение в чужих единицах перевесит все остальные.

Как это применяют в SBSE

Отбор и приоритизация регрессионных тестов. Пара «покрытие / время» разобрана выше; в проде добавляют третью цель — историческую вероятность падения теста — и получают фронт стратегий для CI. Подробнее — в статье про генерацию тестов.

Next Release Problem. Zhang, Harman, Mansouri, GECCO 2007 переформулировали планирование релиза как двухкритериальную задачу (ценность / стоимость) вместо однокритериальной с бюджетным ограничением. Вместо одного плана менеджер получает кривую «сколько ценности за сколько денег» — куда более полезный артефакт для переговоров.

Модуляризация легаси. Praditwong, Harman, Yao, IEEE TSE 2011 показали, что многокритериальная постановка (когезия, зацепление, число модулей, разброс размеров) даёт качественно лучшие разбиения, чем однокритериальная максимизация Modularization Quality в классическом Bunch.

Генерация тестов. Прорыв последних лет — MOSA и DynaMOSA (Panichella et al., ICST 2015; TSE 2018): каждая непокрытая ветка объявляется отдельной целью, и покрытие класса становится many-objective задачей с сотнями целей. Ключевой трюк — preference sorting: перед обычной недоминируемой сортировкой в нулевой фронт принудительно помещаются лучшие по каждой отдельной цели особи, что возвращает селективное давление при огромном $m$. Именно этот алгоритм работает внутри современного EvoSuite.

Автоматическое исправление программ. Пара «пройденные тесты / размер патча» напрямую борется с переобучением патча под тестовый набор — см. статью про APR.

Писать всё это самому в проекте не нужно — берите библиотеку: pymoo (лучший старт: NSGA-II/III, MOEA/D, индикаторы, визуализация фронтов), jMetal / jMetalPy (академический стандарт SBSE), DEAP (tools.selNSGA2 и selSPEA2 из коробки), MOEA Framework (Java, аккуратный экспериментальный harness), Platypus (простой API для прототипов). Свою реализацию стоит написать ровно один раз — чтобы понять алгоритм, как выше в статье.

Типичные ошибки

1. Скаляризация «чтобы не возиться». Веса выдумываются, невыпуклые компромиссы теряются, команда даже не узнаёт, что они были.
2. Цели без нормировки. Ломает crowding distance, hypervolume и любую скаляризацию сразу.
3. Скоррелированные цели. «Покрытие строк» и «покрытие ветвей» — почти одна цель; раздувание $m$ ухудшает поиск, ничего не давая взамен.
4. Сравнение MOEA по среднему фитнесу. У фронта нет «среднего качества» — используйте HV или IGD.
5. Один запуск вместо тридцати. Разброс между запусками часто больше, чем разница между алгоритмами.
6. Плавающая опорная точка HV. Числа из разных экспериментов становятся несравнимыми.
7. Большая популяция при дорогом фитнесе. Если evaluate — это 40 секунд прогона тестов, то $N=200$ и 500 поколений — 46 суток. Бюджет считайте в вызовах фитнеса, а не в поколениях.
8. NSGA-II при $m \ge 6$. Работать будет, сходиться — нет. Берите NSGA-III, MOEA/D или IBEA.
9. Штрафы вместо constrained-domination. Возвращает вас к подбору весов, от которого вы уходили.
10. Отдать заказчику фронт из 100 точек. Человек не выбирает из ста вариантов: кластеризуйте до 5–7 характерных компромиссов («минимальный», «сбалансированный», «максимальное покрытие»).

Мини-итог

• Если целей больше одной и они конфликтуют — единственного оптимума нет, есть фронт Парето.
• Доминирование — частичный порядок; отсюда вся специфика: фронты вместо сортировки, метрики множеств вместо чисел.
• NSGA-II = быстрая недоминируемая сортировка + crowding distance + элитизм через $P_t \cup Q_t$, $O(mN^2)$ на поколение. Дефолтный выбор для 2–3 целей.
• SPEA2 = внешний архив + raw fitness по силе доминаторов + плотность по $k$-му соседу. Дороже, зато равномернее фронт.
• Качество меряют hypervolume (не требует эталона, совместим с Парето) и IGD — обязательно со статистикой по десяткам запусков.
• При $m \ge 4$ доминирование вырождается: переходите к NSGA-III, MOEA/D или indicator-based алгоритмам.
• Итог работы MOO — не решение, а набор осознанных компромиссов для человека, принимающего решение.

Источники

• K. Deb, A. Pratap, S. Agarwal, T. Meyarivan. «A fast and elitist multiobjective genetic algorithm: NSGA-II», IEEE Transactions on Evolutionary Computation, 2002.
• E. Zitzler, M. Laumanns, L. Thiele. «SPEA2: Improving the Strength Pareto Evolutionary Algorithm», TIK-Report 103, ETH Zürich, 2001.
• E. Zitzler et al. «Performance assessment of multiobjective optimizers: an analysis and review», IEEE TEC, 2003.
• K. Deb, H. Jain. «An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: NSGA-III», IEEE TEC, 2014.
• Q. Zhang, H. Li. «MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition», IEEE TEC, 2007.
• K. Deb. «Multi-Objective Optimization using Evolutionary Algorithms», Wiley, 2001 — базовый учебник по теме.
• S. Yoo, M. Harman. «Pareto efficient multi-objective test case selection», ISSTA 2007.
• A. Panichella, F. Kifetew, P. Tonella. «Automated Test Case Generation as a Many-Objective Optimisation Problem with Dynamic Selection of the Targets» (DynaMOSA), IEEE TSE, 2018.
• A. Arcuri, L. Briand. «A Hitchhiker’s Guide to Statistical Tests for Assessing Randomized Algorithms in Software Engineering», STVR, 2014.
• Документация pymoo — читаемые реализации и примеры всех обсуждённых алгоритмов.

Что дальше

Мы прошли эволюционную ветку метаэвристик: локальный поиск, генетические алгоритмы, генетическое программирование и многокритериальность. Но есть принципиально другая семья алгоритмов, где поиск ведёт не популяция «родителей и потомков», а рой агентов, обменивающихся информацией через среду или напрямую.

Дальше — Роевой интеллект: муравьиные алгоритмы и PSO.