Дифференциальная эволюция (DE), один из ключевых алгоритмов эволюционных вычислений, широко применяется в задачах оптимизации «чёрного ящика» благодаря своей простоте и высокой эффективности. Тем не менее её производительность сильно зависит от выбора гиперпараметров и стратегий — это давняя проблема для исследователей. Для решения этой задачи команда EvoX недавно опубликовала исследование в IEEE Transactions on Evolutionary Computation (IEEE TEVC) под названием «MetaDE: Evolving Differential Evolution by Differential Evolution». Как мета-эволюционный метод, использующий DE для эволюции собственных гиперпараметров и стратегий, MetaDE обеспечивает динамическую настройку параметров и стратегий, а также включает GPU-ускоренные параллельные вычисления. Такой подход существенно повышает как вычислительную эффективность, так и качество оптимизации. Экспериментальные результаты показывают, что MetaDE демонстрирует выдающуюся производительность как на бенчмарке CEC2022, так и в задачах управления роботами. Исходный код MetaDE доступен на GitHub: https://github.com/EMI-Group/metade.
Предпосылки
В области эволюционных вычислений производительность алгоритмов часто существенно зависит от выбора гиперпараметров. Определение наиболее подходящих настроек параметров для конкретной задачи является давней исследовательской проблемой. Дифференциальная эволюция (DE), как классический эволюционный алгоритм, широко ценится за свою простоту и надёжную способность к глобальному поиску; тем не менее её производительность крайне чувствительна к выбору гиперпараметров. Традиционные методы обычно опираются либо на настройку на основе опыта, либо на адаптивные механизмы для улучшения производительности. Однако при столкновении с разнообразными сценариями задач эти подходы часто не могут обеспечить баланс между эффективностью и широкой применимостью.
Концепция «мета-эволюции» была предложена ещё в прошлом веке с целью использования самих эволюционных алгоритмов для оптимизации конфигураций гиперпараметров этих алгоритмов. Хотя мета-эволюция существует уже много лет, её практическое применение было ограничено высокими вычислительными требованиями. Недавние достижения в области GPU-вычислений ослабили эти ограничения, обеспечив мощную аппаратную поддержку для эволюционных алгоритмов. В частности, появление распределённого GPU-ускоренного фреймворка EvoX значительно облегчило разработку эволюционных алгоритмов на GPU. На этом фоне наша исследовательская группа предложила новый мета-эволюционный подход, использующий DE для эволюции собственных гиперпараметров и стратегий, тем самым открывая новый путь решения давней проблемы настройки параметров в эволюционных алгоритмах.
Что такое мета-эволюция?
Основную идею мета-эволюции можно сформулировать как «использование эволюционного алгоритма для эволюции самого себя» (Evolving an Evolutionary Algorithm by an Evolutionary Algorithm). Эта концепция выходит за рамки традиционных методов эволюционных вычислений: она не только применяет эволюционные алгоритмы для поиска оптимальных решений задачи, но и адаптирует гиперпараметры и стратегии алгоритмов через их собственные эволюционные процессы.
Иными словами, мета-эволюция вводит парадигму «самоэволюции», позволяя алгоритмам оптимизировать самих себя в процессе исследования пространства поиска решений задачи. Непрерывно совершенствуясь в ходе эволюционного процесса, алгоритмы становятся более адаптивными и способны поддерживать высокую эффективность в различных сценариях задач.
На примере MetaDE: его архитектура основана на этой философии. В двухуровневой структуре нижний уровень («исполнитель») решает заданную задачу оптимизации с помощью параметризованного DE. Верхний уровень («эволюционер») одновременно использует DE для оптимизации конфигураций гиперпараметров исполнителя. Такая структура позволяет DE не только выступать в роли решателя, но и «исследовать», как лучше настроить собственные параметры и стратегии для более эффективного решения различных задач. Этот процесс подобен системе, которая постепенно понимает и совершенствует себя — переход от «пассивного решения задачи» к «активной самоэволюции». Благодаря этому она лучше адаптируется к разнообразным задачам. Если рассматривать DE как сложную систему, MetaDE фактически реализует «рекурсивный» способ самопознания и самосовершенствования внутри этой системы.
Термин «рекурсия» в информатике обычно описывает функцию или процедуру, вызывающую саму себя. В MetaDE эта концепция приобретает новый смысл: это внутренне рекурсивный механизм оптимизации, использующий DE для эволюции гиперпараметров DE. Эта самореферентная схема не только воплощает мощную адаптивность, но и предлагает новый взгляд на теорему «бесплатных обедов не бывает». Поскольку не существует единого универсально оптимального набора параметров для всех задач, предоставление алгоритму возможности автономно эволюционировать является ключом к нахождению лучших конфигураций параметров для конкретной задачи.
Благодаря этому рекурсивному мета-эволюционному подходу MetaDE достигает нескольких преимуществ:
1. Автоматическая настройка параметров
Трудоёмкий процесс ручной настройки устраняется. Алгоритм сам учится настраивать свои гиперпараметры, снижая необходимость вмешательства человека и повышая эффективность.2. Повышенная адаптивность
MetaDE динамически реагирует на изменяющиеся характеристики и условия задачи, модифицируя стратегии в реальном времени для улучшения производительности. Это значительно повышает гибкость алгоритма.3. Эффективный поиск Используя присущий параллелизм, MetaDE значительно ускоряет поиск в крупномасштабных задачах оптимизации. Он находит допустимые решения для многомерных сложных задач в разумные сроки. Алгоритмическая реализация
MetaDE использует тензорные методы и GPU-ускорение для обеспечения эффективных параллельных вычислений. Одновременная обработка множества особей популяции заметно повышает общую вычислительную эффективность, что особенно выгодно в задачах однокритериальной оптимизации «чёрного ящика» и крупномасштабной оптимизации. Благодаря тензоризации ключевых параметров и структур данных (например, популяции, приспособленности, параметров стратегий) MetaDE не только достигает более высокой вычислительной эффективности, но и расширяет свои возможности для решения сложных задач оптимизации. По сравнению с классическим DE и другими эволюционными алгоритмами (EA) MetaDE демонстрирует превосходную производительность при решении крупномасштабных задач. Благодаря тензорному подходу MetaDE более эффективно использует вычислительные ресурсы, обеспечивая более быстрые решения и более точные результаты оптимизации по сравнению с традиционными методами.
Архитектура PDE
Исследовательская группа сначала предложила параметризованную алгоритмическую структуру DE (PDE), полностью поддерживающую модификацию параметров и стратегий. В этой структуре F и CR являются непрерывными параметрами, тогда как остальные параметры — дискретными. Пунктирные рамки обозначают диапазон допустимых значений параметров. Функция мутации определяется левым и правым базовыми векторами, а также параметром, контролирующим количество разностных векторов.
Архитектура MetaDE
MetaDE использует двухуровневую структуру, состоящую из эволюционера (верхний уровень) и нескольких исполнителей (нижний уровень). Эволюционер — это DE (или потенциально другой эволюционный алгоритм), отвечающий за оптимизацию параметров PDE. Каждая особь
x_i в популяции эволюционера соответствует уникальной конфигурации параметров θ_i. Эти конфигурации передаются в PDE для создания различных вариантов DE, каждый из которых управляется исполнителем, работающим независимо над заданной задачей оптимизации. Каждый исполнитель возвращает своё лучшее значение приспособленности y^* эволюционеру, который присваивает это значение приспособленности y_i соответствующей особи x_i.
Экспериментальная производительность
Для всесторонней оценки эффективности MetaDE исследовательская группа провела систематические эксперименты, охватывающие множество бенчмарков и реальных сценариев. В каждом эксперименте использовался эволюционер (DE со стратегией rand/1/bin) и исполнители (PDE с размером популяции 100). Основные компоненты экспериментов включают:
Бенчмарк CEC2022 Сравнение MetaDE с различными вариантами DE в задачах однокритериальной оптимизации.
Сравнение с четырьмя лучшими алгоритмами CEC2022 Оценка MetaDE в сравнении с четырьмя лучшими алгоритмами соревнования CEC2022 при одинаковом бюджете вычислений целевой функции (FE).
Вычисления целевой функции (FE) при фиксированном времени Анализ вычислительной эффективности MetaDE при GPU-ускорении.
Задачи управления роботами Применение MetaDE к задачам управления роботами в среде платформы Brax для подтверждения практической применимости.
Бенчмарк CEC2022: сравнение с основными вариантами DE
Команда сравнила MetaDE с несколькими представительными вариантами DE на наборе бенчмарков CEC2022, включая:
- Standard DE (rand/1/bin)
- SaDE и JaDE (адаптивные алгоритмы DE)
- CoDE (DE с интеграцией стратегий)
- SHADE и LSHADE-RSP (адаптивный DE на основе истории успехов)
- EDEV (интегрированные варианты DE)
Все алгоритмы были реализованы на платформе EvoX с использованием GPU-ускорения и размером популяции 100 для обеспечения справедливости. Эксперименты проводились при различных размерностях (10D и 20D) при одинаковом ограничении по времени вычислений (60 секунд).
Результаты оптимизации CEC2022 при 10D
Результаты оптимизации CEC2022 при 20D
MetaDE в целом достигает более быстрой и стабильной сходимости на большинстве тестовых функций. Его параметризованный DE (PDE) в сочетании с оптимизацией верхнего уровня обеспечивает динамическую адаптацию к различным пространствам задач, повышая общую устойчивость и качество поиска.
Сравнение с четырьмя лучшими алгоритмами CEC2022 (при одинаковом количестве FE)
Для дальнейшей оценки оптимизационных возможностей MetaDE мы сравнили его с четырьмя лучшими алгоритмами соревнования CEC2022 при одинаковом бюджете вычислений целевой функции:
- EA4eig: гибридный метод, объединяющий несколько EA
- NL-SHADE-LBC: улучшенный адаптивный DE
- NL-SHADE-RSP-MID: улучшенный SHADE с оценкой средней точки
- S-LSHADE-DP: вариант DE, поддерживающий разнообразие популяции через динамическое возмущение
Каждый из этих алгоритмов был запущен с официальными настройками параметров и исходным кодом при одинаковых ограничениях FE. Статистические сравнения (критерий суммы рангов Уилкоксона, уровень значимости 0,05)
были проведены между MetaDE и каждым базовым алгоритмом на наборе тестов CEC2022. Последняя строка таблицы показывает производительность каждого алгоритма по сравнению с MetaDE на различных тестовых функциях: + (значимо лучше), ≈ (нет значимой разницы) и − (значимо хуже).
Сравнение алгоритмов соревнования CEC2022 при 10D (одинаковое количество FE)
Сравнение алгоритмов соревнования CEC2022 при 20D (одинаковое количество FE)
MetaDE стабильно демонстрирует высокую производительность, особенно на сложных задачах, требующих устойчивой сходимости. Благодаря своему самоадаптивному механизму MetaDE эффективно корректирует стратегию для различных ландшафтов поиска, тем самым повышая эффективность поиска и способность к глобальной оптимизации. Эти результаты показывают, что MetaDE не только превосходит основные варианты DE, но и демонстрирует высокую конкурентоспособность по сравнению с лучшими алгоритмами соревнований.
Вычислительная эффективность: FE за фиксированное время (60 секунд)
Исследовательская группа дополнительно зафиксировала количество вычислений целевой функции (FE), выполненных различными алгоритмами за одинаковое фиксированное время работы (60 секунд).
Количество FE, достигнутое каждым алгоритмом за 60 секундПри использовании одного и того же фреймворка EvoX с GPU-ускоренными параллельными вычислениями MetaDE в среднем достигал уровня 10⁹ FE, тогда как традиционные варианты DE достигали лишь около 10^6 FE. Это преимущество обусловлено параметризованным подходом MetaDE, который проводит крупномасштабные параллельные оценки особей, обеспечивая более эффективное использование аппаратных ресурсов. В результате алгоритм исследует больше решений за одно и то же временное окно, повышая как качество решений, так и стабильность.
Эволюционное обучение с подкреплением: задачи управления роботами
В обучении с подкреплением (RL) эффективность и стабильность оптимизации стратегий имеют решающее значение. Градиентные методы, такие как PPO и SAC, могут страдать от затухания или взрыва градиентов в многомерных средах. Напротив, эволюционное обучение с подкреплением (EvoRL) обходит эти проблемы, используя безградиентный поиск для прямой оптимизации параметров стратегий.
Процесс эволюционного обучения с подкреплением
В рамках фреймворка EvoRL MetaDE:
- Автоматически оптимизирует параметры нейронных сетей, повышая адаптивность моделей стратегий.
- Динамически настраивает гиперпараметры, улучшая стабильность обучения.
- Использует GPU-ускорение для ускорения оптимизации стратегий.
Для оценки производительности MetaDE на сложных задачах оптимизации мы применили его к задачам управления роботами с использованием GPU-ускоренной оптимизации на платформе моделирования Brax. Исследование включало три задачи — Swimmer, Hopper и Reacher — каждая из которых моделировалась трёхслойной полносвязной нейронной сетью (MLP) с целью максимизации награды. Примечательно, что каждый MLP содержит около 1500 параметров, создавая 1500-мерную задачу оптимизации для эволюционных алгоритмов (EA). Это предъявляет строгие требования как к поисковым возможностям, так и к вычислительной эффективности.
Кривые сходимости для трёх сред Brax
Как показано на рисунке, MetaDE демонстрирует высокую производительность в задачах управления роботами на базе Brax, достигая лучших результатов в задаче Swimmer и близких к оптимальным результатов в задачах Hopper и Reacher. Его основное преимущество заключается в высоком качестве начальной популяции, обеспечивающем быструю сходимость на ранних этапах и получение высококачественных решений. Эти результаты свидетельствуют о том, что MetaDE способен эффективно оптимизировать стратегии нейронных сетей, что делает его хорошо подходящим для задач управления роботами со сложным физическим моделированием и открывающим широкие перспективы для практического применения.
Заключение и перспективы
MetaDE — это инновационный мета-эволюционный подход, который не только превосходно справляется с решением задач оптимизации, но и автономно настраивает и совершенствует собственные стратегии. Используя преимущества дифференциальной эволюции, MetaDE демонстрирует значительный потенциал в адаптивной настройке параметров и эволюции стратегий. Экспериментальные результаты показывают превосходную устойчивость в ряде бенчмарков, а его практическая применимость подтверждается успехом в задачах управления роботами через эволюционное обучение с подкреплением. Ключевая задача заключается в поддержании оптимального баланса между обобщением и специализацией — обеспечении того, чтобы алгоритм мог адаптироваться к разнообразным задачам, одновременно эффективно оптимизируя конкретные проблемы. Это исследование открывает новые перспективы для самоадаптивных эволюционных алгоритмов и может стимулировать дальнейшие достижения в области мета-эволюции для сложных систем.
Открытый исходный код и сообщество
Статья: https://arxiv.org/abs/2502.10470
GitHub: https://github.com/EMI-Group/metade
Вышестоящий проект (EvoX): https://github.com/EMI-Group/evox
QQ-группа: 297969717
QQ-группа | Evolving Machine Intelligence
MetaDE построен на основе фреймворка EvoX. Если вас интересует EvoX, ознакомьтесь со статьёй о EvoX 1.0 для получения подробной информации.
(https://mp.weixin.qq.com/s/uT6qSqiWiqevPRRTAVIusQ)
