ACO - Parte 1

PRACTICA 1: ACO

Parte 1

ACO son las siglas de Ant Colony Optimization en español: Optimizacion Colonia de Hormigas, se le llama así porque simula el comportamiento de las hormigas en sus colonias  que cuando buscan comida (su objetivo) van dejando feromonas por los caminos por donde pasan y cuando tienen que elegir entre dos caminos eligen el que tenga un mayor rastro de feromonas, eso significa que ese camino es un mejor camino que el que contiene menos feromonas y con el paso del tiempo las hormigas crearan el mejor camino para su objetivo.

ACO es una técnica que utiliza la probabilidad para resolver problemas donde su solución sea el mejor camino o ruta en un grafo.

Practica:

• Generar instancias para el problema del viajero (programa) 

Instancia 1. Transporte Escolar

En una escuela primaria se cuenta con el servicio de transporte escolar para recoger a los niños inscritos en la lista del servicio a sus casas correspondientes.

El conductor del autobús tiene que recoger a los 5 niños a sus casas, sin importar el orden, pero el objetivo es que haga el recorrido más corto para evitar desperdiciar gasolina.

Instancia 2. Biblioteca

Una estudiante necesita sacar cinco libros de la biblioteca (matemáticas, español, historia, geografía, química) estos están localizados en diferentes corredores alrededor del lugar, pero lo tiene que hacer en el menor tiempo posible, por lo que necesita encontrar la ruta más rápida para evitar cargar tanto tiempo los libros. Los datos se encuentran organizados en la matriz y son los metros que tiene que caminar para llegar a cada libro.

GENERADOR DE INSTANCIAS

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
int main()
{ system("color 3B"); 
 int i,j,n=10;
 int arre[10][10],h[10][10],num=5;
 srand(time(NULL));

for (i=0;i<num;i++)
     {
     for (j=0;j<num;j++)
     {
  if(i<j) 
  {
   arre[i][j]=rand()%n;
   h[i][j]=arre[i][j];
  }  
    if(i==j)
  {
   arre[i][j]=0;
   h[i][j]=arre[i][j];
  }
  if(i>j)
     {
   h[i][j]=arre[j][i];
  }  
        printf ("\t%d ",h[i][j]);                
     }
     printf ("\n");
     }
}

A partir de esta ejecución llenamos la matriz de la instancia 1

A partir de esta ejecución llenamos la matriz de la instancia 2

• Resolver una 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.

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.

• Generar diagrama de flujo para ACO