О циклических клеточных автоматах было написано в этой статье. Целью данной статьи является рассмотрение условий возникновения спиралей, также известных как демоны. Средством достижения цели является изменение начальных условий и слежение за развитием клеточного автомата. В результате будут сделаны обобщающие выводы об условиях образования спиралей.
Каждая ячейка взаимодействует со своими четырьмя соседями — окрестностью фон Неймана. Окрестность фон Неймана — это ячейки, которые расположены горизонтально и вертикально. Ниже приведен набор правил циклического клеточного автомата.
Первое поколение начинается со случайных состояний в каждой из ячеек. Следующее поколение создается путем применения вышеуказанных правил одновременно к каждой ячейке предыдущего поколения. Изменение состояния происходит для каждой ячейки одновременно. Другими словами, каждое поколение является чистой функцией предыдущего. Правила продолжают применяться неоднократно, создавая новые поколения.
Как видно из рисунка выше, клеточный автомат проходит три этапа:
1. Случайное поле.
2. Цветные области.
3. Спирали, также известные как демоны.
Добавим еще одно измерение к решетке. В этом измерении мы отобразим состояние ячейки. Ячейка будет подниматься до тех пор, пока она не достигнет вершины кубоида, а затем она упадет вниз. Такая модель является хорошим представлением об изменении состояния клеточного автомата.
Выберем несколько (например 12) случайных ячеек и рассмотрим изменение их состояний во времени.
Теперь нетрудно догадаться, в какой из трех стадий клеточного автомата текущая ячейка находится в каждый момент времени:
1. Случайное поле. Очевидно, что в начальный момент каждая ячейка находится в этой стадии.
2. Цветная область. Как только ячейка начинает изменять свое состояние, она попадает в эту стадию. Можно определить следующий критерий для данной стадии: число итераций, за которые ячейка проходит полный цикл, больше, чем число состояний клеточного автомата. Рассматриваемый клеточный автомат имеет 15 состояний от 0 до 14. Если ячейка изменяет состояние 0 на состояние 14 за более чем 15 итераций алгоритма (например, за 20 или 25), то она находится в стадии Цветная область клеточного автомата.
3. Спирали, также известные как демоны. Если ячейка изменяет состояние 0 на состояние 14 точно за 15 итераций, то она находится в стадии спираль клеточного автомата. Таким образом, критерием может быть: число итераций, за которое ячейка проходит полный цикл, в точности равный числу состояний клеточного автомата.
Обратим внимание на некоторые особенности перехода из одного состояния в другое.
1. Согласно правилам клеточного автомата ячейка никогда не может вернуться в более низкое состояние, если речь не идет о повторении цикла. Например, из состояния 9 ячейка не может попасть в состояние 8. Но из состояния 14 ячейка всегда попадает в состояние 0, т.к. состояние 0, является следующим состоянием для состояния 14.
2. Согласно правилам клеточного автомата, клетка не может перепрыгивать через состояния.
Наличие граничных состояний (0 и 14) является необходимым условием для генерации спиралей. Однако, как будет показано ниже, рассмотренные выше особенности перехода из одного состояния в другое накладывают ограничения на пространственное расположение ячеек в разных состояниях, включая границу.
На рисунке ниже показано изменение доли каждого состояния на протяжении итераций алгоритма.
Как мы видим, изменения во фракциях являются колебательными. Эти колебания кажутся беспорядочными и слишком сложными для анализа. Тем не менее, мы пытаемся понять их. Для этого мы изменим начальные условия клеточного автомата.
По правилам клеточного автомата ячейка в любом состоянии не может возникнуть сама по себе (кроме нулевой итерации). Для ее создания в окрестности ячейки должна быть ячейка с тем же самым состоянием. Таким образом, если вначале не заданы все возможные состояния клеточного автомата, отсутствующие состояния никогда не возникнут. Цикл никогда не будет замкнут, и спираль никогда не возникнет.
Важную роль играет пространственное расположение ячеек с различными состояниями. Рассмотрим это на примере. 15 ячеек со всеми возможными состояниями клеточного автомата, помещены случайным образом на сетку. Оставшиеся ячейки инициализированы нулевым состоянием. Таким образом, мы имеем разные расстояния между исходными ячейками. Запустим симуляцию и посмотрим, как изменятся фракции ячеек.
Рассмотрим изменения фракций в 3D-режиме.
Как видно на рисунке выше, доля ячеек в состоянии 0 уменьшается. Потому что, согласно правилам клеточного автомата, они служат пищей для клеток с состоянием 1. Фракция клеток в состоянии 1 сначала увеличивается, а затем уменьшается. Ячейки с состоянием 1 образует цветную область. Эта цветная область растет до тех пор пока по соседству с ней есть только пища (ячейки с нулевым состоянием). Цветная область сама становится пищей и начинает уменьшаться, как только в ее районе появляется преемник (ячейка с состоянием 2). Время роста (количество итераций) этой цветной области зависит от расстояния между исходными ячейками с состоянием 1 и 2, которое является случайным.
Как видно из рисунка, фракция клеток в состоянии выше третьего равна нулю. Это связано с тем, что расстояние между исходными ячейками слишком велико. В то же время число итераций ограничено и равно 400. Цветная область не достигает следующего преемника в течение 400 итераций. Таким образом наша модель движется слишком медленно. Тем не менее, это позволяет понять принцип роста и уменьшения цветных областей:
1. Цветная область растет, пока ее границы имеют пищу (клетки с более низким состоянием).
2. Цветная область начинает уменьшаться, когда в ее окружении появляются преемники (клетки с более высоким состоянием).
Процесс формирования цветных областей может быть ускорен двумя способами:
1. Увеличением числа итераций.
2. Уменьшением расстояния между исходными ячейками.
Мы используем второй способ. Поместим исходные ячейки так, чтобы они были расположены на расстоянии 10 ячеек друг от друга.
Рассмотрим фракции на трехмерном графике.
На рисунке выше мы видим движение цветных областей от состояния 0 до состояния 13. Цветная область не переходит в последнее состояние, которое равно 14, потому что нет преемника (ячейки с состоянием 14). Хотя, мы и поместили ячейку с этим состоянием на решетку в самом начале, но единственная ячейка с состояния 14 была поглощена ее преемником (ячейкой с состоянием 0), пока цветная область с состоянием 13 не успела ее достичь.
Состояние 14 исчезло из клеточного автомата навсегда. Оно никогда не появится снова.
Таким образом, цикл никогда не будет закрыт, и спирали никогда не будут сформированы. Это важная особенность циклических клеточных автоматов. Неудачное пространственное расположение ячеек не может порождать цикл. Как найти удачное пространственное расположение ячеек. Очевидно, что они должны располагаться как можно ближе друг к другу, чтобы они могли взаимодействовать как можно быстрее (пока их не поглотит преемник).
Разместим начальные ячейки одна за другой.
Рассмотрим изменения фракций на 3D-графике.
Как мы видим, фракции клеток равномерно распределены между всеми состояниями. Цветная область проходит через все возможные состояния. Цикл завершается для каждой начальной ячейки.
Мы видим образование спирали.
Таким образом, можно сделать вывод: спираль — это цветная область, для которой одновременно выполняются три условия:
1. Размер цветной области — только одна ячейка.
2. Цветная область имеет в своей окрестности пищу (ячейки с более низким состоянием)
3. Цветная область имеет в своей окрестности преемников (ячейки с более высоким состоянием)
2. Если число итераций, за которые ячейка проходит полный цикл, в точности равно числу состояний клеточного автомата, то это спираль.
3. По правилам клеточного автомата ячейка в любом состоянии не может возникнуть сама по себе (кроме нулевой итерации). Для ее создания в окрестности ячейки должна быть ячейка с тем же самым состоянием.
4. Цветная область растет, пока ее границы имеют пищу (клетки с более низким состоянием). Цветная область начинает сокращаться, когда в ее окрестности появляются преемники (клетки с более высоким состоянием).
5. Неудачное пространственное расположение исходных ячеек может не порождать цикл, потому что последние несколько состояний могут исчезнуть навсегда и никогда не появится снова. Таким образом, клеточный автомат теряет несколько состояний и не способен производить больше спирали.
6. Чтобы избежать этого, исходные ячейки нужно располагать как можно ближе друг к другу, чтобы они могли взаимодействовать как можно быстрее (пока их не поглотили преемники).
7. Спираль — это цветная область, для которой одновременно выполняются три условия:
— размер цветной области — только одна ячейка;
— цветная область имеет в своей окрестности пищу (клетки с более низким состоянием);
— цветная область имеет в своей окрестности преемников (ячейки с более высоким состоянием).
(2) Clifford A. Reiter, Medley of Spirals from Cyclic Cellular Automata.
(3) Yiqing Cai, CYCLIC CELLULAR AUTOMATA ON NETWORKS AND COHOMOLOGICAL WAVES.
(4) Indrajit Banerjee, Prasenjit Chanak, Hafizur Rahaman, CCABC: Cyclic Cellular Automata Based Clustering For Energy Conservation in Sensor Networks.
(5) K. J. Kwak, Y. M. Baryshnikov, E. G. Coffman, Cyclic Cellular Automata: A Tool for Self-organizing Sleep Scheduling in Sensor Networks
Автор: ScientificDimension
