Algoritmos genéticos
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.
TSP
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).
Solución
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.
Código
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.
¡Saludos!
@fferegrino :)
Eres mi fucking Idolo
ReplyDeleteAhora lo mismo pero con Búsqueda Tabú :D
ReplyDeleteHahaha, gracias.
ReplyDeleteYa estoy en eso :D D:
This comment has been removed by a blog administrator.
ReplyDeleteHola es que estoy un poco enredado y descargue el visual c# 2010 pero creo que por eso me crea conflicto para ejecutarlo, no tengo nada de experiencia entonces nose como cargar el proyecto en el visual y lo intente hacer como lo hacia en netbeans con java pero me da unos errores. lo que debo hacer es probar tu codigo y luego buscar que reciba esta lista de ciudades y observar cuanto demora en resolverlo 2392 ciudades es que debo exponer sobre ello.
ReplyDeletehttp://read.pudn.com/downloads51/sourcecode/math/176765/ACOTSP.V1.0/ACOTSP.V1.0/pr2392.tsp__.htm
te agradeceria si me pudieras ayudar a correrlo y contarme un poco si es posible que reciba esa lista de ciudades
Excelente proyecto. Muy bien desarrollado. Gracias por ser tan generoso en compartir el proyecto completo para C#. Ayudó en mi clase de logística para presentar el tema del agente viajero.
ReplyDelete