Повна версія

Головна arrow Інформатика arrow Моделирование сложных сетей

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

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

Концепция клеточных автоматов была впервые предложена больше полстолетия тому назад Дж. Фон Нейманом (J. Von Neumann) и развита С. Вольфрамом (S. Wolfram) в фундаментальной монографии "Новый вид науки".

Дж. Фон. Нейман (1903-1957)

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

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

Нейман Дж. Теория самовоспроизводящихся автоматов. - М.: Мир, 1971. - 382 с.

Клеточный автомат представляет собой дискретную динамическую систему, совокупность одинаковых клеток, одинаковым образом соединенных между собой. Все клетки образуют сеть (решетку) клеточных автоматов. Состояние каждой клетки определяются состоянием клеток, входящих в ее локальную окрестность и называемых ближайшими соседями. Окрестностью клетки с номером ] - 0( /) называется множество его ближайших соседей. Состояние ] -й клетки в момент времени t +1 определяется некоторым правилом Г, которое можно выразить, например, языком булевой алгебры:

у^ +1) = Г(у, 0(& ^ . (3.9.1)

C. Вольфрам

Wolfram S. A New Kind of Science. Champaign, IL: Wolfram Media Inc., 2002. Wolfram S. ed. Theory and Applications of Cellular Automats. Singapore: World Scientific. 1986. Тоффоли Т., Марголус Н. Машины клеточных автоматов. - М.: Мир, 1991.

Во многих задачах считается, что сама клетка относится к своим ближайшим соседям, т.е. є 0(j), в этом случае формула упрощается: у](ґ +1) = ¥(0(]), ґ). Клеточные автоматы удовлетворяют таким

правилам:

  • - изменение значений всех клеток происходит одновременно (единица измерения - такт);
  • - сеть клеточных автоматов однородная, т.е. правила изменения состояний для всех клеток одинаковые;
  • - на клетку могут повлиять лишь клетки из ее локальной окрестности;
  • - множество состояний клетки конечное.

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

В случае двумерной решетки, элементами которой являются квадраты каждую клетку удобно задавать двумя индексами - у у.

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

Можно добавить и диагональные элементы - окрестность Мура (G. Moore):

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

Это позволяет определять общее соотношение значения клетки на шаге £ +1 по сравнению с шагом t:

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

При этом: 1) каждая клетка может находиться в двух состояниях: 1 -новинка принята; 0 - новинка не принята. 2) автомат, восприняв инновацию один раз, запоминает ее навсегда (состояние 1, которое не может быть измененным). 3) автомат одобряет решение относительно принятии новинки, ориентируясь на мнение восьми ближайших соседей, т.е. если в окрестности данной клетки

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

Bhargava S.C., Kumar A., Mukherjee A. A stochastic cellular automata model of innovation diffusion. Technological forecasting and social change, 1993. - Vol. 44. - № 1. - pp. 8797.

В модели диффузии информации предполагалось, что клетка может быть в одном из трех состояний: 1 - "свежая новость" (клетка окрашивается в черный цвет); 2 - новость, которая устарела, но сохраненная в виде сведений (серая клетка); 3 - клетка не имеет информации, переданной новостным сообщением (клетка белая, информация не дошла или уже забыта). В модели приняты такие правила распространения сообщений:

  • — сначала все поле состоит из белых клеток за исключением одной, черной, которая первой "приняла" новость (рис. 3.9.1 а);
  • — белая клетка может перекрашиваться только в черный цвет или оставаться белой (она может получать новость или оставаться "в неведении");
  • — белая клетка перекрашивается, если выполняется условие, аналогичное модели диффузии инноваций:

рт > 1 (это условие модифицируется для т ˂ 2: 1.5 • рт > 1);

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

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

Процесс эволюции системы клеточных автоматов

Рис. 3.9.1 - Процесс эволюции системы клеточных автоматов "диффузии новостей": а - исходное состояние; б-д -промежуточные состояния; е - конечное состояние

Типичные зависимости количества клеток, которые находятся в разных состояниях в зависимости от шага итерации приведены на рис. 3.9.2. При этом, очевидно, суммарное количество клеток, которые находятся во всех трех состояниях на каждом шагу итерации постоянно и равно количеству клеток, а при стабилизации системы клеточных автоматов соотношения серых, белых и черных клеток приблизительно составляет: 3:1:0.

Количество клеток каждого из цветов в зависимости от шага эволюции: белые клетки - (+); серые клетки - (•); черные клетки - (■)

Рис. 3.9.2 - Количество клеток каждого из цветов в зависимости от шага эволюции: белые клетки - (+); серые клетки - (•); черные клетки - (■)

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

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

Соответственно, динамика белых клеток хк (количество клеток в момент £) может моделироваться "перевернутой" функцией хв с аналогичными параметрами:

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

где хь - количество черных клеток в момент времени £. Таким образом, получаем:

Вид представленной на рис. 55 зависимости позволяет предположить, что в качестве функции /(^т^) может быть

выбрано следующее выражение (логистическая функция):

где С - некоторая нормирующая константа.

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

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

Непрерывные зависимости, полученные в результате аналитического моделирования, в зависимости от шага эволюции: сплошная линия - серые (хg); пунктирная линия - белые (хw); сплошная жирная линия - черные (хь )

Рис. 3.9.3 - Непрерывные зависимости, полученные в результате аналитического моделирования, в зависимости от шага эволюции: сплошная линия - серые (хg); пунктирная линия - белые (хw); сплошная жирная линия - черные (хь )

 
<<   ЗМІСТ   >>