Cromosoma (algoritmo evolutivo)

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

Tenga en cuenta que el número negativo aquí se da en complemento a dos . Esta representación directa utiliza cinco bits para representar los tres valores de${\displaystyle D_{2}}$, aunque dos bits serían suficientes. Esto supone una redundancia significativa. Una alternativa mejorada, en la que se añadiría 28 para el mapeo genotipo-fenotipo, podría tener este aspecto:

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

Para el procesamiento de tareas con variables de decisión de valor real o entero mixto, son adecuados los EA como la estrategia evolutiva ^{[ 15 ]} o los GA de codificación real ^{[ 16 ] [ 17 ] [ 18 ]} . En el caso de valores enteros mixtos, a menudo se utiliza el redondeo, pero esto representa una 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 GA de codificación entera. ^{[ 19 ] [ 20 ]} Para este propósito, los dígitos válidos de los valores reales se asignan a enteros mediante la multiplicación por un factor adecuado. Por ejemplo, 12.380 se convierte en el entero 12380 al multiplicarlo por 1000. Esto, por supuesto, 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.

Los problemas combinatorios se ocupan principalmente de encontrar una secuencia óptima de un conjunto de elementos elementales. Como ejemplo, consideremos el problema del viajante que quiere visitar un número determinado de ciudades exactamente una vez en el recorrido más corto posible. La asignación más simple y obvia a un cromosoma consiste en 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, los operadores de variación solo pueden cambiar el orden de los genes y no eliminar ni duplicar ninguno. ^{[ 22 ]} El cromosoma contiene así la ruta de un posible recorrido por las ciudades. Como ejemplo, la secuencia${\displaystyle 3,5,7,1,4,2,9,6,8}$De nueve ciudades pueden servir, a las que corresponde el siguiente cromosoma:

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 ]}

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 a su vez está sujeta a evolución, se habla de coevolución . Un ejemplo típico es la estrategia evolutiva (EE), 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 la planificación de tareas. ^{[ 24 ]}

Este enfoque se basa en la premisa de que las buenas soluciones se fundamentan en una selección adecuada de parámetros estratégicos o en genes de control que influyen en el mapeo genotipo-fenotipo. El éxito del ES respalda esta premisa.

Los cromosomas presentados anteriormente son adecuados para tareas de procesamiento de optimización continua, mixta, entera pura o combinatoria. Sin embargo, para una combinación de estas áreas de optimización, resulta cada vez más difícil mapearlas a simples cadenas de valores, según la tarea. Para este propósito, el algoritmo evolutivo de aprendizaje general GLEAM (EA GLEAM) propone la siguiente extensión del concepto de gen: ^{[ 25 ]} Un gen se considera la descripción de un elemento o rasgo elemental del fenotipo, que puede tener múltiples parámetros. Para ello, se definen tipos de genes que contienen tantos parámetros del tipo de datos apropiado como se requieran para describir el elemento particular del fenotipo. Un cromosoma ahora consta de genes como objetos de datos de los tipos de genes, donde, según la aplicación, cada tipo de gen aparece exactamente una vez como un gen o puede estar contenido en el cromosoma cualquier número de veces. Esto último da lugar a cromosomas de longitud dinámica, como se requiere para algunos problemas. ^{[ 26 ] [ 27 ]} Las definiciones de tipo de gen también contienen información sobre los rangos de valores permisibles de los parámetros del gen, que se observan durante la generación del cromosoma y por las mutaciones correspondientes, por lo que no pueden dar lugar a mutaciones letales. Para tareas con una parte combinatoria, existen operadores genéticos adecuados que pueden mover o reposicionar genes en su conjunto, es decir, con sus parámetros.

Se utiliza como ejemplo una tarea de planificación , en la que se deben planificar 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 deben ejecutarse uno tras otro. En este contexto, los recursos heterogéneos significan diferentes tiempos de procesamiento a diferentes costos, además de diferentes capacidades de procesamiento. ^{[ 24 ]} Por lo tanto, cada operación de planificació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 planificación y, por lo 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 cuales 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 paso de trabajo correspondiente, 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 representados en una lista.

Las representaciones arbóreas en un cromosoma se utilizan en la programación genética , un tipo de algoritmo evolutivo 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 adjunta muestra el árbol sintáctico de una expresión matemática a modo de ejemplo. Los operadores de mutación pueden reorganizar, cambiar o eliminar subárboles según la estructura sintáctica representada. La recombinación se realiza intercambiando subárboles adecuados. ^{[ 28 ]}