Асинхронный клеточный автомат

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

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

Напротив, асинхронное обновление не обязательно разделяет эти две фазы: в простейшем случае (полностью асинхронное обновление) изменения состояния реализуются немедленно.

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

Общий метод, неоднократно открытый независимо (К. Накамура в 1970-е гг., Т. Тоффоли в 1980-е гг. и К. Л. Неханив в 1998 г.), позволяет точно эмулировать поведение синхронного клеточного автомата через асинхронный, построенный как простой модификация синхронного клеточного автомата (Неханив 2002). Однако правильность этого метода была строго доказана совсем недавно (Неханив, 2004). Как следствие, из результатов по синхронным клеточным автоматам непосредственно следует, что асинхронные клеточные автоматы способны эмулировать, например, « Игру жизни» Конвея , универсальные вычисления и самовоспроизведение (например, как в универсальном конструкторе Фон Неймана ).Более того, общая конструкция и доказательство также применимы к более общему классу сетей синхронных автоматов (неоднородные сети автоматов над ориентированными графами, допускающими внешние входы, включая клеточные автоматы как частный случай), конструктивно показывая, как их поведение может быть асинхронным. реализуется соответствующей сетью асинхронных автоматов.

Обновление схем

В нескольких исследованиях были реализованы асинхронные модели и обнаружено, что их поведение отличается от синхронных. Берсини и Объезды (1994) показали, насколько чувствительна «Игра жизни» Конвея к схеме обновления. Любое интересное поведение исчезает в асинхронном случае. Харви и Боссомайер (1997) отметили, что стохастическое обновление в случайных логических сетях приводит к выражению только точечных аттракторов : повторяемого циклического поведения не существует, хотя они и ввели концепцию свободных циклических аттракторов. Канада (1994) показала, что некоторые одномерные модели CA, которые генерируют нехаотические закономерности при синхронном обновлении, генерируют границы хаоса при рандомизации . Орпонен (1997) продемонстрировал, что любая синхронно обновляемая сеть пороговых логических единиц (см. Искусственный нейрон ) может быть смоделирована сетью, которая не имеет ограничений на порядок обновлений. Сиппер и др. (1997) исследовали эволюцию неоднородных центров сертификации, выполняющих конкретные вычислительные задачи. Эти модели ослабляют обычное требование, чтобы все узлы имели одно и то же правило обновления. В их моделях узлы были организованы в блоки. Узлы внутри блока обновлялись синхронно, но блоки обновлялись асинхронно. Они экспериментировали с тремя схемами: (1) на каждом временном шаге блок выбирается случайным образом с заменой; (2) на каждом временном шаге блок выбирается случайным образом без замены; (3) на каждом временном шаге блок выбирается в соответствии с фиксированным порядком обновления.

Существуют разные типы асинхронного обновления, и разные авторы описывают их по-разному. Схемы, показанные на изображениях ниже, следующие (Cornforth et al. 2005):

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

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


Исходное правило 30	Правило 30 обновляется случайным образом

Правило 30 обновляется в случайном порядке	Правило 30 обновляется в циклическом порядке.

Правило 30 самосинхронизации	Правило самосинхронности 30

Подразумеваемое

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

Ссылки

Х. Берсини и В. Детурс, 1994. Асинхронность вызывает стабильность в моделях на основе клеточных автоматов, Труды IV-й конференции по искусственной жизни , страницы 382-387, Кембридж, Массачусетс, июль 1994 г., том 204, вып. 1–2, стр. 70–82.
Корнфорт, Д., Грин, Д., и Ньют, Д. 2005, Упорядоченные асинхронные процессы в многоагентных системах, Physica D , том 204, вып. 1–2, стр. 70–82.
Корнфорт Д., Грин Д.Г., Ньют Д. и Кирли М. 2002, Маршируют ли искусственные муравьи в ногу? Упорядоченные асинхронные процессы и модульность в биологических системах . В Стэндиш, Бедау, Аббасс, Труды Восьмой Международной конференции по искусственной жизни , Сидней, стр. 28-32.
Фатес Н., (2014), Экскурсия по асинхронным клеточным автоматам, Journal of Cellular Automata : Vol. 9(5-6), стр. 387-416, препринт
Фатес Н. и Морван М. (2005), Экспериментальное исследование устойчивости к асинхронизму элементарных клеточных автоматов, Сложные системы : Том 16 / Выпуск 1, стр. 1–27.
Фатес Н., Морван М., Н. Шабанель и Э. Тьерри (2006), Полностью асинхронное поведение элементарных клеточных автоматов с двойным состоянием покоя, Теоретическая информатика : Том 362, стр. 1–16.
Харви И. и Боссомайер Т.Р.Дж. (1997). Время вне соединения: аттракторы в асинхронных логических сетях. В «Мужьях и Харви» (ред.), «Материалы четвертой европейской конференции по искусственной жизни» , 67–75, MIT Press .
Канада Ю. (1994). Эффекты случайности в асинхронных одномерных клеточных автоматах . Искусственная жизнь IV .
Неханив, CL (2002). Эволюция асинхронных клеточных автоматов, Искусственная жизнь VIII , 65–73, MIT Press.
Неханив, CL (2004). Сети асинхронных автоматов могут имитировать любую сеть синхронных автоматов, Международный журнал алгебры и вычислений , 14(5-6):719-739.
Орпонен, П. (1997). Вычисления с использованием истинно асинхронных сетей пороговой логики. Теоретическая информатика 174(1-2):123-136.
Сиппер М., Томассини М. и Капкарре М.С. (1997). Развитие асинхронных и масштабируемых неоднородных клеточных автоматов. Учеб. международного Конф. по искусственным нейронным сетям и генетическим алгоритмам (ICANNGA97) , Springer-Verlag.
Виртуальная лаборатория Университета Монаша Онлайн-моделирование асинхронного обновления в клеточных автоматах.