Как управлять эволюционным поиском? На примере конечных автоматов

ты возьмешь только то, что поймешь,
а поймешь только то, что исправишь.
— Владимир Леви

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

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

Один из способов понять как возникает сложность  — это попробовать создать ее самому. 

Поэтому мы поговорим об эволюционных алгоритмах на примере созданной мной модели GUCA (Graph Unfolding Cellular Automata). Ее можно запустить на компьютере, чтобы проверять гипотезы и находить закономерности: какие изменения приводят к прогрессу, какие — к стагнации, а какие — к эффектным, но бессмысленным решениям.

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

Github

Сайт-песочница 

YouTube

Дисклеймер: Мы не биологи, и эволюционная метафора для нас — удобный язык для разговора об оптимизации и поиске, поэтому термины из биологии могут использоваться неточно. 

Что можно понять с помощью эволюционных алгоритмов? 

Типы задач, которые решают ЭА

Эволюционные алгоритмы применимы в задачах, где:

• пространство решений огромно (и перебор бессмысленен)

• пространство решений дискретно - сложно применять оптимизационные алгоритмы основанные на градиентном спуске (используемые для обучения нейронных сетей),

• нет очевидного пути построения результата,

• решений может быть несколько и даже не лучшие из них нас могут устроить.

Часто это задачи про структуры: формы, сети, правила роста, динамические системы, где итог возникает из множества локальных шагов. 

Как управлять эволюцией

Что именно можно делать, чтобы проверить гипотезы об эволюции с помощью модели?

• Создавать и менять параметры самого генетического алгоритма: отбор, вариации, механизмы сохранения лучших решений, поддержка разнообразия.

• Настраивать цель (fitness): по каким измеримым признакам мы решаем, что нам нужно получить в итоге.

Дальше поговорим про то, как устроены два этих блока.
 

Коротко о GUCA 

GUCA (Graph Unfolding Cellular Automata) — это проект из области Artificial Life: модель, где можно запускать рост структур (в виде графа) на компьютере и наблюдать их создание из простых локальных правил. Подробное описание, примеры организмов и интерактивная песочница разобраны в первой статье про проект: GUCA: эволюция на графах, а сейчас опишем основу.

Клеточный автомат на графе

Обычный клеточный автомат (по типу “Жизни” Конвея) живет на регулярной решетке: клетки имеют фиксированных соседей и на каждом шаге меняют состояние по правилам.

В GUCA вместо классической решетки — граф, то есть структура из вершин (узлов) и рёбер (связей между ними). Вершины в таком случае — это “клетки”,  а ребра определяют “соседство”. В отличие от классических клеточных автоматов, где “пространство” существует “всегда” граф сам по себе и является “пространством” и не задан заранее. Он может расти и перестраиваться: появляться новые узлы, возникать и исчезать связи, а значит — меняется геометрия структуры.

Геном

“ДНК” в GUCA — это упорядоченный список правил вида

если (условие) → выполнить (действие).

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

• текущее состояния узла,

• предыдущее состояния,

• число связей (сколько соседей у узла)

• число “родителей”.

Действия описывают рост и перестройку графа: узел может 

• сменить состояние, 

• породить нового соседа, 

• создать связь с другим узлом,

•  разорвать связь,

• “умереть” (исчезнуть из графа). 

Один элемент списка — это “ген”, весь список — “геном”. Геном общий для всех узлов, но в каждый момент времени срабатывают только те правила-гены, чьи условия подходят конкретному узлу. А еще такой список легко копировать, резать, склеивать и тасовать — то, что нужно для эволюционного отбора.

Теперь о том, как устроен сам эволюционный алгоритм на основе этого субстрата.

Генетический алгоритм в GUCA-evo-lab

Генетический алгоритм (ГА) в GUCA-evo-lab — это набор условий, по которым популяция геномов меняется от поколения к поколению.

Общая схема алгоритма

Каждый эксперимент начинается с рандомного набора геномов, в котором прогоняется фиксированное  количество итераций (сейчас от 1000 до 15000, минуты и десятки минут) эволюционного цикла. Вот его схема:

инициализируем стартовую популяцию геномов

для поколения = 1...ngen:

берем популяцию геномов

создаём потомков (вариации):

       кроссинговер 

       мутации

для каждого генома:

       разворачиваем фенотип (“выращиваем” граф по правилам) 

       считаем fitness (приспособленность) фенотипа

собираем следующее поколение:

стохастический отбор на основе fitness 

добавляем элиту (лучшие без изменений)

добавляем часть случайных новых геномов

новое поколение становится текущим для следующего цикла

Мутации и кроссинговер

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

Мутации — это изменения генома, которые создают новые варианты правил и их комбинаций:

• точечные изменения параметров правила,

• замена одного правила другим,

• добавление или удаление правила,

• перестановка порядка правил.

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

Симуляция

После того как поколение частично изменилось из-за мутаций, каждый геном нужно оценить. 

Для этого запускаем симуляцию (развертывание графа с помощью правил из генома), и получаем фенотип: сам граф с набором измеримых характеристик.

Отбор наиболее приспособленных

После оценки нужно решить главный вопрос нашего поколения: кто станет родителями следующей популяции Если мы просто возьмём топ-N, это приведет к проблемам: при шумной оценке топ может отражать удачный случай, а при слишком жестком отборе популяция теряет разнообразие и схлопывается вокруг одного решения.

Поэтому отбор стохастический. В GUCA-evo-lab реализовано 3 “классических” метода отбора:

• ранговые схемы;

• турнирные схемы;

• пропорциональные.

Сборка нового поколения

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

• Элита: несколько лучших решений переносятся в следующее поколение без изменений, чтобы закрепить лучшие в популяции решения.

• Random immigrants: полностью случайные геномы для поддержания разнообразия. — мигранты нам еще пригодятся когда будем исследовать многоостровные сценарии эволюции.

После этого цикл запускается с самого начала с заново собранной популяцией.

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

Fitness: как получить от эволюции то, что нужно

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

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

Формулируем задачу

Для примера поставим перед ЭА задачу построить квадратную решётку/сетку. Чем хороша такая задача:

• человеку ее легко представить и оценить визуально,

• при этом вручную создавать с помощью правил GUCA ее трудно (в этом видео мы справились, но думали долго),

• для эволюции это тоже челлендж (для сравнения, создание треугольной решетки просто настолько, что справляется GPT 4o).

Как объяснить алгоритму, что "нужна квадратная решетка, и чем больше и качественней, без дефектов - тем лучше"? С помощью fitness-функции. По ней принимается решение, какие структуры отбирать для следующего поколения.

В нее можно засунуть конкретные параметры для оценки. Мы говорим, что чем больше сетка, тем лучше. Но что значит “больше”? Продолговатая сетка больше чем квадратная? Количество узлов с 4 соседями или количество граней с размером 4? А если попадаются другие грани или узлы? 

На эти вопросы и отвечает фитнесс-функция. Попробуем разобрать, какие критерии мы вложим в fitness, чтобы получить нашу цель.

1. Выживаемость

Прежде чем формулировать критерии для конкретного случая, нужно убедиться, что фенотип является валидным объектом.

Для этого делаем слой с гейтами — это условия, которые переводят фенотип на низкий базовый уровень score, либо сразу выкидывают его из гонки “уродцев”:

1. Непустой фенотип: граф не должен выродиться в ничто.

2. Граф не должен превысить лимит по числу вершин.

3. Связность — фенотип (для задачи построения quad mesh) не должен быть россыпью островков.

Еще есть ограничение, специфичное для задач типа mesh. Нужно, чтобы итоговый объект выглядел как плоская сетка. Поэтому мы вводим требование планарности: граф должен быть таким, чтобы его можно было нарисовать на плоскости без пересечений рёбер. Иначе дальше будут страдать метрики “квадратности” и периметра.

2. Внутренняя область

После этапа выживаемости мы обнаруживаем, что локальные правила чаще всего выращивают деревья — связные графы без циклов. Деревья “удобны” для эволюции: они легко растут, редко ломают связность, и в них проще поддерживать локальные условия. Но для создания сетки нам нужны именно циклы, а не деревья.

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

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

3. Квадратные грани

После всех подготовок можно дать первый целевой сигнал.

Нам становится важен размер грани — это число рёбер на ее границе. Тогда квадратная грань — это внутренняя грань размера 4 (четырёхугольная “ячейка”). Поэтому базовая идея этапа выглядит так:

1. награждаем за число внутренних квадратных граней (размера 4).

2. штраф за неправильные грани, чтобы сохранялся градиент в сторону увеличения квадратов, но не отсеивались все дефектные графы. 

3. штраф за слишком большие или странные по периметру/границе грани.

По итогу мы получаем правила “квадратности” на уровне ячеек — какие грани мы хотим видеть.

4. Вершины

Кажется, всего уже достаточно: мы награждаем квадраты, штрафуем не-квадраты, и на выходе получаем сетку. Но на выходе часто получаются “перекошенные” графы, где квадратные ячейки не образуют сетку.

Чтобы это учесть, будем смотреть на степень вершины — сколько рёбер входит в вершину (сколько у узла соседей). Для квадратной решётки характерно, что во внутренней области вершины имеют степень 4. Поэтому fitness:

• поощряет внутренние вершины степени 4

• подавляет структуры с аномально большими степенями, где сетка вырождается в систему “узлов-коммутаторов”

Исключение из правил:

• отделять внешние вершины: на границе степень может быть <4 и за это не стоит штрафовать.

5. Топология и общая форма

Мы научили фенотип делать много квадратных граней и стыковать их на уровне вершин. Но появляется неочевидная вещь: можно набрать много квадратов и все равно получить плохую сетку. Например, очень вытянутую конструкцию или “трубочку” (формально планарную).

Поэтому на этом этапе:

1. Оцениваем двумерность структуры.
   Образуется ли достаточно “толстая” область в двух направлениях, а не просто цепочка? Чтобы понять это используется отдельная метрика WH (минимум от "ширины" и "высоты" quad mesh).

2. Проверяем внешнюю оболочку.
   Оболочка (shell) — это внешний контур планарного графа. В quad mesh она используется как вспомогательное ограничение: оболочка не должна быть слишком маленькой относительно числа квадратных ячеек. Это помогает отсекать вырожденные конфигурации.

6. Стабилизация

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

Вот что нужно учесть, чтобы избежать лазеек эволюции:

• Проверка устойчивости

Если оценивать геном в одном и том же сценарии, он может стать идеальным для частного случая, но разваливаться при изменении условий. Для этого оценку можно агрегировать по нескольким прогонам, с разными seed-значениями. Тогда отбор начинает поощрять не частный удачный случай, а более надёжное поведение.

• Штраф за излишнюю сложность

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

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

Итог

Итак, что из этого примера можно понять о постановке цели:

• fitness — формализованный вопрос, который мы задаем эволюции. Если вопрос задан неполно, эволюция почти гарантировано найдёт не то, что мы имели в виду, а то, что мы смогли измерить.

• Хорошая фитнесс-функция строится поэтапно, и каждый новый слой появляется как ответ на лазейку.

Философский вывод: мы можем не понимать, как прийти к результату, но мы должны иметь хорошее представление о том, что хотим получить в итоге. Кстати, это работает не только для генетических алгоритмов, но и для организации, состоящей из людей, и для AI-агентов тоже. 

Сравнение с человеческими решениями

Человеки:

В качестве упражнения можно посоревноваться с ГА и попробовать создать квадратную решетку на сайте GUCA с помощью редактора. Вот что получилось: 

• 15 генов

•  7 состояний для решетки с глубиной поиска 2

• Думали ~60 мин 

• Fitness функция (которую мы использовали для ГА) этот результат оценила хуже, чем эволюционные...

Главное различие с эволюцией в том, что человек мыслит “сверху вниз”, то есть от абстракции к конкретике, делая декомпозицию. Поэтому, придумать последовательный алгоритм, который бы строился на локальных правилах — задача для тех, у кого есть несколько свободных вечеров и elo в шахматах > 1000.  

LLM:

В отсутствие свободных вечеров можно поручить задачку AI, чем мы тоже занялись. В разных режимах (простой диалог/режим агента) GPT 5.4 справилась с переменным успехом. Один из лучших вариантов:

• 51 ген для решетки 5*5 

• 8 состояний

• Думала 39 минут

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

GUCA-evo-lab:

• Сейчас лучшие варианты это: 8 генов, 6 состояний узлов

• Думает еще дольше — пару дней

Решение менее точное, как можно понять: могут быть не квадратные грани и искусственные ограничения из-за рандомности генов (например, если в паре генов поменять parents или другое условие, результат будет лучше, но эволюция до этого “не доходит”).

Эволюционные тупики…

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

Пространство решений для графов с 3 генами (слева) и с 4 генами (справа). Фитнесс-функция задана для квадратной решетки

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

Другие трудности связаны с плато — областями, где множество решений имеют одинаковый или близкий fitness. На плато отбор перестает задавать выраженное направление поиска, и эволюция замедляется или сводится к нейтральному дрейфу.

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

…и что с ними делать

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

Цель для GUCA-evo-lab — выявить закономерности, которые позволили бы генетическому алгоритму быстрее адаптироваться к новым задачам без полной перенастройки с нуля. 

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

В следующей статье расскажем про итоги этих экспериментов, а еще про закономерности в параметрах ГА, которые удалось найти за все время.