Representación de soluciones.Los algoritmos genéticos

Representación de soluciones

Los algoritmos genéticos no trabajan directamente sobre las soluciones del problema en

cuestión, sino que lo hacen sobre una abstracción de los objetos solución, usualmente

denominadas cromosomas por analogía con la evolución natural biológica. Un cromosoma es

un vector de genes, mientras que el valor asignado a un gen se denomina alelo.

En la terminología biológica, genotipo denota al conjunto de cromosomas que definen

las características de un individuo. El genotipo sometido al medio ambiente se denomina

fenotipo. En términos de los algoritmos genéticos el genotipo también esta constituido por

cromosomas, utilizándose generalmente un único cromosoma por individuo solución al

problema. Por ello suelen utilizarse indistintamente los términos genotipo, cromosoma e

individuo. Por su parte, el fenotipo representa un punto del espacio de soluciones del

problema.

Dado que un algoritmo genético trabaja sobre cromosomas, se debe definir una función

de codificación sobre los puntos del espacio de soluciones, que mapea todo punto del espacio

de soluciones en un genotipo, tal como se indica en la Figura 2.3. La función inversa de la

codificación, denominada decodificación permite obtener el fenotipo asociado a un

cromosoma.

Codificación : Espacio de soluciones ® cromosoma

Figura 2.3: Especificación de la función de codificación de un algoritmo genético.

Tomando en cuenta la observación anterior, los mecanismos de codificación de

individuos solución resultan importantes para el proceso de búsqueda de los algoritmos

genéticos. Habitualmente los algoritmos genéticos utilizan codificaciones binarias de largo

fijo. Los individuos se codifican por un conjunto de cardinalidad conocida de valores binarios

(ceros y unos) conocido como string de bits o bitstring. Cada bitstring representa a una

solución potencial del problema de acuerdo al mecanismo de codificación predefinido, en

general dependiente del problema.

Otros esquemas de codificación han sido utilizados con menor frecuencia en los

algoritmos genéticos. En particular las codificaciones basadas en números reales son útiles

para representar soluciones cuando se resuelven problemas sobre espacios de cardinalidad no

numerable, como en el caso de determinación de parámetros en problemas de control o

entrenamiento de redes neuronales. Los esquemas basados en permutaciones de enteros son

útiles para problemas de optimización combinatoria que involucran hallar ordenamientos

óptimos, como los problemas de scheduling o el reconocido Traveling Salesman Problem.

Codificaciones dependientes de los problemas se han propuesto con frecuencia, como un

...