Keywords
Interacting particle systems
asymptotical convergence
Feynman-Kac formula
measure valued processes
Algoritmos genéticos
sistemas de partículas interactuantes
convergencia asintótica
fórmula de Feynman-Kac
procesos valuados en medida
How to Cite
Abstract
We present in this work a natural Interacting Particle System (IPS) approach for modeling and studying the asymptotic behavior of Genetic Algorithms (GAs). In this model, a population is seen as a distribution (or measure) on the search space, and the Genetic Algorithm as a measure valued dynamical system. This model allows one to apply recent convergence results from the IPS literature for studying the convergence of genetic algorithms when the size of the population tends to infinity.
We first review a number of approaches to Genetic Algorithms modeling and related convergence results. We then describe a general and abstract discrete time Interacting Particle System model for GAs, and we propose a brief review of some recent asymptotic results about the convergence of the N -IPS approximating model (of finite N -sized-population GAs) towards the IPS model (of infinite population GAs), including law of large number theorems, ILp-mean and exponential bounds as well as large deviations principles.
Finally, the impact of modeling Genetic Algorithms with our interacting particle system approach is detailed on different classes of generic genetic algorithms including mutation, cross-over and proportionate selection. We explore the connections between Feynman-Kac distribution flows and the simple genetic algorithm. This Feynman-Kac representation of the infinite population model is then used to develop asymptotic stability and uniform convergence results with respect to the time parameter.
References
Del Moral, P.; Guionnet, A. (1999) “A central limit theorem for nonlinear filtering using interacting particle systems”, Ann. Appl. Probab. 9(2): 275–297.
Del Moral, P.; Guionnet, A. (1998) “Large deviations for interacting particle systems. Applications to nonlinear filtering problems”, Stochastic Processes and their Applications 78: 69–95.
Del Moral, P.; Guionnet, A. (1998) “On the Stability of Measure Valued Processes. Applications to nonlinear filtering and interacting particle systems”, Publications du Laboratoire de Statistiques et Probabilités, Université Paul Sabatier, No 03-98.
Del Moral, P.; Guionnet, A. (1999) “On the stability of measure valued processes with applications to filtering”, C.R. Acad. Sci., Paris, t. 328, Série I.
Del Moral, P.; Jacod, J. (1999) “The Monte-Carlo method for filtering with discrete time observations. Central limit theorems”, Publications du Laboratoire de Probabilités, Paris VI, No 515.
Del Moral, P.; Ledoux, M. (2000) “Convergence of empirical processes for interacting particle systems with applications to nonlinear filtering”, Journal of Theoret. Probability 13(1): 225–257.
Del Moral, P.; Miclo, L. (2000) “Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to non-linear filtering”, to appear in J. Azéma, M. Emery, M. Ledoux & M. Yor (Eds.) Séminaire de Probabilités. Lecture Notes in Mathematics, Vol. 1729, Springer-Verlag, Berlin: 1–145.
Del Moral, P.; Miclo, L. (2000) “A Moran particle system approximation of Feynman-Kac formulae”, Publications du Laboratoire de Statistiques et Probabilités, No 11-98 (1998). To appear in Stochastic Processes and their Applications.
Del Moral, P.; Miclo, L. (1999) “Asymptotic stability of nonlinear semigroups of Feynman-Kac type”, Publications du Laboratoire de Statistiques et Probabilités, No 04-99 (1999).
Del Moral, P. (1996) “Nonlinear filtering: interacting particle resolution”, Markov Processes and Related Fields 2.
Del Moral, P. (1998) “Measure valued processes and interacting particle Systems. Application to nonlinear filtering problems”, Ann. Appl. Probab. 8(2): 438–495.
Shiryaev, A.N. Probability, Second edition, Springer, Berlin.
Vose, M.D. (1997) “Logarithmic convergence of random heuristic search”, Evolutionary Computation 4(4): 395–404.
Prugel-Bennet, A.; Rogers, A. (1999) “Modelling GA dynamics”. To appear in the Proceedings of the Second Evonet Summerschool on Theoretical Aspects of Evolutionary Computing, Springer, Berlin.
Ackley, D.H. (1987) A Connectionist Machine for Genetic Hill-Climbing. Kluwer, Boston.
Agapie, A. (1997) “Genetic algorithms: minimal conditions for convergence”, in: J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer & D. Snyers (Eds.) Artificial Evolution’97, LNCS, Springer-Verlag, Berlin.
Altenberg, L. (1995) “The schema theorem and Price’s theorem”, in: L. D. Whitley & M. D. Vose (Eds.) Foundations of Genetic Algorithms 3, Morgan Kaufmann, San Mateo, CA: 23–49.
Ankenbrandt, C.A. (1991) “An extention to the theory of convergence and a proof of the time complexity of genetic algorithms”, in: G. J. E. Rawlins (Ed.) Foundations of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA: 53–68.
Antonisse, J. (1989) “A new interpretation of schema notation that overturns the binary encoding constraint”, in: J. D. Schaffer (Ed.) Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA: 86–91.
Bäck, T. (1992) “The interaction of mutation rate, selection, and self-adaptation in genetic algorithm”, in: R. Manner & B. Manderick (Eds.) Proceedings of the 2nd Conference on Parallel Problems Solving from Nature, Morgan Kaufmann, San Mateo CA: 85–94.
Bäck, T. (1993) “Optimal mutation rate in genetic search”, in: S. Forrest (Ed.) Proceedings of the 5th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA: 2–8.
Bäck, T. (1995) Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York.
Baluja, S. (1995) “An empirical comparison of seven iterative and evolutionary function optimization heuristics”, Technical Report CMU-CS-95-193, Carnegie Mellon University.
Berny, A. (1999) Statistical Machine Learning and Combinatorial Optimization. To appear in the Proceedings of the Second Evonet Summerschool on Theoretical Aspects of Evolutionary Computing, Springer, Berlin.
Beyer, H.G. (1993) “Toward a theory of evolution strategies: Some asymptotical results for the (1, +λ)-theory”, Evolutionary Computation 1(2): 165–188.
Beyer, H.G. (1994) “Toward a theory of evolution strategies: the (µ, λ)-theory. Evolutionary Computation 2(4): 381–407.
Beyer, H.G. (1995) “Toward a theory of evolution strategies: on the benefit of sex – the (µ/µ, λ)-theory”, Evolutionary Computation 3(1): 81–111.
Beyer, H.G. (1995) “Toward a theory of evolution strategies: self-adaptation”, Evolutionary Computation 3(3): 311–347.
Blumer, M.G. (1980) The Mathematical Theory of Quantitative Genetics. Clarendon Press, Oxford.
Booker, L.B. (1993) “Recombination distributions for genetic algorithms”, in: L. D. Whitley (Ed.) Foundations of Genetic Algorithms 2, Morgan Kaufmann, Palo Alto, CA: 29–44.
Bruce, I.D.; Simpson, R.J. (1999) “Evolution determined by trajectory of expected populations: sufficient conditions with application to crossover”, Evolutionary Computation 7(2):151–171.
Cerf, R. (1994) Une Théorie Assymptotique des Algorithmes Génétiques. PhD thesis, Université de Montpellier II.
Cerf, R. (1996) “An asymptotic theory of genetic algorithms”, in: J.-M. Alliot, E. Lutton, E. Ronald, M. Schoenauer & D. Snyers (Eds.) Artificial Evolution, volume 1063 of LNCS. Springer Verlag, Berlin.
Chakraborty, U.; Deb, K.; Chakraborty, M. (1996) “Analysis of selection algorithms: a markov chain approach”, Evolutionary Computation 4(2): 133–168.
Darroch, J.N.; Senata, E. (1965) “On quasi-stationary distributions in absorbing discrete time finite markov chains”, Journal of Applied Probability: 88–100.
Das, R.; Whitley, D. (1991) “The only challenging problems are deceptive: global search by solving order-1 hyperplanes”, in: R. K. Belew & L. B. Booker (Eds.) Proceedings of the 4th International Conference on Genetic Algorithms, Morgan Kaufmann, Palo Alto CA: 166–173.
Davis, L. (1991) Towards an Exploration of the Simulated Annealing Exploration Theory onto the Simple Genetic Algorithm. PhD Thesis, University of Florida, Gainesville, FL.
Davis, T.E.; Principe, J.C. (1991) “A simulated annealing like convergence theory for simple genetic algorithm”, in: R. K. Belew & L. B. Booker (Eds.) Proceedings of the 4th International Conference on Genetic Algorithms, Morgan Kaufmann, Palo Alto CA: 174–181.
Droste, S.; Jensen, T.; Wegener, I. (1998) “A rigorous complexity analysis of the (1+1) evolutionary algorithm for linear functions with boolean inputs”, in: Proceedings of the Fifth IEEE International Conference on Evolutionary Computation, IEEE Press.
Fogel, D.B. (1992) “An analysis of evolutionary programming”, in: D. B. Fogel & W. Atmar (Eds.) Proceedings of the 1st Annual Conference on Evolutionary Programming, Evolutionary Programming Society: 43–51.
Fogel, L.J. (1962) “Autonomous automata”, Industrial Research 4: 14–19.
Francois, O. (1999) “An evolutionary strategy for global minimization and its markov chain analysis”, IEEE Transactions on Evolutionary Computation.
Garnier, J.; Kallel, L. (1998) “Statistical distribution of the convergence time for long k-path problems”, Technical Report 378, CMAP, Ecole Polytechnique, Avril 1998; to appear in IEEE Transactions on Evolutionary Computation.
Garnier, J.; Kallel, L. (1999) “Statistical distribution of the convergence time for long k-path problems”, IEEE Transactions on Evolutionary Computation.
Garnier, J.; Kallel, L.; Schoenauer, M. (1999) “Rigourous results of the first hitting times for binary mutations”, Evolutionary Computation 7(2): 173–203.
Gieringer, H. (1944) “On the probability theory of linkage in mendelian heridity”, Annals of Math. Stat. 15: 25–57.
Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, Reading MS.
Goldberg, D.E. (1998) “The race, the hurdle and the sweet spot: lessons from genetic algorithms for the automation of design innovation and creativity”, Technical Report 98007, Illinois University.
Goldberg, D.E.; Deb, K. (1991) “A comparative analysis of selection schemes used in genetic algorithms”, in: G. J. E. Rawlins (Ed.) Foundations of Genetic Algorithms, Morgan Kaufmann, Palo Alto CA: 69–93.
Goldberg, D.E.; Richardson, J. (1987) “Genetic algorithms with sharing for multi-modal function optimization”, in: J. J. Grefenstette (Ed.) Proceedings of the 2nd International Conference on Genetic Algorithms, Lawrence Erlbaum Associates: 41–49.
Goldberg, D.E.; Segrest, P. (1987) “Finite markov chain analysis of genetic algorithms”, in: J. J. Grefenstette (Ed.) Proceedings of the 2nd International Conference on Genetic Algorithms, Lawrence Erlbaum Associates: 1–8.
Grefenstette, J.J. (1991) “Conditions for implicit parallelism”, in: G. J. E. Rawlins (Ed.) Foundations of Genetic Algorithms, Morgan Kaufmann, Palo Alto CA: 252–261.
Hartl, H.F.; Belew, R.K. (1990) “A Global Convergence Proof for a Class of Genetic Algorithms”, Technical report, Technische Universität Wien.
Holland, J.H. (1962) “Outline for a logical theory of adaptive systems”, Journal of the Association of Computing Machinery 3.
Holland, J.H. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
Horn, J. (1993) “Finite markov chain analysis of genetic algorithms with niching”, in: S. Forrest (Ed.) Proceedings of the 5th International Conference on Genetic Algorithms, Morgan Kaufmann, Palo Alto CA: 110–117.
Kallel, L.; Naudts, B. (1999) “Longpaths for the genetic algorithm”, in: W. Banzhaf & C. Reeves (Eds.) Foundations of Genetic Algorithms 5, Morgan Kaufmann, Palo Alto CA: 27–43.
Kimura, M. (1964) “Diffusion models in population genetics”, Applied Probability. Methuen’s Review Series in Applied Probability.
Koza, J.R. (1994) Genetic Programming: On the Programming of Computers by means of Natural Evolution. The MIT Press, Cambridge MS.
Mahfoud, S.W. (1993) “Finite markov chain model for an alternative selection strategy for the genetic algorithm”, Complex Systems 7(2): 155–170.
Wentzell, A.D.; Freidlin, M.I. (1984) Random Perturbations of Dynamical Systems. Springer Verlag, Berlin.
Moran, P.A.P. (1958) “Random processes in genetics”, Proceedings of the Cambridge Philosophical Socity, 64: 60–71.
Mühlenbein, H. (1991) “Evolution in space and time”, in: G. J. E. Rawlins (Ed.) Foundations of Genetic Algorithms, Morgan Kaufmann, Palo Alto CA: 316–338.
Mühlenbein, H. (1992) “How genetic algorithms really work: I. Mutation and hill-climbing”, in: R. Manner & B. Manderick (Eds.) Proceedings of the 2nd Conference on Parallel Problems Solving from Nature, Morgan Kaufmann, Palo Alto CA: 15–25.
Mühlenbein, H. (1997) “The equation for the response to selection and its use for prediction”, Evolutionary Computation 5(3): 303–346.
Nix, A.E.; Vose, M.D. (1992) “Modeling genetic algorithms with markov chains”, Annals of Mathematics and Artificial Intelligence 5(1): 79–88.
Prugel-Bennet, A. (1997) “Modelling evolving populations”, Theoretical Biology 185: 81–95.
Prugel-Bennet, A.; Shapiro, J.L. (1994) “An analysis of genetic algorithms using statistical mechanics”, Physics Review Letters 72(9): 1305–1309.
Qi, X.; Palmieri, F. (1994) “Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space: basic properties of selection and mutation”, IEEE Transactions on Neural Networks 5(1): 102–119.
Qi, X.; Palmieri, F. (1994) “Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space: analysis of the diversification role of crossover”, IEEE Transactions on Neural Networks 5(1): 120–128.
Radcliffe, N.J. (1992) “Nonlinear genetic representations”, in: R. Manner & B. Manderick (Eds.) Proceedings of the 2nd Conference on Parallel Problems Solving from Nature, Morgan Kaufmann, Palo Alto CA: 259–268.
Rattay, M. (1996) Modelling the Dynamics of Genetic Algorithms Using Statistical Mechanics. PhD Thesis, Manchester University.
Rechenberg, I. (1973) Evolutionstrategie: Optimierung Technisher Systeme nach Prinzipien des Biologischen Evolution. Fromman-Holzboog Verlag, Stuttgart.
Rogers, A.; Prugel-Bennet, A. (1998) “Genetic drift in genetic algorithm selection schemes”, IEEE Transactions on Evolutionary Computation.
Rogers, A.; Prugel-Bennet, A. (1999) “Modelling the dynamics of a steady state genetic algorithm”, in: W. Banzhaf & C. Reeves (Eds.) Foundations of Genetic Algorithms 5, Morgan Kaufmann, Palo Alto CA: 57–68.
Rogers, A.; Prugel-Bennet, A. (1999) “A solvable model of a hard optimization problem”, to appear in the Proceedings of the second Evonet Summerschool on Theoretical Aspects of Evolutionary Computing.
Rudolph, G. (1994) “Convergence analysis of canonical genetic algorithm”, IEEE Transactions on Neural Networks 5(1): 96–101.
Rudolph, G. (1994) “Convergence of non-elitist strategies”, in: Z. Michalewicz, J. D. Schaffer, H.-P. Schwefel, D. B. Fogel & H. Kitano (Eds.) Proceedings of the First IEEE International Conference on Evolutionary Computation, IEEE PRess: 63–66.
Rudolph, G. (1996) “How mutation and selection solve long path problems in polynomial expected time”, Evolutionary Computation 4(2): 195–205.
Rudolph, G. (1997) “Asymptotical convergence rates of simple evolutionary algorithms under factorizing mutation distributions”, in: J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer & D. Snyers (Eds.) Artificial Evolution’97, Springer, Berlin: 223–233.
Rudolph, G. (1997) Convergence Properties of Evolutionary Algorithms. Kovac, Hamburg, 1997.
Shapiro, J.; Prugel-Bennet, A. (1997) “Genetic algorithm dynamics in a two well potential”, in: R. K. Belew & M. D. Vose (Eds.) Foundations of Genetic Algorithms 4, Morgan Kaufmann, Palo Alto CA: 101–115.
Schwefel, H.-P. (1981) Numerical Optimization of Computer Models. John Wiley & Sons, New-York. 1995 – 2nd edition.
Stephens, C.; Waelbroeck, H. (1997) “Effective degree of freedom in genetic algorithms and the block hypothesis”, in: Th. Bäeck (Ed.) ICGA97, Morgan Kaufmann, Palo Alto CA: 34–40.
Stephens, C.; Waelbroeck, H. (1999) “Schemata evolution and building blocks”, Evolutionary Computation 7(2): 109–124.
Suzuji, J. (1993) “A markov chain analysis on a genetic algorithm”, in: S. Forrest (Ed.) Proceedings of the 5th International Conference on Genetic Algorithms, Morgan Kaufmann, Palo Alto CA: 146–153.
Suzuji, J. (1997) “A further result on the markov chain model of genetic algorithms and its application to a simulated annealing-like strategy”, in: R. K. Belew & M. D. Vose (Eds.) Foundations of Genetic Algorithms 4, Morgan Kaufmann, Palo Alto CA: 53–72.
Thierens, D.; Goldberg, D.E. (1993) “Mixing in genetic algorithms”, in: S. Forrest (Ed.) Proceedings of the 5th International Conference on Genetic Algorithms, Morgan Kaufmann, Palo Alto CA: 38–55.
Trouvé, A. (1993) Paralllisation Massive du Recuit Simul. PhD Thesis, Université Paris XI.
Trouvé, A. (1996) “Cycle decomposition and simulated annealing”, SIAM Journal Control and Optimisation 34(3): 966–986.
Laarhoven, P.J. van; Aarts, E.H.L. (1987) Simulated Annealing: Theory and Applications. Kluwer Academic Press, Dordrecht.
Vose, M.D.; Liepins, G.E. (1991) “Punctuated equilibria in genetic search”, Complex Systems 5(1): 31–44.
Vose, M.D. (1991) “Generalizing the notion of schemata in genetic algorithms”, Artificial Intelligence 50(3): 385–396.
Vose, M.D. (1993) “Modeling simple genetic algorithms”, in: L. D. Whitley (Ed.) Foundations of Genetic Algorithms 2, Morgan Kaufmann, Palo Alto CA: 63–73.
Vose, M.D.; Wright, A.H. (1995) “Stability of vertex fixed points and applications”, in: L. D. Whitley & M. D. Vose (Eds.) Foundations of Genetic Algorithms 3, Morgan Kaufmann, Palo Alto CA: 103–113.
Vose, M.D. (1999) The Simple Genetic Algorithm: Foundations and Theory. The MIT Press, Cambridge MS.
Wilson, S.W. (1991) “GA-easy does not imply steepest-ascent optimizable”, in: R. K. Belew & L. B. Booker (Eds.) Proceedings of the 4th International Conference on Genetic Algorithms, Morgan Kaufmann, Palo Alto CA.
Zhigljavsky, A.A. (1992) Theory of Global Random Search. Mathematics and its Applications. Kluwer, Dordrecht.
Prügel-Bennett, A.; Shapiro, J.L. (1994) “An analysis of genetic algorithms using statistical mechanics”, Phys. Rev. Lett. 72(9): 1305–1309.
Prügel-Bennett, A.; Shapiro, J.L. (1997) “The dynamics of a genetic algorithm for simple random ising systems”, Physica D 104: 75–114.
Levin, E.; Tishby, N.; Solla, S.A. (1990) “A statistical approach to learning and generalization in layered neural networks”, Proceedings of the IEEE 78(10): 1568–1574.
Nimwegen, E. van; Crutchfield, J.P.; Mitchell, M. (1997) “Finite populations induce metastability in evolutionary search”, Physics Letters A 229(2): 144–150.
Rowe, J.E. (2000) “Cyclic attractors and quasispecies adaptibility”, in: L. Kallel, B. Naudts & A. Rogers (Eds.) Theoretical Aspects of Evolutionary Computing, Springer Verlag, Berlin.
Rowe, J.E. (2000) “The dynamical systems model of the simple genetic algorithm”, in: L. Kallel, B. Naudts & A. Rogers (Eds.) Theoretical Aspects of Evolutionary Computing, Springer Verlag, Berlin.
Rowe, J.E.; Vose, M.D.; Wright, A.H. “Group properties of crossover and mutation”. In preparation.
Ronnewinkel, C.; Wilke, C.O.; Martinez, T. (2000) “Genetic algorithms in time-dependent environments”, in: L. Kallel, B. Naudts & A. Rogers (Eds.) Theoretical Aspects of Evolutionary Computing, Springer Verlag, Berlin.
Rowe, J.E. (1999) “Finding attractors for periodic fitness functions”, in: W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honovar, M. Jakiela & R.E. Smith (Eds.) Proc. Genetic and Evolutionary Computation Conference (GECCO99), Morgan Kaufmann, Palo Alto CA.
Rowe, J.E. (1999) “Population fixed-points for functions of unitation”, in: W. Banzhaf & C. Reeves (Eds.) Foundations of Genetic Algorithms 5, Morgan Kaufmann, Palo Alto CA: 69–84.