stringtranslate.com

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 de un AE consideradas en una iteración, que también se denominan individuos según el modelo biológico. Los individuos de una población pueden generar otros individuos como descendencia con la ayuda de los operadores genéticos del procedimiento.

El modelo de población más simple y ampliamente utilizado en las 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 cruzamiento , por lo que 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 unas pocas generaciones ( iteración de una EA), siempre que no hayan surgido otras crías mejores en esta fase. Si la solución encontrada de esta manera no es la óptima buscada, eso se llama convergencia prematura . [3] Este efecto se puede observar con mayor frecuencia en poblaciones panmícticas. [4]

En la naturaleza, rara vez se encuentran grupos de apareamiento globales. Lo que prevalece es un cierto y limitado aislamiento debido a la distancia espacial. Los vecindarios locales resultantes inicialmente evolucionan de forma independiente y los mutantes tienen una 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.

Por lo tanto, es obvio dividir la población global anterior en subestructuras. Para este propósito se introdujeron dos modelos básicos, los modelos de isla , que se basan en una división de la población en subpoblaciones fijas que intercambian individuos de vez en cuando, [1] [5] y los modelos de vecindad , que asignan individuos a vecindades superpuestas, [4] [6] también conocidos como algoritmos genéticos celulares o evolutivos (cGA o cEA). [7] [8] La división asociada de la población también sugiere una paralelización correspondiente del procedimiento. Por esta razón, el tema de los modelos de población también se discute con frecuencia en la literatura en relación con la paralelización de EA. [1] [2] [4] [5] [9] [10]

Modelos de islas

Ejemplo de un modelo de isla que consta de ocho islas y dos estructuras vecinas: un anillo unidireccional simple (flechas negras) y una estructura más compleja (flechas verdes y negras)

En el modelo de isla, también llamado modelo de migración o modelo de grano grueso , la evolución tiene lugar en subpoblaciones estrictamente divididas. Estas pueden organizarse panmícticamente, pero no tienen por qué serlo. De vez en cuando se produce un intercambio de individuos, lo que se denomina migración . [2] [5] El tiempo entre un intercambio se denomina época y su final puede ser desencadenado por varios criterios: p. ej., después de un tiempo determinado o un número determinado de generaciones completadas, o después de la ocurrencia de un estancamiento. El estancamiento puede detectarse, por ejemplo, por el hecho de que no se ha producido ninguna mejora de la aptitud en la isla durante un número determinado de generaciones. Los modelos de isla introducen una variedad de nuevos parámetros de estrategia: [11] [12] [13] [14]

Con estos parámetros se puede influir considerablemente en la presión selectiva, que aumenta con la interconexión de las islas y disminuye con el número de subpoblaciones o la duración de la época.

Modelos de vecindad o algoritmos evolutivos celulares

Estructura en forma de toro (derecha) con dos figuras de vecindad bidimensionales ejemplares (izquierda). Los demes en forma de bloque de los individuos A y B tienen los dos vecinos comunes que se muestran en amarillo.

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 adyacente ilustra esto al mostrar 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 fácilmente colonizados por otros competitivos y tal vez fusionar los contenidos de la solución durante este proceso. Al mismo tiempo, 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]

Ejemplos de vecindades, también llamadas demes, en EA celulares bidimensionales: lineales, compactas, de diamante y... cualquier otra.
Dos ejemplos de vecindarios superpuestos (demes) del modelo de vecindario unidimensional en forma de anillo de un EA. Los dos demes de los individuos X e Y se superponen mínimamente, mientras que los de A y B muestran una superposición máxima.

Una estructura comúnmente utilizada para organizar los individuos de una población es una cuadrícula toroidal 2D, [1] [2] [15] aunque el número de dimensiones se puede extender fácilmente (a 3D) o reducir (a 1D, por ejemplo, un anillo, [6] [15] vea 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 hasta 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, vea 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 tiene 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 padre que se reemplaza o, menos estrictamente, solo mejor que el peor individuo en el deme. [2] [6] La primera regla es elitista y crea una presión selectiva mayor que la segunda regla no elitista. En las 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 mayoritariamente 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 panmixy 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. El resultado es un equilibrio mejor y dinámico entre la búsqueda en amplitud y profundidad adaptada al espacio de búsqueda durante una ejecución. La búsqueda en profundidad tiene lugar en los nichos y la búsqueda en amplitud en los límites de los nichos y a través de la evolución de los diferentes nichos de toda la población. [17] 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. [18] Esto significa que los vecindarios de anillo son adecuados para lograr resultados de alta calidad, incluso si esto requiere tiempos de ejecución comparativamente largos. Por otro lado, si uno está principalmente interesado en resultados rápidos y buenos, pero posiblemente subóptimos, las topologías 2D son más adecuadas.

Comparación

Al aplicar ambos modelos de población a algoritmos genéticos, [5] [6] estrategia evolutiva [18] [19] y otros EA, [20] [21] 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 de lo que se esperaría con EA panmícticos.

Los modelos de isla tienen la desventaja, en comparación con los modelos de vecindad, de que introducen una gran cantidad de nuevos parámetros de estrategia. A pesar de los estudios existentes sobre este tema en la literatura [11] [22] [23], sigue existiendo un cierto riesgo de que los usuarios presenten configuraciones desfavorables. En cambio, con los modelos de vecindad solo se debe especificar el tamaño de la vecindad y, en el caso del modelo bidimensional, se añade la elección de la figura de vecindad.

Paralelismo

Dado que ambos modelos de población implican la partición de la población, son muy adecuados como base para paralelizar un EA. [5] [10] [24] Esto se aplica aún más a los EA celulares, ya que se basan únicamente en 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] [25] [26] El modelo de isla también admite la paralelización, por ejemplo, asignando un procesador a cada isla. Si las subpoblaciones de las islas se organizan panmícticamente, todas las evaluaciones de los descendientes de una generación se pueden paralelizar adicionalmente. [9] [14] [27] En aplicaciones del mundo real, las evaluaciones suelen ser, con mucho, la parte que más tiempo consume. Por supuesto, también es posible diseñar las subpoblaciones de la isla como cEA, de modo que se apliquen las afirmaciones realizadas anteriormente sobre la paralelización de cEA. De esta manera, se pueden crear estructuras de población jerárquicas con las paralelizaciones adecuadas. [9] No sólo se pueden utilizar clústeres de ordenadores comparativamente caros sino también tarjetas gráficas ( GPU ) económicas para la paralelización. [28] [29]

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 pone de relieve el hecho de que modelo e implementación son dos conceptos diferentes.

Bibliografía

Véase también

Referencias

  1. ^ abcd Cantú-Paz, Erik (1998). "Un estudio de algoritmos genéticos paralelos" (PDF) . Calculadoras paralelas . 10 (2): 141-171.
  2. ^ abcdef Gordon, VS; Whitley, D. (1993), Forrest, S. (ed.), "Algoritmos genéticos seriales y paralelos como optimizadores de funciones" (PDF) , Actas de la Quinta Conferencia Internacional sobre Algoritmos Genéticos , San Mateo, CA: Morgan Kaufmann, págs. 177–183, ISBN 978-1-55860-299-1
  3. ^ Leung, Yee; Gao, Yong; Xu, Zong-Ben (1997). "Grado de diversidad de la población: una perspectiva sobre la convergencia prematura en algoritmos genéticos y su análisis de cadena de Markov". IEEE Transactions on Neural Networks . 8 (5): 1165–1176. doi :10.1109/72.623217. ISSN  1045-9227. PMID  18255718.
  4. ^ abc Gorges-Schleuter, Martina (1990). Algoritmos genéticos y estructuras poblacionales: un algoritmo masivamente paralelo (PhD). Universität Dortmund, Fakultät für Informatik, Alemania.
  5. ^ abcde Cantú-Paz, Erik (1999). Algoritmos genéticos paralelos eficientes y precisos (tesis doctoral, Universidad de Illinois, Urbana-Champaign, EE. UU.). Algoritmos genéticos y computación evolutiva. Vol. 1. Springer, Nueva York, NY. doi :10.1007/978-1-4615-4369-5. ISBN 978-1-4613-6964-6.
  6. ^ abcdefghi Gorges-Schleuter, Martina (1991), Schwefel, Hans-Paul; Männer, Reinhard (eds.), "Paralelismo explícito de algoritmos genéticos a través de estructuras poblacionales", Resolución de problemas paralelos a partir de la naturaleza , Lecture Notes in Computer Science, vol. 496, Berlín/Heidelberg: Springer-Verlag, págs. 150-159, doi :10.1007/bfb0029746, ISBN 978-3-540-54148-6, consultado el 15 de diciembre de 2022
  7. ^ abcde Gordon, V. Scott; Mathias, Keith; Whitley, Darrell (1994). "Algoritmos genéticos celulares como optimizadores de funciones". Actas del simposio ACM de 1994 sobre computación aplicada - SAC '94 . Phoenix, Arizona, Estados Unidos: ACM Press. págs. 237–241. doi :10.1145/326619.326732. ISBN 978-0-89791-647-9.S2CID6418773  .​
  8. ^ ab Giacobini, M.; Tomassini, M.; Tettamanzi, AGB; Alba, E. (octubre de 2005). "Intensidad de selección en algoritmos evolutivos celulares para celosías regulares". Transacciones IEEE sobre computación evolutiva . 9 (5): 489–505. doi :10.1109/TEVC.2005.850298. ISSN  1089-778X. S2CID  3184685.
  9. ^ abc Khalloof, Hatem; Mohammad, Mohammad; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2020-11-02). "Un marco genérico flexible y escalable para la paralelización jerárquica de metaheurísticas basadas en la población". Actas de la 12.ª Conferencia internacional sobre gestión de ecosistemas digitales . Evento virtual Emiratos Árabes Unidos: ACM. págs. 124–131. doi :10.1145/3415958.3433041. ISBN 978-1-4503-8115-4. Número de identificación del sujeto  227179748.
  10. ^ de Sudholt, Dirk (2015), Kacprzyk, Janusz; Pedrycz, Witold (eds.), "Algoritmos evolutivos paralelos" (PDF) , Springer Handbook of Computational Intelligence , Berlín, Heidelberg: Springer, págs. 929–959, doi :10.1007/978-3-662-43505-2_46, ISBN 978-3-662-43504-5, consultado el 13 de febrero de 2023
  11. ^ ab Cantú-Paz, Erick (1999), "Topologías, tasas de migración y algoritmos genéticos paralelos multipoblacionales", Actas de la 1.ª Conferencia Anual sobre Computación Genética y Evolutiva (GECCO) , pp. 91–98
  12. ^ Belkadi, K.; Gourgand, M.; Benyettou, M. (8 de noviembre de 2006). "Algoritmos genéticos paralelos con migración para el problema de programación de flujo híbrido". Revista de Matemáticas Aplicadas y Ciencias de la Decisión . 2006 : 1–17. doi : 10.1155/JAMDS/2006/65746 . ISSN  1173-9126.
  13. ^ Abdelhafez, Amr; Alba, Enrique; Luque, Gabriel (septiembre de 2019). "Análisis de rendimiento de algoritmos genéticos distribuidos sincrónicos y asincrónicos en multiprocesadores". Swarm and Evolutionary Computation . 49 : 147–157. doi :10.1016/j.swevo.2019.06.003. S2CID  196193164.
  14. ^ ab Adar, N.; Kuvat, G. (2016). "Algoritmos genéticos paralelos con topología dinámica utilizando computación en clúster". Avances en ingeniería eléctrica y computacional . 16 (3): 73–80. doi : 10.4316/AECE.2016.03011 . ISSN  1582-7445.
  15. ^ abc Alba, Enrique; Troya, José Ma (2000), Schoenauer, Marc; Deb, Kalyanmoy; Rudolph, Günther; Yao, Xin (eds.), "Algoritmos evolutivos celulares: evaluación de la influencia de la proporción", Parallel Problem Solving from Nature PPSN VI , vol. 1917, Berlín, Heidelberg: Springer, pp. 29–38, doi :10.1007/3-540-45356-3_3, ISBN 978-3-540-41056-0, consultado el 11 de febrero de 2023
  16. ^ Folino, G.; Pizzuti, C.; Spezzano, G. (1998). "Combinación de algoritmos genéticos celulares y búsqueda local para resolver problemas de satisfacibilidad". Actas de la Décima Conferencia Internacional IEEE sobre Herramientas con Inteligencia Artificial (Cat. No.98CH36294) . Taipei, Taiwán: IEEE. págs. 192–198. doi :10.1109/TAI.1998.744842. ISBN . 978-0-7803-5214-8.S2CID8048158  .​
  17. ^ Alba, Enrique; Dorronsoro, Bernabé (2008). Algoritmos genéticos celulares. Nueva York: Springer. pag. 12.ISBN​ 978-0-387-77610-1.OCLC 370728730  .
  18. ^ ab Gorges-Schleuter, Martina (1998), Eiben, Agoston E.; Bäck, Thomas; Schoenauer, Marc; Schwefel, Hans-Paul (eds.), "Un estudio comparativo de la selección global y local en estrategias evolutivas", Resolución de problemas paralelos de la naturaleza — PPSN V , Lecture Notes in Computer Science, vol. 1498, Berlín, Heidelberg: Springer, pp. 367–377, doi :10.1007/bfb0056879, ISBN 978-3-540-65078-2, consultado el 11 de febrero de 2023
  19. ^ Sprave, Joachim (1994), "Estrategia de evolución de vecindarios lineales" (PDF) , Actas de la 3.ª Conferencia Anual sobre Programación Evolutiva , Singapur: World Scientific, págs. 42-51 , consultado el 5 de noviembre de 2022
  20. ^ Jakob, Wilfried (1 de septiembre de 2010). "Un marco de adaptación general basado en costo-beneficio para algoritmos multimeme". Computación memética . 2 (3). pág. 207: 201–218. doi :10.1007/s12293-010-0040-9. ISSN  1865-9292. S2CID  167807.
  21. ^ Alba, Enrique; Dorronsoro, Bernabé; Alfonso, Hugo (2005). «Algoritmos meméticos celulares». Revista de informática y tecnología . 5 (4): 257–263 . Consultado el 4 de noviembre de 2022 .
  22. ^ Wen-Yang Lin; Tzung-Pei Hong; Shu-Min Liu (2004). "Sobre la adaptación de parámetros de migración para algoritmos genéticos multipoblacionales". 2004 IEEE International Conference on Systems, Man and Cybernetics (IEEE Cat. No.04CH37583) . Vol. 6. La Haya, Países Bajos: IEEE. págs. 5731–5735. doi :10.1109/ICSMC.2004.1401108. ISBN . 978-0-7803-8567-2.S2CID31844333  .​
  23. ^ Hong, Tzung-Pei; Lin, Wen-Yang; Liu, Shu-Min; Lin, Jiann-Horng (20 de abril de 2007). "Tasas de migración que se ajustan dinámicamente para algoritmos genéticos multipoblacionales". Revista de inteligencia computacional avanzada e informática inteligente . 11 (4): 410–415. doi : 10.20965/jaciii.2007.p0410 . ISSN  1883-8014.
  24. ^ Luque, Gabriel; Alba, Enrique (2011). Algoritmos genéticos paralelos. Estudios en inteligencia computacional. Vol. 367. Berlín, Heidelberg: Springer. doi :10.1007/978-3-642-22084-5. ISBN 978-3-642-22083-8.
  25. ^ Luque, Gabriel; Alba, Enrique; Dorronsoro, Bernabé (julio de 2009). "Una implementación paralela asincrónica de un algoritmo genético celular para la optimización combinatoria". Actas de la 11.ª conferencia anual sobre computación genética y evolutiva . Montreal, Québec, Canadá: ACM. pp. 1395–1402. doi :10.1145/1569901.1570088. ISBN . 978-1-60558-325-9. Número de identificación del sujeto  14113702.
  26. ^ Zhongwen Luo; Hongzhi Liu (2006). "Algoritmos genéticos celulares y búsqueda local para el problema 3-SAT en hardware gráfico". Conferencia internacional IEEE sobre computación evolutiva de 2006. Vancouver, BC, Canadá: IEEE. págs. 2988–2992. doi :10.1109/CEC.2006.1688685. ISBN. 978-0-7803-9487-2.S2CID8142372  .​
  27. ^ Cahon, S.; Melab, N.; Talbi, E.-G. (mayo de 2004). "ParadisEO: un marco para el diseño reutilizable de metaheurísticas paralelas y distribuidas". Journal of Heuristics . 10 (3): 357–380. doi :10.1023/B:HEUR.0000026900.92269.ec. ISSN  1381-1231. S2CID  14972999.
  28. ^ Jähne, Paul (2016). Mayr, Heinrich Christian; Pinzger, Martín (eds.). Descripción general del estado actual de la investigación sobre paralelización de algoritmos evolutivos en tarjetas gráficas (PDF) . Bonn: Gesellschaft für Informatik, RFA. ISBN 978-3-88579-653-4.OCLC 962381748  . {{cite book}}: |work=ignorado ( ayuda )
  29. ^ García-Calvo, Raúl; Guisado, Jl; Díaz-del-Río, Fernando; Córdoba, Antonio; Jiménez-Morales, Francisco (enero 2018). "Unidad de procesamiento de gráficos: algoritmos genéticos mejorados para resolver la dinámica temporal de las redes reguladoras de genes". Bioinformática Evolutiva . 14 . doi :10.1177/1176934318767889. ISSN  1176-9343. PMC 5898668 . PMID  29662297.