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 la perspectiva del individuo, que codifica una solución tentativa a un problema de optimización, aprendizaje o búsqueda. La idea esencial de este modelo es dotar a la población del algoritmo evolutivo (AE) de una estructura especial definida como un grafo conectado , en el que cada vértice es un individuo que se comunica con sus vecinos más cercanos. En particular, los individuos se ubican conceptualmente en una malla toroidal y solo pueden recombinarse con individuos cercanos. Esto da lugar a un tipo de localidad conocido como "aislamiento por distancia". El conjunto de posibles parejas de un individuo se denomina su vecindario . 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). No existe una demarcación clara entre grupos adyacentes, y los nichos cercanos podrían ser fácilmente "colonizados" por nichos competitivos, fusionando potencialmente el contenido de las soluciones durante el proceso.

Un algoritmo evolutivo celular (cEA) suele desarrollar una cuadrícula bidimensional estructurada de individuos, aunque también son posibles otras topologías. En esta cuadrícula, durante la evolución se crean de forma natural grupos de individuos similares, lo que fomenta la exploración dentro de sus límites. La explotación se lleva a cabo principalmente mediante la competencia directa y la fusión dentro de estos grupos.

La cuadrícula suele ser una estructura toroidal bidimensional, aunque el número de dimensiones se puede ampliar o reducir fácilmente (a una dimensión, es decir, un anillo). El vecindario de un punto específico de la cuadrícula (donde se ubica un individuo) se define en términos de la distancia de Manhattan desde ese punto a otros individuos de la población. Cada punto de la cuadrícula tiene un vecindario que se superpone con los vecindarios de los individuos cercanos. En el algoritmo básico, todos los vecindarios tienen el mismo tamaño y forma. Los dos vecindarios más utilizados son L5, también llamado vecindario de von Neumann o NEWS (Norte, Este, Oeste y Sur), y C9, también conocido como vecindario de Moore. Aquí, L significa "lineal" y C significa "compacto".

En los algoritmos evolutivos colaborativos (cEA), los individuos solo pueden interactuar con sus vecinos durante el ciclo reproductivo, donde se aplican los operadores de variación. Este ciclo reproductivo se ejecuta dentro del entorno de cada individuo y, generalmente, consiste en seleccionar dos progenitores entre sus vecinos según un criterio determinado, aplicarles los operadores de variación (recombinación y mutación, por ejemplo) y reemplazar al individuo considerado por la descendencia recién creada según un criterio dado; por ejemplo, reemplazar si la descendencia representa una mejor solución que el individuo considerado.

En un algoritmo evolutivo colaborativo (AEC) síncrono convencional , el algoritmo procede desde el primer individuo de la esquina superior izquierda hacia la derecha y luego a las siguientes filas, utilizando la información de la población para crear una nueva población temporal. Tras finalizar con el último individuo de la esquina inferior derecha, la población temporal se completa con los individuos recién calculados y comienza el paso de reemplazo. En este paso, la población anterior se reemplaza de forma completa y síncrona con la nueva población según algún criterio. Generalmente, el reemplazo mantiene al mejor individuo en la misma posición en ambas poblaciones; es decir, se utiliza el elitismo.

Según la política de actualización de la población utilizada, también se puede definir un autómata celular asíncrono (cEA), un problema bien conocido en autómatas celulares . En los cEA asíncronos, el orden en que se actualizan los individuos de la cuadrícula cambia según el criterio elegido: barrido lineal, barrido aleatorio fijo, nuevo barrido aleatorio y selección uniforme. Los cuatro métodos utilizan el individuo recién calculado (o el original, si es mejor) para los cálculos de sus vecinos.

La superposición de los vecindarios proporciona un mecanismo implícito de migración de soluciones al cEA. Dado que las mejores soluciones se propagan suavemente por toda la población, la diversidad genética se conserva durante más tiempo que en los EA no estructurados. Esta dispersión gradual de las mejores soluciones a través de la población es uno de los principales aspectos del buen equilibrio entre exploración y explotación que los cEA logran durante la búsqueda. Este equilibrio puede ajustarse (y, por extensión, el nivel de diversidad genética a lo largo de la evolución) modificando, por ejemplo, el tamaño del vecindario utilizado, ya que el grado de superposición entre los vecindarios aumenta en función de su tamaño.

Un cEA puede considerarse un autómata celular (AC) con reglas de reescritura probabilísticas, donde el alfabeto del AC es equivalente al número potencial de soluciones del problema. Por lo tanto, el conocimiento derivado de la investigación en AC puede aplicarse a los cEA.

Los algoritmos evolutivos celulares (cEA) se adaptan muy bien al paralelismo, por lo que suelen encontrarse en la literatura sobre metaheurísticas paralelas . En particular, el paralelismo de grano fino permite asignar hilos de ejecución independientes a cada individuo, lo que posibilita que todo el cEA se ejecute en una plataforma de hardware concurrente o incluso paralela. De esta forma, se pueden obtener grandes reducciones de tiempo al ejecutar cEA en FPGA o GPU .

Sin embargo, es importante destacar que los cEA son un modelo de búsqueda que, en muchos sentidos, difiere de los EA tradicionales. Además, pueden ejecutarse en plataformas secuenciales y paralelas, lo que refuerza la idea de que el modelo y la implementación son dos conceptos distintos.

Aquí encontrará una descripción completa de los fundamentos para la comprensión, el diseño y la aplicación de las cEA.

• Autómata celular
• Evolución de dos fases
• Enrique Alba
• Algoritmo evolutivo
• Metaheurística
• metaheurística paralela

• E. Alba, B. Dorronsoro, Algoritmos genéticos celulares , Springer-Verlag, ISBN 978-0-387-77609-5, 2008
• AJ Neighbor, JJ Durillo, F. Luna, B. Dorronsoro, E. Alba, MOCell: Un nuevo algoritmo genético celular para la optimización multiobjetivo, International Journal of Intelligent Systems, 24:726-746, 2009
• E. Alba, B. Dorronsoro, F. Luna, A.J. Neighbor, P. Bouvry, L. Hogie, Un algoritmo genético multiobjetivo celular para una estrategia de difusión óptima en redes MANET metropolitanas , Computer Communications, 30(4):685-697, 2007
• E. Alba, B. Dorronsoro, Cálculo de nueve nuevas mejores soluciones hasta la fecha para VRP con capacidad mediante un GA celular , Information Processing Letters, Elsevier, 98(6):225-230, 30 de junio de 2006
• M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba, La intensidad de selección en algoritmos evolutivos celulares para retículos regulares , IEEE Transactions on Evolutionary Computation, IEEE Press, 9(5):489-505, 2005
• E. Alba, B. Dorronsoro, El equilibrio entre exploración y explotación en algoritmos genéticos celulares dinámicos , IEEE Transactions on Evolutionary Computation, IEEE Press, 9(2)126-142, 2005

• El sitio web sobre algoritmos evolutivos celulares
• Grupo de Investigación NEO de la Universidad de Málaga, España. Archivado el 28/09/2018 en Wayback Machine.