stringtranslate.com

Modelo de población (algoritmo evolutivo)

El modelo poblacional de un algoritmo evolutivo (EA) 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 a seguir. Los individuos de una población pueden generar más individuos como descendencia con la ayuda de los operadores genéticos del procedimiento.

El modelo poblacional más simple y ampliamente utilizado en las AE es el modelo global o panmíctico , que corresponde a una población no estructurada. [1] [2] Permite a cada individuo elegir cualquier otro individuo de la población como socio para la producción de descendencia por cruce , por lo que los detalles de la selección son irrelevantes siempre que la aptitud de los individuos desempeñe un papel importante. 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 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 se puede observar con mayor frecuencia en poblaciones panmícticas. [4]

En la naturaleza, rara vez se encuentran grupos globales de apareamiento. Lo que prevalece es un cierto y limitado aislamiento debido a la distancia espacial. Los vecindarios locales resultantes evolucionan inicialmente de forma independiente y los mutantes tienen mayores posibilidades de persistir durante varias generaciones. Como resultado, la diversidad genotípica en el acervo genético se conserva por más tiempo que en una población panmíctica.

Por lo tanto, es obvio dividir la población anteriormente global por subestructuras. Para ello 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 barrio , que asignan individuos a barrios superpuestos. , [4] [6] también conocidos como algoritmos genéticos o evolutivos celulares (cGA o cEA). [7] [8] La correspondiente división de la población sugiere también una correspondiente paralelización del procedimiento. Por esta razón, el tema de los modelos poblacionales también se discute frecuentemente en la literatura en relación con la paralelización de los EA. [1] [2] [4] [5] [9] [10]

Modelos de isla

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 insular, también llamado modelo de migración o modelo de grano grueso , la evolución tiene lugar en subpoblaciones estrictamente divididas. Estos pueden organizarse panmícticamente, pero no es necesario. De vez en cuando se produce un intercambio de individuos, lo que se denomina migración . [2] [5] El tiempo entre un intercambio se llama época y su final puede ser desencadenado por varios criterios: por ejemplo, después de un tiempo determinado o un número determinado de generaciones completas, o después de que se produzca un estancamiento. El estancamiento puede detectarse, por ejemplo, por el hecho de que no se ha producido ninguna mejora en la aptitud física en la isla durante un número determinado de generaciones. Los modelos de islas introducen una variedad de nuevos parámetros estratégicos: [11] [12] [13] [14]

Con estos parámetros se puede influir considerablemente en la presión de selección. Por ejemplo, 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 de toro (derecha) con dos figuras vecinas bidimensionales ejemplares (izquierda). Los demes en forma de bloque de los individuos A y B tienen 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 de EA una estructura especial definida como un gráfico 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 están conceptualmente colocados en una malla toroidal y solo se les permite recombinarse con individuos cercanos. Esto lleva a una especie de localidad conocida como aislamiento por distancia . [6] [7] El conjunto de parejas potenciales de un individuo se llama vecindario o demo . La figura adyacente lo ilustra al mostrar dos vecindarios ligeramente superpuestos de dos individuos marcados en amarillo, a través de los cuales la información genética puede difundirse entre los dos demes. Se sabe que en este tipo de algoritmo, 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 contenidos de soluciones durante este proceso. Al mismo tiempo, los nichos más lejanos pueden verse afectados más lentamente. [6] [7] Los EA con este tipo de población también son bien conocidos como EA celulares (cEA) [8] [15] o algoritmos genéticos celulares (cGA). [7] [16]

Ejemplos de barrios, también llamados demos, en EA celulares bidimensionales: lineales, compactos, rombos y... cualquier otro.
Dos ejemplos de vecindades superpuestas (demes) del modelo de vecindad unidimensional en forma de anillo de un EA. Los dos demos de los individuos X e Y se superponen mínimamente, mientras que los de A y B muestran un 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 ampliar fácilmente (a 3D) o reducir (a 1D, por ejemplo, un anillo, [ 6] [15] ver la figura de la derecha). La vecindad de un individuo particular en la cuadrícula se define en términos de la distancia de Manhattan entre él y otros miembros de la población. En el algoritmo básico, todos los barrios tienen el mismo tamaño y formas idénticas. Los dos vecindarios más utilizados para CEA bidimensionales son L5 y C9; consulte la figura de la izquierda. Aquí, L significa Lineal mientras que C significa Compacto . Cada demo representa una subpoblación panmíctica dentro de la cual la selección de pareja y la aceptación de la descendencia tiene lugar mediante la sustitución del 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 reemplazado o, de manera menos estricta, sólo mejor que el peor individuo del grupo. . [2] [6] La primera regla es elitista y crea una presión selectiva más alta 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 difusión mayoritariamente lenta de la información genética a través de los límites del vecindario, de ahí el nombre modelo de difusión . Una descendencia mejor ahora necesita más generaciones que en panmixy para extenderse entre la población. Esto promueve el surgimiento 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 en profundidad adaptado al espacio de búsqueda durante una ejecución. La búsqueda en profundidad se realiza 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 difusión de 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 las vecindades de anillo son muy adecuadas para lograr resultados de alta calidad, incluso si esto requiere tiempos de ejecución comparativamente largos. Por otro lado, si uno está interesado principalmente en resultados rápidos y buenos, pero posiblemente subóptimos, las topologías 2D son más adecuadas.

Comparación

Al aplicar ambos modelos poblacionales 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 forma más fiable y rápida de lo que se esperaría con los EA panmícticos.

Los modelos de isla tienen la desventaja, en comparación con los modelos de vecindario, de que introducen una gran cantidad de nuevos parámetros estratégicos. A pesar de los estudios existentes sobre este tema en la literatura, [11] [22] [23] persiste un cierto riesgo de entornos desfavorables para el usuario. En los modelos de vecindad, por el contrario, sólo hay que 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 una 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. Así, 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 pueden paralelizarse adicionalmente. [9] [14] [27] En aplicaciones del mundo real, las evaluaciones suelen ser, con diferencia, la parte que consume más tiempo. Por supuesto, también es posible diseñar las subpoblaciones insulares como ACE, de modo que se apliquen las afirmaciones anteriores sobre la paralelización de ACE. De esta manera se pueden crear estructuras de población jerárquicas con las paralelizaciones adecuadas. [9] Para la paralelización se pueden utilizar no sólo clusters de ordenadores relativamente caros, sino también tarjetas gráficas ( GPU ) económicas. [28] [29]

Sin embargo, es importante destacar que los CEA, o los 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 en plataformas secuenciales y paralelas, lo que destaca el hecho de que modelo e implementación son dos conceptos diferentes.

Bibliografía

Ver 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 en serie 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, sí; Gao, Yong; Xu, Zong-Ben (1997). "Grado de diversidad poblacional: una perspectiva sobre la convergencia prematura en algoritmos genéticos y su análisis de la cadena de Markov". Transacciones IEEE en redes neuronales . 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, Nueva York. 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, recuperado el 15 de diciembre de 2022
  7. ^ abcde Gordon, V. Scott; Mathías, Keith; Whitley, Darrell (1994). "Algoritmos genéticos celulares como optimizadores de funciones". Actas del simposio ACM de 1994 sobre informática aplicada - SAC '94 . Phoenix, Arizona, Estados Unidos: ACM Press. págs. 237-241. doi :10.1145/326619.326732. ISBN 978-0-89791-647-9. S2CID  6418773.
  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; Mahoma, Mahoma; Shahoud, Shadi; Duepmeier, Clemens; Hagenmeyer, Veit (2 de noviembre de 2020). "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. S2CID  227179748.
  10. ^ ab 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 de poblaciones múltiples", Proc. de la 1ª Conferencia Anual. sobre Computación Genética y Evolutiva (GECCO) , págs. 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 del taller 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 2019). "Análisis de rendimiento de algoritmos genéticos distribuidos síncronos y asíncronos en multiprocesadores". Enjambre y computación evolutiva . 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 mediante computación en clúster". Avances en Ingeniería Eléctrica e Informática . 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; Rodolfo, Günther; Yao, Xin (eds.), "Algoritmos evolutivos celulares: evaluación de la influencia de la proporción", Resolución de problemas paralelos a partir de la naturaleza PPSN VI , vol. 1917, Berlín, Heidelberg: Springer, págs. 29–38, doi :10.1007/3-540-45356-3_3, ISBN 978-3-540-41056-0, recuperado 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 la resolución de problemas de satisfacibilidad". Actas 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. S2CID  8048158.
  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.; Detrás, Thomas; Schoenauer, Marc; Schwefel, Hans-Paul (eds.), "Un estudio comparativo de la selección global y local en las estrategias de evolución", Resolución de problemas paralelos desde la naturaleza - PPSN V , Lecture Notes in Computer Science, vol. 1498, Berlín, Heidelberg: Springer, págs. 367–377, doi :10.1007/bfb0056879, ISBN 978-3-540-65078-2, recuperado el 11 de febrero de 2023
  19. ^ Sprave, Joachim (1994), "Estrategia de evolución de vecindario lineal" (PDF) , Actas de la tercera 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 general de adaptación basado en costos-beneficios para algoritmos multimemas". Computación memética . 2 (3). pag. 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 Ciencias y Tecnología de la Computación . 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 Conferencia internacional IEEE sobre sistemas, hombre y cibernética (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. S2CID  31844333.
  23. ^ Hong, Tzung-Pei; Lin, Wen-Yang; Liu, Shu-Min; Lin, Jiann-Horng (20 de abril de 2007). "Ajustar dinámicamente las tasas de migración 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 optimización combinatoria". Actas de la undécima conferencia anual sobre computación genética y evolutiva . Montreal Québec Canadá: ACM. págs. 1395-1402. doi :10.1145/1569901.1570088. ISBN 978-1-60558-325-9. S2CID  14113702.
  26. ^ Zhongwen Luo; Hongzhi Liu (2006). "Algoritmos genéticos celulares y búsqueda local de problema 3-SAT en hardware gráfico". Conferencia internacional IEEE 2006 sobre Computación Evolutiva . Vancouver, BC, Canadá: IEEE. págs. 2988–2992. doi :10.1109/CEC.2006.1688685. ISBN 978-0-7803-9487-2. S2CID  8142372.
  27. ^ Cahon, S.; Melab, N.; Talbi, E.-G. (mayo de 2004). "ParadisEO: un marco para el diseño reutilizable de metaheurísticas distribuidas y paralelas". Revista de heurística . 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.