Аннотация
Многокритериальные эволюционные алгоритмы (МОЭА) стали важным направлением исследований в области эволюционных вычислений за последние два десятилетия. Этот обзор представляет современное состояние исследований в области МОЭА, включая основные алгоритмы, показатели эффективности, тестовые задачи, приложения и вызовы. Статья охватывает широкий спектр подходов, от классических методов до последних разработок, и предоставляет всесторонний анализ сильных и слабых сторон различных алгоритмов. Особое внимание уделяется вопросам сходимости, разнообразия и эффективности вычислений в контексте многокритериальной оптимизации.
Ключевые слова: многокритериальная оптимизация, эволюционные алгоритмы, Парето-оптимальность, показатели эффективности, тестовые задачи.
Abstract
Multiobjective evolutionary algorithms (MOEAs) have become an important research area in evolutionary computation over the past two decades. This survey presents the state-of-the-art research in MOEAs, including major algorithms, performance metrics, test problems, applications, and challenges. The paper covers a wide range of approaches from classical methods to recent developments, and provides a comprehensive analysis of the strengths and weaknesses of various algorithms. Special attention is paid to convergence, diversity, and computational efficiency issues in the context of multiobjective optimization.
Keywords: multiobjective optimization, evolutionary algorithms, Pareto optimality, performance metrics, test problems.
Введение
Многокритериальные задачи оптимизации (МКО) широко распространены в реальном мире, где часто необходимо одновременно оптимизировать несколько противоречивых целей. В отличие от однокритериальной оптимизации, где существует единственное оптимальное решение, в МКО существует множество решений, представляющих различные компромиссы между целями. Эти решения образуют так называемый фронт Парето.
Эволюционные алгоритмы (ЭА) оказались особенно эффективными для решения МКО благодаря их способности находить множество решений за один запуск. За последние два десятилетия было разработано множество многокритериальных эволюционных алгоритмов (МОЭА), каждый из которых предлагает различные подходы к балансировке сходимости и разнообразия решений.
Основная задача МОЭА: найти набор решений, который хорошо аппроксимирует истинный фронт Парето с точки зрения как сходимости (близость к истинному фронту), так и разнообразия (равномерное распределение по фронту).
Этот обзор структурирован следующим образом: сначала рассматриваются основные концепции МКО, затем представлены классические и современные МОЭА, обсуждаются показатели эффективности и тестовые задачи, анализируются практические приложения и выделяются основные вызовы и направления будущих исследований.
Основные концепции многокритериальной оптимизации
Решение x доминирует над решением y (x ≺ y), если x не хуже y по всем критериям и строго лучше хотя бы по одному критерию.
Решение является Парето-оптимальным, если не существует другого решения, которое доминирует над ним.
Множество всех Парето-оптимальных решений в пространстве критериев.
Множество всех Парето-оптимальных решений в пространстве решений.
Точка в пространстве критериев, составленная из оптимальных значений каждого критерия по отдельности.
Точка в пространстве критериев, составленная из наихудших значений каждого критерия среди Парето-оптимальных решений.
Формальная постановка задачи
Многокритериальная задача оптимизации формулируется как:
Минимизировать: F(x) = (f₁(x), f₂(x), ..., fₘ(x))ᵀ
При условиях: x ∈ Ω
где:
x = (x₁, x₂, ..., xₙ)ᵀ - вектор решений
Ω - пространство допустимых решений
fᵢ: Ω → ℝ - i-я целевая функция
m ≥ 2 - количество целевых функций
Основная цель МОЭА - найти хорошее приближение истинного фронта Парето P* с помощью аппроксимирующего фронта P.
Классификация многокритериальных эволюционных алгоритмов
Используют методы агрегации целей и основаны на фитнес-функциях с даммингом. Примеры: VEGA, MOGA.
- VEGA (1984)
- MOGA (1993)
- NSGA (1994)
- NPGA (1994)
Используют концепцию доминирования Парето и механизмы поддержания разнообразия. Примеры: NSGA-II, SPEA2.
- SPEA (1999)
- NSGA-II (2002)
- SPEA2 (2001)
- PAES (2000)
Используют индикаторы качества, разложение задач и гибридные подходы. Примеры: MOEA/D, HypE.
- MOEA/D (2007)
- HypE (2007)
- IBEA (2004)
- SMS-EMOA (2005)
Подробный обзор ключевых алгоритмов
Разработанный Дебом и др. в 2002 году, NSGA-II стал одним из самых популярных МОЭА благодаря своей эффективности и простоте реализации. Основные особенности:
Эффективный алгоритм O(mN²) для классификации решений по фронтам доминирования.
Мера плотности решений, используемая для поддержания разнообразия внутри каждого фронта.
Сохраняет лучшие решения между поколениями, обеспечивая монотонное улучшение.
1. Инициализировать популяцию P₀ размером N
2. Для t = 0 до T-1:
2.1. Создать потомство Q₀ с помощью генетических операторов
2.2. Объединить Rₜ = Pₜ ∪ Qₜ
2.3. Выполнить недоминируемую сортировку Rₜ → F₁, F₂, ...
2.4. Pₜ₊₁ = ∅, i = 1
2.5. Пока |Pₜ₊₁| + |Fᵢ| ≤ N:
Pₜ₊₁ = Pₜ₊₁ ∪ Fᵢ
i = i + 1
2.6. Отсортировать Fᵢ по расстоянию переполнения
2.7. Добавить в Pₜ₊₁ первые (N - |Pₜ₊₁|) решений из Fᵢ
3. Вернуть Pₜ
Предложенный Чжаном и Ли в 2007 году, MOEA/D использует принцип разложения многокритериальной задачи на множество скалярных подзадач:
Основная идея: вместо непосредственной работы с многокритериальной задачей, MOEA/D разлагает ее на N скалярных подзадач с помощью весовых векторов и методов агрегации (например, взвешенная сумма, Tchebycheff, граничное пересечение).
Преимущества MOEA/D включают:
- Высокую вычислительную эффективность благодаря параллельному решению подзадач
- Хорошую сходимость за счет локальной информации о соседних подзадачах
- Гибкость в выборе методов агрегации
- Естественное получение равномерно распределенных решений
Показатели эффективности МОЭА
Измеряют близость найденного фронта к истинному фронту Парето.
GD IGD ε-индикаторОценивают равномерность распределения решений по фронту Парето.
Spread Spacing Δ-показательОбъединяют измерения сходимости и разнообразия в одну метрику.
HV R2 S-метрика| Показатель | Полное название | Назначение | Преимущества | Недостатки |
|---|---|---|---|---|
| GD | Generational Distance | Сходимость | Простота вычисления | Не учитывает разнообразие |
| IGD | Inverted Generational Distance | Сходимость и разнообразие | Комплексная оценка | Требует знания истинного фронта |
| HV | Hypervolume | Композитный | Теоретически обоснован | Вычислительно сложный |
| Spread | Spread Indicator | Разнообразие | Хорошо измеряет равномерность | Чувствителен к крайним точкам |
| ε | Additive Epsilon Indicator | Сходимость | Не требует эталонного фронта | Может быть неинформативным |
Гиперобъем (Hypervolume - HV)
Гиперобъем является одним из наиболее популярных и теоретически обоснованных показателей эффективности МОЭА. Он измеряет объем пространства критериев, доминируемого аппроксимирующим фронтом относительно заданной точки отсчета.
Формальное определение:
HV(P, r) = volume(⋃_{x∈P} [f₁(x), r₁] × [f₂(x), r₂] × ... × [fₘ(x), rₘ])
где:
P - аппроксимирующий фронт Парето
r = (r₁, r₂, ..., rₘ) - точка отсчета (обычно хуже всех точек P)
volume(·) - функция вычисления объема
Преимущества гиперобъема включают строгую монотонность (увеличение HV означает улучшение по Парето) и возможность одновременной оценки сходимости и разнообразия. Основной недостаток - вычислительная сложность, которая растет экспоненциально с увеличением количества критериев.
Тестовые задачи и бенчмарки
Серия из 6 тестовых задач (ZDT1-ZDT6) для двукритериальной оптимизации. Разработана для тестирования различных аспектов МОЭА.
- ZDT1: выпуклый фронт Парето
- ZDT2: невыпуклый фронт Парето
- ZDT3: разрывный фронт Парето
- ZDT4: множество локальных оптимумов
- ZDT5: бинарное представление
- ZDT6: неоднородная плотность
Серия из 7 тестовых задач (DTLZ1-DTLZ7) для многокритериальной оптимизации с произвольным количеством критериев.
- DTLZ1: линейный фронт Парето
- DTLZ2: сферический фронт Парето
- DTLZ3: множество локальных оптимумов
- DTLZ4: смещенное распределение
- DTLZ5: вырожденный фронт
- DTLZ6: вырожденный фронт с множеством локальных оптимумов
- DTLZ7: разрывный фронт
Гибкая система тестовых задач, позволяющая генерировать задачи с различными свойствами фронта Парето и сложностью ландшафта.
- WFG1: смешанный тип формы
- WFG2: выпуклый разрывный фронт
- WFG3: линейный вырожденный фронт
- WFG4: вогнутый фронт с множеством локальных оптимумов
- WFG5: вогнутый фронт с декомпозиционными трудностями
- WFG6: вогнутый фронт с зависимостями позиционных параметров
- WFG7: вогнутый фронт с зависимостями расстоятельных параметров
- WFG8: вогнутый фронт с зависимостями параметров
- WFG9: вогнутый фронт с параметрическими и зависимостными трудностями
| Серия задач | Количество критериев | Основные характеристики | Типичное использование |
|---|---|---|---|
| ZDT | 2 | Различные формы фронта, локальные оптимумы | Базовое тестирование алгоритмов |
| DTLZ | M ≥ 2 | Масштабируемость, различные сложности | Тестирование масштабируемости |
| WFG | M ≥ 2 | Гибкость, различные свойства | Всесторонняя оценка |
| CEC | M ≥ 2 | Реалистичные сложности | Соревнования, сравнения |
Практические приложения
Оптимизация аэродинамических профилей, конструкций, планирование производства с учетом стоимости, веса, прочности и других критериев.
Проектирование лекарств, анализ геномных данных, планирование лечения с учетом эффективности и побочных эффектов.
Портфельная оптимизация, управление рисками, планирование инвестиций с учетом доходности и риска.
Оптимизация энергосистем, планирование возобновляемых источников, управление окружающей средой.
Маршрутизация, планирование расписаний, оптимизация цепочек поставок.
Оптимизация баз данных, проектирование сетей, планирование ресурсов в облачных вычислениях.
Пример: проектирование антенны
В задаче проектирования антенны часто требуется одновременно оптимизировать несколько характеристик:
Критерии для минимизации:
1. КСВ (коэффициент стоячей волны) в рабочей полосе частот
2. Уровень боковых лепестков диаграммы направленности
3. Размеры антенны
4. Стоимость производства
Ограничения:
1. Диапазон рабочих частот
2. Минимальный коэффициент усиления
3. Максимально допустимые размеры
МОЭА позволяют инженерам получить набор проектных решений, представляющих различные компромиссы между этими критериями, и выбрать наиболее подходящее решение в зависимости от конкретных требований проекта.
Вызовы и направления будущих исследований
С увеличением количества критериев (более 3) резко возрастает сложность визуализации, сравнения и выбора решений, а также увеличиваются требования к размеру популяции для адекватного покрытия фронта Парето.
Разработка эффективных алгоритмов для задач с 4 и более критериями. Традиционные МОЭА, основанные на доминировании Парето, теряют эффективность при большом количестве критериев.
Решение задач, в которых целевые функции или ограничения изменяются со временем. Требуются алгоритмы, способные адаптироваться к изменениям и отслеживать движущийся фронт Парето.
Снижение вычислительной сложности алгоритмов, особенно для задач с дорогостоящими вычислениями целевых функций (например, CFD-моделирование).
Разработка методов, позволяющих эксперту взаимодействовать с алгоритмом в процессе оптимизации, уточняя предпочтения и направляя поиск.
Интеграция МОЭА с методами локального поиска, машинного обучения и другими техниками для повышения эффективности.
Перспективные направления исследований
- Мета-МОЭА: алгоритмы, автоматически адаптирующие свои параметры и стратегии в процессе работы
- Параллельные и распределенные МОЭА: использование многопроцессорных систем и облачных вычислений
- МОЭА для больших данных: алгоритмы, способные работать с огромными объемами данных и высокими размерностями
- Теоретический анализ: разработка математических основ для анализа сходимости и сложности МОЭА
- Прикладные исследования: адаптация МОЭА для конкретных областей применения с учетом их специфики
Выводы
Многокритериальные эволюционные алгоритмы прошли значительный путь развития за последние два десятилетия, превратившись из исследовательских прототипов в мощные инструменты для решения сложных практических задач. Наиболее значительные достижения были сделаны в следующих областях:
- Разработка эффективных алгоритмов: От VEGA и MOGA к NSGA-II, SPEA2 и MOEA/D, современные МОЭА демонстрируют значительно улучшенную производительность
- Создание комплексных тестовых наборов: ZDT, DTLZ и WFG задачи обеспечивают стандартизированную основу для сравнения алгоритмов
- Разработка теоретически обоснованных показателей: Метрики вроде гиперобъема и ε-индикатора позволяют объективно оценивать качество решений
- Расширение областей применения: От теоретических исследований к решению реальных инженерных, экономических и научных задач
Несмотря на значительный прогресс, перед исследователями стоят серьезные вызовы, связанные с проклятием многомерности, динамическими задачами, вычислительной эффективностью и интерактивностью. Будущие исследования, вероятно, будут сосредоточены на разработке алгоритмов для задач со многими целями, создании адаптивных и гибридных подходов, а также на углублении теоретического понимания свойств МОЭА.
МОЭА продолжают оставаться активной и динамично развивающейся областью исследований, обещающей дальнейшие прорывы как в теории, так и в практике многокритериальной оптимизации.
Литература
- Zhou A., Qu B.Y., Li H., Zhao S.Z., Suganthan P.N., Zhang Q. Multiobjective evolutionary algorithms: A survey of the state of the art // Swarm and Evolutionary Computation. — 2011. — Vol. 1, No. 1. — P. 32-49.
- Deb K. Multi-objective optimization using evolutionary algorithms. — Chichester: John Wiley & Sons, 2001. — 518 p.
- Coello Coello C.A., Lamont G.B., Van Veldhuizen D.A. Evolutionary algorithms for solving multi-objective problems. — 2nd ed. — New York: Springer, 2007. — 800 p.
- Deb K., Pratap A., Agarwal S., Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation. — 2002. — Vol. 6, No. 2. — P. 182-197.
- Zitzler E., Laumanns M., Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm // Technical Report 103, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, 2001.
- Zhang Q., Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition // IEEE Transactions on Evolutionary Computation. — 2007. — Vol. 11, No. 6. — P. 712-731.
- Zitzler E., Thiele L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach // IEEE Transactions on Evolutionary Computation. — 1999. — Vol. 3, No. 4. — P. 257-271.
- Knowles J., Corne D. The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisation // Proceedings of the 1999 Congress on Evolutionary Computation. — 1999. — Vol. 1. — P. 98-105.
- Ishibuchi H., Tsukamoto N., Nojima Y. Evolutionary many-objective optimization: A short review // 2008 IEEE Congress on Evolutionary Computation. — 2008. — P. 2419-2426.
- Fleming P.J., Purshouse R.C., Lygoe R.J. Many-objective optimization: An engineering design perspective // Evolutionary Multi-Criterion Optimization. — 2005. — P. 14-32.