Algoritmo evolutivo celular
Un algoritmo evolutivo celular ( cEA ) es un tipo de algoritmo evolutivo (EA) en el que los individuos no pueden aparearse arbitrariamente, sino que cada uno interactúa con sus vecinos más cercanos sobre los que se aplica un EA básico (selección, variación, reemplazo).
El modelo celular simula la evolución natural desde el punto de vista del individuo, que codifica una solución tentativa (optimización, aprendizaje, búsqueda) del problema. La idea esencial de este modelo es dotar a la población del EA de una estructura especial definida como un grafo conexo, en el que cada vértice es un individuo que se comunica con sus vecinos más cercanos. En particular, los individuos se establecen conceptualmente en una malla toroidal y solo se les permite recombinarse con individuos cercanos. Esto nos lleva a una especie de localidad conocida como aislamiento por distancia . El conjunto de parejas potenciales de un individuo se llama su vecindad.. Se sabe que, en este tipo de algoritmo, los individuos similares tienden a agruparse creando nichos, y estos grupos operan como si fueran subpoblaciones separadas (islas). De todos modos, no existe un límite claro entre los grupos adyacentes, y los nichos cercanos podrían ser fácilmente colonizados por nichos competitivos y tal vez fusionar los contenidos de la solución durante el proceso. Simultáneamente, los nichos más lejanos pueden verse afectados más lentamente.
Un algoritmo evolutivo celular (cEA) generalmente desarrolla una cuadrícula bidimensional estructurada de individuos, aunque también son posibles otras topologías. En esta cuadrícula, los grupos de individuos similares se crean naturalmente durante la evolución, lo que promueve la exploración en sus límites, mientras que la explotación se realiza principalmente mediante la competencia directa y la fusión dentro de ellos.
La cuadrícula suele ser una estructura toroidal 2D, aunque el número de dimensiones se puede ampliar fácilmente (a 3D) o reducir (a 1D, por ejemplo, un anillo). La vecindad de un punto particular de la cuadrícula (donde se coloca a un individuo) se define en términos de la distancia de Manhattan a otros en la población. Cada punto de la cuadrícula tiene una vecindad que se superpone a las vecindades de los individuos cercanos. En el algoritmo básico, todos los vecindarios tienen el mismo tamaño y formas idénticas. Los dos barrios más utilizados son L5, también llamado Von Neumann o NEWS (Norte, Este, Oeste y Sur), y C9, también conocido como barrio de Moore . Aquí, L significa Lineal mientras que C significacompacto _
En los cEA, los individuos solo pueden interactuar con sus vecinos en el ciclo reproductivo donde se aplican los operadores de variación. Este ciclo reproductivo se ejecuta dentro de la vecindad de cada individuo y, generalmente, consiste en seleccionar dos progenitores entre sus vecinos según un determinado criterio, aplicándoles los operadores de variación (recombinación y mutación por ejemplo), y reemplazando al individuo considerado por el descendencia recién creada siguiendo un criterio dado, por ejemplo, reemplazar si la descendencia representa una mejor solución que el individuo considerado.
En un cEA síncrono regular , el algoritmo procede desde el primer individuo superior izquierdo hacia la derecha y luego hacia varias filas utilizando la información de la población para crear una nueva población temporal. Después de terminar con el último individuo de abajo a la derecha, la población temporal se completa con los individuos recién computados y comienza el paso de reemplazo. En él, la población antigua se reemplaza completa y sincrónicamente con la recién calculada de acuerdo con algún criterio. Por lo general, el reemplazo mantiene al mejor individuo en la misma posición de ambas poblaciones, es decir, se utiliza el elitismo.
