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

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

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

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

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

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


Схемы обновления

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

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

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

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

Rule30 sync.png
Rule30 RAI.png
Исходное правило 30 Правило 30 обновляется случайным образом
Rule30 RAO.png
Rule30 cyclic.png
Правило 30 обновляется в случайном порядке Правило 30 обновляется в циклическом порядке
Rule30 clock.png
Rule30 self.png
Правило 30 с автоподстройкой частоты Самосинхронное правило 30

Последствия

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

Ссылки

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