2/15/2010

Algoritmo Genético: Problema Agente Viajero (TSP)

4 comentarios
El problema del agente viajero, consiste en encontrar el orden en que un viajante de comercio debería visitar varias ciudades para que la distancia recorrida sea mínima. Se trata de un problema NP completo, en el que la única alternativa para su solución consiste en verificar todas las posibles opciones para encontrar cuál es la óptima, hay que tener en cuenta que si el número de ciudades es n, el número de posibles recorridos a ensayar resulta ser n!/2n.
Una de las soluciones para resolver este problema es usando algoritmo genéticos, puesto que una de sus aplicaciones es la resolución de problemas de optimización complejos, aquellos cuyo tiempo de ejecución mediante algoritmos convencionales crece exponencialmente o factorialmente con el aumento del tamaño del problema.
------------------------
El Informe Completo con la Base Teórica lo puedes descargar desde aquí
------------------------

Problema TSP usando Algoritmo Genético
Para resolver el problema TSP se codificó el cromosoma de la siguiente manera:
Representa el orden de las ciudades que debe seguir el agente para su recorrido. El tamaño de este arreglo es el número de ciudades del problema. No puede existir una ciudad que se repita en el recorrido.
La función de evaluación de cada cromosoma esta dado por la longitud del recorrido del mismo, es decir que longitud recorre el agente si sigue el orden de las ciudades que están en el cromosoma. El recorrido completo es de ir de la primera hasta la n-sima ciudad y regresar a la ciudad de partida.
El tipo de Cruzamiento que se uso fue “Cruzamiento de un punto”:
Después del cruzamiento, los hijos tienen un problema, existe una ciudad que se repite: la ciudad 4 en el hijo 1 y la ciudad 7 en hijo 2.
Para resolver este problema, se hizo lo siguiente: la ciudad que se repite en la parte heredada del padre 1, es reemplazada por alguna ciudad (no se encuentre en la parte de la ciudad a reemplazar) de la parte que no es heredada del padre 2.
Para la mutación, se escoge aleatoriamente de la población (después del cruce) tantos individuos como la probabilidad de mutación lo indique. Se uso el tipo de mutación “Order Chaining”, el cual consiste en seleccionar aleatoriamente dos números (ciudades) y cambiarlos. 

Resultados:
Problema 7 Ciudades:
 

Para cada Caso se realizo 20 pruebas:

4 comentarios: