Algoritmos genéticos

Un poco de biología.

Cada individuo de cada una de las especias que habitan en nuestro planeta poseen ciertas características que lo identifican. Si hablamos de seres humanos, cada uno posee cierta estatura, cierto color de ojos y de cabello y cierto tipo sanguíneo, entre otras muchas. Estas características "externas", aunque algunas de ellas no se puedan ver, como el tipo sanguíneo, constituyen lo que se denomina el fenotipo de un individuo. Cada una de estas características es igual a la correspondiente de alguno de los antecesores del individuo, es decir, nos son dadas por herencia, o por lo menos nos es dada cierta predisposición a ella (como la diabetes, por ejemplo). El fenotipo es resultado de la interacción del medio ambiente en que se desarrolla un individuo y la herencia que éste recibe de sus ancestros. La herencia impone ciertos límites o predisposiciones que, al sumarse con el medio, generan el fenotipo. A veces el medio no importa, por ejemplo, no puede intervenir en nuestro color de ojos (hasta donde mi conocimiento sabe), pero en otras influye de manera determinante. Si se posee cierta predisposición a padecer enfermedades cardiovasculares pero se tiene una excelente condición aeróbica desde pequeño, posiblemente éstas nunca se padezcan. El fenotipo de cada individuo está determinado por las proteínas que produce, y esto a su vez está definido en la información genética de cada una de sus células.

La información acerca de cuáles proteínas se producirán está contenida en los cromosomas del individuo. En cada célula somática (aquellas que constituyen el organismo) existen dos juegos de cromosomas que definen las mismas características; un juego es aportado del padre del individuo y el otro lo es de la madre. Un ser humano posee 23 pares de cromosomas.

Hay células especiales llamadas gametos, que intervienen en la reproducción (los espermatozoides y los óvulos humanos pertenecen a esta categoría). Los gametos no se reproducen por mitosis como el resto de las células, el proceso de división se llama en este caso meiosis. En la mitosis las ćelulas producidas son diploides, mientras que en la meiosis el resultado, los gametos, son haploides, sólo tienen un juego de cromosomas.

Partiendo de una célula diploide el proceso meiótico se realiza de la siguiente manera:

1. Se duplica el número de cromosomas en la célula, esto es, se hace una copia de cada cromosoma. Al final quedan dos juegos correspondientes al padre y dos a la madre.
2. Se cruzan un juego de cromosomas del padre con uno de la madre, formándose dos juegos de cromosomas híbridos. El resultado es un juego de cromosomas puros del padre, un juego puro de la madre y dos juegos de cromosomas híbridos.
3. Se divide la célula dos veces y al final del proceso quedan cuatro células haploides: una con cromosomas puros del padre, una con cromosomas puros de la madre y dos con cromosomas híbridos.

Algoritmos genéticos.

En la naturaleza las características de los seres vivos, incluso aquéllas que los hacen óptimos para habitar en su medio, están determinadas por las proteínas que producen. A su vez, como hemos visto, estas proteínas (o más bien, los aminoácidos que las forman) se codifican en el material genético contenido en cada una de las células del individuo. Así pues, la naturaleza ha mapeado cada posible solución al problema de crear un individuo óptimo en una secuencia particular de bases que producirá ciertas proteínas, ha codificado el dominio del problema (todos los posibles individuos) mapeándolo al conjunto de todas las posibles secuencias de nucleótidos.

Así, para un algoritmo genético lo primero que se requiere es determinar en qué espacio se encuentran las posibles soluciones al problema que se pretende resolver. En caso de tener un problema de optimización de una función cuyo dominio es un subconjunto de los números reales, entonces este subconjunto es al que nos referimos. Pero el algoritmo opera sobre "códigos genéticos", sobre genotipos que se deberán mapear al espacio de soluciones. Es decir, es necesario codificar de alguna manera el dominio del problema para obtener estructuras manejables que puedan ser manipuladas por el AG (algoritmo genético). Cada una de estas estructuras constituye el equivalente al genotipo de un individuo en términos biológicos. El elemento del dominio del problema al que se mapea este genotipo es el análogo al fenotipo. Es frecuente que el código de los elementos del dominio del problema utilice un alfabeto binario (0 o 1).

Una vez que se ha definido la manera de codificar los elementos del dominio del problema y se conoce la forma de pasar de un elemento a su código y viceversa, es necesario fijar un punto de partida. Los algoritmos genéticos manipulan conjuntos de códigos en generaciones sucesivas. Nuevamente haciendo una analogía, manipulan poblaciones de códigos. En éstas un código puede aparecer más de una vez. El algoritmo se encargará de favorecer la aparición en la población de códigos que correspondan a elementos del dominio que estén próximos a resolver el problema. En resumen, el algoritmo recibirá como entrada una población de códigos y a partir de ésta generará nuevas poblaciones, donde algunos códigos desaparecerán mientras que otros, que se mapean en mejores soluciones posibles, aparecen con más frecuencia hasta que se encuentra una satisfactoria o hasta que se cumple alguna otra condición de terminación. Para establecer una base nemotécnica, los códigos en una población, es decir, los elementos de ésta serán llamados individuos y a los códigos en general, ya no en el contexto exclusivo de una población, se les denominará indistintamente cromosomas, genotipo, genoma o código genético, por analogía con los términos biológicos de donde surgen.