Клеточные автоматы , как и другие модели многоагентных систем , обычно рассматривают время как дискретное, а обновления состояния как происходящие синхронно . Состояние каждой ячейки в модели обновляется вместе, прежде чем какое-либо из новых состояний повлияет на другие ячейки. Напротив, асинхронный клеточный автомат может независимо обновлять отдельные ячейки таким образом, что новое состояние ячейки влияет на вычисление состояний в соседних ячейках.
Реализации синхронного обновления можно проанализировать в два этапа. Первое, взаимодействие, вычисляет новое состояние каждой ячейки на основе соседства и правила обновления. Государственные ценности хранятся во временном хранилище. На втором этапе обновляются значения состояний путем копирования новых состояний в ячейки.
Напротив, асинхронное обновление не обязательно разделяет эти две фазы: в простейшем случае (полностью асинхронное обновление) изменения состояния выполняются немедленно.
Синхронный подход предполагает наличие глобальных часов, чтобы гарантировать одновременное обновление всех ячеек. Хотя это удобно для подготовки компьютерных систем , это может быть нереалистичным предположением, если модель предназначена для представления, например, живой системы, в которой нет доказательств наличия такого устройства.
Общий метод, неоднократно открывавшийся независимо (К. Накамура в 1970-х, Т. Тоффоли в 1980-х и К.Л. Неханив в 1998 г.), позволяет точно имитировать поведение синхронного клеточного автомата с помощью асинхронного, построенного как простой модификация синхронного клеточного автомата (Неханив 2002). Однако правильность этого метода была строго доказана совсем недавно (Неханив, 2004). Как следствие, из результатов по синхронным клеточным автоматам сразу следует, что асинхронные клеточные автоматы способны имитировать, например, Игру жизни Конвея , универсальных вычислений и самовоспроизведения (например, как в универсальном конструкторе фон Неймана).). Более того, общая конструкция и доказательство также применимы к более общему классу сетей синхронных автоматов (неоднородные сети автоматов над ориентированными графами, допускающие внешние входы - в том числе клеточные автоматы как частный случай), конструктивно показывая, как их поведение может быть асинхронным реализуется соответствующей сетью асинхронных автоматов.
Схемы обновления [ править ]
Несколько исследований реализовали асинхронные модели и обнаружили, что их поведение отличается от синхронных. Bersini и Detours (1994) показали, насколько «Игра жизни» Конвея чувствительна к схеме обновления. В асинхронном случае любое интересное поведение исчезает. Харви и Босомайер (1997) указали, что стохастическое обновление в случайных булевых сетях приводит к выражению только точечных аттракторов : нет повторяемого циклического поведения, хотя они ввели понятие свободных циклических аттракторов. Kanada (1994) показал, что некоторые одномерные модели CA, которые генерируют нехаотические паттерны при синхронном обновлении, порождают край хаоса.шаблоны при рандомизации. Орпонен (1997) продемонстрировал, что любая синхронно обновляемая сеть пороговых логических единиц (см. Искусственный нейрон ) может быть смоделирована сетью, которая не имеет ограничений на порядок обновлений. Сиппер и др. (1997) исследовали эволюцию неоднородных центров сертификации, которые выполняют определенные вычислительные задачи. Эти модели ослабляют обычное требование, чтобы все узлы имели одно и то же правило обновления. В их моделях узлы были организованы в блоки. Узлы в блоке обновлялись синхронно, но блоки обновлялись асинхронно. Они экспериментировали с тремя схемами: (1) на каждом временном шаге случайным образом выбирается блок с заменой; (2) на каждом временном шаге блок выбирается случайным образом без замены; (3) на каждом временном шаге блок выбирается в соответствии с фиксированным порядком обновления.
Существуют разные типы асинхронного обновления, и разные авторы описывают их по-разному. Схемы, показанные на изображениях ниже, следующие (Корнфорт и др., 2005):
- Синхронная схема - все ячейки обновляются параллельно на каждом временном шаге. Это обычная модель, указанная здесь для сравнения.
- Случайная независимая схема - на каждом временном шаге ячейка выбирается случайным образом с заменой и обновляется.
- Схема случайного порядка - на каждом временном шаге все узлы обновляются, но в случайном порядке.
- Циклическая схема - на каждом временном шаге узел выбирается в соответствии с фиксированным порядком обновления, который был выбран случайным образом во время инициализации модели.
- Схема самосинхронизации - каждая ячейка имеет независимый таймер, инициализированный случайным периодом и фазой. Когда период истек, ячейка обновляется и таймер сбрасывается. Обновление является автономным и выполняется с разной скоростью для разных ячеек.
- Схема самосинхронизации - такая же, как схема с синхронизацией, но на фазу таймеров влияет локальная связь с соседями, и поэтому они могут достигать локальной синхронизации.
Диаграммы времени-состояния ниже показывают различия, вызванные изменением схемы обновления модели клеточного автомата без изменения каких-либо других параметров. Используемое правило, правило 30 , одинаково для каждой диаграммы.
| Исходное правило 30 | Правило 30 обновляется случайным образом |
| Правило 30 обновляется в случайном порядке. | Правило 30 обновляется в циклическом порядке |
| Правило 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), Экскурсия по асинхронным клеточным автоматам, Журнал клеточных автоматов : 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.
- Виртуальная лаборатория Университета Монаша Онлайн-моделирование асинхронного обновления в клеточных автоматах.
