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

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

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

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

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

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

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

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

Введение