NSGA-II — Недоминируемая сортировка генетического алгоритма II
- Год
- 2002
- Тип
- Evolutionary multi-objective optimisation algorithm
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
NSGA-II (Non-dominated Sorting Genetic Algorithm II) — стандартный эталонный алгоритм для многокритериальной эволюционной оптимизации, представленный Дебом, Пратапом, Агравалом и Меяриваном в 2002 году.
Вместо сведения множества противоречивых целей к одному показателю, он развивает популяцию кандидатных решений на протяжении поколений и возвращает набор Парето-оптимальных компромиссных решений — фронт Парето — используя быструю недоминируемую сортировку и метрику расстояния между соседями для сохранения разнообразия.
Интуиция метода
Представьте, что вы хотите спроектировать продукт, который одновременно максимально дешев и максимально долговечен. Дешевле обычно означает менее долговечный, поэтому нет единственного идеального ответа — существует семейство разумных компромиссов. NSGA-II работает как популяция конкурирующих дизайнов: каждое поколение слабые дизайны, которые доминируются другими по всем критериям, устраняются, а выжившие распределяются так, чтобы они охватывали весь диапазон компромиссов, а не группировались в одном углу. После достаточного количества поколений у вас остается богатый выбор вариантов — фронт Парето — из которого вы выбираете баланс, соответствующий вашим приоритетам.
История
NSGA-II был опубликован Кальяном Мой Дебом и его коллегами из Индийского технологического института Канпура в 2002 году как исправленный и существенно улучшенный преемник оригинального NSGA (Srinivas & Deb, 1994). Ключевыми инновациями были быстрая процедура недоминируемой сортировки со сложностью O(MN²), явный оператор расстояния между соседями для поддержания разнообразия решений без параметра совместного использования (sharing parameter) и механизм элитарного отбора. Статья 2002 года в IEEE Transactions on Evolutionary Computation стала одной из наиболее цитируемых работ в области эволюционных вычислений и установила NSGA-II как де-факто эталон для многокритериальных эволюционных алгоритмов. Более поздние варианты — NSGA-III (2014) и другие — расширяют фреймворк для многокритериальных задач.
Когда применять
NSGA-II применяется всякий раз, когда задача имеет две или более противоречивые целевые функции, которые не могут быть объединены в один критерий без потери информации. Переменные решения могут быть непрерывными, бинарными или категориальными, и никаких предположений о распределении в ландшафте целей не требуется. Алгоритм подходит для задач проектирования, распределения ресурсов, планирования и портфельных задач, где спектр компромиссных решений более полезен, чем единственная оптимальная точка. Для достижения хорошего покрытия фронта требуется достаточное количество поколений (обычно несколько сотен или более); запуск слишком малого числа поколений является основным режимом отказа.
Ограничения и замечания
- Производительность снижается, когда количество целей превышает три или четыре — расстояние между соседями становится плохой мерой разнообразия в высоких размерностях.
- Требует тщательной настройки размера популяции и количества поколений; слишком малое количество поколений препятствует адекватному покрытию фронта.
- Оценка целевых функций, включающих дорогостоящие симуляции, делает алгоритм вычислительно затратным.
- Результаты стохастичны: различные случайные начальные значения могут привести к разным фронтам Парето, поэтому рекомендуется многократное выполнение и статистическое сравнение (например, по гиперобъему).
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Производит разнообразный набор Парето-оптимальных компромиссных решений за один прогон, избегая необходимости повторять оптимизацию с различными весами.
- Быстрая недоминируемая сортировка выполняется за время O(MN²) (M целей, N размер популяции), что делает ее применимой для умеренных размеров задач.
- Элитарный отбор гарантирует, что хорошие решения, найденные на ранних этапах, никогда не отбрасываются.
- Применим к непрерывным, бинарным и категориальным переменным решения без предположений о распределении.
- Широко проверен в областях инженерии, исследования операций и вычислительных наук.
Применение
- Инженерное проектирование: одновременное минимизация веса и максимизация прочности конструкции механических компонентов.
- Экологические и энергетические системы: балансировка стоимости, выбросов и надежности при планировании энергосетей или возобновляемых источников энергии.
- Здравоохранение и исследования операций: планирование, оптимизирующее время ожидания пациентов, использование ресурсов и стоимость одновременно.
- Оптимизация портфеля в финансах и выбор проектов в бизнесе: компромисс между доходностью, риском и ликвидностью.
- Настройка гиперпараметров в машинном обучении: оптимизация точности по сравнению со сложностью модели или временем вывода.
Как это работает
Как это работает
Популяция кандидатных решений создается путем случайной (или целенаправленной) выборки переменных решения в пределах их границ. Размер популяции устанавливается достаточно большим, чтобы обеспечить разнообразие в пространстве целей с самого начала.
Каждое кандидатное решение декодируется в значения переменных решения, и каждая целевая функция оценивается. Результатом является вектор оценок целей для каждого индивида. Этот шаг часто является вычислительным узким местом, когда цели включают симуляции или дорогостоящие модели.
Решения ранжируются путем недоминируемой сортировки: первый фронт содержит все решения, которые не доминируются никаким другим решением по всем целям; второй фронт содержит решения, доминируемые только решениями из первого фронта; и так далее. Внутри каждого фронта вычисляется оценка расстояния между соседями, чтобы измерить, насколько изолировано решение от своих соседей — более высокое расстояние между соседями означает, что решение занимает менее плотную область фронта.
Элитарная стратегия отбора объединяет текущую популяцию с потомками и сохраняет N лучших индивидов, заполняя фронты по порядку и используя расстояние между соседями для разрешения ничьих в последнем допустимом фронте. Это гарантирует, что хорошие решения, найденные в предыдущих поколениях, никогда не теряются.
Отобранные индивиды размножаются с помощью генетических операторов — бинарного турнирного отбора, симулированного бинарного кроссовера (SBX) и полиномиальной мутации — производя новую популяцию потомков. Эти операторы сохраняют значимые вариации, исследуя окрестности перспективных решений.
Шаги оцениваются через эволюцию, повторяются для заданного числа поколений. Сходимость оценивается путем визуального осмотра фронта Парето или отслеживания индикатора гиперобъема. Окончательным результатом является набор недоминируемых решений, аппроксимирующий истинный фронт Парето.
Частые ошибки
- Запуск менее чем на несколько сотен поколений обычно дает неполный фронт Парето; если вычислительный бюджет ограничен, рассмотрите вместо этого взвешенную однокритериальную оптимизацию.
- Рассматривать задачу с одной целью как многокритериальную избыточно — используйте однокритериальный оптимизатор.
- Пренебрежение установкой разумных границ переменных приводит к тому, что популяции никогда не достигают допустимых или осмысленных областей пространства поиска.
- Сообщение только одного решения из фронта Парето без раскрытия полного фронта скрывает структуру компромиссов, которую призван выявить NSGA-II.
Часто задаваемые вопросы
Сколько поколений нужно NSGA-II?
Универсального правила нет, но запуск менее чем на несколько сотен поколений обычно дает неполный фронт Парето. Практический подход — построить график индикатора гиперобъема по поколениям и остановиться, когда он стабилизируется. Если вычислительный бюджет не позволяет этого, взвешенный однокритериальный оптимизатор является более безопасной альтернативой.
Что такое фронт Парето?
Фронт Парето — это набор решений, где невозможно улучшить один критерий, не ухудшив при этом хотя бы один другой. NSGA-II аппроксимирует этот фронт, предоставляя вам полный набор сбалансированных компромиссов, а не единственное решение.
Может ли NSGA-II обрабатывать более двух целей?
Да, но расстояние между соседями — механизм разнообразия — становится менее эффективным, когда количество целей превышает три или четыре (режим «многих целей»). Для задач с пятью или более целями обычно предпочтительнее NSGA-III или алгоритмы, основанные на декомпозиции, такие как MOEA/D.
Является ли NSGA-II детерминированным?
Нет. Генетические операторы и начальная популяция включают случайность, поэтому разные запуски с разными случайными начальными значениями могут давать разные аппроксимации фронта Парето. Лучшая практика — запускать алгоритм несколько раз и сравнивать качество фронта с использованием индикатора гиперобъема.
Похожие методы
Источники
Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
Открыть ссылку DOIСкопировано.Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.
Открыть ссылку DOIСкопировано.