Entre las cosas pendientes que hice el año pasado y no llegué a publicar por falta de tiempo está mi Proyecto de Fin de Carrera. Lo presenté en Marzo del 2009 en la ETS de Ingeniería Informática de la UNED, en Madrid.
El título del proyecto es “Análisis, Aplicación y Evaluación de un Algoritmo Evolutivo”. Concrétamente, se centra en el uso de algoritmos genéticos por medio de la implementación de un problema clásico en computación como es el de la mochila, tratando de analizar qué parámetros del algoritmo genético afectan en mayor medida a su resolución.
Un algoritmo genético no es más que un algoritmo tal que, partiendo de una serie de soluciones factibles o no factibles, las hace evolucionar, generando nuevas soluciones que tienden a mejorar las iniciales. Se utilizan fundamentalmente cuando el espacio de soluciones es muy amplio y no necesitamos la mejor solución, sino que con una buena aproximación obtenida en un espacio de tiempo acotado nos es suficiente.
En el caso concreto del problema que elegí, el problema de la mochila, lo que tratamos de hacer es llenar un contenedor con una capacidad limitada (la mochila) con una serie de objetos, de forma que el valor total de los objetos introducidos en la mochila sea el máximo posible. Cada uno de los objetos tiene un valor y un peso o volúmen asociado. Podemos observar como esto conduce a que pueda haber muchas soluciones posibles, pero estamos buscando aquella que nos proporcione la colección de objetos de mayor valor posible.
Para hacernos una idea de como funciona el algoritmo en este caso, y la manera de trabajar de un algoritmo genético genérico podemos pensar en el siguiente escenario como ejemplo:
- Tenemos una mochila que queremos rellenar que tiene una capacidad máxima C.
- Tenemos una lista con los objetos que podemos meter en la mochila. Cada objeto tiene asociado un valor V y un volúmen Vol.
- Tenemos que llenar la mochila con objetos, de forma que la suma de los volúmenes de los objetos no supere a la capacidad de la mochila y, además, que el valor total de los objetos introducidos sea el máximo posible.
La solución típica sería calcular todas las posibles combinaciones de objetos, con el valor total de la solución, y quedarnos con el mejor. Esta es la solución correcta, y garantiza que el valor máximo ha sido encontrado. El problema aparece cuando tenemos listas con millones, miles de millones o billones de objetos. Calcular todas las posibilidades en este caso es demasiado costoso en tiempo. Existen problemas en los que es imposible obtener una solución con este tipo de cálculo extensivo en un tiempo lógico. Es aquí donde hacen aparición los algoritmos evolutivos y donde resulta especialmente interesante su utilización. El algoritmo genético parte de una serie de soluciones básicas y, a partir de estas, irá mejorando la solución global del problema. La ejecución del algoritmo terminará cuando nosotros lo especifiquemos (un número determinado de generaciones, cuando no siga mejorando la solución tras un número dado de generaciones, en un tiempo fijo… etc)
En nuestro caso, para calcular la solución, partimos de una serie de soluciones iniciales que representan colecciones aleatorias de objetos. Calculamos para todas estas soluciones el valor total de los objetos introducidos en la mochila. El algoritmo genético tomará estas soluciones y realizará operaciones entre ellas, con la intención de ir mejorándolas. Iría tomando objetos de una y otra solución, y calcularía el valor de esta nueva solución. Las nuevas soluciones generadas, se comparan con sus antecesores, y nos vamos quedando con las mejores. Para compararlas se utiliza el valor total de los objetos introducidos en la mochila.
La “población” de soluciones se va mejorando de forma similar a como lo hacen las distintas especies animales en función de la teoría de la evolución de Darwin: por medio de la supervivencia del más apto. De hecho, la generación de nuevas soluciones es el equivalente computacional a la reproducción: dados n progenitores, mezclamos su “código genético” para generar un número determinado de descendientes. A estos descendientes, a su vez, aplicamos operadores que simulan mutaciones, eliminación de los elementos de mayor “edad”… etc
El fichero con la presentación que realicé podeis verlo a continuación:
Por lo demás, aquí os dejo un enlace a la memoria, y otro al software de simulación de la mochila.
El código fuente lo subiré próximamente, en cuanto pueda añadirle un fichero con la licencia y demás parafernalia.
Relacionado
RSS 2.0
