В этом блоге будет краткое введение в некоторые интересные эволюционные алгоритмы оптимизации, над которыми я работал последние несколько месяцев. Мы рассмотрим несколько методов, используя различные эволюционные подходы. Хотя мы не будем обсуждать различия между генетическими алгоритмами и эволюционными стратегиями, например, мы рекомендуем читателям отметить эти различия и изучить то, что вас интересует. Не стесняйтесь исследовать их дальше и повторно использовать код с открытым исходным кодом.
Эволюционные алгоритмы (ЭА) имеют долгую и разнообразную историю. Большинство людей знакомы только с самой базовой версией EA, что часто приводит к предвзятому отношению к этому подходу. Но в этой области существует множество вариаций и инноваций, и в этом посте мы познакомим вас с некоторыми из них.
Итак, начнем!
- Дифференциальная эволюция
Это один из подходов к EA, который не пользуется широкой популярностью и поэтому нуждается в понимании. Дифференциальная эволюция (DE) аппроксимирует обратный генетический алгоритм (GA) с дифференциально-взвешенной мутацией. Используя такие операторы, как дифференциальная мутация и кроссовер, а также отбор и модуляризация, алгоритм может развиваться в направлении глобального оптимума.
На приведенном выше изображении алгоритма DE, ищущего свой ландшафт пригодности, ясно, как два вектора (X_r2 и X_r3) взаимодействуют, создавая дифференциально взвешенный мутированный вектор в новом направлении. Это приводит к более быстрой сходимости. Для улучшения этого алгоритма можно использовать множество стратегий.
2. Генетический алгоритм с обратными операторами
Для этого метода операторы ГА (а не сам алгоритм) меняются местами. Хотя это может показаться колдовством, это можно рассматривать как приближение к DE без других его параметров. На практике этот алгоритм действительно хорошо работает для таких приложений, как криптография, обработка изображений или задачи оптимизации черного ящика.
3. Генетический алгоритм с реверсами
Можно не только поменять местами компоненты ГА, но и изменить поведение ГА. Разворот можно рассматривать как конечный период времени (100 шагов), в течение которого ГА изменяет свое поведение, чтобы максимизировать, а не минимизировать свою цель. Это может помочь данному ГА избежать локальных оптимумов, предотвратить его полное застревание и найти лучшие решения. Время разворота и интервал определяются программистом. Во время этой фазы максимизации и возврата к минимизации мы наблюдаем увеличение потерь.
Подробнее о разворотах можно прочитать в этом препринте arXiv.
4. Цепочка
Цепочка — это простая концепция: вы берете алгоритм оптимизации и передаете его решение, полученное на следующий алгоритм оптимизации. Вы можете изменить это дальше, введя операторы мутации.
Одна из специализированных форм цепочки называется итеративной цепочкой, когда мы повторяем процедуру цепочки несколько раз. Однако часто необходимо использовать механизм, называемый ранней остановкой, чтобы остановить итерационный процесс, поскольку функция потерь расходится.
Повторяющаяся цепочка немного похожа на подходы стекирования, используемые в машинном обучении. Вы можете найти реализации цепочек в наборе инструментов fliscop (версия PyPi).
5. Gradient Evolution или ES с информацией о градиенте
Это один из алгоритмов, который очаровал меня тем, как Эволюционные стратегии (ES) могут полагаться на информацию о градиенте (от градиентного спуска) для лучшей оптимизации. В конечном итоге метод ES можно использовать как часть более широкой стратегии аппроксимации градиента. Это будет реализовано аналогично полной и усеченной декомпозиции по отдельным значениям (SVD). Градиентная эволюция обеспечивает более быструю сходимость и обучение, а также позволяет нам обучать агентов.
На изображении выше видно, как ES работает по сравнению с ES на основе градиента в тесте Lunar Lander OpenAI. Более подробную информацию можно найти в этом наборе инструментов для эволюции градиента.
Я настоятельно рекомендую читателям прочитать ссылки, если что-то возбудило ваше любопытство!
Чао!
Не стесняйтесь писать мне в Твиттере @agrover112 для любых вопросов или идей, касающихся области эволюционных алгоритмов, искусственного интеллекта и т. д.
Обязательно подпишитесь на @Orthogonal_lab, чтобы получать больше контента по таким темам, как вычислительная нейронаука, искусственный интеллект и многим другим!
Рекомендации
[1] Agrover112/fliscopt: Алгоритмы оптимизации расписания полетов. (github.com)
[2] Лекция 13: Реализация дифференциальной эволюции с использованием MATLAB — YouTube
[3] [2202.00912] Включение локального исследования: генетические алгоритмы с реверсированием (arxiv.org)
[4] Как выполнить оптимизацию — документация nevergrad (facebookresearch.github.io)
