nach oben

Natural Computing

Erschienen in:

01.12.2013

Geiringer theorems: from population genetics to computational intelligence, memory evolutive systems and Hebbian learning

verfasst von: Boris S. Mitavskiy, Elio Tuci, Chris Cannings, Jonathan Rowe, Jun He

Erschienen in: Natural Computing | Ausgabe 4/2013

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The classical Geiringer theorem addresses the limiting frequency of occurrence of various alleles after repeated application of crossover. It has been adopted to the setting of evolutionary algorithms and, a lot more recently, reinforcement learning and Monte-Carlo tree search methodology to cope with a rather challenging question of action evaluation at the chance nodes. The theorem motivates novel dynamic parallel algorithms that are explicitly described in the current paper for the first time. The algorithms involve independent agents traversing a dynamically constructed directed graph that possibly has loops and multiple edges. A rather elegant and profound category-theoretic model of cognition in biological neural networks developed by a well-known French mathematician, professor Andree Ehresmann jointly with a neurosurgeon, Jan Paul Vanbremeersch over the last thirty years provides a hint at the connection between such algorithms and Hebbian learning.

Vorheriger Artikel Biochemical connectionism

Nächster Artikel Expanding the landscape of biological computation with synthetic multicellular consortia

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 actual probability distribution on the similarity classes makes no difference in the final outcome as long as every color can be selected with positive probability. Furthermore, the probability distributions may actually depend on time themselves under some mild assumptions see Mitavskiy et al. (2012) for complete details.

A more mathematically inclined reader, might want to observe that inflating the population by a factor of m increases the total number of states within each of the similarity classes by the same factor m while preserving the average hight of the rollouts within the population. This allows us to apply the classical Markov inequality as one of the cornerstone tools to establish the Geiringer-like theorem with nonhomologous recombination as the inflation factor \(m \rightarrow \infty\). For the full details please see Mitavskiy et al. (2012).

In fact, the general finite-population Geiringer theorem in Mitavskiy and Rowe (2006) (see also Mitavskiy and Rowe 2005 and Mitavskiy et al. 2012) says that all populations obtainable in this manner occur with equal probability.

The version presented in the current article is mildly modified but the proofs are virtually identical.

Evidently, the edge weights could alternatively be updated as the ratios in Eqs. 1 through 8, 9, and 10. In fact, any scaling by a constant factor would do.

There are several stochastic techniques for action selection during the simulation process and deciding on an appropriate policy to preserve the delicate balance between exploration and exploitation is a rather active research area where much progress has been made (Agrawal 1995; Auer 2002). It is worth acknowledging that optimal action selection policies based on minimizing expected regret in partially observable and random environments is an active research topic.

For more technically oriented readers, this means that such a relation may be only symmetric and reflexive, but not necessarily transitive.

Agrawal R (1995) Sample mean based index policies with o (logn) regret for the multi-armed bandit problem. Adv Appl Probab 27:1054–1078CrossRefMATH

Auer P (2002) Using confidence bounds for exploration–exploitation trade-offs. J Mach Learn Res 3:397–422MathSciNet

Auger A, Doerr B (2011) Theory of randomized search heuristics. Series on theoretical computer science. Elsevier, Amsterdam

Barr M, Wells C (1998) Category theory for computing science. Prentice Hall, Upper Saddle River

Ehresmann A, Smeonov P (2012) Wlimes: towards a theoretical framework for wandering logic intelligence memory evolutive systems. In: Simeonov PL, Smith LS, Ehresmann AC (eds) Integral biomathics: tracing the road to reality. Springer, Heidelberg

Ehresmann A, Vanbremeersch JP (2006) The memory evolutive systems as a model of Rosens organisms. Axiomathes 16:165–214CrossRef

Ehresmann A, Vanbremeersch JP (2007) Memory evolutive systems: hierarchy, emergence, cognition, studies in multidisciplinarity, vol 4. Elsevier, Amsterdam

Ehresmann A, Baas N, Vanbremeersch JP (2004) Hyperstructures and memory evolutive systems. Int J Gen Syst 33(5):553–568CrossRefMATH

Geiringer H (1944) On the probability of linkage in mendelian heredity. Ann Math Stat 15:25–57MathSciNetCrossRefMATH

Geiringer H (1948) On the mathematics of random mating in case of different recombination values for males and females. Genetics 33:548–564

Geiringer H (1949) Chromatid segregation of tetraploids and hexaploids. Genetics 34:665–684

Hebb DO (1949) The organization of behavior. Wiley, New York

Mc Lane S (1971) Categories for the working mathematician. Springer, New YorkCrossRef

Mitavskiy B, Cannings C (2006) Exploiting quotients of Markov chains to derive properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm. In: Simulated evolution and learning (SEAL-2006), Hefei

Mitavskiy B, Cannings C (2009) Estimating the ratios of the stationary distributions of Markov chains modeling evolutionary algorithms using the quotient construction method. Evol Comput 17(3):343–377CrossRef

Mitavskiy B, He J (2013) A further generalization of the finite-population Geiringer-like theorem for POMDPs to allow recombination over arbitrary set covers. In: Foundations of genetic algorithms 12 (FOGA-2013). ACM Press, New York

Mitavskiy B, Rowe J (2005) A schema-based version of Geiringer theorem for nonlinear genetic programming with homologous crossover. In: Foundations of genetic algorithms 8 (FOGA-2005). Lecture notes in computer science, vol 3469. Springer, Heidelberg, pp 156–175

Mitavskiy B, Rowe J (2006) An extension of Geiringer theorem for a wide class of evolutionary algorithms. Evol Comput 14(1):87–118MathSciNet

Mitavskiy B, Rowe J, Wright A, Schmitt L (2007) An improvement of the quotient construction method and further asymptotic results on the stationary distribution of the Markov chains modeling evolutionary algorithms. In: IEEE congress on evolutionary computation (CEC-2007), Singapore

Mitavskiy B, Rowe J, Wright A, Schmitt L (2008) Quotients of Markov chains and asymptotic properties of the stationary distribution of the Markov chain associated to an evolutionary algorithm. Genet Program Evol Mach 17(3):109–123CrossRef

Mitavskiy B, Rowe J, Cannings C (2012) A version of Geiringer-like theorem for decision making in the environments with randomness and incomplete information. Int J Intell Comput Cybern 5(1):36–90MathSciNetCrossRef

Muhlenbein H (1991) Parallel genetic algorithms, population genetics, and combinatorial optimization. In: Parallelism, learning, evolution, Neubiberg, pp 398–406

Poli R, Stephens C, Wright A, Rowe J (2002) A schema-theory-based extension of Geiringer’s theorem for linear GP and variable-length GAs under homologous crossover. In: Foundations of genetic algorithms (FOGA 2002), Torremolinos, pp 45–62

Rabani Y, Rabinovich Y, Sinclair A (1995) A computational view of population genetics. In: Annual ACM symposium on the theory of computing. ACM Press, New York, pp 83–92

Weng J (2012) Natural and artificial intelligence. BMI Press, Okemos

Titel: Geiringer theorems: from population genetics to computational intelligence, memory evolutive systems and Hebbian learning
verfasst von: Boris S. Mitavskiy
Elio Tuci
Chris Cannings
Jonathan Rowe
Jun He
Publikationsdatum: 01.12.2013
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 4/2013
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-013-9395-4

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 4/2013

A review of morphogenetic engineering

Foreword: asynchronous cellular automata and applications

Special issue on the frontiers of natural computing

Consideration of mobile DNA: new forms of artificial genetic regulatory networks

On computational complexity of graph inference from counting

Modeling membrane systems using colored stochastic Petri nets

Premium Partner