Материал: patrakeev_im_geoprostranstvennye_tekhnologii_v_modelirovanii
|
|
|
|
|
|
0,1 |
|
|
|
|
|
|
|
-1,1 |
0,1 |
1,1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
-1,0 |
|
0,0 |
|
1,0 |
|
|
|
|
-1,0 |
0,0 |
1,0 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,-1 |
|
|
|
|
|
|
-1,-1 |
0,-1 |
1,-1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Хн |
|
|
|
|
|
|
|
|
Хм |
|
|
|
|
|
|
|
|
а) |
|
|
|
|
|
|
|
|
б) |
|
|
Рис. 3.2 – Шаблоны соседства Джон фон Неймана (а) и Э.Ф. Мура (б) |
|||||||||||||||||
|
|
|
Таким образом, непосредственными соседями единичного автомата |
||||||||||||||
z |
|
|
Z 2 |
являются |
автоматы |
z + |
x1, z + |
x2, …, |
z + xn, где |
||||||||
|
|||||||||||||||||
|
|
||||||||||||||||
|
|
||||||||||||||||
Х = {x1, x2, |
…. , |
xn}; |
хj |
|
Z2 (j = 1…. |
n). Индекс соседства Х описывает |
|||||||||||
|
|||||||||||||||||
единый шаблон соседства (ШС – |
единый геометрический образ соседей- |
||||||||||||||||
автоматов) для каждого единичного z-автомата структуры. ШС так же определяет позиции автоматов-соседей относительно каждого конкретного единичного автомата, который имеет с ними непосредственный информационный интерфейс. Если индекс соседства Х содержит элемент 0d = {0, 0, 0, …., 0}, то каждый единичный автомат структуры принадлежит собственному ШС. Не нарушая общности, можно
предположить, что Х-индекс соседства |
содержит 0d – элемент, |
определяющий центральный автомат ШС. |
|
В литературе доказано [1,2], что динамика d-ОС (d ≥ 1) не зависит от выбора в качестве центрального любого автомата ШС структуры. Таким образом, деление d-ОС на структуры с ярко выраженным градиентом передачи информации, обусловленным выбором центрального автомата шаблона соседства, не изменяет динамических и вычислительных возможностей ОС-моделей во временном отношении, хотя и влияет на их конструктивные характеристики, то есть на характеристики, зависящие от
геометрии пространства структуры. |
|
Например, 1-ОС с индексами соседства Х = {-k, …, -1, 0, 1, …, |
p} |
при k, p 
{0, 1, …., n-1} и определяющем соотношении p + k +1 = n в динамическом отношении строго эквивалентны друг другу, то есть на каждый шаг моделируемой 1-ОС с индексом Х из указанного класса требуется только один шаг моделирующей ее 1-ОС с индексом соседства из того же класса Х.
Среди шаблонов соседства (ШС) различают связные и несвязные, этот показатель в общем случае существенно влияет на динамику ОС-моделей.
66
ШС называется связным, если занимаемая им область связана в топологическом смысле, иначе шаблон соседства называется несвязным.
Так, например, две 1-ОС с индексами соседства Х1 = {0, 1, 2, 3, 4, 5, 6, 7} и Х2 = {0, 1, 2, 4, 5,7, 8, 10} имеют связный и несвязный ШС
соответственно (рис. 3.3), что даже для случая идентичных локальных функций перехода может приводить к различиям в их динамике.
Первые три рассмотренные компоненты d-ОС, а именно: А-алфавит состояний единичных автоматов, однородное пространство Zd структуры и Х-индекс соседства образуют однородную среду, которая является статической составляющей ОС-модели. Статическая часть описывает лишь физическую организацию структуры и ее геометрию, но не описывает взаимодействие (динамику) между единичными автоматами. Для задания функционирования d-ОС необходима возможность описывать текущие состояния всех единичных автоматов в любой дискретный момент времени t ≥ 0.
Набор текущих состояний всех единичных автоматов называется конфигурацией d-ОС ( КФ ). А именно, конфигурация d-ОС есть произвольное отображение КФ : Zd → A. Множество всевозможных кофигураций относительно Z d и A обозначим как С(А, d), то есть можно записать тождество:
С(А, d) = { КФ | КФ : Z d → A}
Функционирование d-ОС осуществляется в дискретной шкале времени t = 0,1, …. и определяется локальной функцией перехода (ЛФП) τ(n) , которая задает состояние каждому единичному автомату структуры в момент времени t на основе состояний всех соседних ему автоматов в момент времени (t-1). Для классических ОС- моделей ЛФП представляются в виде:
τ(n)(а1,а2, ….., |
аn); а j, а *1 A (j = 1…. n) |
(3.1) |
а 1, а 2 ,…., |
а n → а *1 - множество параллельных подстановок, |
(3.2) |
где а j – состояние любого z-автомата d-ОС и его соседей (согласно индекса соседства Х = {x1, x2, …., xn}) в момент времени (t-1), а а *1 – состояние этого же автомата в следующий момент времени t > 0. При этом z-автомат ОС-структуры предполагается центральным относительно приписываемого ему шаблона соседства (ШС).
67
Вход
а) |
1 |
2 |
3 |
4 |
Выход |
|
|
|
|
5 |
6 |
7 |
8 |
9 |
10 |
Вход
б) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Выход
Рис. 3.3 – Схема непосредственного информационного обмена в связном (а) и несвязном (б) шаблонах соседства (ШС) одномерной структуры
Наиболее удобным является формальное представление ЛФП когда вычисление последующего состояния текущего z-автомата структуры выполняется по формуле (3.1). В целом ряде случаев обязательно требуется использование ЛФП в виде множества параллельных подстановок (3.2).
t |
……….. |
1 1 0 |
1 |
0 |
2 |
3 |
2 2 1 3 3 ………. |
: Ω |
|
|
|
|
|
|
|
|
|
|
|
|
↓ |
|
|
|
|
|
|
|
|
|
|
|
|
|
: Ω* |
t+1 |
……….. |
|
2 |
|
|
|
………. |
|
|
|
|
|
z- выделенный автомат структуры |
|
|||
Множество параллельных подстановок определяют программу (параллельный алгоритм) функционирования классической ОС-модели. Параллельные подстановки представляют собой низкоуровневый параллельный язык программирования в среде ОС-моделей.
Формульное представление ЛФП особенно предпочтительно при компьютерной реализации ОС-моделей. Вопросы формального представления ЛФП достаточно подробно изложены в монографиях [3, 4].
Вышеперечисленные три черты (однородность, параллелизм, локальность взаимодействия) обеспечиваются уже самой ОС-аксиоматикой. В свете перечисленных свойств, классические ОС являются высоко абстрагированными моделями реального физического мира, функционирующими во времени и пространстве. Поэтому классические ОС лучше (чем другие формальные архитектуры) приспособлены для решения задач моделирования сложных динамических систем. Все вышесказанное, а также имеющиеся на сегодня многочисленные примеры позволяют сделать вывод, что ОС могут
68
представлять довольно существенный интерес как в качестве новой перспективной среды моделирования так и исследования многих дискретных процессов, явлений и феноменов.
Завершая изложение базовых элементов ОС, необходимо отметить, что в настоящее время теория ОС находится в стадии довольно интенсивного развития и дальнейшая работа в данном направлении черезвычайно важна с различных точек зрения, учитывая междисциплинарный характер общей ОС-концепции [4].
3.2 Типы классических однородных структур и отношения между типами. Понятие мелкозернистого параллелизма
Большое разнообразие модификаций однородных структур, предназначенных для моделирования пространственной динамики, привело к появлению понятия мелкозернистого параллелизма, который объединил в себе все модели клеточных автоматов на основе двух свойств:
-итерационный процесс вычисления новых состояний клеток;
-локальность межклеточных взаимодействий, когда каждая клетка вычисляет функцию перехода, используя в качестве переменных состояний ограниченного числа близлежащих клеток.
Все однородные структуры подразделяются на бесконечные и конечные. При этом, конечные ОС-модели представляют собой обычные конечные автоматы, которые имеют специфическую клеточную организацию, характеризующуюся набором конечного количества взаимосвязанных идентичных единичных автоматов, которые функционируют синхронно или асинхронно согласно заданным локальным функциям переходов и индексом состояния, а также граничным условиям.
Однако, клеточная организация таких клеточных автоматов и принцип их функционирования способствуют появлению у них качественно новых свойств, недоступных конечным автоматам традиционной организации. Прежде всего это относится к их возможности выполнять параллельную обработку информации и вычисления, а также более адекватно моделировать множество естественных и искусственных процессов, объектов, явлений и феноменов, характеризующихся ярко выраженным коллективным поведением.
Бесконечные ОС представляют собой бесконечные клеточные автоматы, состоящие из бесконечного числа локально взаимосвязанных между собой единичных идентичных автоматов, чья глобальная динамика
69
определяется локальными взаимодействиями всех соседних (согласно индексу соседства) автоматов. При определенной степени абстрагирования бесконечные ОС можно ассоциировать с некоторыми моделями абстрактных вселенных, динамика которых определяется их внутренними законами развития. Такого типа ОС-модели оказываются удобными в случаях, когда требуется исследовать динамику поведения процессов и феноменов в основе которых лежат принципы дискретности, локальности взаимодействий, обратимости. Подобные модели могут с успехом применяться в таких областях, как теория эволюции и развития, информатика, кибернетика, синергетика, искусственный интеллект и др.
Таким образом, конечные ОС используются в качестве моделей некоторого объекта, бесконечные структуры представляют собой саму среду моделирования, в которую погружается та или иная исследуемая модель.
На множество состояний каждой клетки не накладывается никаких ограничений. Состояние может описываться булевыми значениями, целочисленными, вещественными и символьными. Более того, модели, основанные на клеточных автоматах, могут иметь не только синхронный режим смены состояний клеточных автоматов, но и асинхронный. Асинхронный режим предполагает, что смена состояний клеточных автоматов происходит не одновременно в момент времени (t+1), а в любом порядке. Этот порядок может быть случайным или заранее заданным. Для моделирования пространственной динамики во многих случаях используются вероятностные ОС, а также ОС с самыми разными локальными функциями переходов.
Отношения между типами КОС, которые различаются алфавитами, типами локальных функций переходов показано на рис. 3.4.
Что наша жизнь ….. игра.
3.3 Моделирование на основе однородных структур: игра Дж. Конвея «Life»
В качестве примера рассмотрим известную игру «Life», впервые опубликованную в американском журнале «Scientific American» за февраль 1971 г. Игра Дж. Конвея «Life» вызвала большой интерес целого ряда исследователей. Однако изучение однородных структур не получило своего развития до 90-х годов прошлого века до тех пор пока
70