Клеточные автоматы: локальные правила и самоорганизация

План занятия

Теоретическая часть

Дискретная модель и локальные правила — 7 мин.
Одномерный клеточный автомат — 9 мин.
Автомат «Жизнь» Конвея — 12 мин.

Исследование моделей

Распространение процесса по сетке — 8 мин.
Сравнение подходов и выводы — 4 мин.

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

Центральная идея занятия

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

В некоторых клеточных автоматах возникают устойчивые или движущиеся структуры. Их поведение не вводится отдельной командой. Оно следует из многократного применения одинаковых правил ко всем ячейкам. Такое возникновение свойств целой системы из взаимодействий отдельных элементов называется самоорганизацией; понятие эмерджентности подчёркивает, что свойства всей системы нельзя свести к описанию одной клетки.

Основной вопрос. Как простое правило изменения состояния одной клетки может приводить к сложному поведению всей системы?

Теория · основы клеточных автоматов

Устройство клеточного автомата

Клеточный автомат — математическая модель, состоящая из клеток, расположенных в определённой структуре, например в строке или на прямоугольной сетке. У каждой клетки есть состояние, которое меняется по общему правилу с учётом состояний соседних клеток.

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

Четыре составляющие

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

Начальное состояние и границы

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

Состояние центральной клетки определяется по общему правилу, учитывающему её окрестность.

Методологический принцип. Уравнения непрерывного движения не обязательны. Во многих задачах систему можно описать конечным набором состояний и правил перехода.

Модель 1 · одномерный автомат

Одномерный клеточный автомат

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

Каждому сочетанию заранее сопоставляется новое состояние центральной клетки. Такое правило можно записать восемью цифрами 0 или 1. Если прочитать их как двоичное число, получится номер правила от 0 до 255. В интерактивной модели доступны несколько правил, образующих существенно разные узоры.

Три клетки	111	110	101	100	011	010	001	000
Правило 30	0	0	0	1	1	1	1	0

Для правила 30 сочетанию 100 соответствует 1, а сочетанию 111 — 0. Из одних и тех же простых переходов возникает пространственный узор с регулярными и нерегулярными участками. Визуальная сложность узора не требует сложного правила каждой клетки.

Модель 1. Последовательные поколенияСтроки показывают последовательные шаги времени сверху вниз.

состояние 1состояние 0

ПравилоНачальное состояниеСкорость: 8 шагов/с

0номер поколения

1активных клеток в последней строке

Наблюдение. Сравните правила 30 и 90 при одинаковом начальном состоянии. Укажите, какие фрагменты узоров повторяются и какие кажутся нерегулярными.

Вывод. Номер правила не задаёт сложность результата. Поведение автомата определяется сочетанием правила, начального состояния и граничных условий.

Модель 2 · двумерный автомат

«Жизнь» Конвея: устойчивые и движущиеся структуры

«Жизнь» — двумерный клеточный автомат, предложенный математиком Джоном Конвеем. Каждая клетка имеет два состояния: живая или мёртвая. Её соседями считаются восемь клеток, имеющих с ней общую сторону или вершину. Все клетки обновляются одновременно.

Правила учитывают только число живых соседей. Живая клетка сохраняется, если живых соседей два или три. Мёртвая клетка становится живой, если живых соседей ровно три. Во всех остальных случаях клетка на следующем шаге мертва. Эти правила часто обозначаются B3/S23.

Правила перехода

Живая клетка с 2 или 3 живыми соседями остаётся живой.
Мёртвая клетка с 3 живыми соседями становится живой.
Во всех остальных случаях клетка становится или остаётся мёртвой.

Виды поведения

Устойчивая фигура — не изменяется.
Осциллятор — повторяется через несколько шагов.
Движущаяся фигура — периодически повторяет форму, перемещаясь по сетке.

Примеры начальных конфигураций: неподвижная, периодическая и перемещающаяся.

Модель 2. Игра «Жизнь»Щелчок по клетке изменяет её состояние при остановленной модели.

живая клеткамёртвая клетка

Начальная фигураСкорость: 5 поколений/с

0номер поколения

0живых клеток

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

Наблюдение. Сравните устойчивый блок, мигалку и планер. Определите, какие свойства фигур можно установить только после нескольких шагов.

Вывод. Движение планера не задано отдельным правилом. Оно возникает в результате применения одного общего набора локальных правил ко всем клеткам.

Модель 3 · пример прикладного автомата

Распространение процесса по клеточной сетке

Клеточные автоматы применяются не только для исследования абстрактных узоров. Они позволяют задавать упрощённые правила распространения состояния между соседними областями. Например, можно рассматривать распространение пожара, инфекции, информации или химического превращения. Выбор правил зависит от исследуемого явления.

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

Окрестность из четырёх клеток. Диагональные соседи в этой модели не учитываются.

Модель 3. Вероятностное распространениеПараметры меняют характер распространения по сетке.

не затронутаактивназавершенобарьер

Вероятность передачи p: 60%ПрепятствияСкорость: 5 шагов/с

0номер шага

1всего затронуто клеток

1активных клеток

Наблюдение. Сравните результаты при p = 100% и p = 30%. Затем добавьте перегородку. Определите, какие различия обусловлены вероятностью передачи, а какие — устройством пространства.

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

Обобщение · сравнение подходов

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

Преимущества

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

Ограничения

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

Подход	Единица описания	Как изменяется состояние
Численное моделирование движения	Положение и скорость тела	По формулам движения через малые промежутки времени
Клеточный автомат	Состояние клетки	По локальному правилу на каждом шаге
Вероятностный клеточный автомат	Состояние клетки и вероятность события	По правилу и результату случайного выбора

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

Вопросы для самопроверки

Почему одновременное и последовательное обновление клеток способно дать разные результаты?

Какие четыре составляющие необходимо задать для построения клеточного автомата?

Почему движение планера в «Жизни» не означает, что у каждой клетки есть скорость?

Какие дополнительные данные нужны, чтобы использовать модель распространения для количественного прогноза реального процесса?