Cromosoma (computación evolutiva)

Para más información sobre los cromosomas en biología, véase cromosoma.

En el ámbito de los algoritmos genéticos (AG) y, de manera más general, en los algoritmos evolutivos (AE), el término “cromosoma” (también conocido como “genotipo”) se refiere a un conjunto de parámetros que definen una propuesta de solución al problema que el algoritmo evolutivo intenta resolver. Este conjunto de soluciones, siguiendo el modelo biológico, se denomina “población”.​​

El genoma de un individuo está compuesto por uno o, en casos menos frecuentes, varios cromosomas.​​ Este genoma representa la codificación genética de la tarea a resolver. Un cromosoma está constituido por un conjunto de genes, donde cada gen consiste en uno o más parámetros semánticamente conectados, comúnmente denominados “variables de decisión”. Estos genes determinan o influyen en una o más características fenotípicas del individuo.​

En la forma básica de los algoritmos genéticos, los cromosomas se representan como cadenas binarias.​ Sin embargo, en variantes posteriores​​ y en los algoritmos evolutivos en general, se emplea una amplia variedad de otras estructuras de datos para representar los cromosomas.​​​

Diseño cromosómico

Al diseñar la representación genética de una tarea, es fundamental determinar qué variables de decisión y otros grados de libertad deben ser optimizados por el Algoritmo Evolutivo (AE) y posibles heurísticos adicionales. Además, es crucial definir cómo debe realizarse el mapeo entre el genotipo y el fenotipo. El diseño de un cromosoma traduce estas consideraciones en estructuras de datos concretas, para las cuales se debe seleccionar, configurar, ampliar o, en el peor de los casos, crear un AE específico.

Encontrar una representación adecuada del dominio del problema para un cromosoma es una consideración esencial, ya que una buena representación facilita la búsqueda al limitar el espacio de búsqueda. Por el contrario, una representación inadecuada puede ampliar innecesariamente el espacio de búsqueda.​ En este contexto, también es necesario definir o rediseñar operadores de mutación y recombinación que se ajusten al diseño del cromosoma elegido.​ Un requisito importante para estos operadores es que no solo permitan alcanzar, en principio, todos los puntos del espacio de búsqueda, sino que también faciliten esta tarea al máximo.​​

Un cromosoma bien adaptado debe cumplir los siguientes requisitos:

• Debe permitir la accesibilidad a todos los puntos admisibles en el espacio de búsqueda.
• El diseño del cromosoma debe cubrir únicamente el espacio de búsqueda relevante, evitando zonas adicionales innecesarias.
• Debe minimizar la redundancia en la medida de lo posible.
• Pequeños cambios en el cromosoma deben provocar solo pequeños cambios en el fenotipo​, lo que también se conoce como localidad de la relación entre el espacio de búsqueda y el espacio del problema.
• El diseño del cromosoma debe excluir por completo, o en la mayor medida posible, las regiones prohibidas en el espacio de búsqueda.

Aunque el primer requisito es indispensable, dependiendo de la aplicación y del AE utilizado, generalmente se debe aspirar a cumplir el resto de los requisitos en la mayor medida posible. Sin embargo, es importante tener en cuenta que la búsqueda evolutiva se ve apoyada y posiblemente acelerada considerablemente por un cumplimiento lo más completo posible de estos requisitos.

Ejemplos de cromosomas

Cromosomas para codificaciones binarias

En su forma clásica, los Algoritmos Genéticos (AG) utilizan cadenas de bits para representar las variables de decisión que se desean optimizar. A continuación, se presenta un ejemplo con una variable booleana y tres variables enteras con los siguientes rangos de valores $0\leq D_{1}\leq 60$,$28\leq D_{2}\leq 30$ y $-12\leq D_{3}\leq 14$ que puede ilustrar esto:

Ejemplo de representación de cuatro variables de decisión en una cadena de bits

variable de decisión:	$D_{1}=22$						$D_{2}=29$					$D_{3}=-4$					$D_{4}=0$
bits:	0	1	0	1	1	0	1	1	1	0	1	1	1	1	0	0	0
posición:	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1

Tenga en cuenta que aquí el número negativo se da en complemento a dos. Esta representación directa utiliza cinco bits para representar los tres valores de $D_{2}$, aunque bastaría con dos bits. Se trata de una redundancia importante. Una alternativa mejorada, en la que se añada 28 para la correspondencia genotipo-fenotipo, podría ser la siguiente:

Ejemplo de representación mejorada de las cuatro variables de decisión

variable de decisión:	$D_{1}=22$						$D'_{2}=1$		$D_{3}=-4$					$D_{4}=0$
bits:	0	1	0	1	1	0	0	1	1	1	1	0	0	0
posición:	14	13	12	11	10	9	8	7	6	5	4	3	2	1

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

Cromosomas con genes de valor real o entero

Para el procesamiento de tareas que involucran variables de decisión con valores reales o enteros mixtos, se recomienda el uso de Algoritmos Evolutivos (EA) como la estrategia evolutiva,​ o Algoritmos Genéticos (AG) de codificación real.​​​ En el caso de variables con valores enteros mixtos, a menudo se recurre al redondeo, aunque esto puede violar el requisito de no redundancia. Si las precisiones necesarias de los valores reales pueden reducirse de manera razonable, esta violación puede ser mitigada utilizando AG codificados por enteros.​​

Para lograr esto, los dígitos significativos de los valores reales se convierten en enteros mediante la multiplicación por un factor adecuado. Por ejemplo, el valor 12,380 se convierte en el número entero 12380 al multiplicarlo por 1000. Es importante tener en cuenta este factor en el mapeo genotipo-fenotipo para la evaluación y presentación de resultados. Una forma común de representar esto es mediante un cromosoma compuesto por una lista o matriz de valores enteros o reales.

Cromosomas para permutaciones

Los problemas combinatorios se centran principalmente en la identificación de una secuencia óptima dentro de un conjunto de elementos básicos. Un ejemplo clásico de este tipo de problema es el del viajante de comercio, quien debe visitar un número determinado de ciudades exactamente una vez, siguiendo la ruta más corta posible.

La forma más sencilla y directa de asignar esta tarea a un cromosoma consiste en numerar las ciudades de manera consecutiva, interpretar la secuencia resultante como una permutación y almacenarla directamente en un cromosoma. En este contexto, cada gen del cromosoma corresponde al número ordinal de una ciudad específica.​

Es importante destacar que los operadores de variación en este modelo solo pueden alterar el orden de los genes, sin eliminar ni duplicar ninguno de ellos.​ De esta manera, el cromosoma representa la ruta de un posible recorrido por las ciudades. Por ejemplo, consideremos la secuencia$3,5,7,1,4,2,9,6,8$ para un conjunto de nueve ciudades. Esta secuencia se traduce en el siguiente cromosoma:

3

5

7

1

4

2

9

6

8

Además de esta codificación, frecuentemente denominada representación del camino, existen otras formas de representar una permutación, como la representación ordinal o la representación matricial.​​

Cromosomas para la coevolución

La coevolución se refiere a un proceso en el cual una representación genética incluye, además de las variables de decisión, información adicional que influye tanto en la evolución como en el mapeo del genotipo al fenotipo. Esta información adicional también está sujeta a evolución. Un ejemplo clásico de este fenómeno es la Estrategia Evolutiva (ES), que incorpora uno o más tamaños de paso de mutación como parámetros estratégicos en cada cromosoma.​

Otro ejemplo de coevolución es la inclusión de un gen adicional que regula una heurística de selección para la asignación de recursos en una tarea de programación.​ Este enfoque se fundamenta en la premisa de que las soluciones óptimas dependen de una selección adecuada de los parámetros estratégicos o de genes de control que influyen en el mapeo genotipo-fenotipo. El éxito observado en la aplicación de las Estrategias Evolutivas (ES) respalda esta hipótesis.

Cromosomas para representaciones complejas

Los cromosomas descritos anteriormente son altamente adecuados para abordar tareas de optimización continua, mixta entera, entera pura o combinatoria. Sin embargo, cuando se trata de una combinación de estas áreas de optimización, se vuelve cada vez más complejo mapearlas a simples cadenas de valores, dependiendo de la tarea específica. Para abordar esta complejidad, el Algoritmo Evolutivo de Aprendizaje General (GLEAM, por sus siglas en inglés) propone una extensión del concepto de gen.​

En este contexto, un gen se define como la descripción de un elemento o rasgo elemental del fenotipo, el cual puede tener múltiples parámetros. Para ello, se establecen tipos de genes que contienen tantos parámetros del tipo de datos apropiado como sean necesarios para describir el elemento concreto del fenotipo. Un cromosoma, por lo tanto, se compone de genes que actúan como objetos de datos de los tipos de genes definidos. Dependiendo de la aplicación, cada tipo de gen puede aparecer exactamente una vez como gen o puede estar contenido en el cromosoma en múltiples ocasiones. Esta flexibilidad da lugar a cromosomas de longitud dinámica, necesarios para resolver ciertos problemas.​​

Las definiciones de los tipos de genes también incluyen información sobre los rangos de valores permitidos para los parámetros de los genes. Estos rangos se respetan tanto durante la generación del cromosoma como durante las mutaciones correspondientes, evitando así mutaciones letales. Para las tareas que incluyen una parte combinatoria, existen operadores genéticos adecuados que pueden mover o reposicionar los genes en su totalidad, es decir, junto con sus parámetros.

Tres genes ejemplares que coinciden con las definiciones de tipo de gen adyacente en un cromosoma organizado como una lista.

Tres genes ejemplares que coinciden con las definiciones de tipo de gen adyacente en un cromosoma organizado como una lista.

Como ejemplo, consideremos una tarea de programación en la que deben diseñarse flujos de trabajo que requieren distintos números de recursos heterogéneos. Un flujo de trabajo especifica qué pasos pueden procesarse en paralelo y cuáles deben ejecutarse secuencialmente. En este contexto, los recursos heterogéneos implican tiempos de procesamiento diferentes, costos variados y capacidades de procesamiento distintas.​ Por lo tanto, cada operación de programación requiere uno o más parámetros que determinen la selección de recursos, donde los rangos de valores de los parámetros dependen del número de recursos alternativos disponibles para cada paso de trabajo.

Un cromosoma adecuado proporciona un tipo de gen por cada 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. Por ejemplo, la definición del tipo de gen para el paso de trabajo 15, que requiere dos recursos con cuatro y siete alternativas respectivamente, se vería 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.

Árbol sintáctico de una fórmula de ejemplo

Cromosomas para representaciones en árbol

Las representaciones en forma de árbol de un cromosoma son empleadas en la programación genética, una rama de los algoritmos evolutivos (EA), para la generación de programas o circuitos informáticos. Estos árboles corresponden a los árboles sintácticos generados por un compilador, los cuales actúan como una representación interna durante el proceso de traducción de un programa informático.

En la figura adyacente se presenta, a modo de ejemplo, el árbol sintáctico de una expresión matemática. Los operadores de mutación tienen la capacidad de reordenar, modificar o eliminar subárboles, basándose en la estructura sintáctica representada. La recombinación, por su parte, se lleva a cabo mediante el intercambio de subárboles adecuados, permitiendo así la combinación de diferentes partes de los árboles para generar nuevas soluciones.

Bibliografía

• Thomas Bäck (1996): Algoritmos Evolutivos en Teoría y Práctica: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press. ISBN 978-0-19-509971-3.
• Wolfgang Banzhaf, P. Nordin, R. Keller, F. Francone (1998): Genetic Programming - An Introduction. Morgan Kaufmann, San Francisco. ISBN 1-55860-510-X.
• Kenneth A. de Jong (2006): Evolutionary Computation: A Unified Approach. MIT Press, Cambridge, MA. ISBN 0-262-04194-4.
• Melanie Mitchell (1996): An Introduction to Genetic Algorithms (Introducción a los algoritmos genéticos). MIT Press, Cambridge, MA. ISBN 978-0-262-63185-3.
• Hans-Paul Schwefel (1995): Evolution and Optimum Seeking. Wiley & Sons, Nueva York. ISBN 0-471-57148-2.

Referencias

• Datos: Q1502477