El blog de Wewewew

De las clases aprendí que los algoritmos genéticos son métodos de búsqueda y optimización inspirados en la evolución y en la base genética que esta implica. Para el uso de un algoritmo se genera un conjunto de soluciones posibles (nombraremos a cada una de estas soluciones "individuos") a nuestro problema (llamada población), esta población es mutada y recombinada mediante acciones aleatorias, como sucede en la evolución, además son sometidos a una evaluación para decidir cuales son los más aptos y separarlos del resto, que será descartado. En fin.

Llegó momento de entregar el proyecto final de la unidad de aprendizaje Genetic Algorithms, y como proyecto final elegí el clásico problema del agente viajero (Traveling Salesman Problem, TSP), y digo clásico porque en verdad resulta ser de los más usados para ejemplificar una de las muchas aplicaciones de este tipo de algoritmos.

El problema, más o menos, enuncia que: Un agente viajero tiene que visitar n ciudades sin pasar por la misma ciudad más que una vez, así mismo desea recorrer las ciudades trasladandose lo menos posible entre ellas, esto quiere decir que desea encontrar la ruta más corta para pasar por todas y cada una de ellas solamente una vez.

El problema es sencillo y se puede resolver con un algoritmo genético simple, basta con que se emplee técnicas permutativas (evitando así que se de una solución en la que se repitan ciudades para una ruta).

Para llegar a la solución de este problema escribí una pequeña aplicación en C#, en donde se emplea un algoritmo genético para llegar al resultado. 

Para la cruza se emplea el método de Cruza Cíclica, la mutación se realiza intercambiando dos genes seleccionados aleatoriamente y en la selección se elige a la mitad de individuos con mejores soluciones.

Ahora sí, lo más interesante, además de lo ya mencionado dentro de la aplicación se usa la API de gráficos. Me da la impresión de que por ahí puede haber un poco de desperdicio de memoria pero pues ¡meh!

Traté de comentar el código todo lo que pude a manera de que quede claro así que espero les sirva y cualquier comentario y/o aclaración por correo, Twitter o en la sección de comentarios.