Modeling genetic algorithms with interacting particle systems

En este trabajo presentamos un enfoque natural de Sistemas de Partículas Interactuantes (IPS) para modelar y estudiar el comportamiento asintótico de Algoritmos Genéticos (GAs). En este modelo, una población es vista como una distribución (o medida) en el espacio de búsqueda, y el Algoritmo Genético...

Full description

Bibliographic Details
Main Authors:	Del Moral, P., Kallel, L., Rowe, J.
Format:	Online
Language:	spa
Published:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2001
Online Access:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/201

id	RMTA201
record_format	ojs
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
author	Del Moral, P. Kallel, L. Rowe, J.
spellingShingle	Del Moral, P. Kallel, L. Rowe, J. Modeling genetic algorithms with interacting particle systems
author_facet	Del Moral, P. Kallel, L. Rowe, J.
author_sort	Del Moral, P.
description	En este trabajo presentamos un enfoque natural de Sistemas de Partículas Interactuantes (IPS) para modelar y estudiar el comportamiento asintótico de Algoritmos Genéticos (GAs). En este modelo, una población es vista como una distribución (o medida) en el espacio de búsqueda, y el Algoritmo Genético como un sistema dinámico valuado en medida. Este modelo permite aplicar resultados recientes sobre convergencia de la literatura sobre IPS para estudiar la convergencia de GAs cuando el tamaño de la población tiende al infinito. Primero revisamos algunos enfoques para modelar GAs y resultados relacionados con la convergencia. Enseguida describimos un modelo general y de tiempo discreto abstracto para GAs, basado en un IPS, y proponemos una breve revisión de algunos resultados asintóticos recientes acerca de la convergencia de N-IPS modelos de aproximación (de GAs de población finita de tamaño N), que conducen al modelo IPS (de GAs de población infinita), incluyendo teoremas de leyes de los grandes números, LLp-media y cota exponencial, así como principios de grandes desviaciones. Finalmente, se detalla el impacto de modelar Algoritmos Genéticos con nuestro enfoque de IPS sobre diferentes clases de algoritmos genéticos genéricos que incluyen mutación, cruzamiento y selección proporcional. Exploramos las conexiones entre los flujos de distribución de Feynman-Kac y el algoritmo geético simple. Esta representación de Feynman-Kac del modelo de población infinita es usada luego para desarrollar resultados de estabilidad asintótica y convergencia con respecto al parámetro de tiempo.
title	Modeling genetic algorithms with interacting particle systems
title_short	Modeling genetic algorithms with interacting particle systems
title_full	Modeling genetic algorithms with interacting particle systems
title_fullStr	Modeling genetic algorithms with interacting particle systems
title_full_unstemmed	Modeling genetic algorithms with interacting particle systems
title_sort	modeling genetic algorithms with interacting particle systems
title_alt	Modeling genetic algorithms with interacting particle systems
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2001
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/201
work_keys_str_mv	AT delmoralp modelinggeneticalgorithmswithinteractingparticlesystems AT kallell modelinggeneticalgorithmswithinteractingparticlesystems AT rowej modelinggeneticalgorithmswithinteractingparticlesystems
_version_	1811744060285648896
spelling	RMTA2012022-01-18T15:51:50Z Modeling genetic algorithms with interacting particle systems Modeling genetic algorithms with interacting particle systems Del Moral, P. Kallel, L. Rowe, J. Genetic algorithms Interacting particle systems asymptotical convergence Feynman-Kac formula measure valued processes Algoritmos genéticos sistemas de partículas interactuantes convergencia asintótica fórmula de Feynman-Kac procesos valuados en medida 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. En este trabajo presentamos un enfoque natural de Sistemas de Partículas Interactuantes (IPS) para modelar y estudiar el comportamiento asintótico de Algoritmos Genéticos (GAs). En este modelo, una población es vista como una distribución (o medida) en el espacio de búsqueda, y el Algoritmo Genético como un sistema dinámico valuado en medida. Este modelo permite aplicar resultados recientes sobre convergencia de la literatura sobre IPS para estudiar la convergencia de GAs cuando el tamaño de la población tiende al infinito. Primero revisamos algunos enfoques para modelar GAs y resultados relacionados con la convergencia. Enseguida describimos un modelo general y de tiempo discreto abstracto para GAs, basado en un IPS, y proponemos una breve revisión de algunos resultados asintóticos recientes acerca de la convergencia de N-IPS modelos de aproximación (de GAs de población finita de tamaño N), que conducen al modelo IPS (de GAs de población infinita), incluyendo teoremas de leyes de los grandes números, LLp-media y cota exponencial, así como principios de grandes desviaciones. Finalmente, se detalla el impacto de modelar Algoritmos Genéticos con nuestro enfoque de IPS sobre diferentes clases de algoritmos genéticos genéricos que incluyen mutación, cruzamiento y selección proporcional. Exploramos las conexiones entre los flujos de distribución de Feynman-Kac y el algoritmo geético simple. Esta representación de Feynman-Kac del modelo de población infinita es usada luego para desarrollar resultados de estabilidad asintótica y convergencia con respecto al parámetro de tiempo. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2001-08-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/201 10.15517/rmta.v8i2.201 Revista de Matemática: Teoría y Aplicaciones; Vol. 8 No. 2 (2001): Revista de Matemática: Teoría y Aplicaciones; 19-77 Revista de Matemática: Teoría y Aplicaciones; Vol. 8 Núm. 2 (2001): Revista de Matemática: Teoría y Aplicaciones; 19-77 Revista de Matemática; Vol. 8 N.º 2 (2001): Revista de Matemática: Teoría y Aplicaciones; 19-77 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/201/33098 Derechos de autor 2001 Revista de Matemática: Teoría y Aplicaciones

Modeling genetic algorithms with interacting particle systems

Similar Items