Práctica 1 | Parte 1

En esta tarea nuestros puntos a realizar son:

* Generar instancias del problema del viajero
* Resolver una instancia por fuerza bruta
* Generar pseudocódigo o diagrama de flujo para ACO (elegimos el diagrama)

Generando instancias del problema del viajero

Estos son algunos ejemplos de instancias para el problema del viajero:

Instancia A)
Un vendedor de libros que recide en el País México debe visitar al mes cuatro de sus clientes localizados en los estados de Monterrey, San Luis Potosí, Saltillo, Reynosa, sin importar el orden, lo importante es visitar todos los sitios y lograr el menor recorrido posible.
Las Distancias en Km entre las ciudades son:

	Monterrey	San Luis	Saltillo	Reynosa
Monterrey	0	515	88.3	221
San Luis	515	0	451	745
Saltillo	88.3	451	0	318
Reynosa	221	745	318	0

El objetivo es minimizar la distancia total recorrida por el vendedor.

Instancia B)

Un  turista en Nueva York utiliza el transporte público para visitar 4 sitios. El comienzo ni el final del recorrido no es importante, tampoco el orden de la visita, lo importante es visitar todos los sitios con el menor costo de pasaje. La siguiente tabla muestra los pasajes en dólares entre los diferentes lugares.

	Sitio-1	Sitio-2	Sitio-3	Sitio-4
Sitio-1	0	22	28	25
Sitio-2	22	0	19	20
Sitio-3	28	19	0	17
Sitio-4	25	20	17	0

Instancia C) (Programa)
Aquí se muestra un programa hecho en python el cual a partir de el argumento por consola "CIUDADES" genera una matriz simétrica con números aleatorios generando una instancia del problema del viajero.

.

from sys import argv #Nos sirve para tomar argumentos por consola
import random #para llenar los celdas de manera pseudoaletoria


#Este bloque nos sirve para detectar un tipo de erer por los argumentos de consola
try:
 CIUDADES = int(argv[1])
except Exception:
 CIUDADES = 4 #asignar 4 ciudades por si ocurre algun error.

#funcion que crea la matriz por default pone puros 0.
def creaMatriz(CIUDADES):
    matriz = []
    for i in range(CIUDADES):
        matriz.append([0] * CIUDADES)
    return matriz

#creación de la matriz instancia del TSP con enteros pseudoaleatorios en un rango de 1 a 999
def instanciaTSP(CIUDADES):
    matriz = creaMatriz(CIUDADES)
    #gen se utiliza para saber cuantos numeros generar. 
    #La verdad despercicia muchos elementos en concreto solo utiliza (N*N - N)/2 un mejor algoritmo podria solucionarlo
    gen = (CIUDADES*CIUDADES) 
    lrand = [random.randint(1, 999) for i in range(gen)] 
    cont = 0
    #este for anidado es donde los elementos se van guardando de forma simétrica los elementos.
    for i in range(CIUDADES):
        for j in range(CIUDADES):
            if (i != j):
                matriz[i][j] = lrand[cont]
                matriz[j][i] = lrand[cont]
                cont += 1
    return matriz
#funcion para imprimir la matriz
def imprimeMatriz(matriz):
    for ly in matriz:
        for lx in ly:
            print "%3d" % lx,
        print "\n"    

matrix = instanciaTSP(CIUDADES)
imprimeMatriz(matrix)

A continuación se muestra una captura de pantalla de la corrida del programa.

Resolver una instancia por fuerza Bruta

En este caso se escogió la instancia A.
Antes de ello anexo un mapa de México:

Mapa México: http://www.map-of-mexico.co.uk/espanola/imagenes/politicospanishnew.gif

Aquí se muestra un grafo de los vectores y sus pesos

Ahora se utilizaran árboles para lograr todos los posibles resultados empezaremos con Monterrey con todas sus posibles rutas y cargas, se van a sumar las cargas de cada ruta de arriba del origen al fin esto va a generar 4 resultados en total por ciudad inicial.

El mas bajo aqui es 990 que es la ruta Mty-Reynosa-Saltillo-S.L.P.

Seguimos con San Luis Potosí

La ruta mas corta es S.L.P.-Saltillo-Monterrey-Reynosa con 760.3

Seguimos con Saltillo

La ruta mas corta es Saltillo-Monterrey-S.L.P con 1054

Seguimos con Reynosa

La ruta mas corta es Reynosa-Monterrey-Saltillo-S.L.P. con 760.3

El siguiente paso es comparar los resultados preeliminares y ver cual ruta arrojó el menor resultado.

Después de eso llegamos a la conclusion que la ruta mas corta es:
 Reynosa-Monterrey-Saltillo-S.L.P.
ó
al revez:
S.L.P-Saltillo-Monterrey-Reynosa ambos con 760.3

Así es como obtuvimos nuestro resultado utilizando fuerza bruta.

Diagrama de flujo de ACO

Partiendo de la base de que lo que tenemos es una colonia de hormigas y un grafo, creamos el siguiente diagrama de flujo, donde ilustramos de la manera más simple posible el ciclo que cada hormiga sigue, desde que sale del nido hasta que llega a la meta.

Descargar aquí (recomendación):

https://dl.dropboxusercontent.com/u/41478854/ACO.png

Finalizando con esta 1era parte pudimos apreciar y analizar mejor el problema del viajero y notar considerablemente el fastidio de solucionar por fuerza bruta. Además, tenemos que decir que el diagrama de flujo para ACO no fué nada fácil ya que tuvimos que leer demasiado y pensar durante unas cuantas horas.

Referencias:

Mapa de México [Image file]. Retrieved from
http://www.map-of-mexico.co.uk/espanola/imagenes/politicospanishnew.gif

Ant Colony Optimization Algorithm [Video file]. Retrieved from http://www.youtube.com/watch?v=SMc6UR5blS0&feature=related

Dorigo et al (2006). Ant Colony Optimization. Available from http://elisa.dyndns-web.com/~saraelena/material/sistadap/dorigo_aco_2006.pdf