En los algoritmos genéticos (GA), o más generalmente, en los algoritmos evolutivos (EA), un cromosoma (también llamado genotipo) es un conjunto de parámetros que definen una solución propuesta para el 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 la población. El genoma de un individuo consta de uno, o más raramente, varios cromosomas y corresponde a la representación genética de la tarea que se va 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 llaman variables de decisión. Determinan una o más características fenotípicas del individuo o al menos tienen influencia sobre ellas. En su forma básica, los algoritmos genéticos representan el cromosoma como una cadena binaria, mientras que en variantes posteriores y en los EA en general, se utilizan una amplia variedad de otras estructuras de datos.
Cromosomas para codificaciones binarias
En su forma clásica, los GA utilizan cadenas de bits y mapean las variables de decisión a ser optimizadas en ellas. Un ejemplo de una variable de decisión booleana y tres variables de decisión enteras con rangos de valores 0 ≤ D1 ≤ 60, 28 ≤ D2 ≤ 30 y -12 ≤ D3 ≤ 14 puede ilustrar esto:
- Variable de decisión: D1 = 22, D2 = 29, D3 = -4, D4 = 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 el número negativo se presenta en complemento a dos. Esta representación directa utiliza cinco bits para representar los tres valores de D2, aunque dos bits serían suficientes. Esta es una redundancia significativa. Una alternativa mejorada, donde se debe agregar 28 para el mapeo genotipo-fenotipo, podría verse así:
- Variable de decisión: D1 = 22, D2' = 1, D3 = -4, D4 = 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
con D2 = 28 + D2' = 2
Cromosomas con genes de valores reales o enteros
Para el procesamiento de tareas con variables de decisión reales o mixtas enteras, se utilizan EA como la estrategia de evolución o los GA codificados en números reales. En el caso de valores mixtos enteros, a menudo se utiliza el redondeo, pero esto representa una violación de los requisitos de redundancia. Si las precisiones necesarias de los valores reales se pueden acotar razonablemente, esta violación se puede remediar utilizando GA codificados en enteros. Para ello, los dígitos válidos de los valores reales se mapean a enteros mediante multiplicación por un factor adecuado. Por ejemplo, 1380 se convierte en el entero 12380 al multiplicarlo por 1000. Esto debe tenerse en cuenta en el mapeo genotipo-fenotipo para la evaluación y presentación de resultados. Una forma común es un cromosoma que consta de una lista o un array 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, consideremos el problema del viajante de comercio que desea visitar un número dado de ciudades exactamente una vez en el recorrido más corto posible. El mapeo más simple y obvio en un cromosoma es numerar las ciudades consecutivamente, interpretar una secuencia resultante como una permutación y almacenarla directamente en un cromosoma, donde un gen corresponde al número ordinal de una ciudad. El cromosoma contiene el camino de un posible recorrido por las ciudades. Como ejemplo, la secuencia 3, 5, 7, 1, 4, 2, 9, 6, 8 de nueve ciudades puede servir, a la que corresponde el siguiente cromosoma:
- 3 5 7 1 4 2 9 6 8
Además de esta representación de ruta frecuentemente llamada representación de ruta, existen varias otras formas de representar una permutación, como la representación ordinal o la representación matricial.
Cromosomas para co-evolució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 el mapeo del genotipo al fenotipo y está sujeta a la evolución, esto se denomina co-evolució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. Otro ejemplo es un gen adicional para controlar una heurística de selección para la asignación de recursos en tareas de programación.
Este enfoque se basa en la suposición de que las buenas soluciones se basan en una selección adecuada de los parámetros de estrategia o en un gen de control que influye en el mapeo genotipo-fenotipo. El éxito de la estrategia de evolución respalda esta suposición.
Cromosomas para representaciones complejas
Los cromosomas presentados anteriormente son adecuados para el procesamiento de tareas de optimización continua, mixta, puramente entera o combinatoria. Para una combinación de estas áreas de optimización, por otro lado, se vuelve cada vez más difícil mapearlas a cadenas simples de valores, dependiendo de la tarea. El EA GLEAM (General Learning Evolutionary Algorithm and Method) propone la siguiente extensión del concepto de gen para este propósito: 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 consiste en genes como objetos de datos de los tipos de genes, donde, 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 lleva a cromosomas de longitud dinámica, según sea necesario para algunos problemas. Las definiciones de los tipos de genes también contienen información sobre los rangos de valores permitidos de los parámetros del gen, que se observan durante la generación del cromosoma y por 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 como un todo, es decir, con sus parámetros.
Se utiliza una tarea de programación como ejemplo, en la que se deben programar flujos de trabajo que requieren diferentes números de recursos heterogéneos. Un flujo de trabajo especifica qué pasos de trabajo se pueden procesar en paralelo y cuáles deben ejecutarse uno después del otro. En este contexto, recursos heterogéneos significan diferentes tiempos de procesamiento y costos además de diferentes capacidades de procesamiento. 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 del número 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 lo tanto, la precedencia en caso de conflictos de asignación. La definición del tipo de gen ejemplar del paso de trabajo 15 con dos recursos, para los que hay cuatro y siete alternativas respectivamente, se vería así:
Con tres genes ejemplares correspondientes a las definiciones de tipos de genes adyacentes en un cromosoma organizado como una lista:
Sintaxis del árbol de una fórmula ejemplo:
Cromosomas para representaciones de árbol
Las representaciones de árbol en un cromosoma se utilizan en la programación genética, un tipo de EA para generar programas de computadora o circuitos. Los árboles corresponden a los árboles de sintaxis generados por un compilador como representación interna al traducir un programa de computadora. El árbol de sintaxis adjunto muestra el árbol de sintaxis de una expresión matemática como ejemplo. Los operadores de mutación pueden reorganizar, cambiar o eliminar subárboles según la estructura de sintaxis representada. La recombinación se realiza intercambiando subárboles adecuados.
Si quieres conocer otras notas parecidas a El cromosoma en ia: algoritmos genéticos y evolutivos puedes visitar la categoría Inteligencia.