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

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

Еще в 1970 году А.Н. Колмогоровым давался прогноз, что с "развитием современной вычислительной техники будет во многих случаях разумно изучение реальных явлений вести, избегая промежуточный этап их стилизации в духе математики бесконечного и непрерывного, переходя прямо к дискретным моделям". Сейчас уже можно с уверенностью сказать, что этот прогноз сбылся, так как появилось большое количество разнообразных математических систем, основанных на принципе мелкозернистого параллелизма, и, самое главное, появились программные и аппаратные комплексы, способные моделировать работу таких систем.

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

Классической системой с мелкозернистым параллелизмом является клеточный автомат, а игра Джона Конвея "Жизнь" - типичный пример клеточного автомата, представляющего собой дискретную динамическую систему. Клеточные автоматы фактически являются синтетическими мирами, поведение которых определяется простыми локально действующими правилами. В этих мирах пространство представляет собой равномерную сетку, каждая ячейка которой (клетка) содержит информацию о своем состоянии. Изменение времени происходит дискретно, а законы такого мира представляют собой небольшое количество правил, основные из которых описываются таблицей переходов, по которой клетка вычисляет свое новое состояние на каждом такте (минимальный отрезок времени) на основе своего состояния и состояний ее соседей.

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

Познакомимся подробнее с игрой "Жизнь", относящейся к категории так называемых моделирующих игр - игр, которые в той или иной степени имитируют процессы, происходящие в реальной жизни. Жизнь, как естественный процесс - явление настолько сложное и увлекательное, что тысячи ученых пытались раскрыть ее тайны. Свой вклад в решение этой проблемы внес и человек, не имевший к биологии никакого отношения, английский математик Джон Хортон Конвей.

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

Действие игры происходит на плоскости, разделенной на клетки. Каждая клетка окружена 8 такими же клетками (так называемая окрестность Мура) и может находиться в двух состояниях - живом или мертвом (быть пустой). Гибель и рождение всех организмов происходит одновременно. На состояние любой клетки оказывают влияние только состояния соседних с ней клеток. Во времени эти состояния дискретно изменяются в соответствии со следующими правилами (генетическими законами Конвея).

1. Выживание или гибель. Если живая клетка имеет менее 2 или более 3 соседей в окрестности из 8 клеток, то в следующем поколении она умирает (моделирование реальных условий - недостатка питания или перенаселенности), в противном случае она выживает.
2. Рождение. В пустой клетке появляется новая живая клетка, если у нее ровно 3 соседа.

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

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

Познать "Жизнь" на практике проще всего с помощью листа бумаги в клеточку и ручки. Можно воспользоваться также шахматной доской и обычными шашками двух цветов. Еще проще - использовать для этой цели компьютер. Уже на заре развития компьютерной техники были написаны многочисленные программы, моделирующие "Жизнь".

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

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

Более подробную информацию о игре "Жизнь" и программы для наблюдения за эволюцией объектов можно найти по следующему URL: elvisti.kiev.ua/skl/conwey1/w_life_n.htm.

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

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

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

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

Задания
1. Постройте модель процесса распространения инфекции стригущего лишая по участку кожи размером n x n (n-нечетное) клеток. Заражение начинается с центральной клетки. В каждый интервал времени пораженная инфекцией клетка может с вероятностью 1/2 заразить любую из соседних здоровых клеток. Через шесть единиц времени зараженная клетка становится невосприимчивой к инфекции. Возникший иммунитет действует в течение последующих четырех единиц времени, а затем клетка выздоравливает.

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

2. Разработайте имитационную модель системы "хищник-жертва" по следующей схеме. Остров размером 20x20 заселен дикими кроликами, волками и волчицами. Имеется несколько представителей каждого вида. Кролики довольно глупы: в каждый момент времени они с одинаковой вероятностью 1/9 передвигаются в один из восьми соседних квадратов (за исключением участков, ограниченных береговой линией) или просто сидят неподвижно. Каждый кролик с вероятностью 0,2 превращается в 2 кроликов. Волчицы передвигаются случайным образом до тех пор, пока в одном из соседних восьми квадратов не окажется кролик. Если волчица и кролик оказываются в одном квадрате, волчица съедает кролика и получает одно очко, в противном случае она теряет 0,1 очка за каждую единицу времени. Волки и волчицы с нулевым количеством очков умирают. В начальный момент времени все волки и волчицы имеют 1 очко. Волк ведет себя подобно волчице до тех пор, пока в соседних квадратах не исчезнут все кролики; в этом случае, если волчица находится в одном из восьми ближайших квадратов, волк гонится за ней. Если волк и волчица окажутся в одном квадрате, они производят потомство случайного пола. Проследите, как сказываются на эволюции популяции изменение различных параметров модели.