Los autómatas celulares , al igual que con otros modelos de sistemas de agentes múltiples , generalmente tratan el tiempo como discretas y las actualizaciones de estado como si se produjeran de forma sincrónica . El estado de cada celda del modelo se actualiza en conjunto, antes de que cualquiera de los nuevos estados influya en otras celdas. Por el contrario, un autómata celular asíncrono es capaz de actualizar celdas individuales de forma independiente, de tal manera que el nuevo estado de una celda afecta el cálculo de estados en celdas vecinas.
Las implementaciones de actualización síncrona se pueden analizar en dos fases. La primera, interacción, calcula el nuevo estado de cada celda en función de la vecindad y la regla de actualización. Los valores estatales se guardan en una tienda temporal. La segunda fase actualiza los valores de estado copiando los nuevos estados en las celdas.
Por el contrario, la actualización asincrónica no necesariamente separa estas dos fases: en el caso más simple (actualización totalmente asincrónica), los cambios de estado se implementan inmediatamente.
El enfoque síncrono asume la presencia de un reloj global para garantizar que todas las celdas se actualicen juntas. Si bien es conveniente para preparar sistemas informáticos , esto podría ser una suposición poco realista si el modelo pretende representar, por ejemplo, un sistema vivo donde no hay evidencia de la presencia de tal dispositivo.
Un método general descubierto repetidamente de forma independiente (por K. Nakamura en la década de 1970, por T. Toffoli en la década de 1980 y por CL Nehaniv en 1998) permite emular exactamente el comportamiento de un autómata celular sincrónico a través de uno asincrónico construido como un simple modificación del autómata celular síncrono (Nehaniv 2002). Sin embargo, la exactitud de este método sólo ha sido probada rigurosamente más recientemente (Nehaniv, 2004). Como consecuencia, se deduce inmediatamente de los resultados de los autómatas celulares sincrónicos que los autómatas celulares asincrónicos son capaces de emular, por ejemplo, el Juego de la vida de Conway , de computación universal y de autorreplicación (por ejemplo, como en un constructor universal de Von Neumann ). Además, la construcción general y la prueba también se aplican a la clase más general de redes de autómatas síncronos (redes no homogéneas de autómatas sobre gráficos dirigidos, que permiten entradas externas, lo que incluye a los autómatas celulares como un caso especial), mostrando de manera constructiva cómo su comportamiento puede ser asincrónico. realizado por una red de autómatas asincrónica correspondiente.
Actualizar esquemas
Varios estudios han implementado modelos asincrónicos y han encontrado que su comportamiento difiere de los síncronos. Bersini y Detours (1994) han demostrado cuán sensible es el Juego de la vida de Conway al esquema de actualización. Cualquier comportamiento interesante desaparece en el caso asincrónico. Harvey y Bossomaier (1997) señalaron que la actualización estocástica en redes booleanas aleatorias da como resultado la expresión de atractores puntuales únicamente: no hay comportamiento cíclico repetible, aunque introdujeron el concepto de atractores cíclicos sueltos. Kanada (1994) ha demostrado que algunos modelos CA unidimensionales que generan patrones no caóticos cuando se actualizan sincrónicamente generan patrones de borde de caos cuando se aleatorizan. Orponen (1997) ha demostrado que cualquier red actualizada sincrónicamente de unidades lógicas de umbral (ver Neurona artificial ) puede ser simulada por una red que no tiene restricciones en el orden de las actualizaciones. Sipper y col. (1997) investigó la evolución de CA no uniformes que realizan tareas informáticas específicas. Estos modelos relajan el requisito normal de que todos los nodos tengan la misma regla de actualización. En sus modelos, los nodos se organizaron en bloques. Los nodos dentro de un bloque se actualizaron de forma sincrónica, pero los bloques se actualizaron de forma asincrónica. Experimentaron con tres esquemas: (1) en cada paso de tiempo, se elige un bloque al azar con reemplazo; (2) en cada paso de tiempo, se elige un bloque al azar sin reemplazo; (3) en cada paso de tiempo, se elige un bloque de acuerdo con un orden de actualización fijo.
Existen diferentes tipos de actualización asincrónica y diferentes autores las han descrito de diferentes maneras. Los esquemas que se muestran en las imágenes a continuación son los siguientes (Cornforth et al.2005):
- El esquema sincrónico: todas las celdas se actualizan en paralelo en cada paso de tiempo. Este es el modelo convencional, que se indica aquí a modo de comparación.
- El esquema independiente aleatorio: en cada paso de tiempo, se elige una celda al azar con reemplazo y se actualiza.
- El esquema de orden aleatorio: en cada paso de tiempo, todos los nodos se actualizan, pero en orden aleatorio.
- El esquema cíclico: en cada paso de tiempo, se elige un nodo de acuerdo con un orden de actualización fijo, que se decidió al azar durante la inicialización del modelo.
- El esquema de reloj automático : cada celda tiene un temporizador independiente, inicializado en un período y una fase aleatorios. Cuando el período ha expirado, la celda se actualiza y el temporizador se reinicia. La actualización es autónoma y avanza a diferentes velocidades para diferentes celdas.
- El esquema de auto-sincronización : el mismo que el esquema con reloj, pero la fase de los temporizadores se ve afectada por el acoplamiento local con los vecinos y, por lo tanto, pueden lograr la sincronización local.
Los diagramas de tiempo-estado a continuación muestran las diferencias causadas por cambiar el esquema de actualización del modelo de autómatas celulares sin cambiar ningún otro parámetro. La regla utilizada, la regla 30 , es la misma para cada diagrama.
Regla original 30 | Regla 30 actualizada aleatoriamente |
Regla 30 actualizada en orden aleatorio | Regla 30 actualizada en orden cíclico |
Regla 30 con reloj automático | Regla 30 de autosincrono |
Trascendencia
A menudo, los modelos como los autómatas celulares se utilizan para ayudar a comprender los procesos que funcionan en la vida real. Al construir modelos simplificados, se pueden aprender nuevos conocimientos. Siempre existe la duda de cuán simples deben ser estos modelos para describir adecuadamente lo que se está modelando. El uso de modelos asincrónicos puede permitir un nivel extra de realismo en el modelo. Todos los esquemas descritos anteriormente tienen su parte en la vida real. El esquema independiente aleatorio podría ser apropiado para modelar redes sociales o comunicación en redes informáticas . El esquema cronometrado podría ser apropiado para modelar colonias de insectos , mientras que el esquema autosincrónico podría aplicarse al tejido neural .
Referencias
- H. Bersini y V. Detours, 1994. La asincronía induce estabilidad en modelos basados en autómatas celulares, Actas de la IV Conferencia sobre vida artificial , páginas 382-387, Cambridge, MA, julio de 1994, vol 204, no. 1-2, págs. 70-82.
- Cornforth, D, Green, D y Newth, D 2005, Procesos asincrónicos ordenados en sistemas de agentes múltiples, Physica D , vol 204, no. 1-2, págs. 70-82.
- Cornforth, D, Green, DG, Newth D y Kirley M 2002, ¿ Marchan las hormigas artificiales al paso? Procesos asincrónicos ordenados y modularidad en sistemas biológicos . En Standish, Bedau, Abbass, Actas de la Octava Conferencia Internacional sobre Vida Artificial , Sydney, págs. 28-32
- Fatès N., (2014), Una visita guiada de autómatas celulares asincrónicos, Journal of Cellular Automata : Vol. 9 (5-6), págs. 387-416, preimpresión
- Fatès N. y Morvan M., (2005), Un estudio experimental de la robustez del asincronismo para autómatas celulares elementales, Sistemas complejos : Volumen 16 / Número 1, págs. 1-27.
- Fatès N., Morvan M., N. Schabanel y E. Thierry, (2006), Comportamiento totalmente asincrónico de autómatas celulares elementales de doble inactividad, Informática teórica : Volumen 362, págs. 1-16.
- Harvey I. y Bossomaier TRJ, (1997). Tiempo fuera de articulación: atractores en redes booleanas asincrónicas. En Husbands and Harvey (eds.), Actas de la Cuarta Conferencia Europea sobre Vida Artificial , 67-75, MIT Press .
- Kanada Y. (1994). Los efectos de la aleatoriedad en autómatas celulares 1D asincrónicos . Vida artificial IV .
- Nehaniv, CL (2002). Evolution in Asynchronous Cellular Automata, Artificial Life VIII , 65-73, MIT Press.
- Nehaniv, CL (2004). Las redes de autómatas asincrónicas pueden emular cualquier red de autómatas sincrónicas, International Journal of Algebra & Computation , 14 (5-6): 719-739.
- Orponen, P. (1997). Computación con redes lógicas de umbral verdaderamente asincrónicas. Ciencias de la Computación Teórica 174 (1-2): 123-136.
- Sipper M, Tomassini M. y Capcarrere MS (1997). Autómatas celulares no uniformes asincrónicos y escalables en evolución. Proc. de Intl. Conf. sobre redes neuronales artificiales y algoritmos genéticos (ICANNGA97) , Springer-Verlag.
- Laboratorio virtual en la Universidad de Monash Simulaciones en línea de actualización asincrónica en autómatas celulares.