Развитие оптимизации роем частиц (PSO) по сути было историей непрерывного «ручного проектирования». За последние десятилетия исследователи предложили огромное множество улучшений, касающихся весов инерции, стратегий обучения, топологий роя, структур подгрупп и других компонентов, постепенно сформировав вокруг PSO обширное пространство алгоритмического проектирования. Однако чем больше пространство, тем труднее выбор. Столкнувшись с конкретной задачей оптимизации — какие параметры выбрать, какие механизмы обучения использовать, как организовать рой частиц — эти тесно связанные проектные решения и по сей день в значительной степени зависят от опыта исследователей и метода проб и ошибок. PSO становился всё богаче, но и «выбрать правильно» становилось всё труднее. А что, если сам акт «выбора PSO» тоже поручить алгоритмической эволюции?
Фреймворк AutoPSO, предложенный командой EvoX, единообразно кодирует конфигурацию параметров, механизмы обучения и структуру роя PSO в доступном для поиска эволюционном пространстве и автоматически, посредством метаэволюции, ищет оптимальный вариант PSO, адаптированный к конкретной целевой задаче. Этот фреймворк не только оптимизирует решение задачи, но и на более высоком уровне автоматически оптимизирует «какой PSO использовать для решения».
Масштабный поиск в метаэволюции опирается на массово параллельные вычисления, и тензоризованные вычисления, пакетная обработка и параллелизм GPU в EvoX устраняют именно это узкое место — тысячи вариантов-кандидатов могут эволюционировать одновременно, делая практически осуществимым метауровневый поиск, ранее неосуществимый на CPU.
Вычислительная мощность GPU × метаэволюция выводит PSO от «ручного проектирования» к «автоматической генерации».
PSO не хватает не методов — ей не хватает способности автоматически их комбинировать
За прошедшие десятилетия исследования PSO накопили богатый набор механистических опций: как параметры меняются по итерациям, у каких особей учатся частицы, делится ли рой на подгруппы и какие стратегии обновления используют разные подгруппы.
Проблема не в нехватке механизмов, а в том, что большинство из них существует в виде автономных алгоритмов, ориентированных на конкретные задачи. Столкнувшись с новой задачей, исследователям по-прежнему приходится вручную выбирать, комбинировать и проверять механизмы из большого пула, а затем заново их настраивать.
Философия AutoPSO состоит не в том, чтобы отбросить накопленные знания, а в том, чтобы реорганизовать их в пространство повторно используемых компонентов. Он разбивает ключевые аспекты проектирования PSO на несколько модулей:
-
как эволюционируют параметры;
-
у каких образцов учатся частицы;
-
как рой разбивается на подгруппы;
-
какие стратегии обновления применяют разные подгруппы.
В традиционных подходах эти выборы в основном делает человек; в AutoPSO они становятся объектами поиска для алгоритма. Иными словами, AutoPSO — это не о «ручном переизобретении PSO», а о построении метафреймворка, который ещё до решения текущей задачи способен автоматически сконфигурировать подходящий для неё вариант PSO.
Рисунок 1: AutoPSO организует ключевые элементы проектирования PSO в комбинируемые и доступные для поиска модули.
Передать алгоритму саму оптимизацию внешнего уровня, традиционно выполняемую исследователями
Традиционные исследования оптимизации всегда имели двухуровневую структуру. На внутреннем уровне PSO используется для решения целевой задачи — будь то оптимизация функций, инженерное проектирование или политика управления. На внешнем уровне существует менее явная оптимизация: исследователи оптимизируют сам алгоритм.
Какие правила обновления выбрать, как задать параметры, какие обучающие образцы принять, вводить ли механизмы подгрупп, какие механизмы можно комбинировать и какие комбинации нестабильны — эти решения обычно принимались исследователями на основе опыта, а затем уточнялись методом проб и ошибок.
Ключевой сдвиг, который приносит AutoPSO, — передать алгоритму этот процесс внешнего уровня, ранее выполнявшийся исследователями вручную. Частица внешнего уровня больше не представляет собой кандидатное решение целевой задачи — она представляет кандидатный проект PSO, кодирующий параметры, обучающие образцы, разбиение на подгруппы и стратегии обновления. Внутренний PSO с этими конфигурациями решает целевую задачу и возвращает свою производительность в качестве обратной связи на внешний уровень, который продолжает поиск более удачных конфигураций алгоритма.
AutoPSO оптимизирует не только решение задачи, но и «какой PSO использовать для её решения».
Он превращает процесс проектирования алгоритмов, ранее опиравшийся на опыт исследователей, во внутренний эволюционный процесс внутри системы, который может автоматически искаться, оцениваться и итерироваться.
Рисунок 2: Внешний уровень ищет конфигурации алгоритма, а внутренний уровень использует выбранную конфигурацию для решения целевой задачи.
EvoX и GPU: сделать автоматическое проектирование алгоритмов действительно осуществимым
Предложить фреймворк автоматического поиска алгоритмических структур не так сложно; настоящий вызов — вычислительные затраты. Оценка кандидатного проекта PSO требует его полного прогона по процессу решения целевой задачи. Чем больше кандидатных проектов, тем больше вычислительная нагрузка на внутренний уровень.
В традиционных последовательных средах на CPU такие затраты запретительны. Однако этот тип вычислений по своей природе поддается распараллеливанию: кандидатные алгоритмы можно оценивать одновременно, а внутри каждого кандидатного алгоритма обновления частиц также можно обрабатывать пакетно. AutoPSO использует EvoX, чтобы отобразить популяционную структуру эволюционных вычислений на пакетные возможности GPU, позволяя поиску конфигураций на внешнем уровне и решению задачи на внутреннем уровне идти одновременно.
Здесь ускорение на GPU — это не просто сокращение времени одного прогона; важнее то, что оно существенно увеличивает число кандидатных проектов, которые можно сравнить за заданное время. Метаэволюция — это по сути поиск в пространстве алгоритмов, и его качество напрямую зависит от того, сколько кандидатных проектов PSO было оценено. Чем основательнее оценка, тем выше шанс найти конфигурацию, хорошо подходящую текущей задаче.
Ценность EvoX именно в предоставлении этой способности: он организует обновления частиц и оценки приспособленности внутреннего уровня, а также сравнение кандидатных алгоритмов внешнего уровня, в тензорные операции на GPU, позволяя тысячам кандидатных проектов синхронно продвигаться на каждой итерации. Иными словами, EvoX превращает метаэволюцию из процесса «медленных проб и ошибок» в «масштабный параллельный эксперимент» — и именно на этой вычислительной основе строится AutoPSO.
Не только быстрее, но и искуснее в «использовании поиска»
AutoPSO стремится показать не просто то, что он быстро работает на GPU, а то, что после автоматизации процесса проектирования PSO алгоритм действительно способен обнаружить стратегию поиска, лучше подходящую конкретной задаче.
На численном оптимизационном бенчмарке CEC2022 команда EvoX сравнила AutoPSO с исходным PSO, CSO, CLPSO, FIPS и несколькими вариантами социально обучающегося PSO. При одинаковом бюджете времени выполнения многие варианты PSO с фиксированной структурой демонстрировали быстрое начальное снижение значений целевой функции, но склонны были к преждевременному застою. Напротив, AutoPSO мог непрерывно корректировать конфигурацию внутреннего PSO во время выполнения, сохраняя более стабильную тенденцию улучшения на множестве функций.
Команда также провела сравнения при одинаковом числе вычислений функции, и AutoPSO по-прежнему показал превосходные результаты. Это означает, что его преимущество проистекает из более эффективной организации процесса поиска, а не из простого потребления больших вычислительных ресурсов.
Рисунок 3: Результаты экспериментов на численном оптимизационном бенчмарке CEC2022.
Исследовательская команда дополнительно применила AutoPSO к задачам робототехнического управления на основе нейроэволюции. По сравнению с оптимизацией числовых функций такие задачи гораздо ближе к реальным применениям: они включают высокоразмерные параметры политик, значительный шум обратной связи, нерегулярные целевые ландшафты и не всегда доступную информацию о градиенте.
В нескольких средах робототехнического управления Brax AutoPSO достиг более быстрого роста вознаграждения и лучших итоговых результатов. Это говорит о том, что AutoPSO — не просто набор эвристик, подогнанных под конкретный класс функций, а практичный и переносимый подход к автоматическому построению алгоритмов.
Рисунок 4: Результаты экспериментов на задачах робототехнического управления Brax.
Ценность EvoX наиболее наглядно проявляется в экспериментах по масштабируемости. Двухуровневая структура AutoPSO естественным образом влечет больший размер популяции: на внешнем уровне множество кандидатных алгоритмов, а у каждого кандидатного алгоритма на внутреннем уровне — собственный рой частиц. При традиционном последовательном исполнении необходимое время вычислений быстро стало бы непомерным.
На GPU же при увеличении общего размера популяции в 100 раз время выполнения растет лишь примерно в 3 раза. В тестах с 8192 измерениями AutoPSO сохраняет приемлемые временные накладные расходы и достигает ускорения на порядок величины по сравнению с исполнением на CPU.
Рисунок 5: Влияние масштабирования размера популяции на время выполнения.
AutoPSO не расточает ни вычислительную мощность, ни исторические знания
Вместо того чтобы заменять алгоритмические исследования грубой вычислительной мощностью, AutoPSO превращает долго накапливавшиеся результаты исследований в операционные проектные активы. Эффективные механизмы, ранее рассеянные по разным вариантам PSO, абстрагируются в повторно используемые компоненты, а комбинаторные решения, прежде опиравшиеся на человеческий опыт, передаются метаэволюции для проверки на конкретных задачах.
Три элемента незаменимы: исторические знания дают пространство поиска; автоматическая оптимизация ведёт комбинаторный поиск; EvoX вместе с параллелизмом GPU обеспечивает возможность оценки в масштабе. Без исторических знаний поиску недостает перспективных кандидатов; без автоматической оптимизации знания вряд ли можно реорганизовать под конкретную задачу; без параллельных вычислений масштаб поиска не удержать.
AutoPSO освобождает исследователей от повторяющейся настройки параметров и проб с ошибками, направляя их усилия на более ценную работу: определение компонентов, проектирование пространств поиска и построение более надежных конвейеров оценки.
От изменения алгоритмов к построению систем, порождающих алгоритмы
Значение AutoPSO выходит за рамки получения более сильного варианта PSO. Он демонстрирует новую парадигму эволюционных алгоритмов в эпоху параллельных вычислений:
-
Раньше мы исследовали, «как спроектировать лучший алгоритм»;
-
теперь мы исследуем, «как построить систему, способную автоматически порождать, отбирать и улучшать алгоритмы».
По мере того как массовая GPU-оценка кандидатов постепенно становится нормой в исследованиях, границы эволюционных вычислений неизбежно будут меняться: параллельное аппаратное обеспечение — уже не просто платформа, на которой выполняются алгоритмы, оно начинает участвовать в переформировании самих способов проектирования алгоритмов.
AutoPSO × EvoX: помочь эволюционным вычислениям совершить переход из ручной эпохи в автоматическую.
Открытый исходный код / Ресурсы сообщества
Статья:
https://arxiv.org/abs/2608.07539
GitHub:
https://github.com/EMI-Group/autopso
Вышестоящий проект (EvoX):
https://github.com/EMI-Group/evox
QQ-группа:
297969717
QR-код QQ-группы сообщества EvoX.