iStratDE: GPU-вычисления x Сверхбольшие Популяции Раскрывают Полный Потенциал Дифференциальной Эволюции

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

Чтобы восполнить этот пробел, команда EvoX исследовала, как разнообразие стратегий на уровне индивидов формирует динамику поиска и производительность оптимизации DE, и предложила минималистичный вариант: iStratDE (Individual-Level Strategy Diversity Differential Evolution). Основная идея проста: при инициализации каждому индивиду назначается собственная стратегия мутации и кроссовера, и это назначение остаётся неизменным на протяжении всей эволюции. Вводя разнообразие на уровне индивидов — и отбрасывая сложные петли адаптации и обратной связи — iStratDE создаёт устойчивую поведенческую гетерогенность в популяции.

Это свойство становится особенно мощным в больших популяциях. Поскольку алгоритм не требует коммуникации по замыслу, он естественно поддерживает эффективное параллельное выполнение и плавно масштабируется в среды GPU. Команда также предоставляет анализ сходимости при стандартных предположениях достижимости, устанавливая почти наверняка сходимость лучшего найденного значения фитнеса. Обширные эксперименты на тестовом наборе CEC2022 и задачах управления роботами показывают, что iStratDE может соответствовать или даже превосходить основные адаптивные варианты DE. Исходный код опубликован на GitHub: https://github.com/EMI-Group/istratde

Предыстория: Эволюционные Вычисления в Ловушке Сложности

DE долгое время был одним из наиболее эффективных инструментов для непрерывной оптимизации благодаря своим простым операторам и сильным поисковым возможностям. Однако его производительность сильно зависит от выбора стратегии мутации и параметров управления, таких как F и CR. Согласно теореме No Free Lunch, ни одна конфигурация не может доминировать на всех задачах.

На протяжении последних двух десятилетий основным ответом было делать DE всё более адаптивным. От SaDE до семейства LSHADE алгоритмы становились более «интеллектуальными», поддерживая исторические архивы, оценивая успешность стратегий и настраивая параметры на уровне популяции. Но этот интеллект имеет свою цену. Централизованная логика управления вносит существенные вычислительные накладные расходы и, что более важно, серьёзные барьеры синхронизации. В эпоху параллелизма GPU такая зависимость от глобального обмена информацией часто приводит к плохой утилизации оборудования и не позволяет алгоритмам полностью использовать доступные вычислительные ресурсы.

Прорыв: Минимализм и Структурное Разнообразие

Возможно ли сохранить минималистичную природу DE, достигая при этом робастности — или даже превосходящей производительности — сложных адаптивных вариантов?

Команда EvoX отвечает на этот вопрос контринтуитивным предложением: iStratDE. Вместо того чтобы делать алгоритм «умнее» во время выполнения, iStratDE даёт популяции максимальное разнообразие с самого начала. Опираясь на распределённый GPU-ускоренный фреймворк EvoX, iStratDE демонстрирует, что крупномасштабная параллельная эволюция может быть существенно усилена простым назначением стратегий на уровне индивидов, без введения каких-либо адаптивных механизмов.

Что такое iStratDE?

Философию iStratDE можно резюмировать как «разные индивиды, разные роли».

В обычных вариантах DE стратегии обычно определяются или адаптируются на уровне популяции. В iStratDE разнообразие стратегий вводится на уровне индивида:

Назначено раз и навсегда. При инициализации каждому индивиду случайным образом назначается независимая стратегия мутации-кроссовера и набор параметров управления.
Децентрализованное выполнение. После назначения эти стратегии остаются неизменными в течение всего эволюционного процесса. Каждый индивид ищет по собственному набору правил, не отчитываясь перед центральным контроллером и не ожидая обратной связи от других.
Внутренний параллелизм. Поскольку индивиды не зависят друг от друга через сложную синхронизацию, iStratDE устраняет коммуникационные накладные расходы и естественно отображается на архитектуру SIMT GPU.

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

Почему iStratDE Работает?

Несмотря на свою простоту, iStratDE показывает выдающиеся результаты как на тестовом наборе CEC2022, так и на задачах управления роботами в Brax. Два механизма особенно важны:

Неявный элитизм. Не каждая стратегия подходит для каждой задачи, но в достаточно большой популяции некоторые индивиды случайно получат высокосовместимые конфигурации. Эти «элиты» быстро поднимаются и направляют поиск к высококачественным областям.
Асинхронная сходимость. Разные стратегии сходятся с разной скоростью. Некоторые индивиды делают агрессивные прорывы рано, тогда как другие улучшаются более стабильно позже. Это разнообразие в темпе сходимости помогает предотвратить преждевременный коллапс популяции в локальные оптимумы.

Ключевые Преимущества iStratDE

Вводя разнообразие стратегий на уровне индивидов, iStratDE предлагает несколько важных преимуществ:

Экстремальная структурная простота. Удаляет исторические архивы, модули обучения параметров и дополнительные гиперпараметры, возвращая DE к чистой и высоко воспроизводимой форме.
Выдающаяся эффективность GPU. Благодаря бескоммуникационному дизайну iStratDE достигает почти линейного ускорения на GPU и может управлять популяциями свыше 100 000 индивидов.
Лучшая производительность с большими популяциями. В отличие от многих традиционных вариантов DE, которые часто страдают от узких мест эффективности при слишком большой популяции, iStratDE напрямую выигрывает от масштаба: больше индивидов означает более богатое разнообразие, более широкий охват стратегий и более сильную поисковую производительность.
Теоретическая поддержка. Результат о почти наверняка сходимости обеспечивает прочный математический фундамент для этого минималистичного дизайна.

Детали Реализации

iStratDE тесно интегрирует тензоризацию с GPU-ускорением. Его эффективность обусловлена отличительным дизайном блокировки коммуникации: в отличие от адаптивных алгоритмов, зависящих от централизованной статистики, стратегии индивидов iStratDE полностью независимы, устраняя требования к синхронизации и идеально согласуясь с моделью SIMT GPU.

При поддержке фреймворка EvoX iStratDE может эффективно эволюционировать популяции из 100 000+ индивидов параллельно. Эта тензоризованная независимость не только повышает пропускную способность для крупномасштабной оптимизации, но и обеспечивает широкий охват пространства поиска через массовое параллельное исследование.

Построение Пула Стратегий

Для создания разнообразия в популяции команда строит пул стратегий из 192 конфигураций. Каждая стратегия следует форме DE/bl-to-br/dn/cs и состоит из модульных элементов:

Левый базовый вектор, выбранный из rand, best, pbest или current
Правый базовый вектор, также выбранный из rand, best, pbest или current
Количество дифференциальных векторов, выбранное из {1, 2, 3, 4}
Схема кроссовера, включающая биномиальный, экспоненциальный и арифметический кроссовер

Кроме того, масштабирующий фактор F и скорость кроссовера CR каждого индивида независимо выбираются из U(0, 1). Через различные комбинации этих компонентов iStratDE генерирует широкий спектр поисковых поведений — от высокоисследовательских до сильно эксплуатационных.

Обзор Архитектуры

iStratDE следует чрезвычайно простому децентрализованному рабочему процессу:

Начальное назначение. Система инициализирует позиции популяции и случайным образом назначает каждому индивиду выделенную стратегию и набор параметров.
Постоянная эволюция. Во время цикла оптимизации каждый индивид всегда выполняет мутацию и кроссовер в соответствии со своей назначенной конфигурацией. Решения эволюционируют, но стратегии — нет.
Неявная интеграция. Поскольку популяция велика и гетерогенна, iStratDE не требует явной адаптивной координации. Возникает естественное разделение труда: индивиды, ориентированные на исследование, открывают новые области, тогда как индивиды, ориентированные на эксплуатацию, уточняют перспективные решения.

Рис. 1. Фреймворк iStratDE: инициализация, децентрализованное назначение стратегий и постоянная эволюция.

Экспериментальные Результаты

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

Эксперименты включают:

Стресс-тесты со сверхбольшими популяциями, масштабируемыми до 100 000 индивидов
Бенчмарки CEC2022, сравнивающие iStratDE с основными адаптивными вариантами DE и лучшими методами соревнований за 60 секунд
Анализ масштабируемости популяции, показывающий, что iStratDE продолжает улучшаться с ростом популяции, тогда как традиционные методы достигают предела масштабируемости
Задачи управления роботами, использующие большие популяции для оптимизации многомерных нейронных контроллеров в Brax

1. Бенчмарки CEC2022 при Фиксированном Временном Бюджете

При одинаковом 60-секундном бюджете традиционные адаптивные алгоритмы остаются ограничены классическим размером популяции около 100 из-за их последовательной логики и накладных расходов синхронизации. Напротив, iStratDE спроектирован специально для выполнения на GPU SIMT и может эффективно управлять популяциями из 100 000 индивидов.

В результате iStratDE выполняет до 10^9 оценок функции в том же временном окне, достигая примерно 100-кратной вычислительной пропускной способности по сравнению с традиционными методами. На большинстве тестовых функций эта комбинация минималистичной структуры и массивного параллелизма приводит к более высокой скорости сходимости и конечной точности.

Рис. 2. Сравнение пропускной способности оценок функции при фиксированном временном бюджете.

Рис. 3. Сравнение производительности оптимизации на 10-мерном тестовом наборе CEC2022.

2. Робастность в Многомерных Ландшафтах

Команда дополнительно оценивает iStratDE на сложных 200-мерных повёрнутых и смещённых версиях функций Швефеля, Растригина и Экли. Традиционные адаптивные методы DE, такие как JADE и SHADE, а также CMA-ES, сильно страдают от проклятия размерности и часто застревают на ранних стадиях.

Напротив, iStratDE поддерживает сильный поисковый импульс благодаря комбинации крупномасштабного параллелизма и разнообразия стратегий. Он не только превосходит специализированные базовые методы, такие как CSO, но и демонстрирует конкурентную робастность по сравнению с MetaDE, недавним GPU-оптимизатором на основе обучения. На сложных функциях, таких как Экли, iStratDE успешно находит глобальный оптимум.

Рис. 4. Сравнение производительности на 200-мерных смещённых и повёрнутых тестовых задачах.

3. Масштабируемость Популяции

Одно из самых поразительных открытий состоит в том, что iStratDE опровергает классическое предположение о том, что простое увеличение популяции не продолжает улучшать DE. Когда размер популяции растёт с 10^2 до 4 x 10^5, iStratDE продолжает стабильно улучшаться без явных признаков насыщения.

Напротив, традиционные адаптивные алгоритмы DE обычно перестают извлекать пользу при превышении умеренного порога популяции и могут даже деградировать из-за накладных расходов синхронизации. Этот результат предполагает, что iStratDE может конвертировать дополнительные вычислительные ресурсы непосредственно в лучшую производительность оптимизации.

Рис. 5. Анализ масштабируемости популяции iStratDE при увеличении размеров популяции.

4. Сравнение с Лучшими Методами Соревнования CEC2022

Для проверки верхней границы производительности команда сравнивает iStratDE с лучшими методами соревнования CEC2022, включая EA4eig, NL-SHADE-LBC и NL-SHADE-RSP. При идентичных бюджетах оценок функции iStratDE остаётся высококонкурентным, несмотря на значительно более простую структуру. На нескольких сложных функциях 10D и 20D он достигает результатов, сопоставимых — или лучших — по сравнению с этими изощрёнными базовыми методами.

Рис. 6. Сравнение iStratDE с лучшими методами соревнования CEC2022.

5. Практическое Применение: Управление Роботами в Brax

Наконец, команда применяет iStratDE к задачам управления роботами в Brax, включая Swimmer, Reacher и Hopper, где цель — оптимизация контроллеров нейронных сетей с примерно 1500 параметрами.

Используя популяцию из 10 000, iStratDE сравнивается с CMA-ES, CSO и традиционными вариантами DE. На задачах Swimmer и Hopper iStratDE быстро находит политики с высокой наградой и демонстрирует более сильную сходимость, чем методы CMA-ES и LSHADE. Это показывает, что iStratDE не только теоретически элегантен, но и практически эффективен для многомерной оптимизации чёрного ящика.

Рис. 7. Кривые сходимости iStratDE в трёх средах управления Brax.

Заключение и Перспективы

iStratDE — это возвращение к основам алгоритмов. Вместо наращивания всё более сложной адаптивной логики он строит мощные поисковые возможности на основе разнообразия стратегий на уровне индивидов. Полностью раскрывая параллельный потенциал современных GPU, iStratDE демонстрирует силу структурированного разнообразия в мультимодальной и многомерной оптимизации.

Результаты показывают, что iStratDE может конкурировать — а в некоторых случаях превосходить — ведущие адаптивные варианты DE как на бенчмарках, так и на реальных задачах управления. В более широком смысле эта работа выделяет важный принцип проектирования: сложность — не единственный путь к производительности; гетерогенность популяции сама по себе может быть мощным двигателем эволюции.

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

Открытый Код / Ресурсы Сообщества

Статья: https://arxiv.org/abs/2602.01147

GitHub: https://github.com/EMI-Group/istratde

Основной Проект (EvoX): https://github.com/EMI-Group/evox

Группа QQ: 297969717

QR-код группы сообщества EvoX в QQ.