GUCA: эволюция на графах («Живые графы» 2.0)

1. Введение. От вопросов об эволюции к Artificial Life

1.1 Вопросы эволюции

Где проходит граница между случайностью и замыслом? Почему в наших ДНК куча мусора? Можно ли воспроизвести эволюцию в машине, и как зарождалась жизнь? Хотя и на последний вопрос ответа нет, но мы можем создать эксперимент, который позволяет моделировать механизмы эволюции с нуля. О таком эксперименте и пойдет речь сегодня. 

Это маленький мир из области Artificial Life — искусственной жизни, где эволюция идёт внутри компьютера.

1.2. Немного про Artificial Life

Artificial Life — направление развития технологий с целью запустить что‑то “жизнеподобное” внутри компьютера.

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

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

GUCA (Graph Unfolding Cellular Automata) — один из таких маленьких миров: в нём мы выращиваем “организмы” из узлов и рёбер графа.

1.3 Видео и интерактивное приложение

Перед тем как нырять в подробности, можно просто посмотреть, как это выглядит. У GUCA есть короткое ( 6 мин.)  видео‑демо и интерактивная веб‑песочница (https://roma-goodok.github.io/guca/)  написанная на TypeScript.

1.4. От абстрактной эволюции к GUCA

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

GUCA — попытка сделать такую игрушку. Вместо клеток у нас вершины графа, вместо длинной строки ДНК — компактный список правил, который говорит, в каких условиях узлу менять состояние, когда “рожать” соседей, когда цепляться за других и когда отсоединяться.

Первая версия у меня появилась ровно 15 лет назад, ещё в 2010‑м, как настольное приложение на C# и приложение на  вымершем Silverlight (сработала эволюция) — про неё есть отдельная статья 2010 года с подробностями реализации и скриншотами.

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

Дальше я буду говорить именно про текущую версию GUCA: графы, которые растут по правилам, и геномы, которые можно отдавать на откуп эволюции.

2. Что такое GUCA на интуитивном уровне

Условно, GUCA — это клеточный автомат (cell automation), который живёт не на привычной квадратной решётке, а на графе. Представьте организм, собранный из точек‑клеток и связей между ними. У каждой точки есть состояние: A, B, C… — просто разные “типы” клеток.

Граф не задан заранее, он может расти, меняться, деградировать, порождать новые графы, в том числе свои копии (т.е. реплицироваться). Для каждого узла есть набор правил — “геном” — который говорит: в каких условиях узел должен сменить состояние, когда родить соседа, когда протянуть к кому‑то ребро, а когда умереть. Из одного стартового узла с состоянием, например, “A” за десятки шагов может вырасти вполне сложная конструкция.

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

Теперь формализуем: из чего состоят условия и действия, и как они образуют “геном”. 

 3. Геном GUCA: условия и действия

3.1 Геном как список правил

Внутри GUCA у автомата действительно есть своя “ДНК”, или геном. Это упорядоченный список маленьких правил вида

если (условие) → сделать (действие)

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

3.2 Узел и его состояние

У каждого узла в графе есть дискретное состояние (например, A, B, C и т. д.) и небольшая память об истории - предыдущее состояние или знание о том, что узел только что родился.

3.3. Условия (condition)

У каждого гена есть блок condition, который описывает, когда он вообще имеет право сработать. Сейчас в GUCA используются четыре основных типа условий:

• current = … — текущее состояние узла (например, A, B, C).

• prior = … — состояние узла на предыдущем шаге (полезно знать историю и отличать “только что родился” от “давно живёт”).

• conn > / < / = … — сколько у узла связей с другими узлами вообще.

• parents > / < / = … — сколько у узла “родителей” (сколько раз его породили).

Часть полей можно не заполнять. Например, можно сказать “мне не важно прошлое состояние, главное — что сейчас узел в состоянии A и у него меньше трёх связей”.

3.4. Действия (op)

Второй блок гена — op, он описывает, что именно сделать с узлом, если условие выполнилось. Примеры операций:

• TurnToState → G — перейти в новое состояние G.

• GiveBirthConnected → A — породить новую вершину в состоянии A и сразу соединить её с текущей.

• TryToConnectWithNearest → A — попытаться соединиться с ближайшей вершиной в состоянии A. Причём, глубину поиска ближайших вершин можно ограничить на уровне глобальных параметров, например, “не дальше двух рёбер от текущей вершины”.

• DisconnectFromNearest → A — разорвать связь с ближайшими вершинами состояния A.

• (в расширенной версии есть ещё и Die — удаление узла из графа).

В совокупности пары

условие → действие

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

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

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

Итак, пары “условие → действие” составляют дискретный геном. У такого устройства генома есть несколько свойств, из‑за которых GUCA ведёт себя очень жизнеподобно.

3.5. Три приятных свойства такого генома

1. Локальные правила → глобальный граф.
   Каждый ген “смотрит”и “действует” только на один узел и его ближайший контекст: текущее/прошлое состояние, количество связей, число родителей. Никакого “плана” сверху нет — глобальная форма целиком возникает из этих локальных решений. Из набора одинаковых правил в разных местах графа вырастают кольца, сетки, фракталы и другие “звери”. Искусственный разум пока не родился.

2. Маленькие изменения — большие последствия.
   Поменяли одно число в условии (conn <= 5 на conn <= 6) или одно состояние‑операнд — и структура начинает расти совсем по‑другому. Вместо аккуратной сетки получается лохматый шар, вместо стабильной фигуры — взрыв и гибель системы. Ландшафт получается очень “неровный”: небольшая мутация в геноме может радикально поменять фенотип - как и в нашей жизни.

3. Дискретный список правил, почти как ДНК/РНК.
   Геном — это просто список правил, который удобно резать, склеивать и тасовать. Можно взять часть генов из одного “организма”, часть — из другого и собрать гибрид. Можно моделировать некоторые аспекты эволюции, связанные с последовательностью ДНК и хромосомами: кроссинговер, дублирование участков, выключение и включение “генов”. Всё это хорошо ложится на генетические алгоритмы, которые будут скрещивать и мутировать такие списки, проверяя, какие комбинации дают выживающее поведение.

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

4. Пример: цепочка из семи узлов

Посмотрим, как работает один конкретный геном состоящий лишь из одного гена.

Если в качестве начального графа взять один узел A и задать правило
GiveBirthConnected → A, и условия current=A, prior=Unknown, parents_le=5

то уже на первом шаге появится два узла, соединенных между собой.

Далее такими же шагами (где новый узел порождает еще один) вырастет цепочка из 7 узлов, после которого условия перестанут выполняться. 

Вот что получается с помощью одного простого правила.  Пример был создан вручную. 

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

 5. Эволюция геномов: как работает генетический алгоритм

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

В GUCA (пока) использована довольно классическая схема эволюции. Упрощенно один эксперимент выглядит так:

1. Стартовая популяция. Алгоритм создает случайную популяцию геномов произвольной длины.

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

   1. берём стартовый граф (обычно один узел A);

   2. запускаем симуляцию на несколько шагов;

   3. смотрим, что именно он вырастил: развал, сетку, кольцо, фрактал или что‑то странное.

3. Оценка приспособленности (fitness).
   Получившийся граф превращается в одно число — значение fitness‑функции.
   Как именно считать это число — мы задаем сами: можно награждать за определенную структуру графа, его размер, и свойства  и т.д.  Или прорисовывать граф в картинку и измерять похожесть на к.н. категорию используя нейронную сеть. Чем выше fitness, тем «успешнее» геном в наших условиях.

4. Отбор. Геномы сортируются по фитнесу.
   Те, кто справился хуже, выбывают. Те, кто лучше, продолжают род.

5. Размножение и мутации.
   Из лучших геномов собирается новое поколение:

   1. часть просто копируется,

   2. часть скрещивается (берутся фрагменты правил от разных «родителей»),

   3. часть мутирует — случайно меняются параметры условий или действий, иногда добавляются или удаляются правила.

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

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

6. Песочница: какие “организмы” уже получаются

Давайте посмотрим на  конкретных “животных” (формально - растений, т.к. они пока никого не едят и не двигаются) с сайта, которых уже удалось вырастить:

• dumbbell, hairy circle, primitive fractal — базовые формы из ранних экспериментов, их “гены” созданы вручную, а не с помощью эволюции.

• triangle mesh — треугольная сетка. Практически первый продукт эволюционного алгоритма, который получился так, как его задумывал создатель :)

• quad mesh — следующий шаг: более сложная структура, для которой нужно было подобрать правила так, чтобы она развивалась устойчиво и предсказуемо.

  

• hex replicator - репликатор в рамках одной симуляции, — цепная реакция рождающихся шестиугольников

Симуляции интерактивны:

• можно в любой момент поставить паузу, увеличить масштаб и изучить конкретный узел;

• посмотреть, какие именно правила сработали для него на последних шагах;

• временно отключить часть генов и посмотреть, как меняется поведение.

Еще есть инструмент «ножницы»:

• ими можно разрезать связи в уже выросшем графе и посмотреть, схлопнется ли всё, или структура попробует восстановиться.

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

Онлайн-песочница удобна тем, что в ней можно:

• редактировать гены существующих организмов — изменять условия, операции, порядок правил;

• рекомбинировать их: например, взять гены dumbbell и hairy circle и собрать гибрид (такой на сайте тоже есть);

• запускать рост заново и сравнивать, как ведут себя разные версии генома.

Поэкспериментировав с этими организмами, мы начали замечать мотивы, очень похожие на биологические.

7. Наблюдаемые эффекты

В текущей версии GUCA уже появляются мотивы, которые мы привыкли видеть в биологии. Для игрушечной цифровой модели это довольно много: классические эффекты Artificial Life начинают проявляться сами, без явного “запрограммируй мне регенерацию, пожалуйста”.

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

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

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

Это очень похоже на цифровой вариант «кембрийских взрывов»: длинные спокойные скучные фазы и внезапные скачки разнообразия или повышения сложности.

• Ну и тупики эволюции, куда же без них.

8. GUCA на карте Artificial Life: NCA, ALIENS, developmental GCA

GUCA не существует в вакууме — вокруг есть целый зоопарк проектов, которые тоже играют в эволюцию и искусственную жизнь.

8.1. Чуть формальней: генотип и фенотип

Если сравнить с классическими подходами вроде NEAT (NeuroEvolution of Augmenting Topologies),  то там структура графа закодирована в генотипе

В GUCA связь между:

• генотипом (набором локальных правил на графе) и

• фенотипом (тем, во что вырастает  и ведёт себя система)

получается опосредованной и гетерородной.

Мы не прописываем желаемый итоговый граф, а задаём только локальные реакции узлов. Форма организма — побочный эффект их совместной работы. Это ближе к тому, как устроена живая биология.

8.2. GUCA и open‑ended миры (ALIENS, NCA, developmental GCA)

Есть и более «размашистые» проекты. Если кратко: NCA (Neural Cellular Automata) — это клеточные автоматы с нейросетью вместо жёстких правил, ALIENS и похожие проекты — это открытые миры с очень богатой физикой и поведением.

• эксперименты с Neural Cellular Automata (NCA) — где вместо фиксированной таблицы правил используется обучаемая модель;

• open‑ended симуляторы вроде проекта ALIENS; (графы взаимодействуют с друг другом и борются за ресурсы, логика реализована на передаче сообщений между узлами, вкоречена нейронная сеть)

• Недавно появились похожие работы по Developmental Graph Cellular Automata, включая статью «Growing Reservoirs with Developmental Graph Cellular Automata» (2025) и более общие исследования под названием «Developmental Graph Cellular Automata» (2023)

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

За счёт этого:

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

Конечно, можно комбинировать идеи других подходов или расширять GUCA, например добавлением стохастического асинхронного обновления, вместо детерминированного…

9 Зачем это нужно и кому может быть интересно

9.1. Честный ответ 

Практического применения у этой модели нет. (Пока что?)

Нам просто интересно её делать, смотреть, как ведёт себя эволюция, и что происходит, когда ничего не кодируется  явно, а только ставятся условия отбора.

Самая близкая "прикладная" мысль — когда-нибудь соединить это с идеей альтернативного построения систем вроде децентрализованных колоний роботов фон Неймана или с роевым управлением (“swarm intelligence”).

9.2 Микролаборатория эволюции

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

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

В моделях типа GUCA всё проще. Мы можем задавать:

• длину “гена” (списка правил), точнее величину штрафа за длину гена начиная с пороговой длин

• количество возможных состояний узлов,

• схему мутаций и скрещиванияю

• способ отбора (что именно считаем “успехом” графа).

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

Я не утверждаю, что GUCA “доказывает” формулу Эйгена или Прайса (с которыми, кстати, предварительно по моим экспериментам не всё так однозначно) — это всё‑таки игрушечный цифровой мир. Но такой мир удобно использовать, чтобы проверять гипотезы в духе этих теорий:
что будет, если увеличить мутации при фиксированной длине генома,
или наоборот — удлинить геном, почти не меняя уровень мутаций;
как ведёт себя отбор, если награждать не отдельные графы, а целые “популяции” графов; обнаружить эффекты эволюции генных сетей; уточнить роль специализированного пола и полового отбора; проанализировать в деталях свойства ландшафта фитнесс-функции и т.п.

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

Недавний пример подобных работ:  как моделирование морфогенеза с помощью клеточных автоматов (NCA) используется для проверки научных гипотез о природе старения  (правда, возможно, около научных) “Aging as a Loss of Goal-Directedness: An Evolutionary Simulation and Analysis Unifying Regeneration with Anatomical Rejuvenation” https://advanced.onlinelibrary.wiley.com/doi/pdf/10.1002/advs.202509872

10. Как самому  поиграть с GUCA

Если просто смотреть, как растут чужие графы, удовольствие быстро заканчивается. Гораздо интереснее — устроить себе пару мини‑квестов или даже вызовов и попробовать вырастить что‑то своё. Например:

• собрать репликатор — структуру, которая не просто разрастается, а умеет порождать отдельные копии себя;

• сделать “гуляющую дырку” в регулярной сетке, которая не зарастает сразу, а  ползёт по графу (как дислокация в кристаллической решётке).

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

• придумать организм с регенерацией, который побывав под “ножницами” хотя бы частично восстанавливает форму;

• придумать пульсирующую форму, которая не умирает, но и не замирает — просто меняет конфигурацию по циклу (“семафоры”);

• настроить две конкурирующие популяции узлов  (например, узлы состояний A и B), чтобы они образовывали границы и “острова” ;

• 3D: GUCA никак не ограничена “плоскими” графами, а на сайте есть функция отображения в 3D, так что можно попробовать создать кубы, сферы и прочий “minecraft”.

• Любая другая ваша идея! Если что пришло в голову - обсудим!

А чтобы добавить немного спортивного интереса, можно устроить мини‑соревнование (хоть с друзьями, хоть в одиночку):
попробовать решить любую из этих задач:

• с минимальным количеством состояний узлов;

• с минимальной длиной генома (числом правил).

Например:
“Кто сделает репликатор с наименьшим числом состояний?”
или
“Кто вырастит шестиугольные соты с самым коротким геномом?”

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

Проверить свои силы можно в интерактивной веб‑песочнице (https://roma-goodok.github.io/guca/)

11. Что дальше: планы на цикл статей. О чем расскажем дальше

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

Примерный план продолжения:

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

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

• Как эволюция обманывает “Создателя”.
  Показать примеры, где мы хотели одного поведения, а система нашла совершенно другой путь к высокой фитнес‑оценке — и почему это, вообще‑то, очень по‑эволюционному.

• Как помочь эволюции не упираться в тупики.
  Поговорить про настройки отбора, мутаций и разнообразия популяции, чтобы система не застревала в “локальных максимумов”.

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

• Онтогенез и морфогенез в мире графов.
  Что можно считать “развитием организма” в GUCA, как разные фазы роста связаны с финальной формой и что происходит, если вмешиваться в процесс.

• “Мусорная ДНК” в графовых геномах.
  Поговорить о неактивных или почти неактивных правилах, которые болтаются в геноме: действительно ли мусор это, или запас на чёрный день, или следы давно прошедших эволюционных этапов.

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