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

A scheduling task is used as an illustration, in which workflows are to be scheduled that require different numbers of heterogeneous resources. A workflow specifies which work steps can be processed in parallel and which have to be executed one after the other. In this context, heterogeneous resources mean different processing times at different costs in addition to different processing capabilities.^[24] Each scheduling operation therefore requires one or more parameters that determine the resource selection, where the value ranges of the parameters depend on the number of alternative resources available for each work step. A suitable chromosome provides one gene type per work step and in this case one corresponding gene, which has one parameter for each required resource. The order of genes determines the order of scheduling operations and, therefore, the precedence in case of allocation conflicts. The exemplary gene type definition of work step 15 with two resources, for which there are four and seven alternatives respectively, would then look as shown in the left image. Since the parameters represent indices in lists of available resources for the respective work step, their value range starts at 0. The right image shows an example of three genes of a chromosome belonging to the gene types in list representation.

Tree representations in a chromosome are used by genetic programming, an EA type for generating computer programs or circuits.^[10] The trees correspond to the syntax trees generated by a compiler as internal representation when translating a computer program. The adjacent figure shows the syntax tree of a mathematical expression as an example. Mutation operators can rearrange, change or delete subtrees depending on the represented syntax structure. Recombination is performed by exchanging suitable subtrees.^[28]