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

1. Что такое клеточный автомат? История возникновения и основные направления развития.

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

Исследование клеточных автоматов имеет почти полувековую историю. Клеточные автоматы были введены Дж. Нейманом в его работе о конструировании самовоспроизводящихся машин [11. В этой работе был построен достаточно сложный автомат, порождающий самовоспроизводящиеся конфигурации в клеточном пространстве. По мнению Дж. Неймана, многие биологические процессы естественно описывать на языке клеточных автоматов, а не дифференциальных уравнений. Оказалось также, что клеточные автоматы позволяют моделировать сложное поведение ряда распределенных систем более просто и наглядно, чем уравнения в частных производных. Например, клеточный автомат, предложенный Н. Винером и А. Розенблютом в 1947 году для описания сердечных аритмий, допускает простое аналитическое исследование. В то же время, уравнения в частных производных, имитирующие такое же поведение, требуют сложного компьютерного анализа [21.

Чтобы определить клеточный автомат, нужно задать решетку обычно одинаковых ячеек-клеток (i=1,2,.), набор возможных значений, которыми характеризуются их состояния < u^ и2,., ц } и правило эволюции конфигураций клеток во времени. Состояние клетки i, t) (где i — координата клетки, величина, а может принимать только значения { и u2.}) меняется в дискретные моменты времени t=l, 2. Состояние клетки в следующий момент времени зависит от состояния A (i, t) самой клетки и состояний ее соседей в данный момент. Например, в одномерном клеточном автомате величина A (i, t) для клетки с координатой i на бесконечной прямой изменяется во времени по следующему закону:

Aii, t+1 > = F (Aii-r.t),. .., A (i, t),. .., A (i+r, t)), (1) где г — размер окрестности, 2 г — число «соседей» .

Функция F может быть детерминированной (в этом случае говорят о «детерминированном» клеточном автомате), а может зависеть от некоторой случайной величины (это так называемые «стохастические» автоматы).

Вид функции F, определяющей правило эволюции автомата, может быть задан «кодом» автомата:

Z^-Ad+j) j=-r.

R= I F[A (i-r),. .., A (i+r)]-K. (2) Г.

A (i-r).A (i + r) >

В целом, для фиксированного числа к состояний клеток и числа 2г+1 соседей общее количество различных правил вида (1) равно.

2г+1) к. То есть, в самом простом случае, при 2 и r=1 (каждая клетка может принимать только два значения и правило эволюции зависит только от значений двух ближайших клеток — соседей) з количество возможных правил равно 22 =256. Отсюда понятно, что с помощью компьютера можно изучить только ничтожную часть всего множества автоматов. Поведение их может быть очень разнообразным. Большинство полученных к настоящему времени результатов относится к классу законных суммирующих автоматов. Законными называют автоматы, для которых выполняются следующие два условия:

F (0, 0.0)=0, (3).

F (А[ i~r, t),. .. , i+r, t)) = F (л (1+г, t),. .. , A{i-r, t)). (4).

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

Л (1,t+l)=F (£ A{i+j, t)). (5).

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

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

Обычно выделяют четыре класса качественного поведения законных суммирующих клеточных автоматов в случае неупорядоченных начальных данных (см. рис. 1). Эволюция автоматов первого класса приводит к пространственно-однородным состояниям (л (i, t)= О, t=1,2, — -ю < i < «(см. рис. 1а)), эволюция автоматов второго класса — к простым периодическим во времени структурам (см. рис. 16). Автоматы третьего класса порождают.

Г).

С-20.

Рис. 1. Примеры конфигураций, порождаемых в результате эволюции клеточных автоматов четырех классов (число состояний te=2, радиус окрестности г=2) в случае неупорядоченных начальных данных. Белые квадраты представляют клетки со значением О, черные — клетки со значением 1. Правила данных клеточных автоматов являются суммирующими" с кодами (а) 4, (б) 56, (в) 10, (г) 20. Код для суммирующих правил определяется формулой.

2r+l)(к-1).

Cf= I knf[n] (см. t4] ь п = О непериодические конфигурации клеток (см. рис. 1в). Клеточные автоматы четвертого класса демонстрируют довольно сложное поведение (см. рис. 1г), с различными локализованными и перемещающимися структурами. Такое качественное поведение автоматов могут описывать различные количественные характеристики [3].

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

Теория динамических систем дает первый подход к количественной классификации поведения клеточных автоматов. При их исследовании можно так же, как в теории динамических систем, вводить разнообразные количественные характеристики аттракторов — ляпуновские показатели, различные виды энтропий и размерностей [3,41.

Особый интерес представляют собой автоматы четвертого класса. Было высказано предположение о том, что автоматы этого класса могут демонстрировать сколь угодно сложное поведение. В принципе поведение любой системы можно смоделировать, имитируя шаг за шагом ее эволюцию. Но в большинстве случаев можно найти более простой алгоритм. Например, чтобы умножить число с помощью компьютера на 2П, нет необходимости 2П раз складывать его с самим собой, можно просто сдвинуть его представление в памяти ЭВМ на п двоичных разрядов. Системы, для которых такие более простые алгоритмы существуют, называют вычислительно приводимыми. Именно это свойство помогает при описании явлений природы выделить небольшой набор существенных переменных, часто называемых параметрами порядка, или переходить к более простому статистическому описанию.

Гипотеза С. Уолфрема, известного специалиста по клеточным автоматам [3−51, состоит в том, что многие физические системы и их модели, для которых в настоящее время не известно простого описания, являются вычислительно неприводимыми. Для них в принципе не могут быть построены эффективные теории. Для них попросту нет способа выяснить, что получится в конце, если непосредственно не проследить эволюцию самой системы или имитирующей ее модели последовательно, шаг за шагом до конца. Единственный способ анализа таких систем — физический или вычислительный эксперимент.

Автоматы четвертого класса относятся именно к таким системам. Не существует простого алгоритма, позволяющего предсказать эволюцию даже локализованных начальных конфигураций. Ярким примером автоматов четвертого класса является двумерный клеточный автомат, называемый игрой «Жизнь» [6,7]. Модель демонстрирует происхождение, рост и развитие сообществ живых клеток < их обычно называют «организмами»). Эта игра определяется следующими правилами. Рассмотрим квадратную решетку клеток на плоскости. Клетка в момент времени t в точке с координатами i, j на бесконечной плоскости (t, i, j — дискретные переменные) может находиться в одном из двух состояний л (i, j, t)=0 («мертвая клетка») или A (i, j, t)=l («живая клетка»). Сначала задается некоторое исходное состояние A (i, j, 0), < i < о", -" < j < а далее на каждом шаге вычисляется величина i+i j+i.

A'(i, jtt)= I I л (k, I, t) — A{i, j, t). (6) k = i-x i = j-1.

Это сумма значений по ближайшим восьми соседям данной клетки (такую окрестность называют также окрестностью Мураесли же в качестве соседей рассматриваются только клетки, имеющие с данной общую сторону, то окрестность называется окрестностью Неймана). Значение в следующий момент определяется формулой.

4(i, j, t+l> = F (а (i, j, t) — А* (i, j, t)), (7) где F (0,3)=1- F (l, y)=l, если y=2 или y=3- Fix, y)=0 в остальных случаях.

Эта модель может описывать большой набор стационарных структур (локализованных в пространстве конфигураций, повторяющих себя на каждом шаге) и циклов sp, повторяющих себя через р шагов (см. рис. 2). В ней существуют движущиеся конфигурации: «планер» (см. рис. 2), различные «корабли», «паровоз». Анализ игры «Жизнь» позволил построить конфигурацию «планерное ружье», испускающую поток «планеров» [6,7]. Столкновение «планеров» может приводить к их «аннигиляции», к возникновению стационарных структур или более сложных конфигураций.

Существует предположение, что автоматы четвертого класса эквивалентны универсальным вычислительным машинам. Это свойство доказано для одного одномерного автомата с числом состояний клетки fc=18 [81 и для игры «Жизнь» 17]. Все основные компоненты компьютера могут быть в ней смоделированы с помощью определенных начальных конфигураций. Имеющиеся в ней перемещающиеся объекты — «планеры» — можно использовать для передачи информации, а различные сценарии их столкновений — для реализации логических ill a.

I: 1 t= о t= 5 1 t= 10 i m t= 15 ж t= 20 В.

Рис. 2. Различные конфигурации в игре «Жизнь». Черные квадраты представляют «живые» клетки, белые — «мертвые», а — стационарные структурыб — примеры циклов (чтобы узнать, что будет в следующий момент времени, достаточно заменить левый крайний столбец на средний, а затем средний — на правый крайний) — в — планер. операций. Например, «аннигиляция» планеров может выполнять логическую функцию «НЕ». Роль «часов» < а это важный элемент в вычислительной системе) может играть «планерное ружье», выпускающее планеры с некоторой определенной частотой.

В настоящее время существует три основных направления, по которым развиваются клеточные автоматы [9−101. Объектом исследований первого направления являются сами клеточные автоматы. Здесь рассматриваются вопросы, касающиеся того, как ведут себя автоматы разных классоввводятся различные виды энтропий, размерностей, ляпуновские показатели, изучается устойчивость автоматов к малым возмущениям в начальных данных, проводится аналогия между конфигурациями автоматов и элементами канторова множества, автоматы сравниваются с формальными языками и т. д. Это направление тесно связано с работами известного специалиста по теории клеточных автоматов С. Уолфрема 13−51.

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

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

В последнее время машины клеточных автоматов, т. е. ЭВМ, сконструированные специально для вычислений с помощью клеточных автоматов и по своей архитектуре напоминающие клеточный автомат, получили широкое распространение в научных кругах, использующих идеи клеточных автоматов для решения различного рода проблем. Одной из первых таких машин является машина клеточных автоматов, созданная Т. Тоффоли и Н. Марголусом 1121. По скорости вычислений для моделей, представляющих собой клеточные автоматы, она сравнима с машинами типа Сгау-1.

Итак, два основных достоинства клеточных автоматов с точки зрения вычислительных систем — это локальность взаимодействия и параллельность вычислений. Второе из этих свойств, как мы уже упоминали, делает клеточные автоматы привлекательными для создания современных вычислительных систем с высокой степенью параллельности. С другой стороны, совершенствование ЭВМ идет сейчас по пути увеличения компактности и уменьшения пути прохождения сигнала с целью увеличить скорость вычислений и уменьшить расход энергии. В клеточных автоматах связи между отдельными элементами являются локальными и размеры автомата не зависят от пути прохождения сигнала. Поэтому машины клеточных автоматов могут быть одновременно и очень большими, и очень быстрыми.

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

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

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

4. 4. Выводы.

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

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

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

Гораздо менее очевидной и более любопытной является зависимость среднего времени жизни от числа уровней в организации. При высоком уровне образования оказывается среднее время жизни организации немонотонно зависит от числа иерархических уровней. Есть простое интуитивное соображение, показывающее, почему это может быть так. Отметим, что полностью некомпетентным чаще всего становится самый верхний уровень (начальник организации) или второй сверху (заместители начальника). Пусть Ri — вероятность того, что после очередного замещения вакансии на уровне i на данном месте появился некомпетентный сотрудник, a v — вероятность образования вакансии в каком-либо отделе на уровне с номером i. Тогда вероятность того, что директор организации станет некомпетентным, равна.

Л) j? =? t r1 1-r){l-p)+i?i2(l-r)2(1-р)2+.. .+ п ^ п-1 п-1 п-1 п-1 п-1.

1=1 (1-Я)l (l-P)l](l-F) п-1 п-1 где Р — уровень образования. Из устройства модели следует, что fi^O. Если уровень образования невелик и людей, которые способны руководить, мало, то жизнеспособность иерархии будет определяться тем, успеет ли «талант» (компетентный на всех уровнях сотрудник) добраться до верхнего уровня за время своей работы. Естественно, чем больше уровней в иерархии, тем меньше вероятность этого. Но, с другой стороны, при высоком уровне образования (Р-> 1), Это значит, что последовательность я убывающая. Следовательно, вероятность некомпетентности директора с увеличением п падает, что приводит к увеличению времени жизни организации { «целое» может жить дольше, чем часть). При остальных значениях величины р, характеризующей уровень образования, эта формула заслуживает более внимательного изучения. В частности, вопрос нахождения критического значения уровня образования pfcr, которое меняет характер зависимости времени жизни организации от числа уровней в ней (при Pр — к его увеличению).

ЗАКЛЮЧЕНИЕ

.

В заключение сформулируем основные результаты диссертации.

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

2. Обнаружены новые качественные эффекты при анализе двумерного клеточного автомата, являющегося обощением модели У. Ооно и М. Кохмото. Среди них новый тип спиральных волн и объекты типа «планеров» { передвигающихся локализованных структур).

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

4. Построена новая модель функционирования иерархической организации. В рамках этой модели выяснено, как влияет ее структура и уровень образования сотрудников на деятельность организации.

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