2.17 Клеточные автоматы

Автоматом называют устройство, которое без непосредственного участия человека выполняет процессы приема, преобразования и передачи энергии, материи и или информации в соответствии с заложенной в него программой [1].

Конечные автоматы выполняют дискретное преобразование информации (рисунок 27).

Рисунок 27 – Конечный автомат

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

Клеточные автоматы [1, 20] являются частным случаем конечных автоматов и используются для моделирования динамического поведения однородных сред. При этом пространство и время дискретны, а физические величины в каждой точке моделируемой среды могут принимать конечное множество значений. Клеточные автоматы можно представить как регулярную решетку ячеек (таблицу клеток), каждая из которых может находиться в конечном числе возможных состояний, например 0 или 1. Состояние системы полностью определяется значениями переменных в каждой клетке и обновляется в результате выполнения последовательности дискретных постоянных шагов во времени (или тактов). В начальный момент времени дается некоторое распределение активных и пассивных клеток. Далее значения переменных в каждой клетке меняются одновременно (синхронно), исходя из значений переменных на предыдущем шаге. Правило определения нового состояния ячейки зависит только от локальных значений ячеек из некоторой окрестности данной ячейки.

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

Рисунок 28 – Типы окрестностей

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

Рисунок 29 – Тор

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

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

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

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

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

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

Рисунок 30– Формирование пространственных структур в активной среде (1-й, 10-й, 20-й и 40-й такты)