stringtranslate.com

Representación genética

En programación informática , la representación genética es una forma de presentar soluciones/individuos en métodos de computación evolutiva . El término abarca tanto las estructuras de datos concretas y los tipos de datos utilizados para realizar el material genético de las soluciones candidatas en forma de genoma, como las relaciones entre el espacio de búsqueda y el espacio de problemas. En el caso más simple, el espacio de búsqueda corresponde al espacio de problemas (representación directa). [1] La elección de la representación del problema está ligada a la elección de los operadores genéticos , los cuales tienen un efecto decisivo en la eficiencia de la optimización. [2] [3] La representación genética puede codificar la apariencia, el comportamiento y las cualidades físicas de los individuos. La diferencia en las representaciones genéticas es uno de los principales criterios que trazan una línea entre las clases conocidas de computación evolutiva. [4] [5]

La terminología suele ser análoga a la genética natural . El bloque de memoria de la computadora que representa una solución candidata se denomina individuo. Los datos de ese bloque se denominan cromosoma . Cada cromosoma consta de genes. Los valores posibles de un gen en particular se denominan alelos . Un programador puede representar a todos los individuos de una población utilizando codificación binaria , codificación permutacional , codificación por árbol o cualquiera de varias otras representaciones. [6] [7]

Representaciones en algunos algoritmos evolutivos populares

Los algoritmos genéticos (AG) son típicamente representaciones lineales; [8] a menudo, pero no siempre, [9] [10] [11] son ​​binarios. [10] La descripción original de Holland de los AG utilizaba matrices de bits . Se pueden utilizar matrices de otros tipos y estructuras esencialmente de la misma manera. La propiedad principal que hace que estas representaciones genéticas sean convenientes es que sus partes se alinean fácilmente debido a su tamaño fijo. Esto facilita la operación de cruce simple. Dependiendo de la aplicación, las representaciones de longitud variable también se han utilizado y probado con éxito en algoritmos evolutivos (EA) [12] [13] en general y algoritmos genéticos [14] [15] en particular, aunque la implementación del cruce es más compleja en este caso.

La estrategia de evolución utiliza representaciones lineales de valores reales, por ejemplo, una matriz de valores reales. Utiliza principalmente la mutación gaussiana y el cruce de mezclas/promedios. [16]

La programación genética (PG) fue pionera en el uso de representaciones arbóreas y desarrolló operadores genéticos adecuados para dichas representaciones. Las representaciones arbóreas se utilizan en la GP para representar y desarrollar programas funcionales con las propiedades deseadas. [17]

El algoritmo genético basado en el ser humano (HBGA) ofrece una forma de evitar la resolución de problemas de representación difíciles al subcontratar todos los operadores genéticos a agentes externos, en este caso, humanos. El algoritmo no necesita conocer una representación genética fija en particular siempre que haya suficientes agentes externos capaces de manejar esas representaciones, lo que permite representaciones genéticas de forma libre y en evolución.

Representaciones genéticas comunes

Distinción entre espacio de búsqueda y espacio de problemas

De manera análoga a la biología, los EA distinguen entre el espacio de problemas (que corresponde al fenotipo ) y el espacio de búsqueda (que corresponde al genotipo ). El espacio de problemas contiene soluciones concretas al problema que se está abordando, mientras que el espacio de búsqueda contiene las soluciones codificadas. La asignación del espacio de búsqueda al espacio de problemas se denomina asignación genotipo-fenotipo . Los operadores genéticos se aplican a los elementos del espacio de búsqueda y, para la evaluación, los elementos del espacio de búsqueda se asignan a los elementos del espacio de problemas a través de la asignación genotipo-fenotipo. [18] [19]

Relaciones entre el espacio de búsqueda y el espacio de problemas

La importancia de una elección apropiada del espacio de búsqueda para el éxito de una aplicación de EA se reconoció desde el principio. [20] [21] [22] Se pueden establecer los siguientes requisitos para un espacio de búsqueda adecuado y, por lo tanto, para un mapeo genotipo-fenotipo adecuado: [23] [24]

Lo completo

Todas las posibles soluciones admisibles deben estar contenidas en el espacio de búsqueda.

Redundancia

Cuando existen más genotipos posibles que fenotipos, la representación genética del EA se denomina redundante . En la naturaleza, esto se denomina código genético degenerado . En el caso de una representación redundante, son posibles las mutaciones neutrales . Se trata de mutaciones que cambian el genotipo pero no afectan al fenotipo. Por lo tanto, dependiendo del uso de los operadores genéticos , puede haber descendencia fenotípicamente inalterada, lo que puede conducir a determinaciones de aptitud innecesarias, entre otras cosas. Dado que la evaluación en aplicaciones del mundo real suele representar la mayor parte del tiempo de cálculo, puede ralentizar el proceso de optimización . Además, esto puede hacer que la población tenga una mayor diversidad genotípica que fenotípica, lo que también puede obstaculizar el progreso evolutivo.

En biología, la teoría neutral de la evolución molecular afirma que este efecto desempeña un papel dominante en la evolución natural. Esto ha motivado a los investigadores de la comunidad de la EA a examinar si las mutaciones neutrales pueden mejorar el funcionamiento de la EA [25] al proporcionar a las poblaciones que han convergido a un óptimo local una forma de escapar de ese óptimo local a través de la deriva genética . Esto se discute de manera controvertida y no hay resultados concluyentes sobre la neutralidad en las EA. [26] [27] Por otro lado, existen otras medidas probadas para manejar la convergencia prematura .

Localidad

La localidad de una representación genética corresponde al grado en el que las distancias en el espacio de búsqueda se conservan en el espacio del problema después del mapeo genotipo-fenotipo. Es decir, una representación tiene una localidad alta exactamente cuando los vecinos en el espacio de búsqueda también son vecinos en el espacio del problema. Para que los esquemas exitosos no sean destruidos por el mapeo genotipo-fenotipo después de una mutación menor , la localidad de una representación debe ser alta.

Escalada

En el mapeo genotipo-fenotipo, los elementos del genotipo pueden escalarse (ponderarse) de manera diferente. El caso más simple es el escalamiento uniforme: todos los elementos del genotipo tienen el mismo peso en el fenotipo. Un escalamiento común es el exponencial. Si los números enteros están codificados en binario, los dígitos individuales del número binario resultante tienen pesos exponencialmente diferentes al representar el fenotipo.

Ejemplo: El número 90 se escribe en binario (es decir, en base dos) como 1011010. Si ahora se cambia uno de los dígitos delanteros en la notación binaria, esto tiene un efecto significativamente mayor en el número codificado que cualquier cambio en los dígitos traseros (la presión de selección tiene un efecto exponencialmente mayor en los dígitos delanteros).

Por esta razón, el escalamiento exponencial tiene el efecto de fijar aleatoriamente las ubicaciones "posteriores" en el genotipo antes de que la población se acerque lo suficiente al óptimo para ajustar estas sutilezas.

Hibridación y reparación en el mapeo genotipo-fenotipo

Al mapear el genotipo al fenotipo que se está evaluando, el conocimiento específico del dominio se puede utilizar para mejorar el fenotipo y/o asegurar que se cumplan las restricciones. [28] [29] Este es un método comúnmente utilizado para mejorar el rendimiento de EA en términos de tiempo de ejecución y calidad de la solución. Se ilustra a continuación con dos de los tres ejemplos.

Ejemplos

Ejemplo de representación directa

Una codificación obvia y comúnmente utilizada para el problema del viajante de comercio y tareas relacionadas es numerar las ciudades que se visitarán consecutivamente y almacenarlas como números enteros en el cromosoma . Los operadores genéticos deben estar adecuadamente adaptados para que solo cambien el orden de las ciudades (genes) y no provoquen deleciones o duplicaciones. [30] [31] Por lo tanto, el orden de los genes corresponde al orden de las ciudades y hay una asignación simple uno a uno.

Ejemplo de un mapeo genotipo-fenotipo complejo.

En una tarea de programación con recursos heterogéneos y parcialmente alternativos que se deben asignar a un conjunto de subtareas, el genoma debe contener toda la información necesaria para las operaciones de programación individuales o debe ser posible derivarlas de él. Además del orden de las subtareas que se deben ejecutar, esto incluye información sobre la selección de recursos. [32] Un fenotipo consiste entonces en una lista de subtareas con sus tiempos de inicio y recursos asignados. Para poder crear esto, se deben crear tantas matrices de asignación como recursos se puedan asignar a una subtarea como máximo. En el caso más simple, se trata de un recurso, por ejemplo, una máquina, que puede realizar la subtarea. Una matriz de asignación es una matriz bidimensional, con una dimensión que son las unidades de tiempo disponibles y la otra son los recursos que se deben asignar. Las celdas vacías de la matriz indican disponibilidad, mientras que una entrada indica el número de la subtarea asignada. La creación de matrices de asignación garantiza en primer lugar que no haya asignaciones múltiples inadmisibles. En segundo lugar, se pueden leer los tiempos de inicio de las subtareas, así como los recursos asignados. [33]

Una restricción común al programar recursos para subtareas es que un recurso solo se puede asignar una vez por unidad de tiempo y que la reserva debe ser por un período de tiempo contiguo. [34] Para lograr esto de manera oportuna, que es un objetivo de optimización común y no una restricción, se puede utilizar una heurística simple : asignar el recurso requerido para el período de tiempo deseado lo antes posible, evitando reservas duplicadas. La ventaja de este procedimiento simple es doble: evita la restricción y ayuda a la optimización.

Si el problema de programación se modifica a la programación de flujos de trabajo en lugar de subtareas independientes, al menos algunos de los pasos de trabajo de un flujo de trabajo tienen que ser ejecutados en un orden determinado. [35] Si la heurística de programación descrita anteriormente ahora determina que el predecesor de un paso de trabajo no se completa cuando debería iniciarse, el siguiente mecanismo de reparación puede ayudar: posponer la programación de este paso de trabajo hasta que todos sus predecesores hayan terminado. [33] Dado que el genotipo permanece sin cambios y la reparación se realiza solo a nivel de fenotipo, también se denomina reparación fenotípica .

Ejemplo de un mapeo genotipo-fenotipo basado en heurística

La siguiente tarea de planificación de la disposición [36] pretende ilustrar un uso diferente de una heurística en el mapeo genotipo-fenotipo: sobre una superficie rectangular se deben disponer diferentes tipos geométricos de objetos de tal manera que quede sin utilizar la menor área posible. Los objetos se pueden girar, no se deben superponer después de su colocación y se deben colocar completamente sobre la superficie. Una aplicación relacionada sería la minimización de desechos al cortar piezas de una placa de acero o una lámina de tela.

Las coordenadas de los centros de los objetos y un ángulo de rotación reducido a posibles isomorfismos de la geometría de los objetos pueden considerarse como variables a determinar. Si esto se hace directamente por un EA, probablemente habrá muchos solapamientos. Para evitarlo, el EA solo determina el ángulo y la coordenada de un lado del rectángulo. Ahora cada objeto se gira y se posiciona en el borde de ese lado, desplazándolo si es necesario para que esté dentro del rectángulo cuando se mueva posteriormente. Luego se mueve paralelo al otro lado hasta que toca otro objeto o llega al extremo opuesto del rectángulo. De esta manera, se evitan los solapamientos y se reduce el área no utilizada por colocación, pero no en general, lo que se deja a la optimización. [37]

Referencias

  1. ^ Eiben, AE; Smith, JE (2015). Introducción a la computación evolutiva. Serie Natural Computing. Berlín, Heidelberg: Springer. p. 40. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
  2. ^ Rothlauf, Franz (2002). Representaciones para algoritmos genéticos y evolutivos. Estudios sobre borrosidad y computación blanda. Vol. 104. Heidelberg: Physica-Verlag HD. p. 31. doi :10.1007/978-3-642-88094-0. ISBN 978-3-642-88096-4.
  3. ^ Eiben, AE; Smith, JE (2015). "Representación y los roles de los operadores de variación". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 49-51. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
  4. ^ Eiben, AE; Smith, JE (2015). "Variantes populares de algoritmos evolutivos". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 99-118. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
  5. ^ Fogel, DB (1995). "Fenotipos, genotipos y operadores en computación evolutiva". Actas de la Conferencia Internacional IEEE de 1995 sobre Computación Evolutiva . Vol. 1. Perth, WA, Australia: IEEE. págs. 193–198. doi :10.1109/ICEC.1995.489143. ISBN . 978-0-7803-2759-7.S2CID17755853  .​
  6. ^ Tomáš Kuthan y Jan Lánský. "Algoritmos genéticos en la compresión de textos basados ​​en sílabas". 2007. pág. 26.
  7. ^ Eiben, AE; Smith, JE (2015). "Representación, mutación y recombinación". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 49–78. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
  8. ^ Goldberg, David E. (1989). Algoritmos genéticos en búsqueda, optimización y aprendizaje automático . Reading, Mass.: Addison-Wesley. ISBN 0-201-15767-5.OCLC 17674450  .
  9. ^ Michalewicz, Zbigniew (1996). Algoritmos genéticos + estructuras de datos = programas evolutivos . Tercera edición revisada y ampliada. Berlín, Heidelberg: Springer. ISBN 978-3-662-03315-9.OCLC 851375253  .
  10. ^ ab Whitley, Darrell (1994). "Un tutorial sobre algoritmos genéticos". Estadística y computación . 4 (2). doi :10.1007/BF00175354. ISSN  0960-3174. S2CID  3447126.
  11. ^ Herrera, F.; Lozano, M.; Verdegay, JL (1998). "Abordando algoritmos genéticos con código real: operadores y herramientas para el análisis del comportamiento". Revisión de inteligencia artificial . 12 (4): 265–319. doi :10.1023/A:1006504901164. S2CID  6798965.
  12. ^ Blume, Christian; Jakob, Wilfried (2002), "GLEAM - Un algoritmo evolutivo para la planificación y el control basado en la estrategia evolutiva", Conf. Proc. of Genetic and Evolutionary Computation Conference (GECCO 2002) , vol. Late Breaking Papers, págs. 31–38 , consultado el 1 de enero de 2023
  13. ^ Hitomi, Nozomi; Selva, Daniel (2018), "Optimización de constelaciones usando un algoritmo evolutivo con un cromosoma de longitud variable", 2018 IEEE Aerospace Conference , IEEE, págs. 1–12, doi :10.1109/AERO.2018.8396743, ISBN 978-1-5386-2014-4, Número de identificación del sujeto  49541423
  14. ^ De Jong, Kenneth A. (2006). "Representación". Computación evolutiva: un enfoque unificado. Nueva Delhi: Prentice-Hall of India. págs. 72–75. ISBN 978-81-203-3002-3.OCLC 276452339  .
  15. ^ Pawar, Sunil Nilkanth; Bichkar, Rajankumar Sadashivrao (2015). "Algoritmo genético con cromosomas de longitud variable para la detección de intrusiones en la red". Revista Internacional de Automatización y Computación . 12 (3): 337–342. doi : 10.1007/s11633-014-0870-x . ISSN  1476-8186. S2CID  255346767.
  16. ^ Schwefel, Hans-Paul (1995). Evolución y búsqueda del óptimo. Nueva York: Wiley & Sons. ISBN 0-471-57148-2.OCLC 30701094  .
  17. ^ Koza, John R. (1989), Sridharan, NS (ed.), "Algoritmos genéticos jerárquicos que operan en poblaciones de programas informáticos", Actas de la undécima conferencia conjunta internacional sobre inteligencia artificial IJCAI-89 , vol. 1, San Mateo, CA, EE. UU.: Morgan Kaufmann, págs. 768–774
  18. ^ Rothlauf, Franz (2002). Representaciones para algoritmos genéticos y evolutivos. Estudios sobre borrosidad y computación blanda. Vol. 104. Heidelberg: Physica-Verlag HD. doi :10.1007/978-3-642-88094-0. ISBN 978-3-642-88096-4.
  19. ^ Whigham, Peter A.; Dick, Grant; Maclaurin, James (2017). "Sobre la correlación entre genotipo y fenotipo en algoritmos evolutivos". Programación genética y máquinas evolutivas . 18 (3): 353–361. doi :10.1007/s10710-017-9288-x. ISSN  1389-2576. S2CID  254510517.
  20. ^ Caruana, Richard A.; Schaffer, J. David (1988), "Representación y sesgo oculto: codificación gris frente a codificación binaria para algoritmos genéticos", Machine Learning Proceedings 1988 , Elsevier, págs. 153-161, doi :10.1016/b978-0-934613-64-4.50021-9, ISBN 978-0-934613-64-4, consultado el 19 de enero de 2023
  21. ^ Liepins, Gunar E.; Vose, Michael D. (1990). "Cuestiones de representación en la optimización genética". Revista de inteligencia artificial experimental y teórica . 2 (2): 101–115. doi :10.1080/09528139008953717. ISSN  0952-813X.
  22. ^ Coli, M.; Palazzari, P. (1995), "Búsqueda de la codificación óptima en algoritmos genéticos", Actas de la Conferencia Internacional IEEE de 1995 sobre Computación Evolutiva , IEEE, doi :10.1109/ICEC.1995, ISBN 978-0-7803-2759-7
  23. ^ Eiben, Agoston E. (2015). "Representación (definición de individuos)". Introducción a la computación evolutiva . JE Smith (2.ª ed.). Berlín, Heidelberg: Springer. pp. 28–30. ISBN 978-3-662-44874-8.OCLC 913232837  .
  24. ^ Rothlauf, Franz (2006). "Tres elementos de una teoría de representaciones". Representaciones para algoritmos genéticos y evolutivos (2.ª ed.). Heidelberg: Springer. pp. 33–96. ISBN 978-3-540-32444-7.OCLC 262692044  .
  25. ^ Galván-López, Edgar; Dignum, Stephen; Poli, Riccardo (2008), O'Neill, Michael; Vanneschi, Leonardo; Gustafson, Steven; Esparcia Alcázar, Anna Isabel (eds.), "Los efectos de la neutralidad constante en el rendimiento y la dificultad del problema en GP", Programación genética , Lecture Notes in Computer Science, vol. 4971, Berlín, Heidelberg: Springer, pp. 312–324, doi :10.1007/978-3-540-78671-9_27, ISBN 978-3-540-78670-2, S2CID  6803107 , consultado el 21 de enero de 2023
  26. ^ Galván-López, Edgar; Poli, Riccardo; Kattan, Ahmed; O'Neill, Michael; Brabazon, Anthony (2011). "Neutralidad en algoritmos evolutivos... ¿Qué sabemos?". Evolving Systems . 2 (3): 145–163. doi :10.1007/s12530-011-9030-5. hdl : 10197/3532 . ISSN  1868-6478. S2CID  15951086.
  27. ^ Knowles, Joshua D.; Watson, Richard A. (2002), Guervós, Juan Julián Merelo; Adamidis, Panagiotis; Beyer, Hans-Georg; Schwefel, Hans-Paul (eds.), "Sobre la utilidad de las codificaciones redundantes en la búsqueda evolutiva basada en mutaciones", Parallel Problem Solving from Nature — PPSN VII , vol. 2439, Berlín, Heidelberg: Springer, pp. 88–98, doi :10.1007/3-540-45712-7_9, ISBN 978-3-540-44139-7, consultado el 21 de enero de 2023
  28. ^ Eiben, AE; Smith, JE (2015). "Hibridación durante el mapeo de genotipo a fenotipo". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 177-178. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
  29. ^ Hart, Emma; Ross, Peter; Nelson, Jeremy (1998). "Resolución de un problema del mundo real mediante un generador de cronogramas impulsado heurísticamente en evolución". Computación evolutiva . 6 (1): 61–80. doi :10.1162/evco.1998.6.1.61. ISSN  1063-6560. PMID  10021741. S2CID  6898505.
  30. ^ Eiben, AE; Smith, JE (2015). "Representación de permutaciones". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 67–74. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto  20912932.
  31. ^ Larrañaga, P.; Kuijpers, CMH; Murga, RH; Inza, I.; Dizdarevic, S. (1999). "Algoritmos genéticos para el problema del viajante: una revisión de representaciones y operadores". Revisión de Inteligencia Artificial . 13 (2): 129–170. doi :10.1023/A:1006529012972. S2CID  10284682.
  32. ^ Bruns, Ralf (1 de enero de 1997). "Enfoques computacionales evolutivos para la planificación". En Baeck, Thomas; Fogel, DB; Michalewicz, Z (eds.). Manual de computación evolutiva. CRC Press. doi :10.1201/9780367802486. ISBN. 978-0-367-80248-6.
  33. ^ ab Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe; Süß, Wolfgang (22 de abril de 2013). "Reprogramación rápida de múltiples flujos de trabajo para recursos heterogéneos restringidos mediante computación memética de múltiples criterios". Algorithms . 6 (2): 245–277. doi : 10.3390/a6020245 . ISSN  1999-4893.
  34. ^ Brucker, Peter (2007). Algoritmos de programación. Berlín, Heidelberg: Springer. doi :10.1007/978-3-540-69516-5. ISBN 978-3-540-69515-8.
  35. ^ Sakellariou, Rizos; Zhao, Henán; Tsiakkouri, Eleni; Dikaiakos, Marios D. (2007), Gorlatch, Sergei; Danelutto, Marco (eds.), "Programación de flujos de trabajo con restricciones presupuestarias", Investigación integrada en computación GRID , Boston, MA: Springer US, págs. 189-202, doi :10.1007/978-0-387-47658-2_14, ISBN 978-0-387-47656-8, consultado el 20 de enero de 2023
  36. ^ Fujita, Kikuo; Akagi, Shinsuke; Hirokawa, Noriyasu (19 de septiembre de 1993). "Enfoque híbrido para anidamiento óptimo utilizando un algoritmo genético y un algoritmo de minimización local". Actas de las Conferencias técnicas de diseño de ASME de 1993. 19.ª Conferencia de automatización del diseño: Volumen 1: dinámica de sistemas mecánicos; diseño concurrente y robusto; diseño para ensamblaje y fabricación; algoritmos genéticos en diseño y optimización estructural . Albuquerque, Nuevo México, EE. UU.: Sociedad Estadounidense de Ingenieros Mecánicos. págs. 477–484. doi :10.1115/DETC1993-0337. ISBN 978-0-7918-1181-8.
  37. ^ Jakob, Wilfried (2021), "La planificación del diseño como ejemplo de manejo inteligente de restricciones complejas", Aplicación exitosa de algoritmos evolutivos: una guía obtenida de aplicaciones del mundo real. , KIT Scientific Working Papers, vol. 170, Karlsruhe: KIT Scientific Publishing, págs. 12-14, arXiv : 2107.11300 , doi : 10.5445/IR/1000135763, S2CID  236318422