Adaptación del tamaño de la población en los algoritmos genéticos

Este documento describe un algoritmo genético combinado con un autómata celular que utiliza un esquema de población celular para mantener diversidad en la población y determinar automáticamente el tamaño de la población. Los individuos del algoritmo genético son organizados en un autómata celular de...

Full description

Autores:
Cantor Monroy, Giovanni Antonio
Tipo de recurso:
Fecha de publicación:
2009
Institución:
Universidad Nacional de Colombia
Repositorio:
Universidad Nacional de Colombia
Idioma:
spa
OAI Identifier:
oai:repositorio.unal.edu.co:unal/70500
Acceso en línea:
https://repositorio.unal.edu.co/handle/unal/70500
http://bdigital.unal.edu.co/2775/
Palabra clave:
57 Ciencias de la vida; Biología / Life sciences; biology
0 Generalidades / Computer science, information and general works
62 Ingeniería y operaciones afines / Engineering
Autómata celular
Algoritmos genéticos
Explosiones cámbricas
Extinciones masivas
Cellular automata
Genetic algorithms
Cambrian explosion
Massive extinction
Rights
openAccess
License
Atribución-NoComercial 4.0 Internacional
Description
Summary:Este documento describe un algoritmo genético combinado con un autómata celular que utiliza un esquema de población celular para mantener diversidad en la población y determinar automáticamente el tamaño de la población. Los individuos del algoritmo genético son organizados en un autómata celular de 2 dimensiones, donde los individuos son considerados activos o inactivos en cada iteración del proceso evolutivo de acuerdo con una función de transición de estados configurada en el autómata celular. Solo los individuos activos son sujetos al proceso de evolución y cuando múltiples padres son requeridos por un operador genético, un esquema de selección local es utilizado, donde los individuos activos en la vecindad pueden ser seleccionados como padres. Un modelo de Explosiones Cámbricas y Extinción Masivas es introducido en el esquema, permitiendo controlar la extinción o sobrepoblación de individuos activos en la población. Experimentos muestran que el esquema propuesto es capaz de mantener diversidad en la población mientras encuentra buenas soluciones en un número apropiado de evaluaciones de la función de aptitud. / Abstract. This paper describes an evolutionary algorithm (EA) which combines cellular automata, Cambrian explosions and massive extinctions ideas in order to maintain diversity and automatically determine the population’s size of the EA. Individuals are organized in a two-dimensional grid (2-dimensional cellular automaton surface) and are considered active or inactive according to the cellular automaton state. The individual state is updated according to the cellular automaton state rules at each step (iteration) of the evolutionary process. Only active individuals are subject to evolution by applying one of the genetic operators and considering just their active neighbors (when multiple parents are required). Depending on the total number of active individuals, a Cambrian explosion or a massive extinction operation is applied, in a random fashion to control the size of the population. We presented a novel genetic diversity analysis using a hierarchical clustering to examine individuals genotype and identify natural population taxonomies. Experiments show that the proposed scheme is able to maintain diversity and find near optimal solutions in an appropriated number of fitness evaluations.