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]
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.
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]
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]
Todas las posibles soluciones admisibles deben estar contenidas en el espacio de búsqueda.
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 .
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.
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.
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.
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.
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.
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 .
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]