Ir al contenido

Documat

Modeling genetic algorithms with interacting particle systems

  • Autores: P. Del Moral, L. Kallel, J. Rowe
  • Localización: Revista de Matemática: Teoría y Aplicaciones, ISSN 2215-3373, ISSN-e 2215-3373, Vol. 8, Nº. 2, 2001, págs. 19-77
  • Idioma: español
  • DOI: 10.15517/rmta.v8i2.201
  • Enlaces
  • Resumen
    • español

      En este trabajo presentamos un enfoque natural de Sistemas de Part´?culas Interactuantes(IPS) para modelar y estudiar el comportamiento asint´otico de AlgoritmosGen´eticos (GAs). En este modelo, una poblaci´on es vista como una distribuci´on (omedida) en el espacio de b´usqueda, y el Algoritmo Gen´etico como un sistema din´amicovaluado en medida. Este modelo permite aplicar resultados recientes sobre convergenciade la literatura sobre IPS para estudiar la convergencia de GAs cuando el tama˜node la poblaci´on tiende al infinito.Primero revisamos algunos enfoques para modelar GAs y resultados relacionadoscon la convergencia. Enseguida describimos un modelo general y de tiempo discretoabstracto para GAs, basado en un IPS, y proponemos una breve revisi´on de algunosresultados asint´oticos recientes acerca de la convergencia de N-IPS modelos de aproximaci´on (de GAs de poblaci´on finita de tama˜no N), que conducen al modelo IPS(de GAs de poblaci´on infinita), incluyendo teoremas de leyes de los grandes n´umeros,LL  Palabras clave:  Algoritmos gen´eticos, sistemas de part´?culas interactuantes, convergenciaasint´otica, f´ormula de Feynman-Kac, procesos valuados en medida.p-media y cota exponencial, as´? como principios de grandes desviaciones.Finalmente, se detalla el impacto de modelar Algoritmos Gen´eticos con nuestroenfoque de IPS sobre diferentes clases de algoritmos gen´eticos gen´ericos que incluyenmutaci´on, cruzamiento y selecci´on proporcional. Exploramos las conexiones entre losflujos de distribuci´on de Feynman-Kac y el algoritmo gen´etico simple. Esta representaci´on de Feynman-Kac del modelo de poblaci´on infinita es usada luego para desarrollarresultados de estabilidad asint´otica y convergencia con respecto al par´ametrode tiempo.

    • English

      We present in this work a natural Interacting Particle System (IPS) approach formodeling and studying the asymptotic behavior of Genetic Algorithms (GAs). In thismodel, a population is seen as a distribution (or measure) on the search space, and theGenetic Algorithm as a measure valued dynamical system. This model allows one toapply recent convergence results from the IPS literature for studying the convergenceof genetic algorithms when the size of the population tends to infinity.We first review a number of approaches to Genetic Algorithms modeling and relatedconvergence results. We then describe a general and abstract discrete timeInteracting Particle System model for GAs, and we propose a brief review of some recentasymptotic results about the convergence of the N-IPS approximating model (offinite N-sized-population GAs) towards the IPS model (of infinite population GAs),including law of large number theorems, IL p-mean and exponential bounds as well aslarge deviations principles.Finally, the impact of modeling Genetic Algorithms with our interacting particlesystem approach is detailed on different classes of generic genetic algorithms includingmutation, cross-over and proportionate selection. We explore the connections betweenFeynman-Kac distribution flows and the simple genetic algorithm. This Feynman-Kacrepresentation of the infinite population model is then used to develop asymptoticstability and uniform convergence results with respect to the time parameter.Keywords:  Genetic algorithms, Interacting particle systems, asymptotical convergence,Feynman-Kac formula, measure valued processes.

  • Referencias bibliográficas
    • Del Moral, P.; Guionnet, A. (1999) “A central limit theorem for nonlinear filtering using interacting particle systems”, Ann. Appl. Probab....
    • Del Moral, P.; Guionnet, A. (1998) “Large deviations for interacting particle systems. Applications to nonlinear filtering problems”, Stochastic...
    • Del Moral, P.; Guionnet, A. (1998) “On the Stability of Measure Valued Processes. Applications to nonlinear filtering and interacting particle...
    • Del Moral, P.; Guionnet, A. (1999) “On the stability of measure valued processes with applications to filtering”, C.R. Acad. Sci., Paris,...
    • Del Moral, P.; Jacod, J. (1999) “The Monte-Carlo method for filtering with discrete time observations. Central limit theorems”, Publications...
    • Del Moral, P.; Ledoux, M. (2000) “Convergence of empirical processes for interacting particle systems with applications to nonlinear filtering”,...
    • Del Moral, P.; Miclo, L. (2000) “Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to non-linear...
    • Del Moral, P.; Miclo, L. (2000) “A Moran particle system approximation of Feynman-Kac formulae”, Publications du Laboratoire de Statistiques...
    • Del Moral, P.; Miclo, L. (1999) “Asymptotic stability of nonlinear semigroups of Feynman-Kac type”, Publications du Laboratoire de Statistiques...
    • 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....
    • 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...
    • 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...
    • Altenberg, L. (1995) “The schema theorem and Price’s theorem”, in: L. D. Whitley & M. D. Vose (Eds.) Foundations of Genetic Algorithms...
    • 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....
    • Antonisse, J. (1989) “A new interpretation of schema notation that overturns the binary encoding constraint”, in: J. D. Schaffer (Ed.) Proceedings...
    • Bäck, T. (1992) “The interaction of mutation rate, selection, and self-adaptation in genetic algorithm”, in: R. Manner & B. Manderick...
    • Bäck, T. (1993) “Optimal mutation rate in genetic search”, in: S. Forrest (Ed.) Proceedings of the 5th International Conference on Genetic...
    • 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,...
    • Berny, A. (1999) Statistical Machine Learning and Combinatorial Optimization. To appear in the Proceedings of the Second Evonet Summerschool...
    • Beyer, H.G. (1993) “Toward a theory of evolution strategies: Some asymptotical results for the (1, +λ)-theory”, Evolutionary Computation...
    • 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):...
    • 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...
    • Bruce, I.D.; Simpson, R.J. (1999) “Evolution determined by trajectory of expected populations: sufficient conditions with application to crossover”,...
    • 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.)...
    • Chakraborty, U.; Deb, K.; Chakraborty, M. (1996) “Analysis of selection algorithms: a markov chain approach”, Evolutionary Computation 4(2):...
    • Darroch, J.N.; Senata, E. (1965) “On quasi-stationary distributions in absorbing discrete time finite markov chains”, Journal of Applied Probability:...
    • Das, R.; Whitley, D. (1991) “The only challenging problems are deceptive: global search by solving order-1 hyperplanes”, in: R. K. Belew &...
    • Davis, L. (1991) Towards an Exploration of the Simulated Annealing Exploration Theory onto the Simple Genetic Algorithm. PhD Thesis, University...
    • Davis, T.E.; Principe, J.C. (1991) “A simulated annealing like convergence theory for simple genetic algorithm”, in: R. K. Belew & L....
    • Droste, S.; Jensen, T.; Wegener, I. (1998) “A rigorous complexity analysis of the (1+1) evolutionary algorithm for linear functions with...
    • Fogel, D.B. (1992) “An analysis of evolutionary programming”, in: D. B. Fogel & W. Atmar (Eds.) Proceedings of the 1st Annual Conference...
    • 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...
    • Garnier, J.; Kallel, L. (1999) “Statistical distribution of the convergence time for long k-path problems”, IEEE Transactions on Evolutionary...
    • Garnier, J.; Kallel, L.; Schoenauer, M. (1999) “Rigourous results of the first hitting times for binary mutations”, Evolutionary Computation...
    • 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...
    • Goldberg, D.E.; Deb, K. (1991) “A comparative analysis of selection schemes used in genetic algorithms”, in: G. J. E. Rawlins (Ed.) Foundations...
    • Goldberg, D.E.; Richardson, J. (1987) “Genetic algorithms with sharing for multi-modal function optimization”, in: J. J. Grefenstette (Ed.)...
    • Goldberg, D.E.; Segrest, P. (1987) “Finite markov chain analysis of genetic algorithms”, in: J. J. Grefenstette (Ed.) Proceedings of the 2nd...
    • Grefenstette, J.J. (1991) “Conditions for implicit parallelism”, in: G. J. E. Rawlins (Ed.) Foundations of Genetic Algorithms, Morgan Kaufmann,...
    • Hartl, H.F.; Belew, R.K. (1990) “A Global Convergence Proof for a Class of Genetic Algorithms”, Technical report, Technische Universität...
    • 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...
    • Kallel, L.; Naudts, B. (1999) “Longpaths for the genetic algorithm”, in: W. Banzhaf & C. Reeves (Eds.) Foundations of Genetic Algorithms...
    • 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...
    • Mühlenbein, H. (1992) “How genetic algorithms really work: I. Mutation and hill-climbing”, in: R. Manner & B. Manderick (Eds.) Proceedings...
    • 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...
    • Qi, X.; Palmieri, F. (1994) “Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space: analysis...
    • Radcliffe, N.J. (1992) “Nonlinear genetic representations”, in: R. Manner & B. Manderick (Eds.) Proceedings of the 2nd Conference on Parallel...
    • 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,...
    • 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...
    • Rogers, A.; Prugel-Bennet, A. (1999) “A solvable model of a hard optimization problem”, to appear in the Proceedings of the second Evonet...
    • 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...
    • 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....
    • 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...
    • 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,...
    • 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...
    • Suzuji, J. (1997) “A further result on the markov chain model of genetic algorithms and its application to a simulated annealing-like strategy”,...
    • Thierens, D.; Goldberg, D.E. (1993) “Mixing in genetic algorithms”, in: S. Forrest (Ed.) Proceedings of the 5th International Conference on...
    • 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...
    • Vose, M.D.; Wright, A.H. (1995) “Stability of vertex fixed points and applications”, in: L. D. Whitley & M. D. Vose (Eds.) Foundations...
    • 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...
    • 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...
    • Nimwegen, E. van; Crutchfield, J.P.; Mitchell, M. (1997) “Finite populations induce metastability in evolutionary search”, Physics Letters...
    • Rowe, J.E. (2000) “Cyclic attractors and quasispecies adaptibility”, in: L. Kallel, B. Naudts & A. Rogers (Eds.) Theoretical Aspects of...
    • Rowe, J.E. (2000) “The dynamical systems model of the simple genetic algorithm”, in: L. Kallel, B. Naudts & A. Rogers (Eds.) Theoretical...
    • 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...
    • 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...
    • Rowe, J.E. (1999) “Population fixed-points for functions of unitation”, in: W. Banzhaf & C. Reeves (Eds.) Foundations of Genetic Algorithms...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno