Top

Natural Computing

Published in:

01-12-2013

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

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

Published in: Natural Computing | Issue 4/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Biochemical connectionism

next article Expanding the landscape of biological computation with synthetic multicellular consortia

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

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

Title: Geiringer theorems: from population genetics to computational intelligence, memory evolutive systems and Hebbian learning
Authors: Boris S. Mitavskiy
Elio Tuci
Chris Cannings
Jonathan Rowe
Jun He
Publication date: 01-12-2013
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 4/2013
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-013-9395-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2013

Kernel clustering using a hybrid memetic algorithm

Exploring programmable self-assembly in non-DNA based molecular computing

On computational complexity of graph inference from counting

Special issue on the frontiers of natural computing

m-Asynchronous cellular automata: from fairness to quasi-fairness

Modeling membrane systems using colored stochastic Petri nets

Premium Partner