ALGORITMO DE OPTIMIZACIÓN POR COLONIA DE HORMIGAS (ACO)

INTRODUCCIÓN

El problema del viajero consiste en el recorrido de aristas para determinar la ruta cuya solución permite al viajero llegar a su destino siendo ésta la óptima debido a que es la de menor costo en comparación con las demás rutas.

El problema del viajero tiene numerosas aplicaciones en las que resaltan el recorrido de un transporte escolar, paquetería y correo,  Agencia de viajes (Tours) entre otras. La dificultad de éste problema es que conforme aumenten el número de nodos, aumentarán las rutas y por lo tanto las combinaciones se incrementarían.

Éste problema puede resolverse con ACO, pero ¿qué es ACO? Por sus siglas en inglés Ant Colony Optimization (Optimización Colonia de Hormigas), se le llama así porque simula el comportamiento de las hormigas desde su hormiguero a la fuente de comida. Mientras se mueven entre estos dos puntos van dejando un rastro de feromona que ayuda a determinar un camino óptimo que las demás hormigas puedan seguir.

La relación de ACO con el problema del viajero es que ésta técnica utiliza la probabilidad para resolver problemas donde su solución sea el mejor camino o ruta en un grafo siendo este el objetivo del problema del viajero.

MARCO  TEÓRICO

El problema consiste en un viajante que tienen un número de destinos los cuales debe visitar, puede partir de cualquier punto con la condición de regresar al mismo. Los demás destinos solo pueden ser visitados una vez por recorrido. El objetivo es recorrer los lugares cuidando que la ruta sea la de menor costo.

Se representa con la estructura de grafo debido a que sus nodos simbolizan ciudades y las ramas los caminos que puede recorrer siendo la conexión de los lugares. Se considera un problema NP-completo ya que es un algoritmo no eficiente, pero existe la validación para la supuesta solución

En una instancia de éste problema involucra al viajero, el número de destinos(nodos) a los que llegará según el objetivo, los caminos y rutas ( ramas) que viene siendo la matriz de costos ( el mapa del recorrido) que conectarán dichos lugares con cierto costo o peso que determinarán el tamaño de la ruta de modo que se elija la óptima.

A continuación se mostrará una instancia resuelta por fuerza bruta donde se verá con mayor claridad la estructura de grafo del problema.

INSTANCIA POR FUERZA BRUTA

Realizamos un ejemplo para poder resolverlo por fuerza bruta; es decir crear todas las combinaciones posibles para que del estado inicial se recorran todos los nodos a través de las aristas regresando al lugar de inicio sin pasar 2 veces o más por un mismo nodo.

El objetivo es identificar por este método cuál es el camino óptimo para realizar el recorrido.

Instancia: Un niño tiene que hacer un recorrido que su madre le ordenó, no importa donde empiece solo tiene que terminar en el mismo sitio con la restricción ya especificada anteriormente. Consiste en pasar por cada uno de los lugares e intentar hacerlo en el menor tiempo posible, los números que se encuentran en la imagen son la cantidad de calles que el niño tiene que atravesar para ir de un lugar a otro, también se muestran los 5 lugares a los que tiene que ir. La solución trata en encontrar el recorrido por donde el niño cruce menos calles para disminuir el tiempo del traslado.

Solución:

Como vamos a estar trabajando con varias combinaciones será un poco tedioso estar viendo todo el nombre del lugar por lo que decidimos poner solo una letra que identifique a cada uno de ellos.

Tienda=A

Florería=B

Tortillería=C

Carnicería=D

Panadería=E

Ahora empezamos a buscar todas las combinaciones posibles, nosotros preferimos usar árboles para cada uno de los lugares. Así como se muestra en la siguiente imagen, hicimos el mismo procedimiento para B, C ,D y E:

A partir de las combinaciones obtenidas de los árboles se consiguió la siguiente tabla:

Inicia y termina en A	Inicia y termina en B	Inicia y termina en C	Inicia y termina en D	Inicia y termina en E
A,B,C,D,E,A A,B,C,E,D,A A,B,D,C,E,A A,B,D,E,C,A A,B,E,C,D,A A,B,E,D,C,A A,C,B,D,E,A A,C,B,E,D,A A,C,D,B,E,A A,C,D,E,B,A A,C,E,B,D,A A,C,E,D,B,A A,D,B,C,E,A A,D,B,E,C,A A,D,C,B,E,A A,D,C,E,B,A A,D,E,B,C,A A,D,E,C,B,A A,E,B,C,D,A A,E,B,D,C,A A,E,C,B,D,A A,E,C,D,B,A A,E,D,B,C,A A,E,D,C,B,A	B,A,C,D,E,B B,A,C,E,D,B B,A,D,C,E,B B,A,D,E,C,B B,A,E,D,C,B B,A,E,C,D,B B,C,A,D,E,B B,C,A,E,D,B B,C,D,A,E,B B,C,D,E,A,B B,C,E,D,A,B B,C,E,A,D,B B,D,A,C,E,B B,D,A,E,C,B B,D,C,A,E,B B,D,C,E,A,B B,D,E,A,C,B B,D,E,C,A,B B,E,A,C,D,B B,E,A,D,C,B B,E,C,A,D,B B,E,C,D,A,B B,E,D,A,C,B B,E,D,C,A,B	C,A,B,D,E,C C,A,B,E,D,C C,A,D,B,E,C C,A,D,E,B,C C,A,E,B,D,C C,A,E,D,B,C C,B,A,D,E,C C,B,A,E,D,C C,B,D,A,E,C C,B,D,E,A,C C,B,E,A,D,C C,B,E,D,A,C C,D,A,B,E,C C,D,A,E,B,C C,D,B,A,E,C C,D,B,E,A,C C,D,E,A,B,C C,D,E,B,A,C C,E,A,B,D,C C,E,A,D,B,C C,E,B,A,D,C C,E,B,D,A,C C,E,D,A,B,C C,E,D,B,A,C	D,A,B,C,E,D D,A,B,E,C,D D,A,C,B,E,D D,A,C,E,B,D D,A,E,C,B,D D,A,E,B,C,D D,B,A,C,E,D D,B,A,E,C,D D,B,C,A,B,D D,B,C,B,A,D D,B,E,A,C,D D,B,E,C,A,D D,C,A,B,E,D D,C,A,E,B,D D,C,B,A,E,D D,C,B,E,A,D D,C,E,A,B,D D,C,E,B,A,D D,E,A,B,C,D D,E,A,C,B,D D,E,B,A,C,D D,E,B,C,A,D D,E,C,A,B,D D,E,C,B,A,D	E,A,B,C,D,E E,A,B,D,C,E E,A,C,B,D,E E,A,C,D,B,E E,A,D,B,C,E E,A,D,C,B,E, E,B,A,C,D,E E,B,A,D,C,E E,B,C,A,D,E E,B,C,D,A,E E,B,D,A,C,E E,B,D,C,A,E E,C,A,B,D,E E,C,A,D,B,E E,C,B,A,D,E E,C,B,D,A,E E,C,D,A,B,E E,C,D,B,A,E E,D,A,B,C,E E,D,A,C,B,E E,D,B,A,C,E E,D,B,C,A,E E,D,C,A,B,E E,D,C,B,A,E

  

Como una de las restricciones es que el recorrido comienza en el mismo lugar donde finaliza, eso nos permite eliminar unas cuantas combinaciones esto porque coinciden con otras al momento de leerlas inversamente, por lo que al momento de hacer la suma de las calles que se pasan en cada recorrido nos darán el mismo resultado.

Inicia y termina en A	Inicia y termina en B	Inicia y termina en C	Inicia y termina en D	Inicia y termina en E
A,B,C,D,E,A=28 A,B,C,E,D,A=27 A,B,D,C,E,A=30 A,B,D,E,C,A=37 A ,B,E,C,D,A=26 A,B,E,D,C,A=34 A,C,B,D,E,A=29 A,C,B,E,D,A=25 A,C,D,B,E,A=28 A,C,D,E,B,A=34 A,C,E,B,D,A=27 A,C,E,D,B,A=37 A,D,B,C,E,A=21   A,D,C,B,E,A=18	B,A,C,D,E,B=34 B,A,C,E,D,B=37 B,A,D,C,E,B=36 B,A,D,E,C,B=27 B,A,E,D,C,B=28 B,A,E,C,D,B=30 B,C,A,D,E,B=25 B,C,A,E,D,B=29 B,C,D,A,E,B=18 B,C,E,A,D,B=21 B,D,A,C,E,B=27 B,D,C,A,E,B=28	C,A,B,D,E,C=37 C,A,B,E,D,C=34 C,A,D,B,E,C=27 C,A,D,E,B,C=25 C,A,E,B,D,C=28 C,A,E,D,B,C=29 C,B,A,D,E,C=27 C,B,A,E,D,C=28 C,B,D,A,E,C=21 C,B,E,A,D,C=18 C,D,A,B,E,C=26 C,D,B,A,E,C=30	D,A,B,C,E,D=27 D,A,B,E,C,D=27 D,A,C,B,E,D=25 D,A,C,E,B,D=27 D,A,E,C,B,D=21 D,A,E,B,C,D=18 D,B,A,C,E,D=37 D,B,A,E,C,D=30 D,B,C,A,B,D=25 D,B,E,A,C,D=28 D,C,A,B,E,D=34 D,C,B,A,E,D=28	E,A,B,C,D,E=28 E,A,B,D,C,E=30 E,A,C,B,D,E=29 E,A,C,D,B,E=28 E,A,D,B,C,E=21 E,B,A,C,D,E=34 E,B,A,D,C,E=26 E,B,C,A,D,E=25 E,B,D,A,C,E=27 E,C,A,B,D,E=37 E,C,A,D,B,E=27 E,C,B,A,D,E=27

Después de utilizar el método de fuerza Bruta para hacer los recorridos por los 5 lugares pudimos identificar los caminos óptimos que el niño puede tomar para cumplir el objetivo de ir a los 5 lugares recorriendo el camino con menos calles.

Como se había dicho anteriormente el problema se puede resolver con el algoritmo ACO por sus siglas en inglés Ant Colony Optimization (Optimización Colonia de Hormigas)

Este algoritmo relativamente reciente (1992) por su creador Marco Dorigo es un ejemplo metahurístico. La metahurística involucra conceptos de genética, biología, inteligencia artificial, matemáticas entre otras. 

Se basa en la metáfora natural del comportamiento de hormigas para encontrar los caminos más cortos entre las fuentes de comida y el hormiguero. También se puede decir que sigue a la inteligencia de enjambre ya que se basa en la conducta de auto organización como lo es ACO, el alineamiento de aves de vuelo, rebaños y cardúmenes.

Enseguida se muestra un diagrama de flujo del proceso que sigue ACO.

Es importante explicar las fórmulas relevantes en ACO; actualización de feromona y evaporación de feromona.  A continuación una explicación sencilla y breve de estas fórmulas.

SELECCIÓN DE CAMINO

La Actualización de Feromona se da cuando se deposita la feromona y luego se evapora, así para cada hormiga

UN POCO DE LO QUE ENCONTRARÁS...

En esta entrada del blog se divide en secciones.

Marco Teórico donde se muestra información general sobre ACO para entender y tener una mejor idea del algoritmo además de datos sobre su origen y relación con el comportamiento de Hormigas.

En la sección de Desarrollo se mostrará el funcionamiento a partir de las fórmulas, empezando por explicar cómo funciona el algoritmo relacionado con el problema del viajero para después presentar la codificación de ACO  mostrando su comportamiento.

Se mostrarán además, en esta sección, los parámetros que utilizamos por ejemplo, la cantidad de hormigas, la tasa de evaporación, el valor inicial de la feromona , etc.

Para aclarar puntos sobre el problema del viajero se han creado dos instancias, una de pocas ciudades y otra de 10 ciudades para mostrar el representar del problema del viajero de forma gráfica y por medio de un generador de instancias.

Finalmente se mostrarán los resultados y las conclusiones de la práctica. 

DESARROLLO

El problema del viajero (TSP; Traveling Salesman Problem) como se explicó anteriormente, consta de un viajante  que tiene un número de destinos los cuales debe visitar, puede partir de cualquier punto con la condición de regresar al mismo. Los demás destinos solo pueden ser visitados una vez por recorrido. El objetivo es recorrer los lugares cuidando que la ruta sea la de menor costo. La relación que tiene con el algoritmo ACO se enfoca en que ambos tienen distintas posibilidades de llegar a su objetivo pero tienen que determinar el de menor costo para convertirlo en la ruta óptima.

Algoritmo
Inicialización del algoritmo.

void Dibujar_instancia(int Distancias,double Costos)
{
    system("cls");
    srand(time(NULL));

    //Distancias
    cout<<"\nDISTANCIAS:\n";
    for(i=0;i&alt;Nodos;i++)
    {
        for(j=i;j<(Nodos);j++)
        {
             if(j==i)
             {
                   Distancias[i][j]=0;
             }else
             {
                   num=1+rand()%(21-1);
                   Distancias[i][j]=num;
                   Distancias[j][i]=num;
             }  
        }
        for(j=0;j<Nodos;j++)
        {
             cout<<setw(4)<<Distancias[i][j];
        }
        cout<<"\n";
    }
    
    //Costos
    cout<<"\n\nCOSTOS\n";
    for(i=0;i<Nodos;i++)
    {
         for(j=0;j<Nodos;j++)
         {
              if(i==j)
              {
                   Costos[i][j]=0;
              }else
              {
              Costos[i][j]=(1/(float)Distancias[i][j]);
              }
              cout<<"  "<<setw(6)<<setprecision(3)<<Costos[i][j];
         }
         cout<<"\n";
    }
    
    //Feromonas
    cout<<"\n\nFEROMONAS:\n";
    for(i=0;i<Nodos;i++)
    {
         for(j=i;j<Nodos;j++)
         {
              if(j==i)
             {
                   Feromonas[i][j]=0;
             }else
             {
                   num=1+rand()%(100-1);
                   numf=(float)num/100;
                   Feromonas[i][j]=numf;
                   Feromonas[j][i]=numf;
             }   
         }
          for(j=0;j<Nodos;j++)
          {
             cout<<" "<<setw(5)<<setprecision(5)<<Feromonas[i][j];
          }  
         cout<<"\n";
    }
    return;
}

void Elegir_CiudadInicio(int Recorridas[Nodos])
{
     desde=0;hacia=0;
     toper=0;
     r=0;
     desde=(0+rand()%(Nodos-1));
     Recorridas[r][0]=desde;
     toper=r;
     return;
}

int main()
{
    cout<<"Numero de nodos: ";
    cin>>Nodos;
    int Distancias[Nodos][Nodos];
    float Feromonas[Nodos][Nodos];
    double Costos[Nodos][Nodos];
    int Recorridas[Nodos][Nodos], Proximas[Nodos][Nodos];
    Dibujar_instancia(Distancias,Costos); 
    for(I=1;I<=5;I++)//5 veces
    {
         Elegir_CiudadInicio(Recorridas);
         for(H=1;H<=3;H++)//para cada hormiga
         {
              Seleccion_deCamino(Feromonas,Costos,Proximas,Recorridas);
              Moverse();
              Sumar_Costo();            
         }
         DepositarFeromonas(Feromonas);
         ImprimirMejorCamino();
    }
    ImprimirResultados();
    system("PAUSE");
}

Selección de la siguiente Arista

void Seleccion_deCamino(float Feromonas[Nodos][Nodos], double Costos[Nodos][Nodos],int Recorridas[Nodos],int Proximas[Nodos])
{
     while(toper<=Nodos)
     {
         int si_esta;
         Proximas={0};
         
         i=0;
         for(q=0;q<Nodos;q++)
         {
              si_esta=0;
              if(Recorridas[toper]=q)
              {
                   si_esta=1;
              }else
              {
                   for(l=0;l<=toper;l++)
                   {
                        if(q=Recorridas[l])
                        {
                             si_esta=1;
                        }
                   }
              }
              if(si_esta=0)
              {
                   Proximas[i]=q;
                   topep=i;
                   i++;
                  
              }
         }
         
         //Probabilidades y cachos
         double arriba,abajo;
         for(i=0;i<=topep;i++)
         {
              arriba=0;
              abajo=0;
              
              arriba=(pow((Feromonas[(Recorridas[toper])][(Proximas[i])]),1)*pow((Costos[(Recorridas[toper])][(Proximas[i])]),1));
              for(l=0;l<=topep;l++)//sumatoria de abajo ;)
              {
                   abajo=abajo+((Feromonas[(Recorridas[toper])][(Proximas[l])])*(Costos[(Recorridas[toper])][(Proximas[l])]));
              }
              Probabilidad[i]=(arriba/abajo);                               
         }
         
         i=0;l=0;
         while(i<=100)
         { 
              for(ii=0;ii<=(Probabilidad[l]*100);ii++)
              {
                   Ruleta[i]=Proximas[l];
                   i++;
              }
              l++;   
         }
         num=0+rand()%(99-0);
         //agregar a cds recorridas
         hacia=Ruleta[num];          
         
         Recorridas[toper][1]=hacia;
         toper++;
         desde=hacia;
         Recorridas[toper][0]=desde;
     }
     return;
}
 

Actualización de la feromona

void DepositarFeromonas(float Feromonas[Nodos][Nodos])
{
     float nuevafer,sumatoriaLK;
     
     for(i=0;i<toper;i++)
     {
          sumatoriaLK+=Feromonas[(Recorridas[i])][(Recorridas[1])]
     }
     sumatoriaLK+=(1/Nodos);
 
     for(i=0;i<Nodos;i++)
    {
         for(j=i;j<Nodos;j++)
         {
              if(j==i)
             {
                   Feromonas[i][j]=0;
             }else
             {
                   nuevafer=((1-0.5)*Feromonas[i][j])+ssumatoriaLK;
                   Feromonas[i][j]=nuevafer;
                   Feromonas[j][i]=nuevafer;
             }   
         }
    }
    return;
}

INSTANCIA 1

El siguiente código es el que nos proporciona valores aleatorios ordenados en una matriz para las instancias del problema del viajero.

El rango de valores que nos puede imprimir este código es de 0 a 99.

En seguida se muestra 2 ejecutables del código anterior  en el que podremos observar que los valores de la diagonal principal son ceros ya que la distancia de un punto hacia ese mismo punto es cero.

En este caso generamos una matriz de 6x6.  Instancia 1.

Así nos quedaría la matriz de la corrida anterior (instancia1).

Este mapa de destinos corresponde a la instancia 1 

Decidimos aumentar un poco la dificultad para que se aprecie mejor cómo funciona el generador de instancias.

INSTANCIA 2

Ahora generamos una matriz de 10x10.

A partir del ejecutable anterior (instancia 2) podremos acomodar los datos en una matriz que nos quedaría así

Este mapa de destinos corresponde a la instancia 2

CONCLUSIÓN

En conclusión de ACO…

El algoritmo ACO aunque de principio parecía fácil, ya que el concepto que utiliza es muy sencillo de entender, al programarlo no resulto de esa forma, incluso nos causó muchas confusiones, mismas que se fueron solucionando al ir desenvolviendo el problema y dividiéndolo parte por parte. Por lo que este algoritmo a pesar de tener muchos pasos a seguir, puede ser programado y reutilizado para más problemas no solo con el problema del viajero.

Pero también entendemos que es mucho mejor opción utilizar este algoritmos para resolver el problema del viajero, a resolverlo por fuerza bruta, ya que con instancias muy grandes podríamos tardar realmente demasiado tiempo en resolver.