Hispanopedia Wiki
Articulo de referencia

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 estruc...

Hispanopedia WikiContenido en espanolLectura gratuita

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 como los tipos de datos utilizados para realizar el material genético de las soluciones candidatas en forma de genoma, y ​​las relaciones entre el espacio de búsqueda y el espacio del problema. En el caso más simple, el espacio de búsqueda corresponde al espacio del problema (representación directa). [ 1 ] La elección de la representación del problema está ligada a la elección de los operadores genéticos , ambos con 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 divisoria entre las clases conocidas de computación evolutiva. [ 4 ] [ 5 ]

La terminología suele ser análoga a la de la genética natural . El bloque de memoria de la computadora que representa una solución candidata se llama individuo. Los datos en ese bloque se llaman cromosoma . Cada cromosoma consta de genes. Los posibles valores de un gen en particular se llaman 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 ]

Los algoritmos genéticos (AG) son típicamente representaciones lineales; [ 8 ] estas son a menudo, pero no siempre, [ 9 ] [ 10 ] [ 11 ] binarias. [ 10 ] La descripción original de GA de Holland usó arreglos de bits . Los arreglos de otros tipos y estructuras pueden usarse esencialmente de la misma manera. La propiedad principal que hace convenientes estas representaciones genéticas es que sus partes se alinean fácilmente debido a su tamaño fijo. Esto facilita una operación de cruce simple. Dependiendo de la aplicación, las representaciones de longitud variable también se han usado y probado con éxito en algoritmos evolutivos (AE) [ 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 evolutiva utiliza representaciones lineales de valores reales, por ejemplo, una matriz de valores reales. Utiliza principalmente mutación gaussiana y cruce por mezcla/promediado. [ 16 ]

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

El algoritmo genético basado en humanos (HBGA) ofrece una forma de evitar la resolución de problemas de representación complejos al delegar todas las operaciones genéticas a agentes externos, en este caso, humanos. El algoritmo no necesita conocer una representación genética fija específica, siempre que existan suficientes agentes externos capaces de manejar dichas representaciones, lo que permite representaciones genéticas de forma libre y en constante evolución.

Representaciones genéticas comunes

Distinción entre espacio de búsqueda y espacio del problema

De forma análoga a la biología, los algoritmos evolutivos distinguen entre el espacio del problema (que corresponde al fenotipo ) y el espacio de búsqueda (que corresponde al genotipo ). El espacio del problema contiene soluciones concretas al problema que se aborda, mientras que el espacio de búsqueda contiene las soluciones codificadas. El mapeo del espacio de búsqueda al espacio del problema se denomina mapeo 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 mapean a elementos del espacio del problema mediante el mapeo genotipo-fenotipo. [ 18 ] [ 19 ]

Relaciones entre el espacio de búsqueda y el espacio del problema.

La importancia de una elección apropiada del espacio de búsqueda para el éxito de una aplicación 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 soluciones admisibles posibles deben estar contenidas en el espacio de búsqueda.

Redundancia

Cuando existen más genotipos posibles que fenotipos, la representación genética del algoritmo evolutivo se denomina redundante . En la naturaleza, esto se conoce como código genético degenerado . En el caso de una representación redundante, son posibles mutaciones neutras . Estas mutaciones modifican el genotipo pero no el fenotipo. Por lo tanto, dependiendo del uso de los operadores genéticos , puede haber descendencia fenotípicamente inalterada, lo que puede dar lugar, entre otras cosas, a determinaciones de aptitud innecesarias. 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 provocar que la población tenga 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 juega un papel dominante en la evolución natural. Esto ha motivado a los investigadores de la comunidad EA a examinar si las mutaciones neutrales pueden mejorar el funcionamiento de 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 EA. [ 26 ] [ 27 ] Por otro lado, hay otras medidas probadas para manejar la convergencia prematura .

Localidad

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

Escalada

En el mapeo genotipo-fenotipo, los elementos del genotipo pueden ponderarse de forma diferente. El caso más sencillo es la ponderación uniforme: todos los elementos del genotipo tienen el mismo peso en el fenotipo. Una ponderación común es la exponencial. Si los números enteros se codifican en binario, los dígitos individuales del número binario resultante tienen ponderaciones 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 iniciales en la notación binaria, esto tiene un efecto significativamente mayor en el número codificado que cualquier cambio en los dígitos finales (la presión de selección tiene un efecto exponencialmente mayor en los dígitos iniciales).

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 como para ajustarse a estas sutilezas.

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

Al relacionar el genotipo con el fenotipo evaluado, se puede utilizar el conocimiento específico del dominio 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 los algoritmos evolutivos en términos de tiempo de ejecución y calidad de la solución. A continuación, se ilustra con dos de los tres ejemplos.

Ejemplos

Ejemplo de una representación directa

Una codificación obvia y comúnmente utilizada para el problema del viajante y tareas relacionadas consiste en numerar las ciudades que se visitarán consecutivamente y almacenarlas como números enteros en el cromosoma . Los operadores genéticos deben adaptarse adecuadamente para que solo cambien el orden de las ciudades (genes) y no provoquen deleciones ni duplicaciones. [ 30 ] [ 31 ] De este modo, el orden de los genes corresponde al orden de las ciudades y existe una correspondencia simple uno a uno.

Ejemplo de un mapeo complejo genotipo-fenotipo

En una tarea de planificación con recursos heterogéneos y parcialmente alternativos que se asignarán a un conjunto de subtareas, el genoma debe contener toda la información necesaria para las operaciones de planificación individuales o debe ser posible derivarlas de él. Además del orden de ejecución de las subtareas, 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, esto es un recurso, por ejemplo, una máquina, que puede realizar la subtarea. Una matriz de asignación es una matriz bidimensional, donde una dimensión es la de las unidades de tiempo disponibles y la otra la de los recursos que se asignarán. 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, también 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 puede asignarse una vez por unidad de tiempo y que la reserva debe ser para un período de tiempo contiguo. [ 34 ] Para lograr esto de manera oportuna, que es un objetivo común de optimizació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 deben ejecutarse 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 ha completado cuando debería comenzar él mismo, 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 del fenotipo, también se denomina reparación fenotípica .

Ejemplo de mapeo genotipo-fenotipo basado en heurísticas

La siguiente tarea de planificación de diseño [ 36 ] tiene como objetivo ilustrar un uso diferente de una heurística en el mapeo genotipo-fenotipo: En una superficie rectangular, se deben disponer diferentes tipos geométricos de objetos de manera que quede la menor área posible sin usar. Los objetos pueden rotarse, no deben superponerse después de su colocación y deben estar completamente posicionados sobre la superficie. Una aplicación relacionada sería la minimización de desperdicios 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 variables a determinar. Si esto se realiza directamente mediante un algoritmo evolutivo (AE), probablemente habrá muchas superposiciones. Para evitarlo, el AE solo determina el ángulo y la coordenada de un lado del rectángulo. Cada objeto se rota y se posiciona en el borde de ese lado, desplazándolo si es necesario para que quede dentro del rectángulo cuando se mueva posteriormente. Luego se mueve paralelamente al otro lado hasta que toca otro objeto o alcanza el extremo opuesto del rectángulo. De esta forma, se evitan las superposiciones y se reduce el área no utilizada por colocación, pero no en general, lo cual se deja a la optimización. [ 37 ]

Referencias

  1. ↑ Eiben, AE; Smith, JE (2015). Introducción a la computación evolutiva . Serie de computación natural. Berlín, Heidelberg: Springer. pág.  40. doi : 10.1007/978-3-662-44874-8 . ISBN 978-3-662-44873-1. S2CID 20912932 . 
  2. ↑ Rothlauf 2002 , pág. 31.
  3. ↑ Eiben, AE; Smith, JE (2015). «Representación y funciones de los operadores de variación». Introducción a la computación evolutiva . Serie de computación natural. Berlín, Heidelberg: Springer. pp. 49–51 . doi : 10.1007/978-3-662-44874-8 . ISBN  978-3-662-44873-1. S2CID 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. pp. 99–118 . doi : 10.1007/978-3-662-44874-8 . ISBN  978-3-662-44873-1. S2CID 20912932 . 
  5. ↑ Fogel, DB (1995). «Fenotipos, genotipos y operadores en computación evolutiva». Actas de la Conferencia Internacional IEEE de Computación Evolutiva de 1995. Vol. 1. Perth, WA, Australia: IEEE. págs. 193–198 . doi : 10.1109/ICEC.1995.489143 . ISBN   978-0-7803-2759-7. S2CID 17755853 . 
  6. ↑ Tomáš Kuthan y Jan Lánský. "Algoritmos genéticos en la compresión de texto basada 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. S2CID 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-5OCLC 17674450​​ 
  9. ↑ Michalewicz, Zbigniew (1996). Algoritmos genéticos + Estructuras de datos = Programas evolutivos . 3.ª edición, revisada y ampliada. Berlín, Heidelberg: Springer. ISBN 978-3-662-03315-9OCLC 851375253​​ 
  10. 1 2 Whitley, Darrell (1994). "Un tutorial de algoritmos genéticos" . Statistics and Computing . 4 (2). doi : 10.1007/BF00175354 . ISSN 0960-3174 . S2CID 3447126 .  
  11. ↑ Herrera, F.; Lozano, M.; Verdegay, JL (1998). "Abordando los algoritmos genéticos de codificación real: operadores y herramientas para el análisis del comportamiento" . Artificial Intelligence Review . 12 (4): 265– 319. doi : 10.1023/A:1006504901164 . S2CID 6798965 . 
  12. ↑ Blume, Christian; Jakob, Wilfried (2002), "GLEAM - Un algoritmo evolutivo para planificación y control basado en estrategia evolutiva" , Actas de la Conferencia de Computación Genética y Evolutiva (GECCO 2002) , vol. Artículos de última hora, págs. 31–38 , consultado el 1 de enero de 2023.  
  13. ↑ Hitomi, Nozomi; Selva, Daniel (2018), "Optimización de constelaciones mediante un algoritmo evolutivo con un cromosoma de longitud variable", 2018 IEEE Aerospace Conference , IEEE, pp. 1–12 , doi : 10.1109/AERO.2018.8396743 , ISBN  978-1-5386-2014-4, S2CID 49541423 
  14. ↑ De Jong, Kenneth A. (2006). «Representación». Computación evolutiva : un enfoque unificado . Nueva Delhi: Prentice-Hall of India. pp. 72–75 . ISBN   978-81-203-3002-3OCLC 276452339​​ 
  15. ↑ Pawar, Sunil Nilkanth; Bichkar, Rajankumar Sadashivrao (2015). "Algoritmo genético con cromosomas de longitud variable para la detección de intrusiones en redes" . International Journal of Automation and Computing . 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 óptima . Nueva York: Wiley & Sons. ISBN 0-471-57148-2OCLC 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 Internacional Conjunta sobre Inteligencia Artificial IJCAI-89 , vol. 1, San Mateo, CA, EE. UU.: Morgan Kaufmann, pp . 768–774  
  18. ↑ Rothlauf 2002 .
  19. ↑ Whigham, Peter A.; Dick, Grant; Maclaurin, James (2017). "Sobre el mapeo de genotipo a fenotipo en algoritmos evolutivos" . Genetic Programming and Evolvable Machines . 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 binaria para algoritmos genéticos", Actas de Machine Learning 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" . Journal of Experimental & Theoretical Artificial Intelligence . 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 Computación Evolutiva de 1995 , 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-8OCLC 913232837​​ 
  24. ↑ Rothlauf, Franz (2006). «Tres elementos de una teoría de las representaciones». Representaciones para algoritmos genéticos y evolutivos (2.ª ed.). Heidelberg: Springer. pp. 33–96 . ISBN   978-3-540-32444-7OCLC 262692044​​ 
  25. ↑ Galván-López, Edgar; Dignum, Stephen; Poli, Riccardo (2008), "The Effects of Constant Neutrality on Performance and Problem Hardness in GP", en O'Neill, Michael; Vanneschi, Leonardo; Gustafson, Steven; Esparcia Alcázar, Anna Isabel (eds.), Genetic Programming , 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/01/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), "Sobre la utilidad de las codificaciones redundantes en la búsqueda evolutiva basada en mutaciones", en Guervós, Juan Julián Merelo; Adamidis, Panagiotis; Beyer, Hans-Georg; Schwefel, Hans-Paul (eds.), Resolución de problemas paralelos de la naturaleza — 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 genotipo-fenotipo". Introducción a la computación evolutiva . Serie de computación natural. Berlín, Heidelberg: Springer. pp. 177–178 . doi : 10.1007/978-3-662-44874-8 . ISBN  978-3-662-44873-1. S2CID 20912932 . 
  29. ↑ Hart, Emma; Ross, Peter; Nelson, Jeremy (1998). "Resolución de un problema del mundo real mediante un constructor de cronogramas heurístico evolutivo" . 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. S2CID 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" . Artificial Intelligence Review . 13 (2): 129– 170. doi : 10.1023/A:1006529012972 . S2CID 10284682 . 
  32. ↑ Bruns, Ralf (1997-01-01). «Enfoques de computación evolutiva 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. 1 2 Jakob, Wilfried; Strack, Sylvia; Quinte, Alexander; Bengel, Günther; Stucky, Karl-Uwe; Süß, Wolfgang (2013-04-22). "Reprogramación rápida de múltiples flujos de trabajo a recursos heterogéneos restringidos mediante computación memética multicriterio" . 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), "Programación de flujos de trabajo con restricciones presupuestarias", en Gorlatch, Sergei; Danelutto, Marco (eds.), 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 (1993-09-19). "Enfoque híbrido para el anidamiento óptimo mediante un algoritmo genético y un algoritmo de minimización local" . Actas de las Conferencias Técnicas de Diseño de la 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 el ensamblaje y la fabricación; Algoritmos genéticos en el diseño y la 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), "Layout Planning as an Example for Smart Handling of Complex Constraints" , Applying Evolutionary Algorithms Successfully - A Guide Gained from Real-world Applications , KIT Scientific Working Papers, vol. 170, Karlsruhe: KIT Scientific Publishing, pp. 12–14 , arXiv : 2107.11300 , doi : 10.5445/IR/1000135763 , S2CID 236318422  
  • Rothlauf, Franz (2002). Representaciones para algoritmos genéticos y evolutivos . Estudios en lógica difusa y computación blanda. Vol.  104. Heidelberg: Physica-Verlag HD. doi : 10.1007/978-3-642-88094-0 . ISBN 978-3-642-88096-4.