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

Abstract

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.