Эволюционирующие клеточные автоматы

1lq9zpa_3skswtp1hsvzcemhkf4.png

Соединим клеточные автоматы с генетическим алгоритмом и посмотрим, что из этого получится.

В статье присутствуют Gif (трафик!) и контрастные картинки. У эпилептиков может случиться эпилептический припадок.

Правила для клеточных автоматов.

Самый простой клеточный автомат — одномерный клеточный автомат (существуют также нульмерные — о них поговорим ниже). В одномерном клеточном автомате у нас есть одномерный массив, ячейки которого (клетки) могут принимать одно из двух состояний (1/0, true/false, белая/черная, живая/мертвая). Следующее состояние клетки в массиве определяется текущим состоянием клетки и состоянием двух соседних клеток, по некоторому правилу.

Всего существует $2^3=8$ комбинаций состояний клетки и двух соседних клеток:

zgjm7o38yhay_o9amhrzn2dlbww.png

Далее для каждой из комбинаций запишем состояние клетки для следующей итерации (для следующего состояния автомата):

dajht24fnhiryiof25oor21a_hs.png

Получили правило для клеточного автомата. Правила для одномерных клеточных автоматов кодируются 8 битами («код Вольфрама»). Всего существует $2^8=256$ элементарных клеточных автоматов:

feojkr-dw1f2osyk4hde4l1sfa4.png

256 автоматов можно перебрать вручную. Не будем на них останавливаться. Посчитаем количество существующих правил для двухмерных клеточных автоматов.

В двухмерном клеточном автомате используется двухмерный массив. У каждой клетки есть 8 соседей в окрестности Мура (существует также окрестность фон Неймана, в которой не учитываются диагональные клетки. Ее в статье не рассматриваем):

dh4yrgpnmfk0optyzjmdb-7d5ly.png

Для удобства запишем клетки в строку (выбранный порядок будем использовать далее в статье):

jeaxrvrwgq65rljhawgwxoytwkq.png

Для двухмерного клеточного автомата существует $2^9=512$ комбинаций состояний клетки и 8-ми соседних клеток:

a9apmt4xs1fnpkeq5z83cbw4gfi.png

Правило для двухмерного клеточного автомата кодируется 512 битами. Всего существует $2^{512}$ двухмерных клеточных автоматов:

bmgimh1bunkeizqaqfmptwvjxxk.png

Число:

$2^{512}\approx1.340781\times10^{154}$

больше количества атомов в наблюдаемой Вселенной ($10^{80}$).
Вручную такое количество автоматов не перебрать. Если бы мы каждую секунду просматривали по одному автомату — за время существования Вселенной мы бы успели просмотреть всего $\approx4.35\times10^{17}$ автоматов.

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

Программировать будем на JavaScript. Все фрагменты кода спрятаны под спойлеры, чтобы не смущать читателей, не знакомых с языками программирования.

Двухмерный клеточный автомат.

Напишем двухмерный клеточный автомат с случайным правилом. Правило будем хранить в массиве rule, длина которого rulesize=512:

Заполняем массив rule
var rulesize=512;
var rule=[];
for(var i=0;i

Далее заполняем начальное состояние автомата рандомом:

Заполняем начальное состояние автомата
var sizex=89;
var sizey=89;
var size=2;
var a=[];
for(var x=0;x

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

Функция, вычисляющая следующее состояние автомата, выглядит следующим образом (чтобы не захламлять — убрал инициализацию холста):

Считаем следующее состояние автомата
function countpoints(){
	var temp=[];
	var xm, xp, ym, yp, q;

	for(var x=0;x

Переменные xm и xp хранят координаты X соседа слева и соседа справа (x minus и x plus). Переменные ym и yp хранят соответствующие Y координаты.

Здесь:

Поле автомата свернуто в бублик
		xm=x-1;
		if(xm==-1) xm=sizex-1;
		xp=x+1;
		if(xp==sizex) xp=0;

мы задаем периодические граничные условия (поле автомата — поверхность тора).

Далее:

… далее
			q=''+a[xm][ym]+a[x][ym]+a[xp][ym]+a[xm][y]+a[x][y]+a[xp][y]+a[xm][yp]+a[x][yp]+a[xp][yp];
			q=parseInt(q, 2);
			temp[x][y]=rule[q];

в указанном выше порядке записываем содержимое клеток в строку. Переводим строку в десятичное число. Для этой комбинации находим в массиве rule состояние, которое должна принимать клетка с координатами x и y.

Оптимизированный вариант

			q=a[xm][ym];
			q=(q<<1)+a[x][ym];
			q=(q<<1)+a[xp][ym];
			q=(q<<1)+a[xm][y];
			q=(q<<1)+a[x][y];
			q=(q<<1)+a[xp][y];
			q=(q<<1)+a[xm][yp];
			q=(q<<1)+a[x][yp];
			q=(q<<1)+a[xp][yp];
			temp[x][y]=rule[q];

После всех итераций заменяем предыдущее состояние автомата новым:

заменяем предыдущее состояние новым

Автомат рисуем с помощью функции setInterval:

setInterval
timerId = setInterval(function() {
	countpoints();
}, 1);

Запустить в браузере

Рекомендую 10–20 раз запустить автомат с случайными правилами, прежде чем продолжить чтение статьи.

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

vwvlyrk7prdlrzcvxv3g3787e6q.gif

Далее перейдем к настройке нашего «телевизора» с помощью генетического алгоритма.

Генетический алгоритм.

Размер начальной популяции — 200 автоматов (особей). Для правил, вместо одномерного массива rule будем использовать двухмерный массив population. Первый индекс (n) — номер особи в популяции.

Создаем популяцию
var PopulationSize=200;
var rulesize=512;
var population=[];
var fitness=[];
for(var n=0;n

Массив fitness содержит коэффициенты приспособленности каждой особи. Этот массив заполняем в процессе отбора. После отбора запускаем эволюционный процесс.

Эволюционный процесс.

Из нашей популяции берем половину наиболее приспособленных (по коэффициенту fitness) особей. Оставшуюся половину уничтожаем. Далее берем по две выжившие особи и скрещиваем их.

ruzzby4r6tjcazvtcqybydxpcea.png

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

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

Функция evolute ();
function evolute(){
	var sizehalf=PopulationSize/2;
	var sizequarter=sizehalf/2;
	var arrayt=[];
	for(var n=0; n

Естественный отбор.

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

Какие критерии можно определить заранее? Возьмем самый простой. Наш «телевизор» слишком сильно мигает. Сохраним два состояния клеточного автомата — на 99 и на 100 итерациях. Посчитаем количество клеток, которые не изменились. Полученное число будем использовать в качестве коэффициента приспособленности. Очевидно, что одного критерия нам не хватит. Легко вручную подобрать автомат, который будем наилучшим образом соответствовать заданному критерию: автомат [0,0,0,…,0] и автомат [1,1,1,…,1]. Эти два автомата на первой итерации заполняются нулями или единицами и перестают изменять свое состояние. Определим второй критерий: разница между количеством 0 и 1 (клеток) в автомате не превышает 100 (число взято «от балды»).

array1 — состояние автомата на 99-й итерации. array2 — на 100-й итерации:

Считаем
function countfitness(array1, array2){
	var sum=0;
	var a0=0;
	var a1=0;
	for(var x=0;x

Запускаем. Оптимальное решение найдено на 421-ом цикле эволюции. На графике можно посмотреть прогресс:

283zglf0je1qq0tfm3xhtaujp60.png

График масштабирован по оси Y. Нижняя точка — 0, верхняя точка — 7921. Очевидно, что 7921 — оптимальное решение (все клетки в автомате 89×89 соответствуют заданному критерию). После 100 итераций ни одна клетка не изменяет своего состояния.

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

Генофонд популяции (по оси Y — особи, по оси X — гены):

cfbyvcxnx8yrb-kacpuujn47omy.png

Посмотрим, какой канал словил наш «телевизор»:

uih2kvb-gvz9kpjayplydu39-mq.gif

Найденное решение не является единственным оптимальным. Если повторно запустить эволюцию (с случайными начальными генотипами) — найдем другие оптимальные решения. Одно из них:

sr1ekjlromek71oih350yarrvv4.gif

Изменим критерии отбора.
Будем считать количество клеток, для которых в окрестности Мура порядка 2 появляется некоторый паттерн. Паттерн возьмем самый простой:

vxtskpwsmqcl8wfukvyub7pmhag.png

Этот критерий интересен тем, что мы проверяем 25 клеток, в то время, как автомат вычисляет состояние клетки исходя из состояний 9 клеток.

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

pbeoq1lgxemfcnjsn2iwds3mclu.png

Ни одна клетка в таком автомате не соответствует заданному критерию. Поэтому немного смягчим критерий:
1. Разрешим сделать одну ошибку в паттерне.
2. Паттерн будем искать не на последней итерации, а на последних 50 итерациях.

Второй критерий (баланс между белыми и черными) уберем.

Запускаем. График:

bgvhkazwhigcg4b-w-emulsg7uw.png

По оси Y масштаб произвольный. (В предыдущем автомате оптимальное решение — 7921. В этом автомате — около 30.)
По оси X — 3569 циклов эволюции. Двумя белыми вертикальными линиями отмечены 500 и 1000 циклов эволюции.
Синие точки — лучшая особь в популяции, красные — худшая, черные — средний коэффициент для всей популяции.

Решение найдено на первых 500 циклах эволюции. Следующие 500 циклов решение улучшается. И далее система практически перестает эволюционировать.

На трех картинках ниже: 500 циклов, 1000 циклов и 3569 циклов эволюции:

tplflxzg6cponh7fjewngrwhebe.pngly1zot9rf_vhbrv6ujdkct1zp8k.pnglals9jymlk3cqao-a-fb2maowo0.png

Генофонд (3569):
5mmx5d8cotsginaowdl7hoxvwhm.png

В динамике:
ospmcuhhumc8dzxjrfvvpqla2yg.gif

На картинке ниже можно посмотреть, как формируется осциллятор (глайдер) в этом автомате:

e1jx7g0arqsdaupwstccpaikbc4.png

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

b4ik9wtoqpky1d7twc3qalsipum.png

Мутации в отмеченных генах не приживаются из-за того, что нарушают формирование паттерна.

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

Запускаем 3569 циклов эволюции. График:

7vzhk6d8mb50exyrhgzffgf7yvo.png

На графике черные точки — средний коэффициент приспособленности в популяции. Белые точки — средний коэффициент приспособленности предыдущего автомата. Найдено решение с одной ошибкой в паттерне.

Генофонд:
dak6ykszm5b1ok9szsw6e0uvnoy.png

100 первых итераций:
yd1yhldvb_-cbdpvjcfnurzzhd8.gif

Последняя (100) итерация:
jgbs5zhz9-zn4bgq6bnnvmvptqc.png

Немного не тот результат, которого мы ожидали. Черные квадраты есть, белых — нет. Ужесточим второй критерий: разница между количеством белых и черных клеток не превышает 100.

Запускаем 14865 циклов эволюции.
На графике сравнение средних коэффициентов приспособленности популяций. Синие точки — наш автомат. Белые и черные — предыдущие автоматы.

xz1erye8esobqdijoiqngzr-lno.png

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

yzrk_etzkyf2beizgjkpjy6gq7a.png

У лучшей особи в среднем 6 клеток соответствуют заданному критерию.

Посмотрим на случайный автомат из популяции.
50 итераций:

c-zzroku4lilkwnx5jmzjigjy0o.gif

Последняя (50) итерация:

luc26a8o1yxtegeixdf-xhssr7o.png

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

Паттерн:

coxhneqvql2fnobzzyuqbpf4_iq.png

Запускаем. 3000 циклов эволюции. График:

eq7cnfjw6tbjwafwujr4zatuhgw.png

Генофонд:

y1vnsamfa1fnq6x5njs4txfjd-i.png

В динамике (100 итераций):

prb7dcvmmuvtlzi2lrbqsej5toc.gif

Последняя (100) итерация:

wmsd5mijf0h5jqym_7s4rmbi5tc.png

Паттерн:

y0pznfk0fqlf9d7awtxxyqccgs4.png

В предыдущих автоматах мы разрешили сделать одну ошибку в паттерне. На этот раз поищем точный паттерн.

Запускаем 4549 циклов эволюции. График:

_6-g5bzhontoftgja3hh3qwgdae.png

Белая вертикальная линия — 2500 циклов эволюции. В этот момент (немного ранее) приспособленность популяции начала быстро расти. Сохранил популяцию, чтобы посмотреть на промежуточное решение. Промежуточное решение оказалось гораздо интересней решения на 4549-ом цикле эволюции.

Решение, найденное на 4549-ом цикле эволюции:

_men0syi_moqn4ksgajtccvlosg.gif

На Gif 100 итераций. Еще после некоторого числа итераций (около 500–2000) состояние автомата практически полностью упорядочено (высота и ширина автомата специально выбраны нечетными числами, чтобы автомат не мог упорядочиться полностью):

2hjy2mcrp8bbmzc_wswkbtehsre.gif

Автомат с четными размерами сторон, после некоторого числа итераций принимает полностью упорядоченное состояние. Автомат 90×90, примерно 1200 итераций:

boh3z62vvtnzzsvlcifaw5f5b90.png

Промежуточное решение (найденное на 2500-ом цикле эволюции):

a3809od0icghlwlrhujkw2ekypk.gif

Данный автомат тоже умеет перерабатывать некоторое начальное хаотическое состояние в некоторое конечное упорядоченное (конечное упорядоченное состояние — смещение паттерна по оси Х влево + несколько клеток-осцилляторов).

Автомат 16×16 упорядочился примерно за 100 итераций:

69rwy6wauq04r-yacyevum52uqm.png

32×32 — около 1000 итераций:

ekrqk4rulygeihgrh0cyfgff6lk.png

64×64 — около 6000 итераций:

ovtehqk-cdy33p1wml9trl4zto4.png

90×90 — около 370000 итераций:

4vvkv9lrk8-2hz7pgaxasnrgslw.png

11×11 (нечетные размеры поля автомата) — около 178700 итераций:

exzz7_nr3ajz-or28n5agoh9ehi.png

Автомат 13×13 не упорядочился за приемлемое время.

На картинке ниже, автомат на поле 256×256 на 100000-й итерации:

pgtxcxfch1sorfcdz8nkknhebxs.png

Рекомендую посмотреть на этот автомат в динамике на большом поле — очень интересно наблюдать за процессом самоорганизации хаоса в этом автомате: запустить в браузере

Генофонд промежуточной популяции:

ebznpes_byulwy6_gm1wwxpiqsa.png

Повторный запуск эволюционного процесса позволяет найти другие решения. Одно из них:

czsev_m2jj3kf3rbsqtvojnh6vs.gif

skyrrtshzmwzm4dlwcvlfgpt9x0.png

Еще один паттерн:

flqwbcg8qmnl80sybmdejrfeoj0.png

При поиске паттерна опять позволим сделать одну ошибку (без ошибок система с выбранным паттерном не эволюционирует).

Запускаем. 5788 циклов эволюции. График:

sclpsl7fscxrixrrh0bflj5xkvg.png

Масштаб произвольный.

Генофонд:

urwykoe4gasz-fqbx2ezxyyiuh8.png

В динамике:

x9dbg6266lmlrushsm8rqz2kkyo.gif

Упорядоченное состояние автомата (смещение паттерна вверх по оси Y + несколько клеток-осцилляторов):

to6p1t62megmpe3iqnqvhayuree.png

Гораздо интересней наблюдать не за самим автоматом, а за мутантами, появляющимися в этой популяции:

nytap-ea9dtbc5avwgyukcejn7u.gif

На Gif автомат 256×256. 200 итераций. Остальные итерации можно посмотреть в браузере.

На этом можно было бы закончить с естественным отбором и перейти к искусственному, но хочется показать, насколько $2^{512}$ огромное число. Среди этого числа автоматов мы можем отыскать автомат рисующий любой заданный паттерн (с некоторой точностью для более сложных паттернов).

Следующий паттерн:

jmrnwakxaoqoiog1sjc_ttocytw.png

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

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

jgbs5zhz9-zn4bgq6bnnvmvptqc.png

Для искомого паттерна, на 100-й итерации каждого автомата в популяции, в окружении каждой клетки будем считать количество клеток совпадающих с паттерном. Будем брать только наилучший результат для каждого автомата. Количество клеток, совпавших с паттерном, будем использовать в качестве коэффициента приспособленности. Паттерн состоит из 7×17=119 клеток. Это число будем считать оптимальным решением. 6000 циклов эволюции позволили найти автомат, рисующий паттерн с 5-ю ошибками (114 клеток совпадают с паттерном).

График в произвольном масштабе:

uokw0l-rb2rh2xyirkqph-dcjts.png

Повышение процента мутаций не ухудшили приспособленность популяции.

В генофонде популяции много мутантов:

42grzykpownjx5qz1qzqcaobzt0.png

Случайный автомат из популяции в динамике:

pdld-5hgkfvzcutjdpxycmohpj0.gif

Лучший автомат на 100-й итерации:

-klat3ootrcxedxkotldsfgi9by.png

Искомый и найденный паттерны:

h-o844shmcturqxhtpx663f0crk.png

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

Генофонд:

z6awhsj_bnvvyhpllou1e-twagi.png

Автомат на 100-й итерации:

8xhmrrccu6ytk1rlw-iowt4z7qk.png

Искомый и найденный паттерны:

ngo1y_vkietoux0rdvad7nysdbw.png

2 ошибки
В процессе написания статьи, система продолжала эволюционировать. Для более точного поиска, размеры поля автомата увеличены до 513×513. Найден автомат, делающий всего две ошибки в паттерне:

8vplb4yhlzktfukk6lxvwuwcd6e.png

На четырех графиках можно увидеть, как эволюционирует система с разными вероятностями мутаций (мутирует 1 ген):

ukqd4-v35vnwsjhqs_4dthnptse.png

Красные точки — средний коэффициент приспособленности в популяции. Черные точки — коэффициент приспособленности каждой особи. По 3000 циклов эволюции для каждой системы.

Генофонды популяций (в том же порядке):

gv4pwk99scxocee7pmiqlod2aeg.png

phjjblpjvuem7-68zxeyjn7spk8.png

ebrtsfx1vh9luuvrisu_qnn0lxw.png

k9ddyzgvqklsyt8dnbafp97ng4s.png

Автоматы на 100-й итерации:

wbx1r_jby9kmdnw6a1k_pupfz0k.png

hvnvgcxnaqykuk1akooog357j1y.png

see6aftzjfoirsezpno9ln3yxam.png

m5vszgpk0gvzuq2lcxgmd0izvjq.png

Проведем еще один эксперимент. Паттерн тот же. Начальные генотипы заполнены случайными генами. Вероятность мутаций — 5%. От 1-го до 8-ми генов мутируют (для каждой особи берется случайное число мутирующих генов). 100 циклов эволюции.

fuushovxp2ejlt1dwc4yoxkhhw0.png

График представляет из себя тепловую карту. Размер точки на графике — 5 пикселей. Начало координат — верхний левый угол.
По оси Y (от 0 до 100) — циклы эволюции. По оси X (от 0 до 119) — количество клеток совпадающих с паттерном (для каждой особи в популяции берем наилучший результат). Яркость точки — количество особей с указанным (координата X) результатом.

Запустим 4 раза генетический алгоритм с теми же параметрами (100 циклов, 5% мутаций, до 8-ми генов мутируют). На графике все 5 запусков:

wqfu5gdry7sumwrmme-zczjba10.png

Следующие 5 запусков: 25% мутаций, до 8-ми генов мутируют:

xsfjrgjfxmoadtby-lrxmsh4s_e.png

Выборка небольшая, но можно сделать выводы об эффективности повышения процента мутаций.

Далее покажу неэффективность используемого в статье способа скрещиваний.

Используемый ранее способ:

ruzzby4r6tjcazvtcqybydxpcea.png

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

9aykn-x8hdvkxdqmzkm3g94_5m4.png

5% мутаций:

oh-fupi3cfvod_9q0dh4mxf6xfc.png

25%:

zwnepkc953ihkx3kf-dikmxe70y.png

Далее будем использовать этот способ скрещиваний.

На этом с естественным отбором закончим. Если у кого-то есть интересные идеи о критериях для естественного отбора — прошу озвучить их в комментариях.

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

Second-order cellular automaton

Рассмотрим нульмерный клеточный автомат первого порядка (все клеточные автоматы, которые мы рассматривали выше — первого порядка). Нульмерный клеточный автомат состоит из одной клетки. Клетка может находиться в одном из двух состояний. Следующее состояние клетки (t) определяется текущим состоянием клетки (t-1). Всего существует 4 нульмерных клеточных автомата (среди них один осциллятор):

fb5g2jggwskqxjfpmyxhswxan8q.png

В клеточном автомате второго порядка, следующее состояние клетки (t) определяется текущим состоянием (t-1) и предыдущим состоянием клетки (t-2). Всего существует 4 комбинации двух состояний клетки. $2^{4}=16$ — количество нульмерных клеточных автоматов второго порядка:

zqf5e28zisbiieqs9xcontthxxk.png

Такие клеточные автоматы демонстрируют более сложные осцилляторы.

$2^{8}=256$ клеточных автоматов третьего порядка:

xzgfztxpzog3ddibpjc0xqaua9g.png

$2^{16}=65536$ клеточных автоматов четвертого порядка одной картинкой показать не получится.

Поиск клеточного автомата $n$-го порядка с периодом осцилляции равным $n$ — задача нетривиальная и крайне интересная. Эта тема заслуживает отдельной статьи.

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

f-jvpve0dmvbwtqcklrvxwfieau.png

Существует $2^{16}=65536$ одномерных клеточных автоматов второго порядка.

Код:

Одномерный клеточный автомат второго порядка
var rule=[];
for(var i=0;i<16;i++) rule[i]=Math.round(Math.random());

var a=[];
var b=[];
var temp;
for(var x=0;x=sizex) xp=xp-sizex;

		q=b[xm];
		q=(q<<1)+b[x];
		q=(q<<1)+b[xp];
		q=(q<<1)+a[x];

		temp[x]=rule[q];
		if(temp[x]) context.fillRect(x*size, y*size, size, size);
	}
	a=b;
	b=temp;
}

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

На картинках ниже, несколько случайных автоматов второго порядка (в левой части картинки — в состоянии t-1 заполнена одна клетка, в правой — для случайных состояний t-1 и t-2, двоичный код — содержимое массива rule):

0011111011001000:
c2ntcpu3kuk88-alpctfnejjg7y.png

0101101110011110:
ccnbo3lnp3d5adwd2jnkuisth88.png

0110000110010010:
_nk4cekco3km6mgeafrkd640bne.png

0110011010010110:
lhko49gakm6bhxfuaw4dbobcn8i.png

1110011010010110:
9u23yn2pjoidf9o3g2foaycjdgu.png

0110111010000101:
vf9z-wkb6neof2bxqmhysriayle.png

1111101001110110:
duhesd1yyqxntanr6dalsfsuscs.png

1001010001100000:
t90ibwzmawvostbxordrn9rjm7u.png

Этот же автомат 256×256:

hftzcuggetbc2e72105hjqurvui.png

512×512

k4set-mwi-cord3oj2cnbtcfphw.png

Остальные автоматы можно посмотреть здесь:
Одномерный клеточный автомат второго порядка.
Одномерный клеточный автомат третьего порядка.

Об одномерных клеточных автоматах второго порядка можно почитать в книге Вольфрама «A New Kind of Science».

Искусственный отбор

Подобно одномерному клеточному автомату второго порядка, в двухмерном клеточном автомате второго порядка будем использовать дополнительную клетку из предыдущего (t-2) состояния автомата.

Для удобства эту клетку разместим в начале двоичной строки:

gn0jdrks6wp2pmanchqjdkesrdo.png

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

_zhevkuac_p5feuvgvwkxs9owzg.png

Добавив одну клетку, мы увеличили количество существующих автоматов в $2^{512}$ раз.
$2^{512} \times 2^{512} = 2^{1024}$ — количество существующих двухмерных автоматов второго порядка.

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

Данный принцип не позволяет выбирать лучший автомат среди случайных автоматов:

3mdipyvfxy88aoggq-yepu2vhle.giffyjq15um17equltw8zaal0-gfm8.pngysxfshnxyn1ikzzkjxd677-4dmm.gif

fmpqjgvu95p417fua0n5qtajmbg.giffyjq15um17equltw8zaal0-gfm8.pngysxfshnxyn1ikzzkjxd677-4dmm.gif

Существует несколько способов решить эту проблему. Предлагаю рассмотреть четыре способа.

1. В начальном состоянии автомата заполнена одна клетка

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

Заполняем начальную популяцию случайными автоматами. Несколько автоматов из начальной популяции (30 итераций для каждого):

snx8bu_us4atuqbxtkumxzsc7g8.giffyjq15um17equltw8zaal0-gfm8.png0oglwb2sqyo8wz2unx8qcrdphgw.gif

Эти два мигают

В популяции присутствует небольшое число автоматов, демонстрирующих менее хаотичное поведение. Их будем отбирать для скрещивания:

5chlssiotqq_-fjdbvvstjdzqp8.giffyjq15um17equltw8zaal0-gfm8.pngvguo3jenfkez3rgmc3vvgluuai8.gif

tegm8tspjof3ti3gj4rneed0je0.giffyjq15um17equltw8zaal0-gfm8.pngklxv5bdctxqun4wqspcmo6e3ikc.gif

20 случайных автоматов из начальной популяции (состояние автоматов на 30-й итерации):

qa7pfg5nmeqxnor0yosu6bt0xza.png

После трех циклов эволюции:

l0zbhmiagwg4iqfonncvgxe5ses.png

После восьми циклов эволюции:

qmxiam8p_ovsaz--aleaseoi3uq.png

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

2. Генотип заполнен частично

Если нарушить соотношение единиц и нулей в генотипе — нарушится соотношение единиц и нулей в фенотипе.

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

Построим график.

Создадим популяцию из 200 автоматов. Генотипы заполняем нулями (1024 гена в генотипе двухмерного автомата второго порядка). Далее $n$ генов заполняем единицами. Для первой популяции $n=0$, для 513-й популяции $n=512$. По оси $x$ — номер популяции. По оси $y$ отмечаем (белыми точками) соотношение единиц и нулей в г

© Habrahabr.ru