Модели клеточных автоматов

Понятие о клеточных автоматах

Приведенная во введении классификация моделей, конечно, является условной. Некоторые широко распространенные подходы, а также ряд «экзотических» моделей занимают промежуточное положение в данной классификации. Например, модели клеточных автоматов могут быть отнесены и к дискретным моделям, и, по-видимому, к имитационным. Отметим, что в настоящее время в связи с доступностью вычислительных комплексов с высокой производительностью в мире вырос интерес к построению агентных моделей. Такие математические модели фактически представляют собой очень сложные клеточные автоматы для количественного описания многих процессов, например кристаллизации белков.

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

Под соседями для элемента j_f в свою очередь, понимаются фиксированно заданные элементы множества 0(/). Для большинства КА такое множество определяется довольно просто, ниже будут приведены примеры наиболее употребительных окрестностей для КА на плоскости. Для некоторых моделей класса КА определение «соседства» — задача весьма непростая.

Для клеточного автомата определяется закон перехода (для детерминированного автомата).

или функция вероятности перехода элемента.

Здесь W — вероятность перехода j-го элемента из состояния а (п, t) в момент времени t в состояние а (п, t + 1) в следующий момент времени при определенных состояниях соседей. Такие клеточные автоматы называются вероятностными.

Приведенные выше определения являются весьма общими. Так, любую явную разностную схему для решения уравнения переноса или теплопроводности можно считать клеточным автоматом в смысле определения и закона перехода в форме (2.1). Однако неявная разностная схема, скажем, для уравнения теплопроводности уже не будет клеточным автоматом (в смысле формы (2.1)).

Конечно, наибольший интерес представляют не переименованные в автоматы численные аппроксимации, а прямые модели, предпочтительно точно решаемые в целых числах. Так, в литературе^[1] приведено описание «чисто аналогового» клеточного автомата (на треугольной или гексагональной решетке), являющегося прямой имитацией плоских движений жидкости. Модель позволяет получить гидродинамические течения (при не слишком больших числах Маха) без решения уравнений Навье — Стокса.

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

Рассмотрим процедуру построения подобной модели из общих соображений, а затем обсудим свойства получаемых моделей.

Пусть в однородном ареале обитания травоядных животных при оптимальной численности популяции пищевых ресурсов хватает на время t_v после чего требуется время t₂ на восстановление запасов пищи.

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

• 1. Заселиться может только незаселенная клетка (рефрактерные клетки не заселяются).
• 2. Через время t_{ возбуждение клетки переходит в состояние рефрактерное™.
• 3. Через время t₂ рефрактерные клетки переходят в состояние покоя.

Очевидно, что подобная модель не в состоянии обеспечить предсказание количественных характеристик процессов, с ее помощью лишь возможно исследовать (имитировать) качественное поведение системы. Замечательно, что это поведение довольно сложно, возможна нетривиальная динамика, существенно зависящая от начальных условий и соотношения параметров t_x и t₂.

Так, при t_x ~t₂ и начальной конфигурации, показанной на рис. 2.1, точка А, которая соседствует и с двумя возбужденными участками, и с двумя рефрактерными, будет являться центром образующейся в системе спиральной волны (читателю предлагается подумать, почему в системе формируется двухрукавная спиральная волна).

Рис. 2.1. Двухрукавная спиральная волна в автомате Винера — Розенблюта. Момент t = 1.

Описанный клеточный автомат (автомат Н. Винера) строился из некоторых соображений экологического характера. Однако ему можно придать ряд истолкований, включая качественную модель распространения возбуждения в коре головного мозга или протекания химической реакции Белоусова Жаботинского^[2]. Развитие спиральной волны, возникшей при эволюции системы, в два момента времени показано на рис. 2.2.

Рис. 2.2. Двухрукавная спиральная волна:

а — момент t = 21; 6 — момент t = 51.

Авторы феноменологической модели исследования реакции Белоусова — Жаботинского^[3] предположили, что сосредоточенная (точечная) модель обладает автокаталитической кинетикой, а причиной сложного пространственновременного поведения оказываются диффузионные процессы.

В одномерном случае система разбивается на одинаковые клетки. Состояние п-й клетки в момент времени t (время в данной модели, конечно, дискретно) определяется неотрицательной функцией А (п, t). Значение A (n>t+ 1) вычисляется по предыдущему состоянию по следующим правилам:

Предварительный этап (2.3) моделирует диффузию. По замыслу авторов, множитель, а определяет коэффициент диффузии системы, 0 < а < 1. Функция F задается правилом.

Для читателей, знакомых с основами применения численных методов для решения уравнений в частных производных, должно быть видно сходство предварительного этапа (2.1) с явной разностной схемой для решения уравнения диффузии, при этом, а играет роль удвоенного параболического числа Куранта (подробнее об этом см. в приложении к данной главе).

При, а = 0 диффузия в системе отсутствует, и правила перехода определяются равенством (2.4), т. е. дискретным отображением. Нарисовав график итераций (диаграмму Ламерея) этого отображения (см. гл. 1), видим, что при М > 1 существует единственный устойчивый цикл периода 3: 0 —> —> М —> 1 —> 0 —>… .

В зависимости от А/, а в автомате (2.3), (2.4) могут существовать циклы с периодом 3 (очевидно, в случае малых а), волновые процессы и турбулентные режимы^[4]. Далее мы вернемся к двумерному обобщению этого автомата.

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

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

Автомат называется правильным, если для него выполнено следующее условие:

Кроме того, если F (0, 0,…, 0) = 0, то автомат называется законным. Если.

то автомат является суммирующиму если же.

то он называется внешне суммирующим.

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

Класс 1. За конечное число шагов автоматы достигают пространственнооднородного состояния. Конечное состояние не зависит от времени и от начальных условий.

Рассмотрим следующий клеточный автомат: каждый элемент может находиться в двух состояниях: 0 и 1. Правила перехода имеют вид.

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

Класс 2. Автомат генерирует локализованные структуры, стационарные или периодические по времени.

Пример 2.2.

Как и в примере 2.1, считаем, что каждый элемент сети может находиться в двух состояниях: 0 и 1. Правила перехода имеют вид.

Такой автомат генерирует устойчивые тройки активных элементов.

Класс 3. Автомат из этого класса порождает непериодические конфигурации клеток, «забывая» при этом о начальных условиях, — обладает так называемым турбулентным перемешиванием.

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

• [1] Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.: Мир, 1991.
• [2] Ахромеева Т. С. и др. Указ, соч.; Лоскутов А. /О. Михайлов А. С. Основы теории сложных систем. М.; Ижевск: Институт компьютерных исследований, 2007.
• [3] Оопо К, Kohmoto М. Discrete model of chemical turbulence // Phys. Rev. Lett. 1985.Vol. 55. № 27. P. 2927−2931.
• [4] Оопо Y. y Kohmoto М. Op. cit.