Многокритериальная оптимизация: когда нужно балансировать

🎯 Зачем это нужно?

Представь, что ты выбираешь новый смартфон 📱. Хочешь максимальную производительность, но минимальную цену. Долгую работу батареи, но лёгкий вес. Крутую камеру, но компактный размер. Звучит знакомо? Это и есть многокритериальная оптимизация!

В реальном мире редко есть один простой критерий успеха:

• 🚗 Автомобили: максимальная скорость + минимальный расход топлива + максимальная безопасность
• 🏥 Лекарства: максимальная эффективность + минимальные побочные эффекты + минимальная стоимость
• 🤖 Нейросети: максимальная точность + минимальное время работы + минимальный размер модели

📚 История вопроса

В 1906 году итальянский экономист Вильфредо Парето изучал распределение богатства и заметил интересную закономерность: нельзя улучшить положение одного человека, не ухудшив положение другого. Эта идея превратилась в принцип Парето - основу современной многокритериальной оптимизации.

Забавный факт: принцип “80/20” (80% результата от 20% усилий) тоже от Парето, но к оптимизации он не относится! 😄

💡 Интуиция

Представь, что ты тренер команды и выбираешь игрока. У тебя есть два кандидата:

• Игрок А: быстрый (9/10), но слабо бьёт (3/10)
• Игрок Б: медленный (4/10), но сильно бьёт (8/10)

Кого выбрать? Нет однозначного ответа! Оба варианта парето-оптимальны - нельзя улучшить один критерий, не ухудшив другой.

[МЕДИА: image_01] Описание: График с двумя осями (скорость и сила удара), показывающий игроков А и Б как парето-оптимальные точки Промпт: “2D scatter plot showing multi-objective optimization concept, two axes labeled speed and power, points A and B marked as pareto-optimal solutions, pareto frontier line, modern clean design, educational style”

В многокритериальной оптимизации мы ищем не одно решение, а множество компромиссных решений - Парето-фронт.

📐 Формальное определение

Задача многокритериальной оптимизации: min F(x) = [f₁(x), f₂(x), …, fₘ(x)]ᵀ

где x ∈ S (допустимое множество)

Доминирование по Парето: Решение x¹ доминирует x² (x¹ ≺ x²), если:

• ∀i: fᵢ(x¹) ≤ fᵢ(x²)
• ∃j: fⱼ(x¹) < fⱼ(x²)

Парето-оптимальность: Решение x* парето-оптимально, если не существует x ∈ S такого, что x ≺ x*.

🔍 Примеры с разбором

Пример 1: Обучение нейросети

Хотим обучить модель для распознавания изображений с двумя целями:

• f₁(x) = accuracy (максимизировать → минимизировать 1-accuracy)
• f₂(x) = inference_time (минимизировать)

# Три модели-кандидата:
models = [
    {"accuracy": 0.95, "time": 100},  # A: точная, но медленная
    {"accuracy": 0.85, "time": 20},   # B: быстрая, но менее точная  
    {"accuracy": 0.80, "time": 80}    # C: хуже по обоим критериям
]

Анализ доминирования:

• A vs B: A точнее, B быстрее → никто не доминирует
• A vs C: A точнее И быстрее → A доминирует C
• B vs C: B точнее И быстрее → B доминирует C

Парето-фронт: {A, B}

[МЕДИА: image_02] Описание: График accuracy vs inference_time с тремя точками, показывающий парето-фронт Промпт: “scatter plot with accuracy on y-axis and inference time on x-axis, three points A B C marked, pareto frontier connecting A and B, point C dominated and crossed out, tech-style visualization”

Пример 2: Портфельная оптимизация

Инвестор выбирает портфель акций:

• f₁(x) = -ожидаемая_доходность (минимизируем отрицание)
• f₂(x) = риск (дисперсия)

Классическая задача: “риск vs доходность”. Парето-фронт здесь называется эффективной границей - все оптимальные портфели лежат на этой кривой.

🎮 Практика

Базовый уровень 🟢

Задание 1: У тебя есть три способа добраться в университет:

• Автобус: время=40мин, стоимость=50₽
• Такси: время=15мин, стоимость=300₽
• Метро: время=30мин, стоимость=60₽

Какие варианты парето-оптимальны? (минимизируем и время, и стоимость)

Задание 2: Три алгоритма машинного обучения:

• SVM: precision=0.9, recall=0.7
• RandomForest: precision=0.8, recall=0.85
• NaiveBayes: precision=0.75, recall=0.6

Построй парето-фронт (максимизируем оба показателя).

Задание 3: Оптимизируем дизайн веб-сайта:

• Вариант А: скорость загрузки=2с, красота=8/10
• Вариант Б: скорость загрузки=5с, красота=9/10
• Вариант В: скорость загрузки=1с, красота=6/10

Определи доминирующие решения.

Продвинутый уровень 🟡

Задание 4: Реализуй функцию проверки доминирования:

def dominates(solution1, solution2):
    # solution = [f1, f2, ..., fn] (все минимизируем)
    # Верни True, если solution1 доминирует solution2
    pass

Задание 5: Задача размещения вышек сотовой связи. Нужно выбрать K=3 точки из N=6 кандидатов для минимизации:

• f₁ = максимальное расстояние до ближайшей вышки
• f₂ = общая стоимость установки

Кандидаты: [(x₁,y₁,cost₁), (x₂,y₂,cost₂), …, (x₆,y₆,cost₆)]

Как бы ты решал эту задачу? Опиши алгоритм.

Задание 6: В задаче оптимизации гиперпараметров нейросети получены результаты:

• Конфигурация 1: loss=0.1, training_time=2ч
• Конфигурация 2: loss=0.12, training_time=1ч
• Конфигурация 3: loss=0.08, training_time=4ч

Нарисуй парето-фронт и объясни выбор для production-системы.

Челлендж 🔴

Задание 7: Метрика Hypervolume Парето-фронт = {(2,5), (3,3), (5,2)}. Референсная точка = (6,6). Вычисли hypervolume - объём пространства, доминируемого фронтом.

Задание 8: Алгоритм NSGA-II Опиши основные этапы генетического алгоритма NSGA-II для многокритериальной оптимизации. Что такое crowding distance и зачем он нужен?

Задание 9: AutoML Challenge У тебя 10 разных архитектур нейросетей. Каждую можно обучать с 5 разными learning_rate. Три критерии: accuracy, model_size, training_time.

Как эффективно найти парето-фронт из 50 возможных конфигураций, не обучая все модели?

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

❌ Ошибка: “Найду лучшее решение по каждому критерию отдельно”
✅ Правильно: Ищем компромиссные решения - парето-фронт
💡 Почему: Оптимум по одному критерию часто ужасен по другим

❌ Ошибка: “Взвешу критерии произвольно: 0.7×f₁ + 0.3×f₂” ✅ Правильно: Веса должны отражать реальные предпочтения пользователя
💡 Почему: Неправильные веса дают бессмысленные решения

❌ Ошибка: “Все точки парето-фронта одинаково хороши” ✅ Правильно: Нужно учитывать контекст и предпочтения
💡 Почему: В реальных задачах важность критериев может меняться

🎓 Главное запомнить

✅ Парето-фронт - множество компромиссных решений, где нельзя улучшить один критерий без ухудшения другого ✅ Доминирование: x¹ ≺ x² если x¹ не хуже по всем критериям и лучше хотя бы по одному
✅ Применение: выбор гиперпараметров ML, portfolio optimization, engineering design

🔗 Связь с другими темами

Назад: Градиентный спуск с ограничениями помогает находить отдельные точки парето-фронта

Вперёд: Эволюционные алгоритмы (NSGA-II, MOEA/D) эффективно строят весь парето-фронт за один запуск

Практика: Hyperparameter tuning в AutoML, A/B тестирование с несколькими метриками, оптимизация рекомендательных систем