Визуальное моделирование динамических процессов на примере простого клеточного автомата игры «Жизнь»

✧ итеративный автомат. Клеточный автомат, в котором лишь один элемент использует для изменения своего состояния значение входного параметра;

✧ односторонний клеточный автомат. Такой автомат допускает лишь одностороннее взаимодействие элементов. Например, в одномерном массиве элементов значение каждого элемента зависит лишь от его состояния и от состояния левого (или правого) соседа.

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

✧ Л-система. Этот тип клеточных автоматов используется для моделирования биологических систем. Это динамические клеточные автоматы (как правило, одномерные или двумерные), в которых с течением времени один элемент может заменяться несколькими или может быть удалённым из системы в соответствии с заданными правилами;

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

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

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

Состояние всех элементов  клеточного автомата (конфигурация клеточного автомата) называется «Райским садом», если такая конфигурация может возникнуть, только лишь как начальное значение в любой эволюции клеточного автомата. Отсутствие такой конфигурации означает, что данный клеточный автомат – эпиморфный.

 

3. МОДЕЛИРОВАНИЕ КЛЕТОЧНЫХ АВТОМАТОВ

 

Существует много видов клеточных автоматов: «правило 184», «Q2R», «пожар», «плотина», «кучи песка», «муравей», «дорожная пробка», «движение твердого тела», «пушечный склад», игра «Жизнь».

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

 

1. Реализация принципа поведения «горящего леса»

 

Вероятностные клеточные автоматы являются обычными клеточными автоматами, где различные правила могут быть применены к каждой клетке в соответствии с некоторой вероятностью. Интересный и простой пример модели вероятностного клеточного автомата это вероятностное правило «горящего леса». Для моделирования используется сетка nxn, представляющая лес и соседство по признаку Мура. Клетки соответствуют деревьям и могут быть в одном из трех состояний: зеленое дерево (1), пустое место (2), горящее дерево (3). Изначально все клетки находятся в состоянии (1) (то есть, содержат зелёное дерево). Состояния клеток изменяются в соответствии со следующими правилами:

- горящее дерево становится пустой ячейкой;

- зелёное дерево становится горящим деревом, если хотя бы один из его ближайших соседей горит;

- на пустом месте дерево растет с вероятностью р;

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

На каждом временном промежутке каждая клетка получает новое случайное  значение от 0 до 1 для вероятности возгорания (f) или рождения (p). Зелёное дерево начинает гореть, когда f больше порогового значения, установленного в 0.001. Новое дерево вырастает на пустом месте когда p больше порогового значения, установленного в 0.1. Эти пороговые значения для f и p, однажды установленные, остаются неизменными в ходе одной реализации. Пороговое значение для f выбирается достаточно малым, поэтому на большей сетке могут начать только несколько пожаров. Пороговое значение для p выбирается большим, чем для f, потому могут вырастать новые деревья и моделирование может продолжаться.

На следующих рисунках показаны примеры моделирования с использованием сетки размером 200x200. В начале (рис. 1а) два пожара (белые участки) начались в лесу (черная область). Огонь начинает распространяться среди зеленых деревьев, оставляя за собой пустые участки (серые области) (рис. 1б). Картина распространения огня похожа на увеличивающиеся круги с белым контуром (горящие участки) и серой территорией внутри (сгоревшие участки).

 

  

 

                               а)                                                       б)

Рис. 1. а) Два пожара начались в лесу (белые участки). б) Огонь распространяется среди зелёных деревьев, оставляя за собой пустые участки.

 

 

В. Реализация принципа поведения «куч песка»

 

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

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

Рис. 2. Верхняя песчинка не двигается.

 

Клеточные автоматы используют для целей моделирования сетку  размером nxn и соседство по Марголусу, которое представляет простой способ взаимодействия с одновременным движением всех частиц. Когда используется соседство по Марголусу, решетка разделена на непересекающиеся блоки размером 2x2; каждый блок перемещается вниз и вправо со следующим поколением, а затем движется обратно. Клетки могут находиться в одном из следующих двух состояний: песчинка (1), пустая ячейка (0). Первоначально, песчинки размещаются случайным образом на решетке (в течение эволюции клеточного автомата не возникает дополнительных песчинок). Состояния ячеек обновляются в соответствии со следующим правилом, которое изображено графически на рис.3:

 

Рис. 3. Принцип поведения кучи песка

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

Рис. 4. Случайное поведение кучи песка

 

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

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

 

 

   

                         а)                                                     б)                                      

 

Рис. 5. а) растущая куча песка. б) создание кучи песка.

 

 

 

 

 

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

 

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

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

- если ячейка белая, он поворачивает на 90 градусов влево и цвет ячейки становится серым;

- если ячейка серая,  он поворачивает на 90 градусов  вправо и цвет ячейки становится  белым.

Движение продолжается, таким образом, до бесконечности. Интересным является то, что после фиксированного числа шагов, муравей строит шоссе и продолжает это бесконечно. Движение муравья на этом шоссе нелинейно, это больше похоже на работу швейной машинки. Хотя принцип муравья кажется очень простым, он водит муравья хаотическим образом. Это свойство также показывает силу моделирования систем клеточными автоматами: даже если принципы работы клеточного автомата очень простые, они могут моделировать очень сложное поведение.

Клеточный автомат использует для целей моделирования решетку  размера nxn и соседство ячеек в понимании фон Неймана; соседство фон Неймана состоит из четырёх ячеек ортогонально окружающих центральную ячейку на двумерной квадратной решетке. Окружающие соседи могут пригодиться для ячеек на границах решетки: когда муравей достигает границ решетки, он возвращается к решетке, моделирующей существование второго муравья. Ячейки могут быть в одном из двух состояний: наличие муравья (1), пустая ячейка (0). Первоначально, все ячейки пустые (состояние 0) кроме одной ячейки, содержащей муравья (состояние 1). Состояния ячеек меняются в соответствии со следующими правилами:

n_i (r + c_i, t + 1) = μ n_i-1 (r, t) + (1 – μ) n_i+1 (r, t)

μ (r, t + 1) = μ (r, t) ⊕ n₁(r, t) ⊕ n₂(r, t) ⊕ n₃(r, t) ⊕n₄(r, t)

 

где ni: новое состояние, r: текущая ячейка, ci: текущее направление, t: текущий временной шаг, μ: цвет ячейки (1 = белый, 0 = чёрный). Первоначально, c₀ = 4,

r = центральная ячейка решетки.

 

                   а)                                       б)                                       в)

Рис. 6. а) муравей начинает свой путь от центра решетки. б) хаотическая ситуация в связи с движением муравья. в) муравей на шоссе.

 

В нашей модели, муравей  начинает свое путешествие из центральной ячейки решетки размером 100x100 (рис. 6а). Все клетки изначально чёрные; муравей делает их белыми, если движется через них. После примерно 7000 шагов муравей попадает в хаотическую ситуацию (рис. 6б). После приблизительно 10000 шагов муравей находит выход из хаотической ситуации и строит шоссе, двигаясь от своего первоначального положения (рис. 6в).

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

 

 

 

 

                                         а)                                           б)

                                        в)                                           г)   

 

Рис.7. Движение второго муравья

 

D. Реализация принципа дорожной пробки

 

Клеточных автоматов для  моделирования дорожного движения получили огромную популярность. Одномерные модели для однополосного автомобильного движения довольно простые и элегантные. Дорога представляется линией ячеек: каждая ячейка занята или не занята машиной. Все машины едут в одном направлении. Их позиции меняются одновременно последовательными итерациями (дискретными временными шагами). Во время движения каждая машина может оставаться в состоянии покоя или перепрыгивать на ближайшее соседнее место вдоль направления движения. Принцип состоит в том, что машина двигается только тогда, когда ячейка назначения пустая. Это значит, что водители близорукие и не знают, будет ли машина впереди двигаться или также заблокирована другой машиной. Поэтому состояние каждой ячейки s₁ целиком определяется занятостью ячейки самой по себе и двух её ближайших соседей s_i-1 и s_i+1. Принцип движения может быть сведён к следующей таблице, где приведены все восемь возможных конфигураций (s_i-1 s_i s_i+1)_t →(s_i)_t+1 :