nach oben

Natural Computing

Erschienen in:

01.06.2012

A study on learning robustness using asynchronous 1D cellular automata rules

verfasst von: Leonardo Vanneschi, Giancarlo Mauri

Erschienen in: Natural Computing | Ausgabe 2/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Numerous studies can be found in literature concerning the idea of learning cellular automata (CA) rules that perform a given task by means of machine learning methods. Among these methods, genetic algorithms (GAs) have often been used with excellent results. Nevertheless, few attention has been dedicated so far to the generality and robustness of the learned rules. In this paper, we show that when GAs are used to evolve asynchronous one-dimensional CA rules, they are able to find more general and robust solutions compared to the more usual case of evolving synchronous CA rules.

Vorheriger Artikel An analysis of different types and effects of asynchronicity in cellular automata update schemes

Nächster Artikel Grids and universal computations on one-dimensional cellular automata

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

The number of considered configurations (50) and the number of repetitions performed for the non deterministic update schemes (30) are clearly empirical and they have been chosen because they are the biggest data that allow us to see the results in a “reasonable” amount of time. As it is often the case in experimental studies, the work could be replicated on a more sophisticated hardware and extended using more configurations and repetitions, in order to possibly obtain more precise outcomes.

Balister P, Bollobás B, Kozma R (2006) Large deviations for mean fields models of probabilistic cellular automata. Random Struct Algorithms 29(1):339–415

Bandini S, Vanneschi L, Wuensche A, Shehata AB (2008) A neuro-genetic framework for pattern recognition in complex systems. Fundam Inf 87(2):207–226

Bersini H, Detours V (1994) Asynchrony induces stability in cellular automata based models. In: Proceedings of artificial life IV. MIT Press, Cambridge, pp 382–387

Blok H, Bergersen B (1999) Synchronous versus asynchronous updating in the game of life. Phys Rev E 59:3876–3879CrossRef

Bouré O, Fatès N, Chevrier V (2011) Robustness of cellular automata in the light of asynchronous information transmission. Technical Research Report, MAIA-INRIA Lorraine-LORIA-INRIA-CNRS: UMR7503—Université Henri Poincaré-Nancy I–Université Nancy II—Institut National Polytechnique de Lorraine

Buvel RL, Ingerson TE (1984) Structure in asynchronous cellular automata. Physica D 1(1):59–68MathSciNet

Capcarrère MS (2002) Evolution of asynchronous cellular automata. In: Proceedings of the 7th international conference on parallel problem solving from nature, PPSN VII. Springer, London, pp 903–912

Chopard B, Droz M (1998) Cellular automata modeling of physical systems. Cambridge University Press, CambridgeMATHCrossRef

Cornforth D, Green DG, Newth D (2005) Ordered asynchronous processes in multi-agent systems. Physica D 204(1–2):70–82MathSciNetCrossRef

Fatés N, Morvan M (2005) An experimental study of robustness to asynchronism for elementary cellular automata. Complex Syst 16(1):1–27

Fatés N, Morvan M, Schabanel N, Thierry E (2005) Asynchronous behaviour of double-quiescent elementary cellular automata. In: Jedrzejowicz J, Szepietowski A (eds) MFCS 2005, LNCS. Springer, Heidelberg, pp 316–327

Fatés N, Regnault D, Schabanel N, Thierry E (2006) Asynchronous behaviour of double-quiescent elementary cellular automata. In: Correa JR et al (eds) LATIN 2006, LNCS. Springer, Heidelberg

Fukś H (2002) Non-deterministic density classification with diffusive probabilistic cellular automata. Phys Rev E 66(2)

Fukś H (2004) Probabilistic cellular automata with conserved quantities. Nonlinearity 17(1):159–173MathSciNetMATHCrossRef

Gács P (1986) Reliable computation with cellular automata. J Comput Syst Sci 32(1):15–78MATHCrossRef

Gács P (2001) Reliable cellular automata with self-organization. J Stat Phys 103(1/2):45–267MATHCrossRef

Gács P, Reif J (1988) A simple three-dimensional real-time reliable cellular array. J Comput Syst Sci 36(2):125–149MATHCrossRef

Ganguly N, Maji P, Dhar S, Sikdar B, Chaudhuri P (2002) Evolving cellular automata as pattern classifier. In: Proceedings of fifth international conference on cellular automata for research and industry. ACRI 2002, Switzerland, pp 56–68

Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, ReadingMATH

Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor

Ibarra O, Palis M, Kim S (1985) Fast parallel language recognition by cellular automata. Theor Comput Sci 41(2–3):231–246MathSciNetMATHCrossRef

Jeanson F (2008) Evolving asynchronous cellular automata for density classification. In: Bullock S et al (eds) Artificial life XI: proceedings of the eleventh international conference on the simulation and synthesis of living systems. MIT Press, Cambridge, pp 282–288

Lumer ED, Nicolis G (1994) Synchronous versus asynchronous dynamics in spatially distributed systems. Physica D 71(1):440–452MATHCrossRef

Maji P, Shaw C, Ganguly N, Sikdar BK, Chaudhuri PP (2003) Theory and application of cellular automata for pattern classification. Fundam Inf 58(3–4):321-354MathSciNetMATH

Mitchell T (1996) Machine learning. McGraw Hill, New YorkMATH

Mitchell M, Crutchfield J, Das R (1996) Evolving cellular automata with genetic algorithms: a review of recent work. In: Proceedings of the first international conference on evolutionary computation and its applications (EvCA 96)

Nehaniv CL (2003) Evolution in asynchronous cellular automata. In: Proceedings of the eighth international conference on artificial life. MIT Press, Cambridge, pp 65–73

Regnault D (2006) Abrupt behavior changes in cellular automata under asynchronous dynamics. In: Proceedings of 2nd European conference on complex systems (ECCS). Oxford, UK

Regnault D, Schabanel N, Thierry E (2007) Progresses in the analysis of stochastic 2D cellular automata: a study of asynchronous 2D minority. In: Kucera L, Kucera A (eds) MFCS 2007, LNCS. Springer, Heidelberg

Schönfish B, de Ross A (1999) Synchronous and asynchronous updating in cellular automata. BioSystems 51(1):123–143CrossRef

Sipper M (1994) Non-uniform cellular automata: evolution in rule space and formation of complex structures. In: Brooks et al (eds) Proceedings of the 4th international workshop on the synthesis and simulation of living systems (artificial life IV). MIT Press, Cambridge, pp 394–399

Sipper M (1996) Co-evolving non-uniform cellular automata to perform computations. Physica D 92(3–4):193–208MathSciNetMATHCrossRef

Sipper M (1997) Evolution of parallel cellular machines: the Cellular Programming Approach. Springer, New YorkCrossRef

Sipper M, Tomassini M, Capcarrere MS (1997) Evolving asynchronous and scalable non-uniform cellular automata. In: Proceedings of international conference on artificial neural networks and genetic algorithms (ICANNGA97). Springer, Vienna, pp 67–71

Smith A III (1972) Real-time language recognition by one-dimensional cellular automata. J Comput Syst Sci 6(3):233–253MATHCrossRef

Tomassini M, Venzi M (2002) Artificially evolved asynchronous cellular automata for the density task. In: ACRI ’01: proceedings of the 5th international conference on cellular automata for research and industry. Springer, London, pp 44–55

Toom A (1980) Stable and attractive trajectories in multicomponent systems. Adv Probab 6(1):549–575MathSciNet

Valsecchi A, Vanneschi L, Mauri G (2010) A study on the automatic generation of asynchronous cellular automata rules by means of genetic algorithms. In: Bandini S et al (eds) Proceedings of the international conference on cellular automata for research and industry, ACRI 2010, vol 6350 of lecture notes in computer science. Springer, Berlin, pp 429–438

Wolfram S (2002) A new kind of science. Wolfram Media, ChampaignMATH

Wuensche A (2004) Self-reproduction by glider collisions: the beehive rule. In: Pollack J et al (eds) International journal. MIT Press, Cambridge, pp 286–291

Titel: A study on learning robustness using asynchronous 1D cellular automata rules
verfasst von: Leonardo Vanneschi
Giancarlo Mauri
Publikationsdatum: 01.06.2012
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 2/2012
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-012-9311-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2012

Preface

Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model

Simple evolution of complex crystal species

Foreword: asynchronous cellular automata and nature-inspired computation

An analysis of different types and effects of asynchronicity in cellular automata update schemes

Fermat’s last theorem and chaoticity

Premium Partner