Modelo de población (algoritmo evolutivo)

El modelo poblacional de un algoritmo evolutivo (AE) describe las propiedades estructurales de su población, a las que están sujetos sus miembros. Una población es el conjunto de todas las soluciones propuestas por un AE en una iteración, denominadas individuos según el modelo biológico. Los individuos de una población pueden generar nuevos individuos como descendencia mediante los operadores genéticos del procedimiento.

El modelo poblacional más simple y ampliamente utilizado en los EA es el modelo global o panmíctico , que corresponde a una población no estructurada. ^{[ 1 ] [ 2 ]} Permite que cada individuo elija a cualquier otro individuo de la población como pareja para la producción de descendencia por cruce , donde los detalles de la selección son irrelevantes siempre que la aptitud de los individuos juegue un papel significativo. Debido a la selección global de pareja, la información genética de individuos incluso ligeramente mejores puede prevalecer en una población después de algunas generaciones ( iteración de un EA), siempre que no haya surgido otra descendencia mejor en esta fase. Si la solución encontrada de esta manera no es la óptima buscada, eso se llama convergencia prematura . ^{[ 3 ]} Este efecto puede observarse con más frecuencia en poblaciones panmícticas. ^{[ 4 ]}

En la naturaleza, las poblaciones con apareamiento global son poco comunes. Lo que predomina es un aislamiento limitado debido a la distancia espacial. Los vecindarios locales resultantes evolucionan inicialmente de forma independiente, y los mutantes tienen mayor probabilidad de persistir durante varias generaciones. Como resultado, la diversidad genotípica en el acervo genético se conserva durante más tiempo que en una población panmíctica.

It is therefore obvious to divide the previously global population by substructures. Two basic models were introduced for this purpose, the island models, which are based on a division of the population into fixed subpopulations that exchange individuals from time to time,^[1][5] and the neighbourhood models, which assign individuals to overlapping neighbourhoods,^[4][6] also known as cellular genetic or evolutionary algorithms (cGA or cEA).^[7][8] The associated division of the population also suggests a corresponding parallelization of the procedure. For this reason, the topic of population models is also frequently discussed in the literature in connection with the parallelization of EAs.^{[1][2][4][5][9][10]}

In the island model, also called the migration model or coarse grained model, evolution takes place in strictly divided subpopulations. These can be organised panmictically, but do not have to be. From time to time an exchange of individuals takes place, which is called migration.^[2][5] The time between an exchange is called an epoch and its end can be triggered by various criteria: E.g. after a given time or given number of completed generations, or after the occurrence of stagnation. Stagnation can be detected, for example, by the fact that no fitness improvement has occurred in the island for a given number of generations. Island models introduce a variety of new strategy parameters:^{[11][12][13][14]}

• Number of subpopulations
• Size of the subpopulations
• Neighbourhood relations between islands: they determine which islands are considered neighbouring and can thus exchange individuals, see picture of a simple unidirectional ring (black arrows) and its extension by additional bidirectional neighbourhood relations (additional green arrows)
• Criteria for the termination of an epoch, synchronous or asynchronous migration
• Tasa de migración: número o proporción de individuos que participan en la migración.
• Selección de migrantes: Existen muchas alternativas para esto. Por ejemplo, los mejores individuos pueden reemplazar a los peores o ser seleccionados al azar. Dependiendo de la tasa de migración, esto puede afectar a uno o más individuos a la vez.

Con estos parámetros, la presión selectiva puede verse influenciada en gran medida. Por ejemplo, aumenta con la interconexión de las islas y disminuye con el número de subpoblaciones o la duración del período.

El modelo de vecindad, también llamado modelo de difusión o modelo de grano fino , define una relación de vecindad topológica entre los individuos de una población que es independiente de sus propiedades fenotípicas . La idea fundamental de este modelo es proporcionar a la población EA 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. ^{[ 2 ] [ 6 ]} En particular, los individuos se establecen conceptualmente en una malla toroidal y solo se les permite recombinarse con individuos cercanos. Esto conduce a un tipo de localidad conocida como aislamiento por distancia . ^{[ 6 ] [ 7 ]} El conjunto de parejas potenciales de un individuo se llama su vecindad o deme . La figura adjunta ilustra esto mostrando dos vecindades ligeramente superpuestas de dos individuos marcados en amarillo, a través de las cuales la información genética puede propagarse entre los dos demes. Se sabe que en este tipo de algoritmo, los individuos similares tienden a agruparse y crear nichos que son independientes de los límites del deme y, en particular, pueden ser más grandes que un deme. ^{[ 6 ] [ 7 ]} No existe una frontera clara entre grupos adyacentes, y los nichos cercanos podrían ser colonizados fácilmente por otros competitivos y tal vez fusionar el contenido de la solución durante este proceso. Simultáneamente, los nichos más alejados pueden verse afectados más lentamente. ^{[ 6 ] [ 7 ]} Los EA con este tipo de población también se conocen como EA celulares (cEA) ^{[ 8 ] [ 15 ]} o algoritmos genéticos celulares (cGA). ^{[ 7 ] [ 16 ]}

Una estructura comúnmente utilizada para organizar a los individuos de una población es una cuadrícula toroidal 2D, ^{[ 17 ] [ 1 ] [ 2 ] [ 15 ]} aunque el número de dimensiones puede extenderse fácilmente (a 3D) o reducirse (a 1D, por ejemplo, un anillo, ^{[ 6 ] [ 15 ]} ver la figura de la derecha). El vecindario de un individuo particular en la cuadrícula se define en términos de la distancia de Manhattan desde él a otros en la población. En el algoritmo básico, todos los vecindarios tienen el mismo tamaño y formas idénticas. Los dos vecindarios más comúnmente utilizados para cEA bidimensionales son L5 y C9, ver la figura de la izquierda. Aquí, L significa Lineal mientras que C significa Compacto . Cada deme representa una subpoblación panmíctica dentro de la cual la selección de pareja y la aceptación de la descendencia tienen lugar reemplazando al padre. Las reglas para la aceptación de la descendencia son de naturaleza local y se basan en el vecindario: por ejemplo, se puede especificar que la mejor descendencia debe ser mejor que el progenitor que se reemplaza o, de forma menos estricta, solo mejor que el peor individuo del deme. ^{[ 2 ] [ 6 ]} La primera regla es elitista y crea una mayor presión selectiva que la segunda regla no elitista. En los EA elitistas , el mejor individuo de una población siempre sobrevive. En este sentido, se desvían del modelo biológico.

La superposición de los vecindarios provoca una propagación mayormente lenta de la información genética a través de los límites del vecindario, de ahí el nombre de modelo de difusión . Una mejor descendencia ahora necesita más generaciones que en la panmixia para propagarse en la población. Esto promueve la aparición de nichos locales y su evolución local, preservando así la diversidad genotípica durante un período de tiempo más largo. ^{[ 6 ] [ 17 ] [ 18 ]} El resultado es un mejor y más dinámico equilibrio entre la búsqueda en amplitud y en profundidad adaptado al espacio de búsqueda durante una ejecución. ^{[ 4 ]} La búsqueda en profundidad tiene lugar en los nichos y la búsqueda en amplitud en los límites del nicho y a través de la evolución de los diferentes nichos de toda la población. ^{[ 19 ]} Para el mismo tamaño de vecindario, la propagación de la información genética es mayor para figuras alargadas como L9 que para un bloque como C9, y nuevamente significativamente mayor que para un anillo. ^{[ 20 ]} Esto significa que los vecindarios de anillo son bien adecuados para lograr resultados de alta calidad, incluso si esto requiere tiempos de ejecución comparativamente largos. Por otro lado, si lo que se busca principalmente son resultados rápidos y buenos, aunque posiblemente subóptimos, las topologías 2D son más adecuadas.

Al aplicar ambos modelos de población a algoritmos genéticos, ^{[ 5 ] [ 6 ]} estrategia evolutiva ^{[ 20 ] [ 17 ] [ 21 ]} y otros EA, ^{[ 22 ] [ 23 ]} la división de una población total en subpoblaciones generalmente reduce el riesgo de convergencia prematura y conduce a mejores resultados en general de manera más confiable y rápida que lo que se esperaría con EA panmícticos. ^{[ 2 ] [ 6 ]}

Los modelos de islas tienen la desventaja, en comparación con los modelos de vecindario, de que introducen un gran número de nuevos parámetros de estrategia. A pesar de los estudios existentes sobre este tema en la literatura, ^{[ 11 ] [ 24 ] [ 25 ]} persiste cierto riesgo de configuraciones desfavorables para el usuario. Con los modelos de vecindario, por otro lado, solo es necesario especificar el tamaño del vecindario y, en el caso del modelo bidimensional, se añade la elección de la figura del vecindario. ^{[ 26 ] [ 20 ] [ 27 ] [ 28 ]}

Dado que ambos modelos de población implican partición de la población, son adecuados como base para paralelizar un EA. ^{[ 5 ] [ 10 ] [ 29 ]} Esto se aplica aún más a los EA celulares, ya que dependen solo de información disponible localmente sobre los miembros de sus respectivos demes. Por lo tanto, en el caso extremo, se puede asignar un hilo de ejecución independiente a cada individuo, de modo que todo el cEA pueda ejecutarse en una plataforma de hardware paralela. ^{[ 6 ] [ 30 ] [ 31 ] [ 32 ]} El modelo de isla también admite la paralelización, por ejemplo, asignando un procesador a cada isla. Si las subpoblaciones de las islas están organizadas panmícticamente, todas las evaluaciones de los descendientes de una generación pueden paralelizarse adicionalmente. ^{[ 9 ] [ 14 ] [ 33 ]} En aplicaciones del mundo real, las evaluaciones suelen ser, con mucho, la parte que consume más tiempo. Por supuesto, también es posible diseñar las subpoblaciones de la isla como cEA, de modo que se apliquen las afirmaciones anteriores sobre la paralelización de cEA. De esta forma, se pueden crear estructuras de población jerárquicas con las paralelizaciones adecuadas. ^{[ 9 ]} Para la paralelización se pueden utilizar no solo clústeres de computadoras relativamente costosos, sino también tarjetas gráficas económicas ( GPU ) ^{[ 34 ] [ 35 ]} o las computadoras de una red ^{[ 18 ]} .

Sin embargo, es importante destacar que los cEA, o EA con una población distribuida en islas, representan un modelo de búsqueda que difiere en muchos aspectos de los EA tradicionales. Además, pueden ejecutarse tanto en plataformas secuenciales como paralelas, lo que subraya que modelo e implementación son dos conceptos distintos.

• Erick Cantú-Paz (2001): Algoritmos genéticos paralelos eficientes y precisos (tesis doctoral, Universidad de Illinois, Urbana-Champaign, EE. UU.). Springer, Nueva York, NY. ISBN 978-1-4613-6964-6doi : 10.1007/978-1-4615-4369-5
• Martina Gorges-Schleuter (1990): Algoritmos genéticos y estructuras poblacionales: un algoritmo masivamente paralelo. Tesis doctoral, Universität Dortmund, Fakultät für Informatik, Alemania.
• Enrique Alba, Bernabé Dorronsoro (2008): Algoritmos Genéticos Celulares . Springer, Nueva York, Nueva York. ISBN 978-0-387-77609-5doi : 10.1007/978-0-387-77610-1
• Dirk Sudholt (2015): Parallel Evolutionary Algorithms. In Janusz Kacprzyk, Witold Pedrycz (eds.): Parallel Evolutionary Algorithms. Springer, Berlin, Heidelberg, pp. 929–959 ISBN 978-3-662-43504-5doi:10.1007/978-3-662-43505-2_46
• Gabriel Luque, Enrique Alba (2011): Parallel Genetic Algorithms. Springer, Berlin Heidelberg. ISBN 978-3-642-22083-8doi:10.1007/978-3-642-22084-5

• Cellular automaton
• Dual-phase evolution
• Evolutionary algorithm
• Metaheuristic