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

Многокритериальная оптимизация (также многокритериальное принятие решений, многокритериальный анализ, векторная оптимизация) — это раздел теории оптимизации и исследования операций, посвящённый задачам, в которых необходимо одновременно улучшать несколько, часто противоречащих друг другу, целевых показателей (критериев). В отличие от однокритериальной оптимизации, где существует единственное наилучшее решение, в многокритериальной задаче, как правило, не существует единственного решения, которое одновременно максимизирует или минимизирует все критерии. Вместо этого ищется множество компромиссных (эффективных, или Парето-оптимальных) решений, а окончательный выбор из них осуществляется лицом, принимающим решения (ЛПР), на основе его субъективных предпочтений.

История

Первые постановки задач многокритериальной оптимизации восходят к работам экономистов XVIII–XIX веков. В 1776 году Адам Смит в «Исследовании о природе и причинах богатства народов» рассматривал баланс между различными экономическими целями. В 1896 году итальянский экономист Вильфредо Парето формализовал понятие эффективности, которое впоследствии стало фундаментальным для многокритериальной оптимизации: решение является эффективным по Парето, если ни один из критериев не может быть улучшен без ухудшения хотя бы одного другого.

В 1940–1950-х годах, с развитием исследования операций и появлением вычислительной техники, многокритериальные задачи начали активно изучаться в военной и промышленной сферах. В 1951 году американский математик Гарольд Кун и Альберт Такер обобщили условия оптимальности для задач с несколькими целевыми функциями. В 1960-х годах советский математик Леонид Канторович, лауреат Нобелевской премии по экономике, разработал методы линейного программирования, которые легли в основу решения многокритериальных задач в планировании.

В 1970-х годах сформировались основные подходы к многокритериальной оптимизации, включая метод анализа иерархий (Томас Саати, 1977), метод ELECTRE (Бернар Руа, 1968) и метод TOPSIS (Хван и Юн, 1981). В 1980–1990-х годах развитие получили эволюционные алгоритмы, такие как генетические алгоритмы (NSGA, SPEA), которые позволили эффективно находить множество Парето-оптимальных решений для сложных нелинейных задач.

Основные понятия

Критерии и целевые функции

В многокритериальной задаче имеется n целевых функций (критериев) \( f_1(x), f_2(x), ..., f_n(x) \), где \( x \) — вектор переменных (решений). Критерии могут быть как максимизируемыми (например, прибыль), так и минимизируемыми (например, затраты). Часто критерии имеют разные единицы измерения и масштабы.

Область допустимых решений

Множество всех возможных значений переменных \( x \), удовлетворяющих ограничениям задачи, называется областью допустимых решений (ОДР). В многокритериальной оптимизации ОДР обычно представляет собой выпуклое или невыпуклое множество в пространстве переменных.

Парето-оптимальность

Решение \( x^* \) называется Парето-оптимальным (или эффективным), если не существует другого решения \( x \), такого, что:

• \( f_i(x) \geq f_i(x^*) \) для всех \( i \) (при максимизации),
• и хотя бы для одного \( i \) неравенство строгое.

Иными словами, ни один критерий не может быть улучшен без ухудшения другого. Множество всех Парето-оптимальных решений образует фронт Парето (или границу Парето) в пространстве критериев.

Лицо, принимающее решения (ЛПР)

В большинстве практических задач окончательный выбор из множества Парето-оптимальных решений делает человек или группа людей — лицо, принимающее решения. ЛПР обладает субъективными предпочтениями относительно важности критериев, которые могут быть выражены в виде весов, порогов или функций полезности.

Классификация методов

Методы многокритериальной оптимизации делятся на три основные категории в зависимости от того, на каком этапе решения учитываются предпочтения ЛПР.

1. Априорные методы (методы с предварительным заданием предпочтений)

В этих методах ЛПР задаёт свои предпочтения (например, веса критериев или целевые уровни) до начала оптимизации. Затем решается однокритериальная задача, и находится единственное решение.

• Метод взвешенных сумм: Каждому критерию присваивается вес \( w_i \), и задача сводится к максимизации (или минимизации) взвешенной суммы \( \sum w_i f_i(x) \). Недостаток: сложность выбора весов, особенно при нелинейных критериях.
• Метод целевого программирования: ЛПР задаёт целевые значения для каждого критерия, а затем минимизируется отклонение от этих целей. Используется в задачах планирования и управления.
• Метод анализа иерархий (МАИ): Разработан Томасом Саати. Позволяет структурировать задачу в виде иерархии (цель — критерии — альтернативы) и попарно сравнивать элементы для получения весов. Широко применяется в стратегическом планировании и выборе проектов.

2. Апостериорные методы (методы генерации множества Парето)

В этих методах сначала генерируется множество Парето-оптимальных решений, а затем ЛПР выбирает из него наиболее подходящее. Эти методы не требуют предварительного задания предпочтений, но могут быть вычислительно затратными.

• Эволюционные алгоритмы: Генетические алгоритмы (например, NSGA-II, SPEA2) моделируют процесс естественного отбора для поиска множества решений, близких к фронту Парето. Они эффективны для задач с большим числом переменных и нелинейными ограничениями.
• Метод ε-ограничений: Один из критериев оптимизируется, а остальные переводятся в ограничения с заданными порогами \( \varepsilon_i \). Изменяя пороги, можно получить различные Парето-оптимальные решения.
• Метод взвешенных сумм с вариацией весов: Путём перебора различных наборов весов решается задача взвешенной суммы, и полученные решения образуют аппроксимацию фронта Парето.

3. Интерактивные методы (методы с постепенным уточнением предпочтений)

В этих методах ЛПР взаимодействует с алгоритмом в процессе решения, постепенно уточняя свои предпочтения на основе промежуточных результатов. Это позволяет сочетать преимущества априорных и апостериорных подходов.

• Метод STEM (Step Method): На каждом шаге ЛПР указывает, какие критерии можно ухудшить, чтобы улучшить другие. Алгоритм строит новое решение, и процесс повторяется.
• Метод NIMBUS: Разработан в Финляндии. Позволяет ЛПР классифицировать критерии (улучшить, сохранить, ухудшить) и автоматически генерирует новые решения.
• Метод SWT (Surrogate Worth Trade-off): ЛПР оценивает «ценность» компромиссов между критериями, и алгоритм корректирует веса.

Применение

Многокритериальная оптимизация применяется в широком спектре областей, где необходимо учитывать несколько противоречивых целей.

Экономика и финансы

• Портфельная оптимизация: Выбор набора активов, максимизирующего ожидаемую доходность при минимизации риска (модель Марковица).
• Бюджетирование: Распределение средств между проектами с учётом затрат, выгод, рисков и социальных эффектов.
• Оценка инвестиционных проектов: Сравнение проектов по критериям NPV, IRR, срока окупаемости и экологических показателей.

Промышленность и инженерия

• Проектирование изделий: Оптимизация конструкции по критериям прочности, веса, стоимости и технологичности. Например, в авиастроении — баланс между аэродинамическими характеристиками и массой.
• Управление производством: Планирование выпуска продукции с учётом затрат, времени, качества и загрузки оборудования.
• Логистика: Выбор маршрутов доставки, минимизирующих время, стоимость и выбросы CO₂.

Энергетика и экология

• Планирование энергосистем: Оптимизация состава генерирующих мощностей по критериям стоимости, надёжности и выбросов парниковых газов.
• Управление водными ресурсами: Распределение воды между потребителями (сельское хозяйство, промышленность, население) с учётом экологических ограничений.
• Оценка воздействия на окружающую среду: Выбор технологий, минимизирующих загрязнение при заданных экономических затратах.

Информационные технологии

• Выбор архитектуры программного обеспечения: Баланс между производительностью, масштабируемостью, стоимостью разработки и безопасностью.
• Оптимизация нейронных сетей: Настройка гиперпараметров (число слоёв, скорость обучения) для максимизации точности при минимизации времени обучения и потребления памяти.
• Управление облачными ресурсами: Распределение вычислительных мощностей между задачами с учётом задержек, стоимости и энергопотребления.

Социальные и гуманитарные науки

• Градостроительство: Планирование городской инфраструктуры по критериям доступности, стоимости, экологии и социальной справедливости.
• Здравоохранение: Оптимизация распределения медицинских ресурсов (больницы, оборудование, персонал) с учётом качества обслуживания, затрат и охвата населения.
• Образование: Выбор учебных программ по критериям стоимости, качества и доступности.

Критика и ограничения

Несмотря на широкое применение, многокритериальная оптимизация имеет ряд ограничений и подвергается критике.

• Субъективность выбора: Окончательное решение зависит от предпочтений ЛПР, которые могут быть нестабильными, неполными или противоречивыми. Разные ЛПР могут выбрать разные решения из одного и того же множества Парето.
• Вычислительная сложность: Для задач с большим числом критериев (более 3–4) и переменных генерация полного фронта Парето может быть вычислительно неосуществима. Эволюционные алгоритмы дают лишь аппроксимацию, качество которой зависит от настроек.
• Проблема масштабирования: С увеличением числа критериев доля Парето-оптимальных решений в ОДР может резко возрасти, что затрудняет выбор. Этот эффект известен как «проклятие размерности».
• Неоднозначность весов: В методах взвешенных сумм веса часто выбираются произвольно или на основе экспертных оценок, что может приводить к необъективным результатам.
• Игнорирование неопределённости: Большинство классических методов предполагают детерминированные критерии, тогда как в реальности данные могут быть неполными или стохастическими. Существуют расширения (например, стохастическая многокритериальная оптимизация), но они сложнее в применении.

Интересные факты

• В 1972 году американский экономист Кеннет Эрроу доказал теорему о невозможности (Arrow’s impossibility theorem), которая утверждает, что не существует идеального метода агрегирования индивидуальных предпочтений в коллективное решение, что имеет прямое отношение к многокритериальному выбору.
• Метод анализа иерархий (МАИ) используется в ядерной энергетике для оценки безопасности реакторов и в военном планировании для выбора целей.
• В 2014 году российские учёные из Института проблем управления РАН разработали метод «Парето-оптимального синтеза» для задач управления сложными техническими системами, который позволяет учитывать до 10 критериев одновременно.
• Эволюционные алгоритмы многокритериальной оптимизации применяются в биологии для моделирования эволюции видов, где «критериями» выступают выживаемость, плодовитость и устойчивость к болезням.

Источники

• Саати Т. Л. «Принятие решений при зависимостях и обратных связях: Аналитические сети». — М.: Либроком, 2015.
• Канторович Л. В. «Математические методы организации и планирования производства». — Л.: Изд-во ЛГУ, 1939.
• Coello Coello C. A., Lamont G. B., Van Veldhuizen D. A. «Evolutionary Algorithms for Solving Multi-Objective Problems». — Springer, 2007.
• Miettinen K. «Nonlinear Multiobjective Optimization». — Springer, 1999.
• Hwang C. L., Yoon K. «Multiple Attribute Decision Making: Methods and Applications». — Springer, 1981.
• Arrow K. J. «Social Choice and Individual Values». — Yale University Press, 1951.