В инженерном проектировании редко приходится оптимизировать лишь один параметр: чаще всего конструктор разрывается между стоимостью, надежностью, весом и производительностью. В рамках курса AA222 в Стэнфордском университете Сидни (Sydney), постдок лаборатории SISL (Stanford Intelligent Systems Laboratory), представила глубокий обзор методов многокритериальной оптимизации, объяснив, как математика помогает находить баланс в условиях неминуемых компромиссов.
⚖️ От одного к многим: суть многокритериальной оптимизации 0:04
До этого момента в курсе рассматривались задачи с одной целевой функцией, где на выходе всегда получалось одно число . В многокритериальной оптимизации (Multiobjective Optimization) ситуация меняется: теперь целевая функция возвращает вектор значений, каждое из которых представляет отдельную цель .
В качестве живого примера Сидни приводит жизнь аспиранта (PhD student), который одновременно пытается оптимизировать сразу несколько показателей :
- Проведение крутых исследований;
- Написание статей;
- Поддержание личного счастья;
- Удовлетворенность научного руководителя;
- Завершение учебы в разумные сроки.
По словам Сидни, некоторые цели могут быть согласованы — например, профессор Майкл Кочендерфер часто говорит, что счастье студента напрямую связано со счастьем руководителя . Однако большинство целей конфликтуют: чем больше времени тратится на «крутые исследования», тем меньше шансов защититься вовремя. Это создает необходимость в поиске компромиссов (trade-offs) .
🏆 Парето-оптимальность и концепция доминирования 3:15
Ключевым понятием в этой области является Парето-оптимальность. Проект считается оптимальным по Парето, если невозможно улучшить один показатель, не ухудшив при этом другой . Совокупность всех таких точек образует «фронт Парето» (Pareto frontier) .
Для наглядности Сидни вводит понятие доминирования:
- Дизайн A доминирует над дизайном B, если он не хуже по всем параметрам и хотя бы по одному параметру строго лучше .
- В шуточном примере с языками программирования (читаемость против производительности) Сидни утверждает, что Julia доминирует над Python .
В классической оптимизации целью является поиск минимума, но в многокритериальной задаче целью становится генерация всего фронта Парето, чтобы проектировщик мог видеть весь спектр доступных компромиссов .
🛠️ Математические методы построения фронта 10:12
Сидни подробно разобрала несколько классических подходов к решению таких задач:
1. Метод ограничений (Constraint Method) Одну цель оставляют в качестве основной для оптимизации, а остальные превращают в жесткие ограничения (например, «параметр $f_2$ должен быть не больше значения $C_2$»). Изменяя (сканируя) значение $C_2$, можно получить различные точки на фронте Парето .
2. Лексикографический метод (Lexicographic Method) Цели ранжируются по важности. Сначала оптимизируется самая важная цель. Затем вторая цель оптимизируется с условием, что первая не станет хуже полученного результата . По мнению Сидни, этот метод часто дает только крайние точки фронта и не всегда эффективен для поиска промежуточных решений .
3. Метод взвешенной суммы (Weighted Sum Method) Это самый интуитивный подход: каждой цели присваивается вес, и они суммируются в единую функцию.
- Плюс: Простота реализации.
- Минус: Метод не способен находить точки в вогнутых (невыпуклых) частях фронта Парето . Если фронт имеет сложную форму, взвешенная сумма просто «перепрыгнет» через целые сегменты возможных решений.
4. Целевое программирование (Goal Programming) Вместо весов задается «точка утопии» — идеальный, но недостижимый результат (например, нулевая вероятность столкновения самолетов при нулевом количестве предупреждений) . Задача сводится к минимизации расстояния (нормы $L_1$, $L_2$ или $L_\infty$) от текущего дизайна до этой идеальной точки .
🧬 Популяционные методы и ранжирование 27:17
Для сложных задач применяются эволюционные алгоритмы. Один из примеров — векторный генетический алгоритм (VEGA), где разные подпопуляции оптимизируются под разные цели, а затем скрещиваются .
Особый интерес представляет метод неблокируемого ранжирования (nondomination ranking) :
- Из всей массы решений выделяются те, что лежат на текущем фронте Парето (Ранг 1).
- Они временно удаляются, и процедура повторяется для оставшихся точек (Ранг 2) .
- Это позволяет оценить, насколько далеко конкретное решение находится от идеального фронта.
Сидни также упомянула техники «нишевания» (niche techniques), которые предотвращают скучивание решений в одной области и обеспечивают равномерное распределение точек вдоль всего фронта Парето .
🍬 Извлечение предпочтений: эксперимент с конфетами 30:54
Даже имея перед глазами фронт Парето, инженер должен выбрать одну конкретную точку для реализации. Но как выбрать веса, если заказчик (например, Федеральное управление гражданской авиации США — FAA) не знает точных математических коэффициентов?
Для этого используется «извлечение предпочтений» (preference elicitation) через парные сравнения . Сидни провела демонстрацию на примере выбора наборов конфет (M&M's, Sour Patch Kids и Skittles):
- Волонтеру Элли предлагались два разных набора конфет (например, 1 M&M, 3 кислых мармеладки, 6 Skittles против другого варианта) .
- Каждый выбор Элли формировал линейное неравенство в пространстве весов .
- После четырех вопросов пространство возможных весов значительно сузилось, что позволило предсказать выбор Элли в новом, контрольном тесте .
Этот метод лежит в основе современных технологий, таких как RLHF (Reinforcement Learning from Human Feedback), используемых для настройки больших языковых моделей . Сидни подчеркнула, что в реальности исследователи учитывают возможную иррациональность людей, используя вероятностные распределения вместо жестких неравенств .
