Адаптация может менять способ поиска, а не только найденные решения. MetaDE воплощает это в EvoX двумя связанными эволюционными уровнями: внутренний решает целевую задачу, внешний оценивает, какие конфигурации DE делают поиск эффективным. MetaDE
Контекст
В области эволюционных вычислений на производительность алгоритмов часто существенно влияет выбор гиперпараметров. Определение наиболее подходящих настроек параметров для конкретной задачи долгое время было сложной исследовательской проблемой. Differential Evolution (DE), как классический эволюционный алгоритм, пользуется популярностью благодаря своей простоте и надежной способности к глобальному поиску; тем не менее, его эффективность крайне чувствительна к выбору гиперпараметров. Традиционные методы обычно полагаются либо на настройку на основе опыта, либо на адаптивные механизмы для улучшения производительности. Однако перед лицом разнообразных сценариев задач этим подходам часто трудно сбалансировать эффективность и широкую применимость.
Концепция «мета-эволюции» была представлена еще в прошлом веке с целью использования самих эволюционных алгоритмов для оптимизации конфигураций гиперпараметров этих же алгоритмов. Хотя мета-эволюция существует уже много лет, ее практическое применение было ограничено высокими требованиями к вычислительным ресурсам. Недавние достижения в области вычислений на GPU ослабили эти ограничения, обеспечив мощную аппаратную поддержку для эволюционных алгоритмов. В частности, появление распределенного фреймворка EvoX с GPU-ускорением значительно облегчило разработку эволюционных алгоритмов на базе GPU. На этом фоне наша исследовательская группа предложила новый подход к мета-эволюции, который использует DE для эволюции собственных гиперпараметров и стратегий, предлагая тем самым новый путь решения давней проблемы настройки параметров в эволюционных алгоритмах.
Что такое мета-эволюция?
Основную идею мета-эволюции можно резюмировать как «использование эволюционного алгоритма для эволюции самого себя» (Evolving an Evolutionary Algorithm by an Evolutionary Algorithm). Эта концепция выходит за рамки традиционных методов эволюционных вычислений, не только применяя эволюционные алгоритмы для поиска оптимальных решений задачи, но и адаптируя гиперпараметры и стратегии самих алгоритмов через их собственные эволюционные процессы.
Другими словами, мета-эволюция вводит парадигму «самоэволюции», позволяя алгоритмам оптимизировать себя по мере исследования пространства поиска решений задачи. Непрерывно совершенствуясь в процессе эволюции, алгоритмы становятся более адаптивными и могут сохранять высокую эффективность в различных сценариях задач.
В качестве примера рассмотрим MetaDE, дизайн которого укоренен в этой философии. В двухслойной структуре нижний слой («исполнитель», executor) решает заданную задачу оптимизации, используя параметризованный DE. Верхний слой («эволютор», evolver) одновременно использует DE для оптимизации конфигураций гиперпараметров исполнителя. Эта структура позволяет DE не только служить решателем, но и «исследовать», как лучше всего настроить собственные параметры и стратегии для более эффективного решения различных задач. Такой процесс сродни системе, которая постепенно понимает и совершенствует саму себя — трансформация от «пассивного решения задачи» к «активной самоэволюции». Следовательно, она может лучше адаптироваться к разнообразным задачам. Если рассматривать DE как сложную систему, MetaDE фактически обеспечивает «рекурсивный» способ самопонимания и самосовершенствования внутри этой системы.
Термин «рекурсия» в информатике обычно описывает функцию или процедуру, которая вызывает саму себя. В MetaDE эта концепция обретает новый смысл: это внутренне рекурсивный механизм оптимизации, который использует DE для эволюции гиперпараметров DE. Эта самореферентная схема не только воплощает мощную адаптивность, но и дает новый взгляд на теорему «о бесплатном обеде» (no free lunch theorem). Поскольку не существует единого, универсально оптимального набора параметров для всех задач, предоставление алгоритму возможности автономно эволюционировать является ключом к поиску лучших конфигураций параметров для конкретной задачи.
Благодаря этому рекурсивному мета-эволюционному подходу MetaDE достигает нескольких преимуществ:
1. Автоматизированная настройка параметров Исключается трудоемкий процесс ручной настройки. Алгоритм сам учится корректировать свои гиперпараметры, сокращая вмешательство человека и повышая эффективность.
2. Повышенная адаптивность MetaDE динамически реагирует на изменяющиеся характеристики и условия задачи, модифицируя стратегии в реальном времени для улучшения производительности. Это значительно повышает гибкость алгоритма.
3. Эффективный поиск Используя присущий параллелизм, MetaDE значительно ускоряет поиск в крупномасштабных задачах оптимизации. Он выдает выполнимые решения для высокоразмерных сложных задач в разумные сроки.
Алгоритмическая реализация
MetaDE использует тензорные методы и GPU-ускорение для обеспечения эффективных параллельных вычислений. Благодаря одновременной обработке множества особей популяции общая вычислительная эффективность заметно повышается, что делает его особенно выгодным в одноцелевой оптимизации «черного ящика» и крупномасштабных задачах оптимизации. Путем тензоризации ключевых параметров и структур данных (например, популяции, приспособленности, параметров стратегии) MetaDE не только достигает более высокой вычислительной эффективности, но и расширяет свои возможности по решению сложных задач оптимизации. По сравнению с классическим DE и другими эволюционными алгоритмами (EAs), 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 при одинаковом бюджете вычислений целевой функции (FEs).
Вычисления целевой функции (FEs) за фиксированное астрономическое время
Анализ вычислительной эффективности MetaDE при GPU-ускорении.
Задачи управления роботами
Применение MetaDE в задачах управления роботами в среде платформы Brax для подтверждения его практической полезности.
Бенчмарк CEC2022: Сравнение с основными вариантами DE
Команда сравнила MetaDE с несколькими репрезентативными вариантами DE на наборе бенчмарков CEC2022, включая:
- Стандартный DE (rand/1/bin)
- SaDE и JaDE (адаптивные алгоритмы DE)
- CoDE (DE с интеграцией стратегий)
- SHADE и LSHADE-RSP (адаптивный DE на основе истории успеха)
- EDEV (интегрированные варианты DE)
Все алгоритмы были реализованы на платформе EvoX с использованием GPU-ускорения и размера популяции 100 для обеспечения объективности. Эксперименты проводились на различных размерностях (10D и 20D) при одинаковом ограничении по времени вычислений (60 секунд).
Результаты оптимизации 10D CEC2022
Результаты оптимизации 20D CEC2022
MetaDE обычно достигает более быстрой и стабильной сходимости в большинстве тестовых функций. Его параметризованный DE (PDE) в сочетании с оптимизацией верхнего уровня обеспечивает динамическую адаптацию к различным пространствам задач, улучшая общую надежность и производительность поиска.
Сравнение с четырьмя лучшими алгоритмами CEC2022 (при одинаковом количестве FEs)
Для дальнейшей оценки оптимизационных способностей MetaDE мы сравнили его с четырьмя лучшими алгоритмами соревнований CEC2022 в рамках одинакового бюджета вычислений целевой функции:
- EA4eig: Гибридный метод, интегрирующий несколько EAs.
- NL-SHADE-LBC: Улучшенный адаптивный DE.
- NL-SHADE-RSP-MID: Расширенный SHADE с оценкой средней точки.
- S-LSHADE-DP: Вариант DE, поддерживающий разнообразие популяции через динамическое возмущение.
Каждый из этих алгоритмов запускался с официальными настройками параметров и исходным кодом при одинаковых ограничениях FEs. Статистические сравнения (критерий Уилкоксона, уровень значимости 0,05) проводились между MetaDE и каждым базовым алгоритмом на наборе тестов CEC2022. Последняя строка таблицы показывает производительность каждого алгоритма по сравнению с MetaDE на различных тестовых функциях: + (значительно лучше), ≈ (нет значимой разницы) и − (значительно хуже).
Сравнение алгоритмов соревнований 10D CEC2022 (одинаковое количество FEs)
Сравнение алгоритмов соревнований 20D CEC2022 (одинаковое количество FEs)
MetaDE последовательно демонстрирует высокие результаты, особенно в сложных задачах, требующих надежной сходимости. Благодаря своему механизму самоадаптации MetaDE эффективно корректирует свою стратегию для различных ландшафтов поиска, тем самым повышая эффективность поиска и возможности глобальной оптимизации. Эти результаты указывают на то, что MetaDE не только превосходит основные варианты DE, но и проявляет сильную конкурентоспособность по сравнению с алгоритмами топового уровня.
Вычислительная эффективность: FEs за фиксированное время (60 секунд)
Исследовательская группа дополнительно зафиксировала количество вычислений целевой функции (FEs), выполненных различными алгоритмами за одно и то же фиксированное время работы (60 секунд).
FEs, достигнутые каждым алгоритмом за 60 секунд
В рамках одного и того же фреймворка EvoX с параллельными вычислениями на GPU, MetaDE в среднем достигал уровня 10⁹ FEs, в то время как традиционные варианты DE достигали лишь около 10⁶ FEs. Это преимущество проистекает из параметризованного подхода MetaDE, который проводит крупномасштабные параллельные оценки особей, обеспечивая более эффективное использование аппаратных ресурсов. Следовательно, алгоритм исследует больше решений за тот же промежуток времени, улучшая как качество решения, так и стабильность.
Эволюционное обучение с подкреплением: задачи управления роботами
В эксперименте MetaDE по управлению роботами параметры нейросетевой политики ищутся без градиентов и обратного распространения её целевой функции. Эволюционное обучение с подкреплением также включает градиентные и гибридные методы; оно не устраняет все трудности PPO или SAC.
В экспериментах используются Swimmer, Hopper и Reacher из Brax с трёхслойными MLP-политиками примерно на 1 500 параметров. Внутренний поиск оптимизирует веса, внешний — параметры и стратегии исполнителя DE. Эти симуляции не доказывают применимость на реальных роботах или общее повышение стабильности обучения.
Кривые сходимости для трех сред Brax
Как показано на рисунке, MetaDE демонстрирует отличные результаты в задачах управления роботами на базе Brax, достигая лучших результатов в задаче Swimmer и близких к оптимальным в Hopper и Reacher. Его главное преимущество заключается в высоком качестве начальной популяции, что обеспечивает быструю сходимость на ранних этапах и получение высококачественных решений. Эти результаты свидетельствуют о том, что MetaDE может эффективно оптимизировать стратегии нейронных сетей, что делает его хорошо подходящим для задач управления роботами со сложным физическим моделированием и открывает широкие перспективы для практического применения.
Заключение и будущие направления
Учитывайте внешние испытания конфигураций и внутренние оценки целевой функции. Сравнивайте методы по общему бюджету и фактически прошедшему времени. iStratDE: разнообразие популяции как принцип параллельного поиска