Modeling genetic algorithms with interacting particle systems

Abstract

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.

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.