Sistemas Adaptativos: Reporte Práctica 1 - ACO (Optimización por Colonia de Hormigas).

Introducción.

El Problema del Agente Viajero o TSP (del inglés Travelling Salesman Problem) básicamente es un problema de Optimización que busca la minimización. Surge con la necesidad de buscar la ruta más corta o de menor costo en un conjunto de ciudades o puntos, esto sin depender del orden a seguir en el viaje siempre y cuando el recorrido sea cerrado.

El TSP es muy importante ya que se aplicar en la vida diaria cuando simplemente estamos de viaje y queremos dar el tour más corto en los lugares turísticos, o hasta en la industria por ejemplo cuando se busca hacer taladrado en piezas de metal tomando el menor tiempo, otras situaciones que pueden aplicar son en el autobús escolar, el repartidor de comida y el diseño de tarjetas electrónicas.

La dificultad de este problema crece a medida de que aumentas las ciudades ya que se generan cada vez más combinaciones que por fuerza bruta; lo cual sería muy tedioso y cansado para resolver.

La Optimización por Colonia de Hormigas o ACO (del inglés Ant Colony Optimization) es una metaheurística para la resolución de problemas como la ruta más corta, la cual se inspira en las colonias de hormigas reales ya que por naturaleza se organizan para ir por la comida cada vez por una mejor ruta.

El ACO es justamente lo que el TSP necesita porque es un Algoritmo que nos ayudará a encontrar la ruta con menor costo.

En esta entrada implementaremos el ACO para la resolución de instancias TSP, primero dando un enfoque teórico para conocer y entender cómo se soluciona este problema, y después la implementación con un programa de la solución de una instancia donde se mostraran los parámetros utilizados y finalmente la verificación de resultados.

Marco Teórico.

El TSP esta dentro de la clase de los problemas NP-Completos y se dice que pertenece a este ya que difícilmente existe un algoritmo eficiente para su resolución para mejor información ver referencias.

En una forma más formal el TSP consiste primeramente dando un grafo ponderado en las aristas por lo general no dirigido, dónde cada vértice representa una ciudad y la arista el costo del viaje, cada vértice esta unido con los vértices restantes. Éste grafo puede ser representado por una matriz. Ya teniendo este grafo o matriz el problema a resolver es encontrar una ruta que permita pasar por todos los vértices (ciudades) y regresar al origen generando el menor costo (ruta más corta).

Una instancia (ejemplo concreto acerca del problema) del TSP sería especificar el número de ciudades con sus respectivos costos o distancias de cada una de las ciudades a todas las demás, he aquí de donde proviene que dependiendo del tamaño de la instancia crece la dificultad de resolverlo ya que el tamaño del espacio de búsqueda está dado por permutaciones, tal que para una instancia de 4 ciudades habría 24 posibles soluciones, pero para una de 10 habría 3,628,800 posibles soluciones.

Veamos una instancia agregando contexto tomado y adaptado del libro de Investigación de Operaciones de Hamdy A. Taha.

"Un vendedor de libros que reside 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, lograr el menor recorrido posible y regresar al punto inicial.
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.

En esta ocasión resolveremos la instancia con la Ayuda de la Fuerza Bruta que cosiste en obtener todos los resultados posibles y observar el menor, esto es sencillo con instancias pequeñas pero se vuelve un dolor de cabeza con algunas más grandes.

Para observar de una mejor manera la instancia se hizo un grafo.

Después se obtuvieron todas las posibles soluciones (rutas)

Para las 4 ciudades se obtuvieron 24 posibles caminos, dónde el camino más o de menor costo fue de 1505 y fue repetido en varios recorridos.

Como se menciono anteriormente ACO (Colonización Basada en Colonias de Hormigas) nos ayuda bastante a resolver el problema TSP ya que su principal objetivo es encontrar la ruta que lo lleve a tener un menor costo .

El ACO es una metaheurística que básada en la naturaleza y esta dentro de la clase de los algoritmos de Swarm Intelligence (Enjambre), creada por Marco Dorigo en el año 1992.

NOTA: Principalemente las formulas y alguna de la información que se presenta a continuación
fue basada del Documento de Marco Dorigo, acerca de ACO en el 2006, revisar Referencias.

Esta técnica se basa en la metáfora natural de las Hormigas y como es su organización que Dorigo la llama "Stigmergy" que es como un mecanismo de coordinación indirecta, las hormigas son ciegas entonces en su búsqueda de alimento ellas dejan un rastro de feromonas por el recorrido que van haciendo la cual cualquier otra hormiga es capaz de detectar.

Al llegar a un cruce de camino (bifurcación) la hormiga elije de forma probabilística ya que toma el camino que contenga un mayor rastro de feromona.

Los mejores caminos serán los que están más cerca a la comida y por lo tanto más feromona ya que un mayor numero de hormigas pasa por ahí aumentando el rastro de feromona.

Los menos prometedores poco a poco se quedan sin feromona debido a la evaporación de ésta ya que pocas hormigas pasas por ahí.

Después de varios recorridos se encuentra el mejor camino.

A partir de esta observación se llego al siguiente algoritmo.

El documento de Alonso acerca de ACO nos muestra un pseudocódigo que nos ayudará a realizar nuestra implementación y es el siguiente:

Procedimiento Metaheuristica_OCH()
 Inicializacion_de_parámetros
 mientras (criterio_de_terminación_no_satisfecho)
     Programación_de_actividades
         Generación_de_Hormigas_y_actividad()
         Evaporacion_de_Feromona()   
     fin Programación_de_actividades
 fin mientras
fin Procedimiento

Procedimiento Generación_de_Hormigas_y_actividad()
    repetir en paralelo desde k=1 hasta m (numero_hormigas)
        Nueva_Hormiga(k)
    fin repetir en paralelo
fin Procedimiento

Procedimiento Nueva_Hormiga(id_Hormiga)
    inicializa_hormiga(id_Hormiga)
    L = actualiza_memoria_hormiga()
    mientras (estado_actual "pi" estado_objetivo)
        P = calcular_probabilidades_de_transición(A,L,W)
        siguiente_estado = aplicar_política_decisión(P,W)
        mover_al_siguiente_estado(siguiente_estado)
        si (actualizacion_feromona_en_linea_paso_a_paso)
             depositar_feromona_en_el_arco_vistado()
        fin si
        L = actualizar_estado_interno()
    fin mientras
    si (actualizacion_feromona_en_linea_a_posteriori)
         para cada arco visitado
              depositar_feromona_en_el_arco_visitado()
         fin para
    fin si
    liberar_recursos_hormiga(id_hormiga)
fin Procedimiento

Para realizar el ACO Dorigo implemento ciertas formulas las cuales ayudan a la selección de camino (arista), la actualización de la feromona (aquí interviene el depósito y evaporación).

En cada iteración, los valores de las feromonas son actualizados por todas las hormigas "m" que han construido una solución. τi j es la feromona asociada con la arista que une a la ciudad i y j , la actualización se lleva a cabo de esta forma:

Dónde:

ρ = Factor de decremento de la feromona (evaporación).

Δτ^k i j = Cantidad de feromona que deposita en la arista (i, j) de la hormiga k:

Esta dada por:

Si k paso por la arista(i, j) en este recorrido toma el arriba

Si no dejes feromona.

Donde Q es el factor constante del incremento de la feromona y Lk es la longitud de los caminos (cuantas ciudades pasa al completar el recorrido. Es constante para cualquier recorrido. depende dlel numero de ciudades).

Para encontrar la Probabilidad de la hormiga k de selección de Aristas de i a j, se sigue la Formula:

Si cij esta en el conjunto de los posibles candidatos. realizar la formula sino asignar 0

Donde:
α = Influencia en el rastro de feromona. (Darle mayor importancia a la feromona).
β = Influencia a la distancia de cada arista.
ηij = información heurística de las distancias o costos de cada arista.
ηil = información heurísitica de los demás caminos candidatos.
τil = feromona de los demás caminos candidatos.

Para comprender mejor la formula de probabilidad la parte del denominador se refiere simplemente a la Sumatoria del producto de la Informacion Heuristica elevado a beta y la feromona elevada a la alfa de todos los candidatos a obtener probabilidades. Es decir a las demás ciudades las cuales puedes seguir el recorrido.

Por último hace falta como obtener la información heurística acerca de las distancias o costos. Aquí dij es la distancia que hay en la arista (i,j) o bien entre la ciudad i y j.

Tanto los costos, la información heurísitica, las feromonas, y el recorrido actual que tiene la hormiga es necesario tenerlos almacenados en algún especie de lista, o arreglo.

Desarrollo.

A continuación se presenta un programa el cual realiza la resolución de las 2 instancias, la primera resuelve el problema de las ciudades y el vendedor de libros (4 ciudades) que es la instancia propuesta en el marco teórico, después se presenta la instancia 2 la cual el programa genera una instancia de 10 ciudades de manera aleatoria, las dos instancias se resuelven basándose en ACO.

Generador de Instancias Aleatorias.

Aquí se muestra el generador de instancias aleatorias el cual recibiendo el parámetro de cuantas ciudades es como realiza la matriz de números aleatorios.

def generador_random(self,NoCiudades):
        self.ciudades = NoCiudades
        ciudad = [[0 for i in range(self.ciudades)] for i in range(self.ciudades)]
        print ciudad
        
        random.seed()
        for i in range(self.ciudades):
            for j in range(self.ciudades):
                if i == j:
                    ciudad[i][j] = 0
                else:
                    if i>0 and j &lt i and i != j:
                        ciudad[i][j]=ciudad[j][i]
                    else:
                        
                        ciudad[i][j] = random.randint(1,25)

        self.feromonas = [[0.01 for i in xrange(0,self.ciudades)]for i in xrange(0,self.ciudades)]
        
        print ciudad
        self.instancia = ciudad

Inicialización del Algoritmo.

El método correrHormiga(), nos ayuda a inicializar el algoritmo el cual realiza las funciones de seleccionar Arista y la Actualización de Feromona

    def correrHormiga(self):
        gral = []
        for hormigas in range(self.ciudades):
            r =  self.seleccionarArista() #mando a correr a una hormiga y almacen en r su recorrido
            gral.append(r)#mando los recorridos a una arreglo general
            self.actualizarFeromonas(r) #al final de cada hormiga actualizo la feromona
        print "Recorridos de cada hormiga: ",gral

        self.evaluarRecorridos(gral) #Evaluo los recorridos de cada Hormiga

Selección de Aristas.

El método de selección de Aristas, obtiene las probabilidades de los caminos a seguir, y después por medio de la ruleta decide que camino tomar.

 def correrHormiga(self):
        gral = []
        for hormigas in range(self.ciudades):
            r =  self.seleccionarArista() #mando a correr a una hormiga y almacen en r su recorrido
            gral.append(r)#mando los recorridos a una arreglo general
            self.actualizarFeromonas(r) #al final de cada hormiga actualizo la feromona
        print "Recorridos de cada hormiga: ",gral

        self.evaluarRecorridos(gral) #Evaluo los recorridos de cada Hormiga
        
                            
    def seleccionarArista(self):#,instancia):
        #for i in xrange(2):
        ruleta = []
        pos_hormiga = self.pos_hormiga
        #variables de la formula
        sumatoria = 0
        Tij_and_Nij = []
        pos_ant = 0
        pos_act = 0
        aristas_checar = []
        recorridos=[0]
        for hormigas in range(self.ciudades-1):
            aristas_checar = []
            for i in range(self.ciudades): #checar que puede usar la lista
                if not i in recorridos and i !=0:
                    aristas_checar.append(i)
            if self.debug:
                print "soy aristas a checar: ",aristas_checar

            Tij_and_Nij = []
            for elemento in aristas_checar: #sacar la sumatoria
                #calcular tij and nij
                if self.debug:
                    print "elemento: ",elemento," pos_hormgiga: ",pos_hormiga
                    print "\t elemento instancia: ",self.instancia[pos_hormiga][elemento]
                Tij = self.feromonas[pos_hormiga][elemento]
                Nij = 1.0/self.instancia[pos_hormiga][elemento]
                elev = math.pow(Tij,self.alfa)*math.pow(Nij,self.beta)
                Tij_and_Nij.append(elev)

            for elemento in Tij_and_Nij:    
                sumatoria += elemento
            if self.debug:    
                print "soy TN: ",Tij_and_Nij
                print "voy a ruleta"
            
            ruleta = []
            i=0
            for T_N in Tij_and_Nij:#asignar a ruleta en base a probabilidad
                Pij = T_N/sumatoria
                if self.debug:
                    print "Soy Pij de elem: ",Pij
                for j in xrange(int(math.ceil(Pij*10.0)+1)):
                    ruleta.append(i)
                i+=1

            if self.debug:
                print "Tij_and_Nij: ",Tij_and_Nij
                print "Sumatoria: ",sumatoria
                print "Ruleta: ",ruleta

            random.shuffle(ruleta)#chaca chaca 

            #SELECCIONAR ARISTA DE LA RULETA
            arista = aristas_checar[ruleta[0]] #seleccinamos una arista
        
            if self.debug:
                print "Arista selccionada: ",arista

            pos_ant = pos_act
            pos_act = arista
            recorridos.append(pos_act)
            if self.debug:
                print "vengo de : ",pos_ant,"voy a : ",pos_act
                print "mis sitios visitados: ",recorridos
            self.ponerFeromonas(pos_ant,pos_act)
        recorridos.append(0)
        return recorridos

Actualización de Feromonas.

El metodo actualizarFeromonas() es el metodo que realiza el depósito y evaporación de las feromonas además utiliza otro método llamado sumaTij_K() y recibe una lista de recorridos los cuales hace referencia al recorrido que paso la hormiga en esta iteración.

     
    def sumaTij_K(self,recorridos):
        suma = 0
        #for i in range(self.ciudades):
        L_k = 0
        for elemento in recorridos:
            L_k += elemento
        suma += self.Q/L_k
        return suma

    def actualizarFeromonas(self,recorridos):
        
        sumaT_i_j = self.sumaTij_K(recorridos)
        nuevas_feromonas = []
        for i in range(len(self.feromonas)):
            lote = []
            for elemento in self.feromonas[i]:
                lote.append( (1-self.P)*elemento + sumaT_i_j )
            nuevas_feromonas.append(lote)

        self.feromonas = nuevas_feromonas
        if self.debug:
            print "Nuevas feromonas: ",self.feromonas

Pueden obtener el código de la siguiente liga: ACO_TSP.py

Resultados.

Ahora bien a partir del código hecho en python se realizarán las pruebas y los resultados.

Para las dos instancias se tomaron estos valores para la probabilidad en la selecciones de Aristas.
α = 1.0
β =1.0

El coeficiente de evaporación se le asignó un valor de p =0.5 y para el coeficiente de depósito de feromona se tomó el valor de Q= 10.

Por razones principales de tiempo no se pudo hacer más experimentación con diferentes valores de parámetros aunque con la lectura de los documentos de Dorigo vimos que estos parámetros son los más genéricos para obtener la solución.

El programa se corre con argumentos de consola en la captura de pantalla se muestran.
El primero es para debug 1 es si 0 es no.
El segundo es para cual instancia utilizar si la predefinida (instancia 1 = 1) o la aleatoria = 0
El tercero si se eligió la aleatoria se designa el tamaño de la instancia si no no especificar.

Resultado de Instancia 1.

Analizando y comparando vemos que coincide con la instancia resuelta por fuerza bruta.

Resultado instancia 2.

Esta es una instancia de 10 ciudades con números aleatorios.

Resultado instancia 3.

Instancia aleatorea la cual confirma que el camino mas corto es el 2.

Resultado instancia 4.

Instancia aleatoria con 7 ciudades y el camino mas corto es el 4.

Conclusiones.

Realmente entender un algoritmo o metaheurística puede resultar algo no tan complicado, sin embargo implementarlo en un lenguaje de programación puede resultar ser un poco más difícil, a pesar de que ACO ayuda a la resolver el TSP también si la instancia es muy pequeña como la que presentamos primero y nunca se probara con instancias más grandes resulta sencillo, más no mejor, implementar un algoritmo de Fuerza Bruta que una Metaheurística como ACO, sin embargo, si la instancia crece resulta ser mejor tener una implementación que ayude a resolver instancias del mismo tamaño y más grandes.

En relación con los resultados si coinciden la instancia uno que fue resuelta por fuerza bruta, se ve que el algoritmo cumple con la búsqueda del mejor camino.

Para terminar, realizar este programa no fue fácil tiene su grado de dificulta y ahora vemos por que tanto tiempo de anticipación se dio y aún así se nos estuvimos apresurados sin embargo pues se trató de entregar el programa funcionando con la mejor calidad posible.