Skip to content
Назад к результатам поиска

Многокритериальный генетический алгоритм (MOGA) — Эволюционный поиск Парето-оптимальных решений

Автор метода
Schaffer, J. D. (early MOGA); Goldberg, D. E. (GA foundations)
Год
1984
Тип
Population-based evolutionary optimizer
Семейство
Simulation / optimization

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

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

Он избегает сведения компромиссов к единой оценке, вместо этого производя набор недоминируемых решений, из которых может выбирать лицо, принимающее решение.

Интуиция метода

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

История

Многокритериальные генетические алгоритмы возникли из векторно-оценочного генетического алгоритма (VEGA) Шаффера в 1984 году, первого GA, явно обрабатывающего несколько целей. Учебник Голдберга 1989 года формализовал ранжирование на основе Парето как принципиальную стратегию назначения приспособленности. Область быстро развивалась с MOGA Фонсеки и Флеминга (1993), NSGA Сриниваса и Деба (1994) и знакового NSGA-II (Деб и др., 2002), который стал стандартным эталоном в этой области и остается наиболее цитируемым эволюционным многокритериальным алгоритмом.

Когда применять

Использовать MOGA, когда задача имеет две или более конфликтующие цели и не существует единственного оптимального решения — типичными областями являются проектирование, конфигурация цепочек поставок, оптимизация портфеля и планирование окружающей среды. Он подходит для невыпуклых, мультимодальных или «черных ящиков» ландшафтов целей, где градиентные методы неприменимы. НЕ использовать его, когда достаточно одной четко определенной цели (вместо этого использовать стандартный GA или математическое программирование), когда оценка популяции вычислительно непомерна и суррогаты недоступны, когда цели могут быть законно агрегированы известной взвешенной суммой без потери информации, или когда небольшой допустимый набор позволяет исчерпывающую перечислимость.

Ограничения и замечания

  • Вычислительная стоимость масштабируется с размером популяции и количеством оценок функций; каждая оценка сложных симуляций может быть дорогостоящей.
  • Сходимость к истинному Парето-фронту не гарантируется — результаты являются эвристическими аппроксимациями, чувствительными к выбору гиперпараметров (размер популяции, скорость скрещивания, скорость мутации).
  • Производительность снижается по мере роста числа целей сверх трех или четырех (многокритериальная оптимизация требует специализированных алгоритмов, таких как NSGA-III или MOEA/D).
  • Требует тщательной настройки генетических операторов и поддержания разнообразия во избежание преждевременной сходимости или плохого покрытия фронта.
  • Не предоставляет единственного рекомендуемого решения — окончательный выбор из Парето-фронта по-прежнему требует оценочных суждений или вторичного правила принятия решений.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Производит разнообразный набор Парето-оптимальных решений за один прогон, предоставляя лицам, принимающим решения, явные варианты компромисса, а не одно решение.
  • Работает на невыпуклых, разрывных и мультимодальных ландшафтах целей без необходимости градиентов или математической структуры, специфичной для задачи.
  • По своей сути основан на популяции, что упрощает распараллеливание по ядрам или распределенным системам.
  • Гибкое кодирование позволяет использовать как непрерывные переменные, так и целые числа, бинарные строки и перестановки в рамках одной структуры.
  • Хорошо поддерживается зрелыми программными библиотеками (DEAP, pymoo, jMetal) и десятилетиями эталонных данных.

Применение

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

Как это работает

Как это работает

1

Сгенерировать начальную популяцию из N кандидатных решений (хромосом) случайным образом или с использованием эвристик предметной области, кодируя каждое решение как вектор переменных принятия решений. Определить k целевых функций f1(x), f2(x), ..., fk(x) для одновременного минимизации или максимизации.

2

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

3

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

4

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

5

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

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

  • Рассмотрение всех решений на Парето-фронте как равнозначных без привлечения экспертов предметной области для окончательного выбора компромисса может привести к произвольным или плохо обоснованным решениям.
  • Использование слишком маленькой популяции приводит к разреженным, нерепрезентативным фронтам; слишком большая популяция увеличивает вычислительную нагрузку без пропорциональной выгоды.
  • Игнорирование обработки ограничений — недопустимые решения должны быть явно оштрафованы или исправлены; невыполнение этого искажает поиск в сторону недопустимых областей.
  • Применение MOGA к задачам с более чем четырьмя целями без перехода к многокритериальному алгоритму приводит к загроможденным, неинформативным фронтам, где почти все решения недоминируемы.
  • Отчетность только о финальном Парето-фронте без диагностики сходимости (гиперобъем за поколения) делает невозможным оценку того, действительно ли алгоритм сошелся.

Часто задаваемые вопросы

Чем MOGA отличается от запуска однокритериального GA с взвешенной суммой целей?

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

Что такое Парето-фронт и почему он важен?

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

Сколько целей MOGA может эффективно обрабатывать?

Стандартные варианты MOGA, такие как NSGA-II, хорошо работают для двух или трех целей. При более чем четырех целях доля недоминируемых решений быстро растет (проклятие размерности в пространстве целей), делая Парето-фронт большим, а давление отбора — слабым. Для четырех и более целей рекомендуются многокритериальные алгоритмы (NSGA-III, MOEA/D, IBEA).

Какой критерий остановки следует использовать?

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

Может ли MOGA обрабатывать ограничения?

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

Похожие методы

Источники

  1. Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addison-Wesley.

    ISBN: 9780201157673
    Скопировано.
  2. 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
    Скопировано.