Cromosoma (algoritmo genético)

En algoritmos genéticos (AG), o más generalmente, algoritmos evolutivos (AE), un cromosoma (también llamado a veces genotipo ) es un conjunto de parámetros que definen una solución propuesta del problema que el algoritmo evolutivo está tratando de resolver. El conjunto de todas las soluciones, también llamadas individuos según el modelo biológico, se conoce como población . ^[1]^[2] El genoma de un individuo consiste en uno, más raramente en varios, ^[3]^[4] cromosomas y corresponde a la representación genética de la tarea a resolver. Un cromosoma está compuesto por un conjunto de genes, donde un gen consiste en uno o más parámetros semánticamente conectados , que a menudo también se denominan variables de decisión . Determinan una o más características fenotípicas del individuo o al menos tienen una influencia sobre ellas. ^{[2] En la forma básica de algoritmos genéticos, el cromosoma se representa como una}cadena binaria , ^[5] mientras que en variantes posteriores ^[6]^[7] y en los AE en general, se utiliza una amplia variedad de otras estructuras de datos . ^[8]^[9]^[10]

Diseño de cromosomas

Al crear la representación genética de una tarea, se determina qué variables de decisión y otros grados de libertad de la tarea deben mejorarse mediante el EA y posibles heurísticas adicionales y cómo debe ser el mapeo genotipo-fenotipo . El diseño de un cromosoma traduce estas consideraciones en estructuras de datos concretas para las cuales luego se debe seleccionar, configurar, extender o, en el peor de los casos, crear un EA. Encontrar una representación adecuada del dominio del problema para un cromosoma es una consideración importante, ya que una buena representación facilitará la búsqueda al limitar el espacio de búsqueda ; de manera similar, una representación más pobre permitirá un espacio de búsqueda más grande. ^[11] En este contexto, también se deben encontrar o definir nuevos operadores de mutación y cruce adecuados ^[2] para que se ajusten al diseño cromosómico elegido. Un requisito importante para estos operadores es que no solo permitan alcanzar todos los puntos en el espacio de búsqueda en principio, sino que también lo hagan lo más fácil posible. ^[12]^[13]

Para que un cromosoma sea adecuado se deben cumplir los siguientes requisitos:

Debe permitir la accesibilidad a todos los puntos admisibles en el espacio de búsqueda.
Diseño del cromosoma de tal manera que cubra sólo el espacio de búsqueda y ninguna área adicional, de modo que no haya redundancia o sólo la menor redundancia posible.

Observancia de causalidad fuerte : pequeños cambios en el cromosoma sólo deberían conducir a pequeños cambios en el fenotipo. ^[14] Esto también se denomina localidad de la relación entre el espacio de búsqueda y el espacio del problema.
Diseñar el cromosoma de tal manera que excluya regiones prohibidas en el espacio de búsqueda por completo o tanto como sea posible.

Si bien el primer requisito es indispensable, en función de la aplicación y del EA utilizado, normalmente sólo hay que conformarse con cumplir los demás requisitos en la medida de lo posible. La búsqueda evolutiva se ve apoyada y posiblemente acelerada considerablemente por un cumplimiento lo más completo posible.

Ejemplos de cromosomas

Cromosomas para codificaciones binarias

En su forma clásica, los AG utilizan cadenas de bits y asignan a ellas las variables de decisión que se optimizarán. Un ejemplo de una variable de decisión booleana y tres variables de decisión enteras con rangos de valores puede ilustrar esto: $0\leq D_{1}\leq 60$ $28\leq D_{2}\leq 30$ $-12\leq D_{3}\leq 14$

Tenga en cuenta que el número negativo aquí se da en complemento a dos . Esta representación sencilla utiliza cinco bits para representar los tres valores de , aunque dos bits serían suficientes. Esto es una redundancia significativa. Una alternativa mejorada, donde se debe agregar 28 para la asignación genotipo-fenotipo, podría verse así: $D_{2}$

con . $D_{2}=28+D'_{2}=29$

Cromosomas con genes de valor real o entero

Para el procesamiento de tareas con variables de decisión de valores reales o enteros mixtos, son adecuados los EA como la estrategia de evolución ^[15] o los AG de codificación real ^[16]^[17]^[18] . En el caso de valores enteros mixtos, a menudo se utiliza el redondeo, pero esto representa cierta violación del requisito de redundancia . Si las precisiones necesarias de los valores reales se pueden reducir razonablemente, esta violación se puede remediar utilizando AG de codificación entera. ^[19]^[20] Para este propósito, los dígitos válidos de los valores reales se asignan a números enteros mediante la multiplicación con un factor adecuado. Por ejemplo, 12.380 se convierte en el número entero 12380 al multiplicarlo por 1000. Por supuesto, esto debe tenerse en cuenta en el mapeo genotipo-fenotipo para la evaluación y la presentación de resultados. Una forma común es un cromosoma que consiste en una lista o una matriz de valores enteros o reales.

Cromosomas para permutaciones

Los problemas combinatorios se ocupan principalmente de encontrar una secuencia óptima de un conjunto de elementos elementales. Como ejemplo, considere el problema del viajante de comercio que quiere visitar un número determinado de ciudades exactamente una vez en el viaje más corto posible. La asignación más simple y obvia a un cromosoma es numerar las ciudades consecutivamente, interpretar la secuencia resultante como una permutación y almacenarla directamente en un cromosoma, donde un gen corresponde al número ordinal de una ciudad. ^[21] Sin embargo, entonces los operadores de variación solo pueden cambiar el orden de los genes y no eliminar ni duplicar ningún gen. ^[22] El cromosoma contiene así el camino de un posible viaje a las ciudades. Como ejemplo puede servir la secuencia de nueve ciudades, a la que corresponde el siguiente cromosoma: $3,5,7,1,4,2,9,6,8$

Además de esta codificación, frecuentemente llamada representación de ruta , existen otras formas de representar una permutación, por ejemplo la representación ordinal o la representación matricial . ^[22]^[23]

Cromosomas para la coevolución

Cuando una representación genética contiene, además de las variables de decisión, información adicional que influye en la evolución y/o en la asignación del genotipo al fenotipo y que está sujeta a la evolución, se habla de coevolución . Un ejemplo típico es la estrategia de evolución (ES), que incluye uno o más tamaños de paso de mutación como parámetros de estrategia en cada cromosoma. ^[15] Otro ejemplo es un gen adicional para controlar una heurística de selección para la asignación de recursos en una tarea de programación. ^[24]

Este enfoque se basa en el supuesto de que las buenas soluciones se basan en una selección adecuada de parámetros de estrategia o en genes de control que influyen en el mapeo genotipo-fenotipo. El éxito del ES da evidencia de esta suposición.

Cromosomas para representaciones complejas

Los cromosomas presentados anteriormente son muy adecuados para tareas de procesamiento de optimización continua, de enteros mixtos, de enteros puros o combinatoria. Por otra parte, para una combinación de estas áreas de optimización, se hace cada vez más difícil mapearlas a cadenas simples de valores, dependiendo de la tarea. La siguiente extensión del concepto de gen es propuesta por EA GLEAM (General Learning Evolutionary Algorithm and Method) para este propósito: ^[25] Un gen se considera como la descripción de un elemento o rasgo elemental del fenotipo, que puede tener múltiples parámetros. Para este propósito, se definen tipos de genes que contienen tantos parámetros del tipo de datos apropiado como sean necesarios para describir el elemento particular del fenotipo. Un cromosoma ahora consta de genes como objetos de datos de los tipos de genes, por lo que, dependiendo de la aplicación, cada tipo de gen ocurre exactamente una vez como gen o puede estar contenido en el cromosoma cualquier número de veces. Esto último conduce a cromosomas de longitud dinámica, ya que son necesarios para algunos problemas. ^[26]^[27] Las definiciones de los tipos de genes también contienen información sobre los rangos de valores permisibles de los parámetros genéticos, que se observan durante la generación de cromosomas y mediante las mutaciones correspondientes, de modo que no puedan conducir a mutaciones letales. Para las tareas con una parte combinatoria, existen operadores genéticos adecuados que pueden mover o reposicionar los genes en su conjunto, es decir, con sus parámetros.

Se utiliza como ejemplo una tarea de programación en la que se deben programar flujos de trabajo que requieren diferentes cantidades de recursos heterogéneos. Un flujo de trabajo especifica qué pasos de trabajo se pueden procesar en paralelo y cuáles se deben ejecutar uno tras otro. En este contexto, los recursos heterogéneos significan diferentes tiempos de procesamiento con diferentes costes, además de diferentes capacidades de procesamiento. ^[24] Por tanto, cada operación de programación requiere uno o más parámetros que determinan la selección de recursos, donde los rangos de valores de los parámetros dependen de la cantidad de recursos alternativos disponibles para cada paso de trabajo. Un cromosoma adecuado proporciona un tipo de gen por paso de trabajo y, en este caso, un gen correspondiente, que tiene un parámetro para cada recurso requerido. El orden de los genes determina el orden de las operaciones de programación y, por tanto, la precedencia en caso de conflictos de asignación. La definición de tipo de gen ejemplar del paso de trabajo 15 con dos recursos, para los que hay cuatro y siete alternativas respectivamente, se vería entonces como se muestra en la imagen de la izquierda. Dado que los parámetros representan índices en listas de recursos disponibles para el respectivo paso de trabajo, su rango de valores comienza en 0. La imagen de la derecha muestra un ejemplo de tres genes de un cromosoma pertenecientes a los tipos de genes en representación de lista.

Cromosomas para representaciones de árboles

Las representaciones de árboles en un cromosoma son utilizadas por la programación genética , un tipo de EA para generar programas o circuitos informáticos . ^[10] Los árboles corresponden a los árboles sintácticos generados por un compilador como representación interna al traducir un programa informático. La figura adyacente muestra el árbol sintáctico de una expresión matemática como ejemplo. Los operadores de mutación pueden reorganizar, cambiar o eliminar subárboles dependiendo de la estructura sintáctica representada. La recombinación se realiza intercambiando subárboles adecuados. ^[28]

Bibliografía

Thomas Bäck (1996): Algoritmos evolutivos en teoría y práctica: estrategias evolutivas, programación evolutiva, algoritmos genéticos , Oxford Univ. Press. ISBN 978-0-19-509971-3
Wolfgang Banzhaf, P. Nordin, R. Keller, F. Francone (1998): Programación genética: introducción , Morgan Kaufmann, San Francisco. ISBN 1-55860-510-X
Kenneth A. de Jong (2006): Computación evolutiva: un enfoque unificado. MIT Press, Cambridge, MA. ISBN 0-262-04194-4
Melanie Mitchell (1996): Introducción a los algoritmos genéticos. MIT Press, Cambridge, MA. ISBN 978-0-262-63185-3
Hans-Paul Schwefel (1995): Evolución y búsqueda del óptimo . Wiley & Sons, Nueva York. ISBN 0-471-57148-2

Referencias

^ "Introducción a los algoritmos genéticos: IV. Algoritmo genético" . Consultado el 12 de agosto de 2015 .
^ abc Eiben, AE; Smith, JE (2015). "Componentes de algoritmos evolutivos". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 28-34. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto 20912932.
^ Baine, Nicholas (2008), "Una optimización de algoritmo genético multicromosómico simple de un controlador de lógica difusa proporcional más derivativa", NAFIPS 2008 - Reunión anual de 2008 de la Sociedad Norteamericana de Procesamiento de Información Difusa , IEEE, págs. 1–5, doi :10.1109/NAFIPS.2008.4531273, ISBN 978-1-4244-2351-4, Número de identificación del sujeto 46591432
^ Peng, Jin; Chu, Zhang Shu (2010), "Un algoritmo genético multicromosómico híbrido para el problema del stock de corte", 3.ª Conferencia internacional sobre gestión de la información, gestión de la innovación e ingeniería industrial , IEEE, págs. 508-511, doi :10.1109/ICIII.2010.128, ISBN 978-1-4244-8829-2, S2CID15608610
^ Holland, John H. (1992). Adaptación en sistemas naturales y artificiales . Cambridge, Mass.: MIT Press. ISBN 0-585-03844-9.OCLC 42854623 .
^ Janikow, CZ; Michalewicz, Z. (1991), Belew, Richard K.; Booker, Lashon B. (eds.), "Una comparación experimental de representaciones binarias y de punto flotante en algoritmos genéticos" (PDF) , Actas de la Cuarta Conferencia Internacional sobre Algoritmos Genéticos , San Francisco, CA: Morgan Kaufmann Publishers, págs. 31–36, ISBN 1-55860-208-9
^ Whitley, Darrell (junio de 1994). "Un tutorial sobre algoritmos genéticos". Estadística y computación . 4 (2). CiteSeerX 10.1.1.184.3999 . doi :10.1007/BF00175354. S2CID 3447126.
^ Whitley, Darrell (2001). "Una visión general de los algoritmos evolutivos: cuestiones prácticas y errores comunes". Tecnología de la información y el software . 43 (14): 817–831. doi :10.1016/S0950-5849(01)00188-4. S2CID 18637958.
^ Bäck, Thomas; Hoffmeister, Frank; Schwefel, Hans-Paul (1991), Belew, Richard K.; Booker, Lashon B. (eds.), "Un estudio de las estrategias evolutivas", Actas de la Cuarta Conferencia Internacional sobre Algoritmos Genéticos , San Francisco, CA: Morgan Kaufmann Publishers, págs. 2–9, ISBN 1-55860-208-9
^ ab Koza, John R. (1992). Programación genética: sobre la programación de computadoras por medio de la selección natural. Cambridge, Mass.: MIT Press. ISBN 0-262-11170-5.OCLC 26263956 .
^ "Algoritmos genéticos". Archivado desde el original el 22 de octubre de 2019. Consultado el 12 de agosto de 2015 .
^ 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.
^ 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.
^ Galván-López, Edgar; McDermott, James; O'Neill, Michael; Brabazon, Anthony (7 de julio de 2010). "Hacia una comprensión de la localidad en la programación genética". Actas de la 12.ª conferencia anual sobre computación genética y evolutiva (PDF) . Portland, Oregón, EE. UU.: ACM. pp. 901–908. doi :10.1145/1830483.1830646. ISBN 978-1-4503-0072-8.S2CID15348983 .
^ ab Schwefel, Hans-Paul (1995). Evolución y búsqueda óptima. Nueva York: John Wiley & Sons. ISBN 0-471-57148-2.OCLC 30701094 .
^ Eshelman, Larry J.; Schaffer, J. David (1993), "Algoritmos genéticos codificados de forma real y esquemas de intervalo", Fundamentos de algoritmos genéticos , vol. 2, Elsevier, págs. 187-202, doi :10.1016/b978-0-08-094832-4.50018-0, ISBN 978-0-08-094832-4, consultado el 26 de enero de 2023
^ 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 .
^ Deep, Kusum; Singh, Krishna Pratap; Kansal, ML; Mohan, C. (junio de 2009). "Un algoritmo genético codificado real para resolver problemas de optimización de números enteros y enteros mixtos". Matemáticas Aplicadas y Computación . 212 (2): 505–518. doi :10.1016/j.amc.2009.02.044.
^ Wang, Fuchang; Cao, Huirong; Qian, Xiaoshi (2011), Liu, Baoxiang; Chai, Chunlai (eds.), "Algoritmo genético codificado en decimales y enteros para el estimador recortado del modelo de múltiples errores lineales en variables", Information Computing and Applications , LNCS 7030, Berlín, Heidelberg: Springer, págs. 359–366, doi :10.1007/978-3-642-25255-6_46, ISBN 978-3-642-25254-9, consultado el 23 de enero de 2023
^ Cheng, Xueli; An, Linchao; Zhang, Zhenhua (2019). "Algoritmo genético de codificación de enteros para optimizar la asignación de redundancia de sistemas serie-paralelo". Revista de revisión de ciencia y tecnología de ingeniería . 12 (1): 126–136. doi : 10.25103/JESTR.121.15 . S2CID 149497992.
^ 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.
^ ab 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.
^ Whitley, Darrell (2000). "Permutaciones". En Fogel, David B.; Bäck, Thomas; Michalewicz, Zbigniew (eds.). Computación evolutiva. Vol. 1, Algoritmos y operadores básicos . Bristol: Institute of Physics Pub. págs. 139–150. ISBN 0-585-30560-9.OCLC 45730387 .
^ 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". p.253-255. Algorithms . 6 (2): 245–277. doi : 10.3390/a6020245 . ISSN 1999-4893.
^ 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
^ Pawar, Sunil Nilkanth; Bichkar, Rajankumar Sadashivrao (junio de 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.
^ Blume, Christian (2000), Cagnoni, Stefano (ed.), "Generación optimizada de instrucciones de movimiento de robots sin colisiones mediante el software evolutivo GLEAM", Aplicaciones en el mundo real de la computación evolutiva , Lecture Notes in Computer Science, vol. 1803, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 330–341, doi :10.1007/3-540-45561-2_32, ISBN 978-3-540-67353-8, consultado el 25 de junio de 2023
^ Eiben, AE; Smith, JE (2015). "Representación de árboles". Introducción a la computación evolutiva. Serie de computación natural. Berlín, Heidelberg: Springer. págs. 75–78. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. Número de identificación del sujeto 20912932.