Многокритериальная оптимизация: эволюционные алгоритмы и метод NSGA-II

Когда задача многокритериальной оптимизации содержит сложные нелинейные, разрывные функции или целочисленные переменные, классические математические методы скаляризации (линейной свертки) терпят полный провал. Они либо застревают в локальных оптимумах, либо физически не способны найти решения, лежащие на вогнутых участках границы Парето. Для преодоления этого алгебраического барьера исследование операций заимствовало мощнейший инструмент из биологии — эволюционные вычисления. Эволюционные алгоритмы способны одновременно исследовать множество областей пространства поиска, оперируя популяциями решений, что делает их идеальным механизмом для одновременного построения всего фронта Парето за один прогон.

Среди сотен метаэвристик абсолютным отраслевым стандартом многокритериальной оптимизации стал алгоритм NSGA-II (Non-dominated Sorting Genetic Algorithm II), разработанный Каляном Дейбом в 2002 году. В отличие от простых генетических алгоритмов, NSGA-II не пытается смешать критерии в одну функцию приспособленности. Вместо этого он использует строгий математический аппарат доминирования по Парето. Решение А доминирует над решением Б, если А не хуже Б по абсолютно всем критериям, и строго лучше хотя бы по одному. На каждом поколении алгоритм берет популяцию решений и разбивает ее на непересекающиеся фронты. Первый фронт состоит из абсолютно недоминируемых решений. Если их удалить, оставшиеся лучшие решения образуют второй фронт, и так далее. Этот процесс называется быстрой недоминируемой сортировкой.

Вторая гениальная инновация NSGA-II — это оператор скученности (Crowding Distance). Главная проблема многокритериального поиска заключается не только в том, чтобы приблизиться к истинной границе Парето, но и в том, чтобы распределить найденные решения максимально равномерно по всему фронту. ЛПР нужен широкий выбор: от самых дешевых до самых надежных вариантов, а не скопление решений в одной узкой нише. Для каждой точки фронта алгоритм вычисляет расстояние до ближайших соседей в многомерном пространстве критериев. Если точка находится в плотном скоплении, ее дистанция скученности мала; если она находится на отшибе (исследует новые территории), ее дистанция велика. Алгоритм всегда отдает предпочтение точкам с большей дистанцией скученности, обеспечивая фантастическое разнообразие генофонда.

Механизм эволюции в NSGA-II опирается на принцип элитизма. Родительская и дочерняя популяции (созданная путем кроссинговера и мутаций) сливаются в единый мега-пул. Из этого пула алгоритм отбирает ровно половину самых лучших особей для следующего поколения, считывая их фронт за фронтом. Если последний фронт, который помещается в квоту, не влезает целиком, оператор скученности отсекает тех особей, которые расположены слишком близко друг к другу. Математическая сложность этого алгоритма составляет O(M*N^2), где M — количество критериев, а N — размер популяции. Это феноменально быстро, что позволяет запускать NSGA-II для оптимизации процессов в реальном времени.

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

Оценить