Asynkron cellulär automat

Cellulära automater , som med andra systemmodeller för flera agenter , behandlar vanligtvis tid som diskret och tillståndsuppdateringar som sker synkront . Tillståndet för varje cell i modellen uppdateras tillsammans, innan någon av de nya tillstånden påverkar andra celler. Däremot kan en asynkron cellulär automat uppdatera enskilda celler oberoende, på ett sådant sätt att det nya tillståndet för en cell påverkar beräkningen av tillstånd i angränsande celler.

Implementeringar av synkron uppdatering kan analyseras i två faser. Den första, interaktion, beräknar det nya tillståndet för varje cell baserat på grannskapet och uppdateringsregeln. Statliga värden förvaras i ett tillfälligt lager. Den andra fasen uppdaterar tillståndsvärdena genom att kopiera de nya tillstånden till cellerna.

Däremot skiljer asynkron uppdatering inte nödvändigtvis åt dessa två faser: i det enklaste fallet (helt asynkron uppdatering) implementeras förändringar i tillstånd omedelbart.

Den synkrona metoden förutsätter närvaron av en global klocka för att säkerställa att alla celler uppdateras tillsammans. Även om det är praktiskt för att förbereda datorsystem , kan detta vara ett orealistiskt antagande om modellen är avsedd att representera, till exempel, ett levande system där det inte finns några bevis för närvaron av en sådan enhet.

En allmän metod som upprepade gånger upptäckts oberoende (av K. Nakamura på 1970-talet, av T. Toffoli på 1980-talet och av CL Nehaniv 1998) tillåter en att efterlikna exakt beteendet hos en synkron cellulär automat via en asynkron konstruerad som en enkel modifiering av den synkrona cellulära automaten (Nehaniv 2002). Riktigheten av denna metod har dock först på senare tid noggrant bevisats (Nehaniv, 2004). Som en konsekvens följer det omedelbart av resultat på synkrona cellulära automater att asynkrona cellulära automater är kapabla att emulera, t.ex. Conways Game of Life , av universell beräkning och självreplikering (t.ex. som i en Von Neumann universell konstruktor ). Dessutom gäller den allmänna konstruktionen och beviset även för den mer allmänna klassen av synkrona automatnätverk (inhomogena nätverk av automater över riktade grafer, som tillåter externa ingångar – vilket inkluderar cellulära automater som ett specialfall), och visar konstruktivt hur deras beteende kan vara asynkront realiseras av ett motsvarande asynkront automatnätverk.

Uppdatera scheman

Flera studier har implementerat asynkrona modeller och funnit att deras beteende skiljer sig från de synkrona. Bersini och Detours (1994) har visat hur känsligt Conways Game of Life är för uppdateringsschemat. Eventuellt intressant beteende försvinner i det asynkrona fallet. Harvey och Bossomaier (1997) påpekade att stokastisk uppdatering i slumpmässiga booleska nätverk endast resulterar i uttryck av punktattraktorer : det finns inget repeterbart cykliskt beteende, även om de introducerade konceptet med lösa cykliska attraherande. Kanada (1994) har visat att vissa endimensionella CA-modeller som genererar icke-kaotiska mönster när de uppdateras synkront genererar kant av kaosmönster när de slumpas fram. Orponen (1997) har visat att vilket synkront uppdaterat nätverk av logiska tröskelenheter (se Artificiell neuron ) kan simuleras av ett nätverk som inte har några begränsningar för uppdateringsordningen. Sipper et al. (1997) undersökte utvecklingen av icke-uniforma CA:er som utför specifika datoruppgifter. Dessa modeller lättar på det normala kravet för alla noder som har samma uppdateringsregel. I deras modeller var noder organiserade i block. Noder inom ett block uppdaterades synkront, men block uppdaterades asynkront. De experimenterade med tre scheman: (1) vid varje tidssteg väljs ett block slumpmässigt med ersättning; (2) vid varje tidssteg väljs ett block slumpmässigt utan ersättning; (3) vid varje tidssteg väljs ett block enligt en fast uppdateringsordning.

Det finns olika typer av asynkron uppdatering, och olika författare har beskrivit dessa på olika sätt. Schema som visas i bilderna nedan är följande (Cornforth et al. 2005):

Det synkrona schemat - alla celler uppdateras parallellt vid varje tidssteg. Detta är den konventionella modellen, som anges här för jämförelse.
Det slumpmässiga oberoende schemat - vid varje tidssteg väljs en cell slumpmässigt med ersättning och uppdateras.
Schemat för slumpmässig ordning - vid varje tidssteg uppdateras alla noder, men i slumpmässig ordning.
Det cykliska schemat - vid varje tidssteg väljs en nod enligt en fast uppdateringsordning, som beslutades slumpmässigt under initieringen av modellen.
Det självklockade schemat - varje cell har en oberoende timer, initierad till en slumpmässig period och fas. När perioden har löpt ut uppdateras cellen och timern återställs. Uppdateringen är autonom och fortskrider i olika takt för olika celler.
Självsynkroniseringsschemat - samma som det klockade schemat, men timerns fas påverkas av lokal koppling till grannar och kan därför uppnå lokal synkronisering.

Tidstillståndsdiagrammen nedan visar skillnaderna som orsakas av att ändra uppdateringsschemat för den cellulära automatmodellen utan att ändra några andra parametrar. Regeln som används, regel 30 , är densamma för varje diagram.


Ursprunglig regel 30	Regel 30 uppdaterad slumpmässigt

Regel 30 uppdaterad i slumpmässig ordning	Regel 30 uppdaterad i cyklisk ordning

Självklockad regel 30	Självsynkron regel 30

Implikationer

Ofta används modeller som cellulära automater för att hjälpa till att förstå processer som fungerar i verkligheten. Genom att bygga förenklade modeller kan nya insikter läras. Det är alltid en fråga om hur enkla dessa modeller ska vara för att på ett adekvat sätt beskriva vad som modelleras. Användningen av asynkrona modeller kan tillåta en extra nivå av realism i modellen. Alla scheman som beskrivs ovan har sin del i det verkliga livet. Det slumpmässiga oberoende schemat kan vara lämpligt för att modellera sociala nätverk eller kommunikation i datornätverk . Det klockade schemat kan vara lämpligt för modellering av insektskolonier , medan det självsynkrona schemat kan tillämpas på neural vävnad .

H. Bersini och V. Detours, 1994. Asynkroni inducerar stabilitet i cellulära automatbaserade modeller, Proceedings of the IVth Conference on Artificial Life , sidorna 382-387, Cambridge, MA, juli 1994, vol 204, nr. 1-2, sid. 70-82.
Cornforth, D, Green, D, & Newth, D 2005, Ordered Asynchronous Processes in Multi-Agent Systems, Physica D , vol 204, nr. 1-2, sid. 70-82.
Cornforth, D, Green, DG, Newth D & Kirley M 2002, Do Artificial Ants March in Step? Beställda asynkrona processer och modularitet i biologiska system . I Standish, Bedau, Abbass, Proceedings of the Eightth International Conference on Artificiellt liv , Sydney, s. 28-32
Fatès N., (2014), En guidad rundtur i asynkrona cellulära automater, Journal of Cellular Automata : Vol. 9(5-6), s. 387-416, förtryck
Fatès N. och Morvan M., (2005), En experimentell studie av robusthet till asynkronism för elementära cellulära automater, komplexa system : Volym 16 / Utgåva 1, s. 1-27.
Fatès N., Morvan M., N. Schabanel och E. Thierry, (2006), Fullt asynkront beteende hos dubbelvilande elementära cellulära automater, Theoretical Computer Science : Volym 362, s. 1 - 16.
Harvey I. och Bossomaier TRJ, (1997). Time Out of Joint: Attraktioner i asynkrona booleska nätverk. I Husbands and Harvey (red.), Proceedings of the Fourth European Conference on Artificiellt liv , 67-75, MIT Press .
Kanada Y. (1994). Effekterna av slumpmässighet i asynkron 1D cellulär automat . Artificiellt liv IV .
Nehaniv, CL (2002). Evolution in Asynchronous Cellular Automata, Artificial Life VIII , 65-73, MIT Press.
Nehaniv, CL (2004). Asynchronous Automata Networks Can Emulate Any Synchronous Automata Network, International Journal of Algebra & Computation , 14(5-6):719-739.
Orponen, P. (1997). Datorer med riktigt asynkrona tröskellogiska nätverk. Teoretisk datavetenskap 174(1-2):123-136.
Sipper M, Tomassini M. och Capcarrere MS (1997). Utveckling av asynkrona och skalbara icke-uniforma cellulära automater. Proc. från Intl. Konf. om artificiella neurala nätverk och genetiska algoritmer (ICANNGA97), Springer-Verlag.
Virtual Laboratory vid Monash University Onlinesimuleringar av asynkron uppdatering i cellulära automater.