X. Codificacion
Introduccion
Elegir una codificacion para los cromosomas es una de las primeras cuestiones que se presentan al resolver un problema con un AG. La codificacion correcta depende mucho del problema.
Este capitulo presenta varias codificaciones que se han utilizado con exito en algoritmos geneticos.
Codificacion binaria
La codificacion binaria es el enfoque mas comun, principalmente porque los primeros trabajos sobre algoritmos geneticos utilizaban este tipo de codificacion.
En la codificacion binaria, cada cromosoma es una cadena de bits, 0 o 1.
| Cromosoma A | 101100101100101011100101 |
| Cromosoma B | 111111100000110000011111 |
Ejemplo de cromosomas con codificacion binaria
La codificacion binaria da muchos cromosomas posibles incluso con un numero pequeno de alelos. Por otro lado, esta codificacion a menudo no es natural para muchos problemas, y a veces deben hacerse correcciones despues del cruce y/o la mutacion.
Ejemplo de problema: Problema de la mochila
El problema: Hay elementos con valores y tamanos dados. La mochila tiene una capacidad fija. Seleccione elementos para maximizar el valor total en la mochila sin exceder su capacidad.
Codificacion: Cada bit indica si el elemento correspondiente esta en la mochila.
Codificacion de permutacion
La codificacion de permutacion puede utilizarse para problemas de ordenamiento, como el problema del viajante de comercio o el ordenamiento de tareas.
En la codificacion de permutacion, cada cromosoma es una cadena de numeros, que representa un numero dentro de una secuencia.
| Cromosoma A | 1 5 3 2 6 4 7 9 8 |
| Cromosoma B | 8 5 6 7 2 3 1 4 9 |
Ejemplo de cromosomas con codificacion de permutacion
La codificacion de permutacion solo es util para problemas de ordenamiento. Incluso en esos problemas, algunos tipos de cruce y mutacion requieren correcciones para mantener consistente el cromosoma (es decir, para conservar una secuencia valida).
Ejemplo de problema: Problema del viajante de comercio (TSP)
El problema: Hay ciudades y distancias dadas entre ellas. El viajante de comercio tiene que visitar todas, recorriendo la menor distancia posible. Encontrar una secuencia de ciudades que minimice la distancia total recorrida.
Codificacion: El cromosoma especifica el orden en que el viajante visita las ciudades.
Codificacion de valores
La codificacion directa por valores puede utilizarse en problemas donde se necesitan valores mas complejos, como numeros reales. Usar codificacion binaria para estos problemas a menudo seria muy dificil.
En la codificacion de valores, cada cromosoma es una cadena de algunos valores. Los valores pueden ser cualquier cosa relacionada con el problema, desde numeros, numeros reales o caracteres hasta objetos mas complicados.
| Cromosoma A | 1.2324 5.3243 0.4556 2.3293 2.4545 |
| Cromosoma B | ABDJEIFJDHDIERJFDLDFLFEGT |
| Cromosoma C | (back), (back), (right), (forward), (left) |
Ejemplo de cromosomas con codificacion de valores
La codificacion de valores funciona muy bien para algunos problemas especializados. Por otro lado, a menudo es necesario desarrollar nuevos operadores de cruce y mutacion que sean especificos del problema.
Ejemplo de problema: Encontrar pesos para una red neuronal
El problema: Hay una red neuronal con una arquitectura dada. Encontrar pesos para las entradas de las neuronas de manera que la red produzca la salida deseada.
Codificacion: Los valores reales en los cromosomas representan los pesos correspondientes de las entradas.
Codificacion en arbol
La codificacion en arbol se utiliza principalmente para hacer evolucionar programas o expresiones, para la programacion genetica.
En la codificacion en arbol, cada cromosoma es un arbol de objetos tales como funciones o comandos en un lenguaje de programacion.
Cromosoma A |
Cromosoma B |
 |
 |
( + x ( / 5 y ) ) |
( do_until step wall ) |
Ejemplo de cromosomas con codificacion en arbol
La codificacion en arbol es muy adecuada para hacer evolucionar programas. El lenguaje de programacion LISP se usa con frecuencia para esto, porque sus programas se representan naturalmente de esta forma y pueden analizarse con facilidad como arboles, de modo que el cruce y la mutacion pueden realizarse relativamente facilmente.
Ejemplo de problema: Encontrar una funcion a partir de valores dados
El problema: Se dan algunos valores de entrada y salida. La tarea consiste en encontrar una funcion que produzca la mejor salida (la mas cercana a la deseada) para todas las entradas.
Codificacion: Los cromosomas son funciones representadas como arboles.
·