Algoritmos genéticos

Hace cosa de un año estaba empezando con mi proyecto fin de carrera. Gracias a la ayuda de mi novia (que hacíamos un trabajo muy similar) logramos terminarlos en tiempo récord.

A grandes rasgos el proyecto era un estudio comparativo de los resultados obtenidos por varios algoritmos en la resolución de un mismo problema. El problema que yo trataba de resolver era el problema de la "Mochila 01" que reza: Disponemos de un número determinado de elementos cada uno de los cuales tiene un peso y un beneficio. Debemos de seleccionar un subconjunto de elementos que nos proporcionen el máximo beneficio sin que la suma de sus pesos sobrepase la capacidad C de la mochila. El subtítulo 01 indica que un elemento se toma (1) o no se toma(0), pero no se pueden coger fracciones o varias copias de un elemento.

Se presentaban tres algoritmos diferentes para resolverlo: uno mediante Programación Dinámica (divide el problema en trozos pequeños y utiliza los resultados de esos subproblemas para calcular el resultado del problema real), un EDA (Algoritmo de Distribución de la Probabilidad) y un Algoritmo Genético Simple.

Hasta ese momento yo desconocía la existencia de Algoritmos Genéticos y cuando oi la propuesta me asusté por ese nombre, pero no tenía otra oportunidad así que tuve que aceptar si quería acabar la carrera a tiempo para matricularme en la superior sin perder ningún año.

No me arrepiento. A pesar de lo rimbombante del nombre, descubrí un mundo de algoritmos muy curiosos y útiles a la par que entretenidos (si te gusta programar). Los Algoritmos Genéticos están basados en la selección natural de las especies (aquellos individuos con mejores aptitudes tendrán más posibilidades de reproducirse) y se utilizan para resolver problemas.

Lo que hacen los Algoritmos Genéticos es transformar la información en una secuencia de genes (información) llamada cromosoma (solución potencial al problema). Por ejemplo, para el problema de la mochila con 3 elementos, tendríamos el cromosoma 0 1 0 que indicaría que los elementos 1 y 3 no forman parte de la solución y que el elemento 2 sería el único elemento del subconjunto solución.
Partiendo de esta base, el algoritmo crearía un número determinado de individuos (cromosomas) formando así una población de X individuos generados al azar. Un ejemplo de población de 4 individuos sería:
1 1 1
0 1 0
0 0 0
1 1 0

Se analiza cada individuo otorgándole una "puntuación". En el caso de la Mochila 01  dicha puntuación de cada cromosoma equivale al beneficio máximo obtenido por el subconjunto de elementos introducidos en la mochila.

Una vez tengamos todos los individuos de una población evaluados se procederá a seleccionar un número determinado de cromosomas que serán los padres de la nueva generación. Aquí existen muchas opciones de selección. Si elegimos un EDA, la población se crea en función de probabilidades obtenidas al analizar la disposición de los beneficios y los genes en la generación anterior. Si utilizamos un operador de ruleta crearemos una virtual en la que cada casilla se corresponderá con un individuo y tendrá un tamaño proporcional a su fitness de modo que tendrá más posibilidades de ser elegido para procrear cuanto mejor sea la solución que nos ofrece.

Este proceso se repetiría durante un número determinado de generaciones y se tomaría como resultado uno de los cromosomas de la generación final. Aunque también es posible tomar el mejor cromosoma seleccionado a lo largo de todas las generaciones. Existen muchas variantes, pero he tratado de simplificar el tema evitando comentar cruces entre genes y demás operadores.

Como curiosidad, el problema de la Mochila 01 es un problema bastante simple que no precisa de Algoritmos genéticos en su resolución. Pero son muy útiles en la resolución de problemas complejos o de difícil solución como el TSP (Viajante de comercio).