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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ и науки Украины

украинский  Государственный химико-технологический  университет

 

Факультет биотехнологии, компьютерных наук и инженерии

 

Кафедра КТВМ

 

 

 

 

 

КУРСОВАЯ  РАБОТА

 

по дисциплине: Моделирование  систем

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

 

 

 

 

                                                                             Работа выполнена

                                                                             студентом  УДХТУ

                                                                             Пришко Ю.В.

                                                                             гр. 3-СКС-5, 3 курс

 

 

                                                                             Научный руководитель:

                                                                             старший преподаватель

                                                                             Рогоза Б.Е.

 

 

 

 

 

 

 

 

 

 

Днепропетровск

2012

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ и науки Украины

украинский  Государственный химико-технологический  университет

 

Факультет биотехнологии, компьютерных наук и инженерии

 

 

 

                                                                                  УТВЕРЖДАЮ:

                                                                                  старший преподаватель

 

                                                                                  __________ Рогоза Б.Е. 

 

 

ЗАДАНИЕ

на курсовую работу по дисциплине

 

“Моделирование систем” 

 

Студенту: Пришко Ю.В. 3-СКС-5 группы 3 курса  факультета БТКНиИ специальности  220400

 

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

 

Содержание работы:

Задача 1. Провести реализацию клеточного автомата в Matlab.

 

Срок выполнения проекта: с __ . __ . 2012 г.   по __ . __ . 2012 г.

Срок защиты:  __ . __ . 2012г.

Дата выдачи задания: __  . __ . 2012г.

Дата сдачи проекта на кафедру: __ . __ . 2012г.

 

Руководитель проекта: старший преподаватель Рогоза Б.Е.

 

Задание принял студент __________________ дата  __ . __ . 2012 г.

 

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ……………………………………………………………………….	4
1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ  …………………………………………………..	5
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ…………………………………….............	5
СВОЙСТВА И КЛАССИФИКАЦИЯ КЛЕТОЧНЫХ АВТОМАТОВ…………………………………………………………………….	6
МОДЕЛИРОВАНИЕ КЛЕТОЧНЫХ АВТОМАТОВ …………………….	8
ИГРА «ЖИЗНЬ»……………………………………………………………..	16
ПРАКТИЧЕСКАЯ  ЧАСТЬ. МОДЕЛИРОВАНИЕ ПЛАНЕРНОГО РУЖЬЯ ГОСПЕРА (GOSPER’S GLIDER GUN)……………………………….	30
ВЫВОДЫ………………………………………………………………………	32
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ…………………………..	33

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

Термин «клеточные автоматы»  начал использоваться в середине XX века для обозначения совокупности зависимых элементов с заданными состояниями и правил, согласно которых состояния этих элементов и зависимости между ними изменяются во времени. Время и состояния при этом дискретные. Использование описанных моделей для формального моделирования самовоспроизводящихся организмов впервые предложено в работе Фон Неймана. Элементы клеточных автоматов предложено представить одномерными или двухмерными бесконечными прямоугольными таблицами. Состояние элемента изменяется в зависимости от его состояния и от состояния двух  (или четырёх − для двухмерного случая) ближайших соседей. 

Клеточные автоматы в силу своей дискретности  сравнительно просто моделируются с помощью  ЭВМ и благодаря этому, в 50-70-е гг.. XX века приобретают популярность. Исследователи разных научных областей изучают и используют клеточные автоматы с разнообразными особенностями для разных целей. В это время выходят основные труды, которые заложили базис для общей теории клеточных автоматов. 

Примерно в это же время появились игры для клеточных автоматов − математические модели,  которые имеют в основании игровое описание. Например, игра «Firing Squad» − задание про одновременный залп всего пушечного склада имеет в основе важную задачу синхронизации, а игра «Game of Life» является моделью поведения популяции в однородном окружении.

 Начиная с 80-х гг.. XX века изучение клеточных автоматов приобрело более специализированный оттенок. На базе общей теории создаются и изучаются разные конфигурации клеточных автоматов для конкретных исследовательских областей.  Благодаря разносторонним исследованиям, удалось создать мощную математическую теорию, направленную на классификацию и изучение особенностей  разных моделей.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. ТЕОРЕТИЧЕЧКАЯ ЧАСТЬ

 

1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

 

Клеточный автомат К есть упорядоченное множество из четырех компонент

 где

  − множество d-мерных векторов с целочисленными координатами − клеточное пространство;

 N − конечное множество мощности m векторов из :

 

с нулевым вектором − шаблон соседства клетки;

А − конечное множество мощности k состояний клетки с выделенным состоянием покоя;

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

 

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

Одномерные (d = 1) клеточные автоматы, у которых m = 2 или к = 2, будем называть ординарными.

Клеточный автомат K* моделирует поведение клеточного автомата K с замедлением n, если для любой эволюции допускаемой клеточным автоматом K, существует гомоморфизм E*, причем такой, что При n = 1 будем говорить, что моделирование осуществляется в реальном времени.

Пусть задана машина Тьюринга

где

Z − одномерное целочисленное пространство − лента; S — конечное множество символов, включая пустой Ø − алфавит машины; Q – конечное множество состояний машины;  − трехэлементное множество, элементы которого соответствуют направлениям перемещения по ленте; − функция переходов, определенная в дискретные моменты времени:

 

Отображение   задает конфигурацию машины Тьюринга на момент t, а кортеж   определяет эволюцию машин Тьюринга. Множество всех возможных эволюции машины Тьюринга обозначим через W. Будем говорить, что клеточный автомат K моделирует машину Тьюринга MT, если существует гомоморфизм

Если клеточный автомат  моделирует универсальную машину Тьюринга то   будем называть универсальным.

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

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

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

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

Клеточные автоматы в общем  случае характеризуются следующими свойствами.

1. Изменения значений всех клеток происходят одновременно после вычисления нового состояния каждой клетки решетки.

2. Решетка однородна. Невозможно отличить никакие два места на решетке по ландшафту.

3. Взаимодействия локальны. Лишь клетки окрестности (как правило, соседние) способны повлиять на данную клетку.

4. Множество состояний клетки конечно.

 

2. СВОЙСТВА И КЛАССИФИКАЦИЯ КЛЕТОЧНЫХ АВТОМАТОВ

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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 :