Хабрахабр

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

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

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

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

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

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

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

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

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

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

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

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

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

Число:

340781\times10^{154}$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/223/157/423/2231574233716084a0829c3348646cf8.svg" alt="$2^{512}\approx1.

Если бы мы каждую секунду просматривали по одному автомату — за время существования Вселенной мы бы успели просмотреть всего <img src="https://habrastorage.org/getpro/habr/formulas/c22/97a/b49/c2297ab49d0df747dff864871b36f6cc.svg" alt="$\approx4. больше количества атомов в наблюдаемой Вселенной ($10^{80}$).
Вручную такое количество автоматов не перебрать. 35\times10^{17}$" data-tex="inline"/> автоматов.

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

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

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

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

Заполняем массив rule

var rulesize=512;
var rule=[];
for(var i=0;i<rulesize;i++) rule[i]=Math.round(Math.random());

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

Заполняем начальное состояние автомата

var sizex=89;
var sizey=89;
var size=2;
var a=[];
for(var x=0;x<sizex;x++){ a[x]=[] for(var y=0;y<sizey;y++){ a[x][y]=Math.round(Math.random()); if(a[x][y]) context.fillRect(x*size, y*size, 1*size, 1*size); }
}

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

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

Считаем следующее состояние автомата

function countpoints(){ var temp=[]; var xm, xp, ym, yp, q; for(var x=0;x<sizex;x++){ xm=x-1; if(xm==-1) xm=sizex-1; xp=x+1; if(xp==sizex) xp=0; temp[x]=[]; for(var y=0;y<sizey;y++){ ym=y-1; if(ym==-1) ym=sizey-1; yp=y+1; if(yp==sizey) yp=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]; if(temp[x][y]) context.fillRect(x*size, y*size, 1*size, 1*size); } } a=temp;
}

Переменные 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 раз запустить автомат с случайными правилами, прежде чем продолжить чтение статьи.

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

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

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

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

Создаем популяцию

var PopulationSize=200;
var rulesize=512;
var population=[];
var fitness=[];
for(var n=0;n<PopulationSize;n++){ population[n]=[]; fitness[n]=0; for(var i=0;i<rulesize;i++){ population[n][i]=Math.round(Math.random()); }
}

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

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

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

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

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

Функция evolute();

function evolute(){ var sizehalf=PopulationSize/2; var sizequarter=sizehalf/2; var arrayt=[]; for(var n=0; n<PopulationSize; n++) arrayt[n]=[population[n], fitness[n]]; arrayt.sort(sortf); arrayt.length=sizehalf; population=[]; fitness=[]; for(var i=0; i<sizequarter; i++){ var i0=i*4; var i1=i*4+1; var i2=i*4+2; var i3=i*4+3; var removed1=Math.floor(Math.random()*(arrayt.length)); var parent1f = arrayt.splice(removed1,1); var parent1=parent1f[0][0]; var removed2=Math.floor(Math.random()*(arrayt.length)); var parent2f = arrayt.splice(removed2,1); var parent2=parent2f[0][0]; var child1=[]; var child2=[]; var qen=Math.floor(Math.random()*rulesize); var temp0=parent1; var temp1=parent2; var temp2=temp0.splice(qen,rulesize); var temp3=temp1.splice(qen,rulesize); var parent1=temp0.concat(temp2); var parent2=temp1.concat(temp3); var child1=temp1.concat(temp2); var child2=temp0.concat(temp3); population[i0]=parent1; population[i1]=parent2; population[i2]=child1; population[i3]=child2; fitness[i0]=0; fitness[i1]=0; fitness[i2]=0; fitness[i3]=0; } var mutation=document.getElementById("mutatepercent").value*1; var m=100/mutation; var m2=0;//0 for(var i=0; i<PopulationSize; i++){ var rnd=Math.floor(Math.random()*(m))+1; if(rnd==1){ var rnd2=Math.floor(Math.random()*(m2))+1; for(var j=0;j<rnd2;j++){ var gen=Math.floor(Math.random()*(rulesize)); if(population[i][gen]) population[i][gen]=0; else population[i][gen]=1; } } }
}

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

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

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

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

Считаем

function countfitness(array1, array2){ var sum=0; var a0=0; var a1=0; for(var x=0;x<sizex;x++){ for(var y=0;y<sizey;y++){ if(array1[x][y]==array2[x][y]) sum++; if(array1[x][y]==0){ a0++; }else{ a1++; } } } if(Math.abs(a0-a1)<100) return sum; return 0;
}

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

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

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

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

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

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

Изменим критерии отбора.

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

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

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

Поэтому немного смягчим критерий: Ни одна клетка в таком автомате не соответствует заданному критерию.

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

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

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

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

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

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

Генофонд (3569):

В динамике:

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

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

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

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

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

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

Генофонд:

100 первых итераций:

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

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

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

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

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

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

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

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

Паттерн:

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

Генофонд:

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

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

Паттерн:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Генофонд:

В динамике:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Генофонд:

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

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

2 ошибки

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

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

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

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

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

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

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

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

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

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

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

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

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

5% мутаций:

25%:

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

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

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

Second-order cellular automaton

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

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

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

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

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

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

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

Существует $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;x++){ a[x]=0; b[x]=0;
}
b[63]=1; var xm, xp, q;
for(var y=2;y<sizey;y++){ temp=[]; for(var x=0;x<sizex;x++){ xm=x-1; if(xm<0) xm=sizex+xm; xp=x+1; if(xp>=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:

0101101110011110:

0110000110010010:

0110011010010110:

1110011010010110:

0110111010000101:

1111101001110110:

1001010001100000:

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

512х512

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На 100-й итерации считаем количество единиц и нулей в состоянии (фенотипе) каждого автомата. Для каждого автомата (с размерами поля 89х89) считаем 100 итераций. Получили кривую: Отмечаем на графике соотношение единиц и нулей (суммарное количество всех единиц делим на суммарное количество всех нулей).

Вместо суммарного соотношения единиц и нулей во всех фенотипах, можно посмотреть на соотношение единиц и нулей в каждом фенотипе:

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

Сравним с автоматами, в которых нулевой ген всегда равен единице:

Посмотрим, как этот ген влияет на фенотип. В автоматах второго порядка есть еще один «нулевой» ген — 512-й.

0-й и 512-й ген всегда равны нулю:

512-й ген всегда равен единице: 0-й ген всегда равен нулю.

Чтобы лишний раз не издеваться над нашими многоуважаемыми эпилептиками, 0-й и 512-й ген будем заполнять нулями в начальной популяции генетического алгоритма.

Посмотрим на автоматы, от которых мы избавились, установив нули в 0-й и 512-й гены.

Первые 8 состояний автомата, в котором заполнен только 0-й ген (нулевой ген равен единице, остальные — нули):

Автомат, в котором заполнен только 512-й ген:

Автомат, в котором заполнены только 0-й и 512-й гены:

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

В этом месте генотипы заполнены на 25%.

Сравним две популяции.

30 случайных автоматов на 1000-й итерации. Первая популяция. Генотипы заполнены на 50% (512 единиц и 512 нулей):

30 случайных автоматов на 1000-й итерации. Вторая популяция. Генотипы заполнены на 25% (256 единиц и 768 нулей):

Мы можем легко выделить некоторые признаки в таких автоматах. Вторая популяция пригодна для искусственного отбора. Например: «более темные», «менее хаотичные» (автоматы, в которых белые клетки группируются) и т.д.

Вероятность мутаций — 10%, до 4-х генов мутируют. Отбираем «более темные». После первого отбора:

После второго отбора:

В популяции появился интересный автомат.

256х256, состояние автомата на 1000-й итераций:

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

После восьмого отбора:

Появился еще один интересный автомат.

256х256, состояние автомата на 1000-й итераций:

Популяция после тринадцати отборов:

256х256, 1000-я итерация для каждого. Несколько автоматов из этой популяции. Под картинкой ссылка, перейдя по которой, можно посмотреть на автомат в динамике:


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.

3. Автомат Конвея и ему подобные

Самый известный двухмерный клеточный автомат первого порядка — автомат Конвея Игра «Жизнь».

Правила для автомата Конвея записываются следующим образом:
Если вокруг мертвой клетки 3 живые клетки — клетка оживает (в противном случае остается мертвой).
Если вокруг живой клетки 2 или 3 живые клетки — клетка остается живой (в противном случае умирает).
Мертвая клетка — 0, живая клетка — 1.

По 9 вариантов вокруг живой и вокруг мертвой клетки. Вокруг клетки может быть от 0 до 8 живых клеток. Запишем все варианты в массив r:

массив r

r=[ 0,0,0,1,0,0,0,0,0, 0,0,1,1,0,0,0,0,0
];

Первая половина массива — для мертвой клетки, вторая — для живой.

Можем расписать правило автомата Конвея для всех возможных (512-ти) комбинаций клетки и 8-ми соседних клеток:

Расписываем правило

r=[ 0,0,0,1,0,0,0,0,0, 0,0,1,1,0,0,0,0,0
];
var rule=[];
var q1, q2;
for(var i=0;i<512;i++){ var ii=i.toString(2); for(var j=ii.length;j<9;j++) ii='0'+ii; q1=1*ii[4]; q2=1*ii[0]+1*ii[1]+1*ii[2]+1*ii[3]+1*ii[5]+1*ii[6]+1*ii[7]+1*ii[8]; if(q1==0) rule[i]=r[q2]; else rule[i]=r[q2+9];
}

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

r=[ 0,0,0,1,0,0,0,0,0, 0,0,1,1,0,0,0,0,0
];
var rule=[];
for(var i=0;i<512;i++){ var q=((i>>4)&1)*8; for(var j=0;j<9;j++){ q+=(i>>j)&1; } rule[i]=r[q];
}

Для автомата второго порядка, вторую половину массива rule копируем из первой:

Копируем

for(var i=0;i<512;i++){ if(rule[i]==0) rule[i+512]=0; else rule[i+512]=1;
}

Видим характерные глайдеры и осцилляторы. Запускаем автомат с указанным правилом. Несколько итераций этого автомата:

Существует $2^{18}=262144$ автоматов подобных автомату Конвея (которые можно записать теми же правилами: количество живых клеток в окружении мертвой, при которых клетка оживает и количество живых клеток в окружении живой, при которых клетка умирает).
Посмотреть на них можно здесь (по умолчанию запускается автомат Конвея, кнопка «Change rule» заполняет массив r случайным образом). Массив r состоит из 18 ячеек.

Несколько случайных автоматов (двоичный код — массив r):

110010011001111111

100001100110111110

011111000100101110

010000110000110010

001111010011100111

000111001000000110

000101100010100001

000001111101011111

000001100110111111

Для генетического алгоритма, в качестве генотипа, можно использовать, как массив r ($2^{18}$ комбинаций), так и массив rule ($2^{512}$ комбинаций для клеточного автомата первого порядка и $2^{1024}$ — для клеточного автомата второго порядка).

Это число позволяет подобрать правило для автомата вручную, без использования генетического алгоритма (собственно, что и сделал Конвей). $2^{18}$ — сравнительно небольшое число.

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

... и для этих

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

Можно увидеть проявление этой симметрии в фенотипе, если в начальном состоянии автомата заполнить одну клетку.

Чтобы сохранить симметрию, в качестве генотипа будем использовать массив r. Проведем эксперимент. В начальном состоянии заполнена одна клетка. 5% мутаций, мутирует 1 ген.

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

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





После первого отбора избавились от автоматов, которые не развиваются:

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

Далее отбирать будем преимущественно автоматы с белым фоном (клетки, до которых автомат не развился).

Черные автоматы мигают.

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

Популяция после второго отбора:

3 отбора:

5 отборов:

8 отборов:

13 отборов:

Те же автоматы на 60-й итерации:

Состояние автоматов на 30-й итерации: 21 отбор.

Состояние автоматов на 60-й итерации:

Состояние автоматов на 30-й итерации: 34 отбора.

Состояние автоматов на 60-й итерации:

Три автомата из этой популяции (по 100 итераций): Далее система не эволюционирует.

[1,0,1,1,1,0,0,1,0,0,1,1,0,1,0,1,1,1]

[1,0,1,1,1,0,0,1,0,0,0,1,0,1,0,1,1,1]

[1,0,0,1,1,0,0,1,1,0,1,0,1,1,0,1,1,1]

Для сравнения случайный автомат:

[1,0,0,1,1,1,0,1,1,1,0,0,1,1,0,0,0,1]

4. Автомат Конвея и ему подобные (2)

Эту окрестность можно разбить на 4 пары и считать количество живых клеток в этих парах: В автоматах с правилами Конвеевского типа, мы считаем количество живых (единиц) клеток в окрестности Мура.

Таким образом, мы увеличиваем число автоматов, но сохраняем симметрию в фенотипе.

Пар 4. В каждой паре может быть от 0 до 2-х живых клеток. По 81-й комбинации вокруг живой и вокруг мертвой клетки. Количество комбинаций $3^4=81$. Всего существует $2^{162}$ автоматов этого типа.

Число:

846\times10^{48}$" data-tex="display"/> <img src="https://habrastorage.org/getpro/habr/formulas/af7/b15/676/af7b156766dd50df4e058a7d0bfb38ad.svg" alt="$2^{162}\approx5.

Вполне астрономическое и сгодится для генетического алгоритма.

Размер генотипа каждой особи — 162 гена:

Заполняем популяцию случайными автоматами

var rulesize=162;
for(var n=0;n<PopulationSize;n++){ population[n]=[]; fitness[n]=0; for(var i=0;i<rulesize;i++){ population[n][i]=Math.round(Math.random()); }
}

Далее расписываем это правило для всех возможных комбинаций клетки и восьми соседних клеток:

Функция fillrule();

function fillrule(){ var r; for(var n=0;n<PopulationSize;n++){ rule[n]=[]; r=population[n]; var q1, q2, q3, q4, q5; var q; for(var i=0;i<512;i++){ var ii=i.toString(2); for(var j=ii.length;j<9;j++) ii='0'+ii; q1=1*ii[4]; q2=1*ii[0]+1*ii[8]; q3=1*ii[1]+1*ii[7]; q4=1*ii[2]+1*ii[6]; q5=1*ii[3]+1*ii[5]; q=parseInt(''+q2+q3+q4+q5,3); if(q1==0) rule[n][i]=r[q]; else rule[n][i]=r[q+81]; } }
}

Массив rule будем использовать при вычислении следующего состояния автомата. Функцию fillrule() вызываем после загрузки страницы и после вызова функции evolute().

30 случайных автоматов, 1000-я итерация: Начальная популяция выглядит хаотично.

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

Популяция после пяти отборов:

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

Под картинкой ссылка, перейдя по которой, можно посмотреть на автомат в динамике: 256х256, 10000-я итерация для каждого.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.


Посмотреть в динамике.

А поиграться?

А поиграться можно здесь:

Двухмерные клеточные автоматы второго порядка.

Интерфейс:

Если надо быстро посчитать 200 итераций — жмем Count 200. Кнопка Start запускает автоматы.
Stop — останавливает.
One — одна итерация.
Clear — останавливает автомат и заполняет начальное состояние рандомом.
Clear (1 cell) — останавливает автомат и заполняет одну клетку в начальном состоянии.
Остальные кнопки в этой строке считают указанное количество итераций для каждого автомата.
Отрисовка автомата на холсте (canvas) съедает все быстродействие. Кнопку Count 5000 не жмем — может подвесить браузер.

Под автоматами чекбоксы. Ниже 20 случайных автоматов (размер популяции — 200 автоматов). Нажимаем Select — приспособленность (fitness) автомата увеличится на указанное справа число.
Mutations — вероятность мутаций.
Gens — число мутирующих генов. Отмечаем самые интересные.

Start evolution — запускает механизм скрещиваний и мутаций.

Fill genotype — заполняет указанное число генов в генотипе каждого автомата.
Conway — заполняет популяцию автоматами Конвеевского типа.

Ниже две строки:
Номера показанных автоматов.
Содержимое массива fenotype.

Генофонд популяции еще ниже.

Весь прогресс сохраняется в локальном хранилище (Local Storage).

С автоматами Конвеевского типа (с теми, которые рассмотрены в статье последними) можно поиграться здесь:

Автомат Конвея и ему подобные (2). 4.

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»