Многокритериальная оптимизация и Парето

Когда целей несколько и они конфликтуют, единственного «лучшего» решения нет — есть множество компромиссов Парето.

Парето-оптимальное решение — решение, которое нельзя улучшить по одному критерию, не ухудшив хотя бы один другой.

Когда целей несколько

До сих пор у нас была одна цель $f$. Но реальность многокритериальна: машину хочется и быструю, и дешёвую, и безопасную; портфель — и доходный, и малорискованный. Эти цели конфликтуют: дешевле обычно значит медленнее. Нельзя минимизировать всё сразу — приходится искать компромиссы.

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

Решение $A$ доминирует $B$, если $A$ не хуже по всем критериям и строго лучше хотя бы по одному. Доминируемые решения отбрасываем — они объективно плохи. А вот среди недоминируемых выбрать «лучшее» уже нельзя без дополнительных предпочтений: они несравнимы. Множество всех недоминируемых решений — это Парето-фронт, граница достижимых компромиссов.

Находим Парето-фронт

Пусть есть варианты телефонов, каждый с ценой (минимизируем) и качеством камеры (минимизируем как «–качество», но удобнее: минимизируем цену и минимизируем «штраф» $=10-\text{качество}$). Найдём недоминируемые.

# (цена, штраф=10-качество): оба критерия минимизируем
phones = {"A": (300, 6), "B": (500, 3), "C": (400, 5),
          "D": (700, 1), "E": (450, 7), "F": (350, 4)}

def dominated(p, others):
    px, py = p
    for (ox, oy) in others:
        if ox <= px and oy <= py and (ox < px or oy < py):
            return True
    return False

front = []
for name, val in phones.items():
    others = [v for n, v in phones.items() if n != name]
    if not dominated(val, others):
        front.append((name, val))

print("Парето-фронт (недоминируемые):")
for name, (price, pen) in sorted(front, key=lambda t: t[1][0]):
    print(f"  {name}: цена={price}, качество камеры={10 - pen}")

Вывод:

Парето-фронт (недоминируемые):
  A: цена=300, качество камеры=4
  F: цена=350, качество камеры=6
  B: цена=500, качество камеры=7
  D: цена=700, качество камеры=9

Телефоны $C$ и $E$ выпали: $C$ доминируется $B$ (дешевле и лучше камера... проверьте: $B$ дороже, но $F$ при $350$ и качестве $6$ доминирует $C$ при $400$ и $5$), $E$ — телефоном $A$ (дешевле и лучше). Оставшиеся $A,F,B,D$ образуют фронт: каждый — разумный выбор при своём бюджете, и между ними решает уже личное предпочтение «цена против камеры».

Сведение к одной цели

Чтобы выбрать одно решение из фронта, вводят дополнительную информацию о предпочтениях. Способы:

• Взвешенная сумма: $\min\ \sum_i w_i f_i(x)$ — назначаем веса важности целям. Просто, но не находит «вогнутые» части фронта.
• $\varepsilon$-ограничения: минимизируем одну цель, остальные переводим в ограничения ($f_2\le\varepsilon$).
• Целевое программирование: минимизируем отклонение от желаемых значений целей.

Как работает под капотом

Эволюционные методы (например, NSGA-II — генетический алгоритм для многокритериальной оптимизации) умеют находить весь Парето-фронт за один прогон: популяция распределяется вдоль фронта, поддерживая разнообразие компромиссов. Это удобно, когда лицо, принимающее решение, хочет увидеть всю палитру вариантов, а уже потом выбрать. Ключевая мысль: многокритериальность не «решается» автоматически — математика даёт фронт, а окончательный выбор требует человеческих предпочтений.

Частые ошибки

• Искать одно «оптимальное» решение. При конфликтующих целях его нет — есть фронт компромиссов.
• Слепо складывать цели с равными весами. Веса выражают предпочтения и сильно влияют на выбор; задавайте их осознанно.
• Складывать величины разных масштабов. Цена в тысячах и качество в баллах несопоставимы без нормировки.

Итоги

• При конфликтующих целях единственного оптимума нет; есть Парето-фронт недоминируемых решений.
• $A$ доминирует $B$, если не хуже по всем целям и лучше хотя бы по одной.
• Выбор из фронта требует предпочтений: взвешенная сумма, $\varepsilon$-ограничения; весь фронт даёт NSGA-II.