Соединим клеточные автоматы с генетическим алгоритмом и посмотрим, что из этого получится.
В статье присутствуют Gif (трафик!) и контрастные картинки. У эпилептиков может случиться эпилептический припадок.
Правила для клеточных автоматов
Самый простой клеточный автомат — одномерный клеточный автомат (существуют также нульмерные — о них поговорим ниже). В одномерном клеточном автомате у нас есть одномерный массив, ячейки которого (клетки) могут принимать одно из двух состояний (1/0, true/false, белая/черная, живая/мертвая). Следующее состояние клетки в массиве определяется текущим состоянием клетки и состоянием двух соседних клеток, по некоторому правилу.
Всего существует комбинаций состояний клетки и двух соседних клеток:
Далее для каждой из комбинаций запишем состояние клетки для следующей итерации (для следующего состояния автомата):
Получили правило для клеточного автомата. Правила для одномерных клеточных автоматов кодируются 8 битами («код Вольфрама»). Всего существует элементарных клеточных автоматов:
256 автоматов можно перебрать вручную. Не будем на них останавливаться. Посчитаем количество существующих правил для двухмерных клеточных автоматов.
В двухмерном клеточном автомате используется двухмерный массив. У каждой клетки есть 8 соседей в окрестности Мура (существует также окрестность фон Неймана, в которой не учитываются диагональные клетки. Ее в статье не рассматриваем):
Для удобства запишем клетки в строку (выбранный порядок будем использовать далее в статье):
Для двухмерного клеточного автомата существует комбинаций состояний клетки и 8-ми соседних клеток:
Правило для двухмерного клеточного автомата кодируется 512 битами. Всего существует двухмерных клеточных автоматов:
Число:
больше количества атомов в наблюдаемой Вселенной ().
Вручную такое количество автоматов не перебрать. Если бы мы каждую секунду просматривали по одному автомату — за время существования Вселенной мы бы успели просмотреть всего автоматов.
Простой перебор не работает, но с помощью генетического алгоритма мы можем найти автоматы, которые наилучшим образом соответствуют некоторым заранее заданным критериям.
Программировать будем на 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];После всех итераций заменяем предыдущее состояние автомата новым:
заменяем предыдущее состояние новым
a=temp;Автомат рисуем с помощью функции 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 (число взято «от балды»).
array1 — состояние автомата на 99-й итерации. array2 — на 100-й итерации:
Считаем
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-ом цикле эволюции. На графике можно посмотреть прогресс:
График масштабирован по оси Y. Нижняя точка — 0, верхняя точка — 7921. Очевидно, что 7921 — оптимальное решение (все клетки в автомате 89х89 соответствуют заданному критерию). После 100 итераций ни одна клетка не изменяет своего состояния.
Синие точки на графике — лучшая особь в популяции. Красные — худшая (учитываются только те особи, которые соответствуют второму критерию). Черные точки — средний коэффициент приспособленности для всей популяции (с учетом особей, не соответствующих второму критерию). Второй критерий (баланс между белыми и черными) очень жесткий. Некоторые автоматы не соответствуют второму критерию даже после 421 цикла эволюции. Поэтому черные точки ниже красных.
Генофонд популяции (по оси Y — особи, по оси X — гены):
Посмотрим, какой канал словил наш «телевизор»:
Найденное решение не является единственным оптимальным. Если повторно запустить эволюцию (с случайными начальными генотипами) — найдем другие оптимальные решения. Одно из них:
Изменим критерии отбора.
Будем считать количество клеток, для которых в окрестности Мура порядка 2 появляется некоторый паттерн. Паттерн возьмем самый простой:
Этот критерий интересен тем, что мы проверяем 25 клеток, в то время, как автомат вычисляет состояние клетки исходя из состояний 9 клеток.
Критерий очень жесткий. Если взять случайный автомат, после 100 итераций он выглядит так:
Ни одна клетка в таком автомате не соответствует заданному критерию. Поэтому немного смягчим критерий:
- Разрешим сделать одну ошибку в паттерне.
- Паттерн будем искать не на последней итерации, а на последних 50 итерациях.
Второй критерий (баланс между белыми и черными) уберем.
Запускаем. График:
По оси Y масштаб произвольный. (В предыдущем автомате оптимальное решение — 7921. В этом автомате — около 30.)
По оси X — 3569 циклов эволюции. Двумя белыми вертикальными линиями отмечены 500 и 1000 циклов эволюции.
Синие точки — лучшая особь в популяции, красные — худшая, черные — средний коэффициент для всей популяции.
Решение найдено на первых 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-ом цикле эволюции:
На Gif 100 итераций. Еще после некоторого числа итераций (около 500-2000) состояние автомата практически полностью упорядочено (высота и ширина автомата специально выбраны нечетными числами, чтобы автомат не мог упорядочиться полностью):
Автомат с четными размерами сторон, после некоторого числа итераций принимает полностью упорядоченное состояние. Автомат 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 + несколько клеток-осцилляторов):
Гораздо интересней наблюдать не за самим автоматом, а за мутантами, появляющимися в этой популяции:
На Gif автомат 256х256. 200 итераций. Остальные итерации можно посмотреть в браузере.
На этом можно было бы закончить с естественным отбором и перейти к искусственному, но хочется показать, насколько огромное число. Среди этого числа автоматов мы можем отыскать автомат рисующий любой заданный паттерн (с некоторой точностью для более сложных паттернов).
Следующий паттерн:
В предыдущих экспериментах мы считали сумму клеток, вокруг которых формируется паттерн (если с одной ошибкой — к сумме прибавляли 1, если без ошибок — прибавляли 2). Полученную сумму использовали в качестве коэффициента приспособленности для генетического алгоритма.
Для более сложного паттерна такой способ не работает. Автомат, в котором меньшее число клеток более точно соответствует заданному критерию (количество клеток совпавших с паттерном в окрестности клетки), каждый раз будет проигрывать автомату, в котором большее число клеток менее точно соответствует заданному критерию. Как в примере с квадратами выше:
Для искомого паттерна, на 100-й итерации каждого автомата в популяции, в окружении каждой клетки будем считать количество клеток совпадающих с паттерном. Будем брать только наилучший результат для каждого автомата. Количество клеток, совпавших с паттерном, будем использовать в качестве коэффициента приспособленности. Паттерн состоит из 7х17=119 клеток. Это число будем считать оптимальным решением. 6000 циклов эволюции позволили найти автомат, рисующий паттерн с 5-ю ошибками (114 клеток совпадают с паттерном).
График в произвольном масштабе:
Повышение процента мутаций не ухудшили приспособленность популяции.
В генофонде популяции много мутантов:
Случайный автомат из популяции в динамике:
Лучший автомат на 100-й итерации:
Искомый и найденный паттерны:
Поигравшись с критериями отбора, размерами поля автомата и процентом мутаций, получилось улучшить популяцию и найти автомат, который делает всего 3 ошибке в паттерне.
Генофонд:
Автомат на 100-й итерации:
Искомый и найденный паттерны:
2 ошибки
В процессе написания статьи, система продолжала эволюционировать. Для более точного поиска, размеры поля автомата увеличены до 513х513. Найден автомат, делающий всего две ошибки в паттерне:
На четырех графиках можно увидеть, как эволюционирует система с разными вероятностями мутаций (мутирует 1 ген):
Красные точки — средний коэффициент приспособленности в популяции. Черные точки — коэффициент приспособленности каждой особи. По 3000 циклов эволюции для каждой системы.
Генофонды популяций (в том же порядке):
Автоматы на 100-й итерации:
Проведем еще один эксперимент. Паттерн тот же. Начальные генотипы заполнены случайными генами. Вероятность мутаций — 5%. От 1-го до 8-ми генов мутируют (для каждой особи берется случайное число мутирующих генов). 100 циклов эволюции.
График представляет из себя тепловую карту. Размер точки на графике — 5 пикселей. Начало координат — верхний левый угол.
По оси Y (от 0 до 100) — циклы эволюции. По оси X (от 0 до 119) — количество клеток совпадающих с паттерном (для каждой особи в популяции берем наилучший результат). Яркость точки — количество особей с указанным (координата X) результатом.
Запустим 4 раза генетический алгоритм с теми же параметрами (100 циклов, 5% мутаций, до 8-ми генов мутируют). На графике все 5 запусков:
Следующие 5 запусков: 25% мутаций, до 8-ми генов мутируют:
Выборка небольшая, но можно сделать выводы об эффективности повышения процента мутаций.
Далее покажу неэффективность используемого в статье способа скрещиваний.
Используемый ранее способ:
Вместо деления генотипа на две части, потомки будут наследовать случайные гены предков:
5% мутаций:
25%:
Далее будем использовать этот способ скрещиваний.
На этом с естественным отбором закончим. Если у кого-то есть интересные идеи о критериях для естественного отбора — прошу озвучить их в комментариях.
Для искусственного отбора будем использовать клеточные автоматы второго порядка.
Second-order cellular automaton
Рассмотрим нульмерный клеточный автомат первого порядка (все клеточные автоматы, которые мы рассматривали выше — первого порядка). Нульмерный клеточный автомат состоит из одной клетки. Клетка может находиться в одном из двух состояний. Следующее состояние клетки (t) определяется текущим состоянием клетки (t-1). Всего существует 4 нульмерных клеточных автомата (среди них один осциллятор):
В клеточном автомате второго порядка, следующее состояние клетки (t) определяется текущим состоянием (t-1) и предыдущим состоянием клетки (t-2). Всего существует 4 комбинации двух состояний клетки. — количество нульмерных клеточных автоматов второго порядка:
Такие клеточные автоматы демонстрируют более сложные осцилляторы.
клеточных автоматов третьего порядка:
клеточных автоматов четвертого порядка одной картинкой показать не получится.
Поиск клеточного автомата -го порядка с периодом осцилляции равным — задача нетривиальная и крайне интересная. Эта тема заслуживает отдельной статьи.
В одномерных клеточных автоматах второго порядка, следующее состояние клетки определяется текущим состоянием трех клеток и предыдущим состоянием одной клетки:
Существует одномерных клеточных автоматов второго порядка.
Код:
Одномерный клеточный автомат второго порядка
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) состояния автомата.
Для удобства эту клетку разместим в начале двоичной строки:
Удобство заключается в том, что при совпадении первой и второй половины генотипа, автомат можно рассматривать как автомат первого порядка:
Добавив одну клетку, мы увеличили количество существующих автоматов в раз.
— количество существующих двухмерных автоматов второго порядка.
Для естественного отбора мы определяли некоторый критерий и сравнивали автоматы по этому критерию. В процессе искусственного отбора, мы выбираем автоматы вручную, пользуясь некоторым невнятным принципом: «этот автомат интересный, а тот — не очень».
Данный принцип не позволяет выбирать лучший автомат среди случайных автоматов:
Существует несколько способов решить эту проблему. Предлагаю рассмотреть четыре способа.
1. В начальном состоянии автомата заполнена одна клетка
Один из способов — наблюдать за развитием клеточного автомата, в начальном состоянии которого заполнена одна клетка.
Заполняем начальную популяцию случайными автоматами. Несколько автоматов из начальной популяции (30 итераций для каждого):
Эти два мигают
В популяции присутствует небольшое число автоматов, демонстрирующих менее хаотичное поведение. Их будем отбирать для скрещивания:
20 случайных автоматов из начальной популяции (состояние автоматов на 30-й итерации):
После трех циклов эволюции:
После восьми циклов эволюции:
Восьми циклов эволюции хватило, чтобы заполнить всю популяцию автоматом с определенным признаком (автомат рисующий треугольники).
2. Генотип заполнен частично
Если нарушить соотношение единиц и нулей в генотипе — нарушится соотношение единиц и нулей в фенотипе.
В генотипе (правиле) автомата записаны следующие состояния клетки для всех возможных комбинаций клетки и соседних клеток. Если в генотипе больше нулей (или единиц) — в следующих состояниях автомата накапливаются нули (или единицы). Любопытно посмотреть на корреляционную зависимость между соотношением единиц и нулей в генотипе и соотношением единиц и нулей в фенотипе.
Построим график.
Создадим популяцию из 200 автоматов. Генотипы заполняем нулями (1024 гена в генотипе двухмерного автомата второго порядка). Далее генов заполняем единицами. Для первой популяции , для 513-й популяции . По оси — номер популяции. По оси отмечаем (белыми точками) соотношение единиц и нулей в генофонде популяции. Получили гиперболу:
Для каждого автомата (с размерами поля 89х89) считаем 100 итераций. На 100-й итерации считаем количество единиц и нулей в состоянии (фенотипе) каждого автомата. Отмечаем на графике соотношение единиц и нулей (суммарное количество всех единиц делим на суммарное количество всех нулей). Получили кривую:
Вместо суммарного соотношения единиц и нулей во всех фенотипах, можно посмотреть на соотношение единиц и нулей в каждом фенотипе:
В левой части графика есть точки с наибольшим отклонением от среднего значения. Можно предположить, что это те автоматы, в генотипах которых нулевой ген равен единице. Предположили — проверили. Устанавливаем нулевой ген всегда равным нулю. Рисуем новый график:
Сравним с автоматами, в которых нулевой ген всегда равен единице:
В автоматах второго порядка есть еще один «нулевой» ген — 512-й. Посмотрим, как этот ген влияет на фенотип.
0-й и 512-й ген всегда равны нулю:
0-й ген всегда равен нулю. 512-й ген всегда равен единице:
Чтобы лишний раз не издеваться над нашими многоуважаемыми эпилептиками, 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.
Вокруг клетки может быть от 0 до 8 живых клеток. По 9 вариантов вокруг живой и вокруг мертвой клетки. Запишем все варианты в массив 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;
}Запускаем автомат с указанным правилом. Видим характерные глайдеры и осцилляторы. Несколько итераций этого автомата:
Массив r состоит из 18 ячеек. Существует автоматов подобных автомату Конвея (которые можно записать теми же правилами: количество живых клеток в окружении мертвой, при которых клетка оживает и количество живых клеток в окружении живой, при которых клетка умирает).
Посмотреть на них можно здесь (по умолчанию запускается автомат Конвея, кнопка «Change rule» заполняет массив r случайным образом).
Несколько случайных автоматов (двоичный код — массив r):
110010011001111111
100001100110111110
011111000100101110
010000110000110010
001111010011100111
000111001000000110
000101100010100001
000001111101011111
000001100110111111
Для генетического алгоритма, в качестве генотипа, можно использовать, как массив r ( комбинаций), так и массив rule ( комбинаций для клеточного автомата первого порядка и — для клеточного автомата второго порядка).
— сравнительно небольшое число. Это число позволяет подобрать правило для автомата вручную, без использования генетического алгоритма (собственно, что и сделал Конвей).
Если же заполнить массив rule случайными автоматами этого типа и использовать этот массив в качестве генотипа — тогда эксперимент можно считать неудачным, в некоторой степени (в достаточной, чтобы не показывать в статье результаты этого эксперимента). В правилах клеточных автоматов этого типа присутствует симметрия. Например, для следующих комбинаций клеток:
... и для этих
состояние клетки на следующей итерации одинаковое. После первого скрещивания нарушается симметрия в правилах особей-потомков. Особи-предки накапливают мутации, которые тоже разрушают симметрию. Нарушение симметрии в генотипе вызывает нарушение симметрии в фенотипе.
Можно увидеть проявление этой симметрии в фенотипе, если в начальном состоянии автомата заполнить одну клетку.
Проведем эксперимент. Чтобы сохранить симметрию, в качестве генотипа будем использовать массив r. 5% мутаций, мутирует 1 ген. В начальном состоянии заполнена одна клетка.
30 случайных автоматов из начальной популяции. Состояние автоматов на 30-й итерации:
Попробуем выделить такие автоматы, которые наиболее медленно развиваются (разрастаются) из одной клетки.
После первого отбора избавились от автоматов, которые не развиваются:
В новой популяции присутствует несколько таких автоматов (которые не развиваются) — это неудачные потомки и мутанты.
Далее отбирать будем преимущественно автоматы с белым фоном (клетки, до которых автомат не развился).
Черные автоматы мигают.
Если нулевой ген равен нулю (если в окружении черной клетки все черные — клетка остается черной) — такие автоматы развиваются с одинаковой скоростью. Автоматы с этим геном (нулевой равен нулю) не соответствуют нашему критерию (наименьшая скорость развития). Количество таких автоматов уменьшается с каждым отбором. Если же нулевой ген равен единице — на первой (нечетной) итерации фон меняется на белый. Далее фон может оставаться белым или мигать (на нечетной итерации — белый, на четной — черный). 30-я итерация, на которой мы производим отбор — четная. Избавившись от автоматов с черным фоном (на 30-й итерации) — избавимся от мигающих (чтобы лишний раз не издеваться над нашими многоуважаемыми эпилептиками).
Популяция после второго отбора:
3 отбора:
5 отборов:
8 отборов:
13 отборов:
Те же автоматы на 60-й итерации:
21 отбор. Состояние автоматов на 30-й итерации:
Состояние автоматов на 60-й итерации:
34 отбора. Состояние автоматов на 30-й итерации:
Состояние автоматов на 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 пары и считать количество живых клеток в этих парах:
Таким образом, мы увеличиваем число автоматов, но сохраняем симметрию в фенотипе.
В каждой паре может быть от 0 до 2-х живых клеток. Пар 4. Количество комбинаций . По 81-й комбинации вокруг живой и вокруг мертвой клетки. Всего существует автоматов этого типа.
Число:
Вполне астрономическое и сгодится для генетического алгоритма.
Размер генотипа каждой особи — 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-я итерация для каждого. Под картинкой ссылка, перейдя по которой, можно посмотреть на автомат в динамике:
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
Посмотреть в динамике.
А поиграться?
А поиграться можно здесь:
Двухмерные клеточные автоматы второго порядка.
Интерфейс:
Кнопка Start запускает автоматы.
Stop — останавливает.
One — одна итерация.
Clear — останавливает автомат и заполняет начальное состояние рандомом.
Clear (1 cell) — останавливает автомат и заполняет одну клетку в начальном состоянии.
Остальные кнопки в этой строке считают указанное количество итераций для каждого автомата.
Отрисовка автомата на холсте (canvas) съедает все быстродействие. Если надо быстро посчитать 200 итераций — жмем Count 200. Кнопку Count 5000 не жмем — может подвесить браузер.
Ниже 20 случайных автоматов (размер популяции — 200 автоматов). Под автоматами чекбоксы. Отмечаем самые интересные. Нажимаем Select — приспособленность (fitness) автомата увеличится на указанное справа число.
Mutations — вероятность мутаций.
Gens — число мутирующих генов.
Start evolution — запускает механизм скрещиваний и мутаций.
Fill genotype — заполняет указанное число генов в генотипе каждого автомата.
Conway — заполняет популяцию автоматами Конвеевского типа.
Ниже две строки:
Номера показанных автоматов.
Содержимое массива fenotype.
Генофонд популяции еще ниже.
Весь прогресс сохраняется в локальном хранилище (Local Storage).
С автоматами Конвеевского типа (с теми, которые рассмотрены в статье последними) можно поиграться здесь:
4. Автомат Конвея и ему подобные (2).
Комментарии (25)
Yermack
26.09.2019 08:45Просто потрясающе!
А вот этот
xcont Автор
26.09.2019 12:30+1
greabock
26.09.2019 09:14+1Теперь я могу удерживать на указательном пальце двухпудовую гирю. Мои аплодисменты!
trapwalker
26.09.2019 11:18Теперь я знаю как бабушки генерируют узоры для вывязывания крючком кружевных салфеток под вазочки. А еще ковры на стенах тоже не без конечных, видимо, автоматов свои узоры получили. Правда там, видимо, эти конечные автоматы самозародились случайно и неосознанно в полных по тюрингу человеческих мозгах.
ardraeiss
26.09.2019 16:01На мой взгляд, это ближе к узорам спицами(всякие там "норвежские"). Крючок, если не квадратную сетку вязать, более именно узорчат.
Celsius
26.09.2019 12:31+2Клеточный автомат это свертка по нескольким фиксированным правилам. Сверточные нейросети работают по такому-же принципу, только там сила влияния регулируется в процессе обучения и правила не дискретные.
Интересовался обработкой изображений при помощи клеточных автоматов, кроме выделения контуров ничего не нашел.
Несколько недель играюсь с реккурентными сверточными нейросетями.
Теоретически, вычислительных возможностей у такого типа на порядки больше, чем у обычных сверток, но пока никакого прорыва нет.
Скорее всего, градиентный спуск тут вреден, надо будет совместить градиентный оптимизатор с генетическим алгоритмом.
naething
26.09.2019 20:55+2Все-таки это не совсем свертка в традиционном понимании этого слова. Свертка — это линейная операция: значение клекти вычисляется как взвешенная сумма ее окрестности. Иными словами, влияние каждого соседа суммируется независимо от других соседей.
А здесь в качестве «ядра» выступает произвольная булева функция от 9 переменных. Линейных булевых функций от девяти переменных существуется всего лишь 2^10, в то время как количество всех функций от 9 переменных — 2^512.
Optimist_38RU
26.09.2019 12:32+1Спасибо за статью. Я не специалист, посмотрел просто на красивые картинки в надежде на какой-то приближенный к жизни вывод: а зачем это все? Это можно как то апроксимировать на эволюцию человека? Типа мы сейчас прошли всего 500 итераций, и нам еще осталось 1500 до достижения пика развития? Или типа, вводим искусственный ген человека и всего за 8 поколений получаем стабильную мутацию.
Yermack
26.09.2019 15:55+1Нет никакого пика развития (сверхлюдей, связи с астралом, сверхмиром и прочих сказок с рентв) есть лишь адаптация к условиям окружающей среды. А про пользу таких моделей как клеточные автоматы можно и нагуглить
rjhdby
26.09.2019 15:55+1Пожалуй самая интересная статья на хабре за последнее время. Спасибо!
PS Вспомнилось, как играли в "жизнь" в школе. В тетрадке в клетку.
darkdaskin
26.09.2019 18:19+1Можно ещё попробовать выпускать несколько автоматов на одно поле и наблюдать, как они сражаются за пространство. В игрушке Powder Toy это реализовано, но там набор автоматов предопределён.
qw1
26.09.2019 20:40+1У одного австралийского фантаста упоминается универсальный клеточный автомат. По аналогии с универсальной машиной тьюринга, он может выполнять любые алгоритмы. Конфигурация клеток на поле задаёт программу и данные.
Уж не знаю, обнаружены ли такие автоматы в реальности.
python273
27.09.2019 00:08+2Game of life внезапно и есть Turing complete
https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
It is possible for gliders to interact with other objects in interesting ways. For example, if two gliders are shot at a block in a specific position, the block will move closer to the source of the gliders. If three gliders are shot in just the right way, the block will move farther away. This sliding block memory can be used to simulate a counter. It is possible to construct logic gates such as AND, OR and NOT using gliders. It is possible to build a pattern that acts like a finite-state machine connected to two counters. This has the same computational power as a universal Turing machine, so the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints; it is Turing complete. In fact, several different programmable computer architectures have been implemented in Conway's Life, including a pattern that simulates Tetris.
Refridgerator
27.09.2019 22:57+2А вот и пример программы на глайдерах:
Life in life
TimeCoder
26.09.2019 20:47+1Глядя на полученные красивые узоры, можно ли сказать, что эксперимент доказывает возможность самопроизвольной эволюции Вселенной? Ну в смысле, взяли пространство и время, насыпали туда кварков, или иных первокирпичиков, стали быстро-быстро всё это трясти, и некий простой механизм (какой?) обеспечил генетическое выведение всё более сложных систем: элементарные частицы, атомы и т.д.?
neonkainside
26.09.2019 21:40+1Не уверен, что это корректно. Какие у элементарных частиц механизмы наследования признаков? Отбор положим есть, но наследственности нет.
findoff
27.09.2019 12:27Здравствуйте, снова заинтересовался клеточными автоматами после вашей статьи.
Скажите, а для подготовки всего что выложили, вы реально использовали JS, или у вас есть аппаратно ускоренная реализация?
Я ночью накидал на webGL на компьютере с GT640 реализацию чисто воспроизведения, причем с шейдером в лоб, даже без оптимизаций после 199x199 пробегало 100 поколений за 8ms (отображал только результат прогона ста поколений, остальное работало циклически во фрэйм-буфере и получал 30-50fps).
Upd: GTX1060, 800x800, 1000 поколений во фрэйм-буфере, и рендер каждого последнего = 20fps (для не оптимизированного правила 3x3x2).
При такой скорости можно замахнуться и на 3x3x2 = 2^18 = 512x512 пикселей картинки в качестве правила. Правда, самое интересное, генетику я еще не реализовал.
Вообще, если кому-то интересно поиграться с результатом то пишите, и если я доведу это до нормального вида, могу выложить(риск крови из глаз) на какой нибудь codesandbox для удобства модификации.
xcont Автор
27.09.2019 14:18+1Скажите, а для подготовки всего что выложили, вы реально использовали JS, или у вас есть аппаратно ускоренная реализация?
На чистом JS. Выкладываю пример для картинки «habr».
Здесь считает.
Запуск производится через консоль. Пишем в консоль evil(3000); и поехали. Туда же, в консоль, записываются массивы для «тепловой карты».
Считал в FireFox. Если считать автоматы с большим полем — Chrome перестает подавать признаки жизни. В FireFox появляется кнопка «Остановить это».
Здесь смотрим, что насчитало.
Refridgerator
Лучшая статья по клеточным автоматам, что я видел. Браво.