🧬 Эволюционные алгоритмы

Полтора месяца назад DeepMind выкатил AlphaEvolve, где LLM-агент генерирует, скрещивает и отбирает фрагменты кода на основе эволюционного подхода. Так появляются новые алгоритмы — от рекордов в матричном умножении до оптимальных расписаний вычислений и топологий печатных плат для TPU. Сообщество уже откликнулось опен-сорсным OpenEvolve — можно запустить тот же процесс самому и выращивать свои программы.

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

Расписание описываем вектором моментов, когда включается красный:

1-й 🚦 5 с, 35 с
2-й 🚦 7 с, 37 с
…
n-й 🚦 3 с, 17 с

Дальше классика:

🐱 Особь - вектор расписания светофоров
🏙️ Популяция - 256 случайно сгенерированных особей
🧑‍🧑‍🧒 Скрещивание - из двух особей создаём третью, унаследовавшую их черты
🐷 Мутация - случайно меняем часть особей и возвращаем их в популяцию
💎 Отбор - подсчёт функции приспособленности - количества проехавших машин за симуляцию в нашем случае. И выбор лучших 256 особей

🌀 Цикл «популяция → скрещивание → мутация → селекция» повторяем, и каждое новое поколение едет не медленнее предыдущего.

🧐 Легко увидеть, что на обоих частях видео все светофоры одинаково горят по 2 раза красным одинаковое время. То есть уважаемые пешеходы проходят одинаково.Этот подход к решению задачи очень наивен. Есть более продвинутые формулировки и результаты. Однако, его можно применять к очень широкому классу задач.

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