viernes, 20 de septiembre de 2013

Practica #1 ACO

Publicado por Pamela Olivares en 19:36 Etiquetas: , , , , 0 comentarios

Introducción

El problema del viajero (TSP) consiste en una especie de grafo o mapa la cual tiene diferentes  vértices, los cuales tenemos que recorrer pasando por cada uno de ellos, con el menor costo posible. El problema del viajero es importante ya que con el podemos ver los diferentes posibilidades de resolver un problema y darnos cuenta que hay maneras mas eficientes para llegar a la "meta", algunas aplicaciones que podría tener seria en las búsquedas de información encontrar el camino mas corto para llegar a la información deseada, para los mapas digitales que permiten encontrar la ruta mas rápida de llegar a cierto punto, entre otros mas.
El problema del viajero puede resultar tedioso ya que si hay muchos vértices hay muchos mas caminos que recorrer y soluciones, esto hace que el problema se vuelva mas largo.
El algoritmo de ACO es un algoritmo un tanto complejo, que permite encontrar la mejor ruta para llegar a la meta, el problema de  ACO es una colonia de hormigas  en la cual una hormiga va buscando el mejor camino y a la vez deja una feromona para que las demás hormigas sigan su camino.
ACO puede utilizarse para resolver el problema del viajero por que al igual que las hormigas van recorriendo los caminos para encontrar una solución optima.
En esta entrada vas a poder encontrar:
  • Marco Teórico contiene una explicación de el problema del viajero y de ACO. Así mismo se incluye un ejemplo de fuerza bruta.
  • Desarrollo contiene la información mas relevante de como se elaboro el algoritmo en el se incluyen códigos y capturas de pantalla.
  • Resultados
  • Conclusiones
  • Referencias 

Marco Teórico

El problema del viajero (TSP) es  un un tipo de problema de complejidad NP-completo. El problema del viajero consiste en recorrer todas las ciudades pasando una vez por cada una de ellas y volver donde inicio el recorrido, en el menor costo y tiempo posible.
Usa una estructura de datos de vecindad y heuristicas simples, también se utilizan métodos de búsqueda local. Se realiza una instancia.
La instancia de este problema consiste en dar un grafo donde cada vértice es una ciudad y las aristas son los caminos los cuales tienen cierto peso (que es el costo) el numero de vértices varia según el caso, en el caso de programación se utiliza una matriz la cual contiene números que representan los costos del recorrido.
Este problema se puede resolver por fuerza bruta pero no es muy recomendable, ya que se tiene una instancia se sacan todas las posibles soluciones del problema sumando los costos de cada camino y el resultado mas pequeño es el camino mas corto.

Aquí dejamos un ejemplo:

Instrucciones: Resolver el ejercicio por fuerza bruta. 
Reglas: Pasar por las 4 ciudades (A,B,C,D) solo una vez y volver a la ciudad de inicio, con el menor costo posible.


Respuestas:

Estas son todas las posibles soluciones:
A,B,C,D 4+2+5=11
A,B,D,C 4+6+5=15
A,C,D,B 1+5+6=12 
A,C,B,D 1+2+6=9
A,D,C,B 2+5+2=9
A,D,B,C 3+6+2=11

B,A,C,D 4+1+5=10
B,A,D,C 4+3+5=12
B,D,C,A 6+5+1=12
B,D,A,C 6+2+1=8
B,C,A,D 2+1+3=6
B,C,D,A 3+5+3=11

C,A,B,D 1+4+6=11
C,A,D,B 1+3+6=10
C,B,D,A 2+6+3=11
C,B,A,D 2+4+3=9
C,D,A,B 5+3+4=12
C,D,B,A 5+6+4=15

D,A,B,C 3+4+2=9
D,A,C,B 3+1+2=6
D,B,A,C 6+4+1=11
D,B,C,A 6+2+1=9
D,C,A,B 5+1+4=10
D,C,B,A 5+2+4=11

 Como se puede observar hay dos caminos cortos con un costo de 6.

ACO significa Ant Colony Optimization que en español significa optimización de colonia de hormigas. ACO se basa en el compartimiento de las hormigas para resolver problemas de optimización y búsqueda  Es también metahuristico ya que se utiliza para buscar soluciones.
ACO fue propuesto en 1991 por Dorigo Etal



El proceso que sigue ACO es el siguiente:

pseudocódigo
  1. Inicio 
  2. Inicio de parámetros
  3. if (condición del Fin)
  4. Búsqueda de soluciones
  5. búsqueda local
  6. actualización de una feromona
  7. else (fin)

Las formulas mas importantes para resolver este algoritmo son las siguientes:



  • Proceso de decisión (selección de arista)

donde:
pi,a es la probabilidad de escoger la rama a estando en el 
punto de decisión i, y

„τi,a es la concentración de feromona en la rama a

  • Actualización de la feromona




\tau_{xy} \leftarrow (1-\rho)\tau_{xy} + \sum_{k}\Delta \tau^{k}_{xy}


Txy = es la cantidad de feromonas depositadas para un estado de transición xy
p= es el coeficiente de evaporación de las feromonas.

Desarrollo


La manera en que resolvimos el problema del viajero fue la siguiente:
Creamos una instancia del problema por medio de una matriz donde los datos (números) de la matriz son los "costos" de los caminos segun sea el caso.

Se crea una condición principal la cual determina el final del programa y del ciclo. En esta condición las hormigas buscan el mejor camino (el mas optimo) para su recorrido.

Se hace una búsqueda de las diversas soluciones, en ella las hormigas buscan todos los caminos posibles de una forma probabilista tomando con mayor probabilidad el camino que mas feromonas tenga.

 Se realiza una búsqueda local de soluciones, en esta las hormigas buscan el mejor camino que este mas cerca en los cuales se encuentre una mayor cantidad de feromona, indicando que por ahí pasaron mas hormigas recientemente.

 Por ultimo se actualizaran los parámetros  en este paso las hormigas se impregnan mas de feromona o se evapora ya que no utilizan el camino.

 A continuación se muestran algunos fragmentos de código de algunas de las funciones de ACO
  •  Genera instancias



  • Actualización de feromona

  •  Selección de aristas 


A continuación generaremos dos instancias una para 4 ciudades y otra 10 ciudades.







Parámetros de ACO

 En esta parte realizamos varias iteraciones y reportaremos algunos datos relevantes.

Numero de Hormigas
Tasa de evaporación
Cantidad de feromona depositada (Q)
Influencia de la feromona( ɑ)
Influencia del nodo( β)
Instancia 1 (4 ciudades)
 4
.01
2.00
3
2
Instancia 2 (10 ciudades)
4
.01
2.00
3
2





Resultados


 Como se puede observar en la siguiente iteración el numero de ciudades es 4, se utilizaron 4 hormigas y el camino mas corto fue de 13.
 En esta segunda iteración se realizo con 10 ciudades y 4 hormigas, el camino mas corto fue de 20

Conclusión:

Aunque el algoritmo se nos hizo algo tedioso, mas que nada por el lenguaje y al dificultad de las formulas, es un algoritmo muy útil y practico para encontrar soluciones optimas.

REFERENCIAS

Tarapacá, U. d. (2013). Aplicación de un algoritmo ACO al problema de taller de flujo de permutación con tiempos de preparación dependientes de la secuencia y minimización de makespan. Obtenido de Ingeniare. Revista chilena de Ingenieria: http://www.scielo.cl/scielo.php?pid=S0718-33052011000200010&script=sci_arttext
Cordon, O. (s.f.). Sistemas complejos, algoritmos evolutivos y bioinspirados. Obtenido de http://sci2s.ugr.es/seminars/5/Curso%20Baeza%20Oscar.pdf


Diaz, J. C. (s.f.). Una hiperheurística para la solución del Problema del Viajante Asimétrico . Obtenido de Monografias: http://www.monografias.com/trabajos35/viajante-asimetrico/viajante-asimetrico.shtml
Mora, A. (28 de noviembre de 2011). Optimizacion basada en colonias de hormigas. Obtenido de SildesHare: http://www.slideshare.net/Slidemora/optimizacin-basada-en-colonias-de-hormigas
Wikipedia. (20 de junio de 2013). Algoritmo colonia de hormigas. Obtenido de Wikipedia: http://es.wikipedia.org/wiki/Algoritmo_colonia_de_hormigas
Wikipedia. (4 de abril de 2013). Problema del viajante. Obtenido de Wikipedia: http://es.wikipedia.org/wiki/Problema_del_viajante





lunes, 2 de septiembre de 2013

Practica #1: ACO (avance)

Publicado por Pamela Olivares en 19:13 0 comentarios

Practica #1
Parte 1

a) Generar instancias para el problema del viajero (programa)  


 

(b) Resolver una instancia por fuerza bruta 

  • Introduccion

  En este ejercicio se resolverá una instancia del problema del viajero.

Resolverlo por fuerza bruta consiste en probar una a una todas o la mayor parte de las posibles respuestas y al final compararlas para ver cuál es la más adecuada tomando en cuenta todas las restricciones que el problema nos plantea.

El método de fuerza bruta no es el más indicado ya que suele tomar mucho tiempo, el tiempo que tardes en resolverlo depende de la cantidad de posibles respuestas que contenga el problema.

  • Instrucciones:


En este ejemplo tomaremos el problema del viajero para resolverlo por el método ya mencionado. El problema del viajero consiste en encontrar el camino más corto (barato) que pase por todas las ciudades del mapa una vez y que termine en la ciudad donde comenzaste.


  • Respuestas:


Para intentar llegar a la respuesta se analizaron los siguientes caminos posibles.

A,B,C,D 4+2+5=11
A,B,D,C 4+6+5=15
A,C,D,B 1+5+6=12 
A,C,B,D 1+2+6=9
A,D,C,B 2+5+2=9
A,D,B,C 3+6+2=11

B,A,C,D 4+1+5=10
B,A,D,C 4+3+5=12
B,D,C,A 6+5+1=12
B,D,A,C 6+2+1=8
B,C,A,D 2+1+3=6
B,C,D,A 3+5+3=11

C,A,B,D 1+4+6=11
C,A,D,B 1+3+6=10
C,B,D,A 2+6+3=11
C,B,A,D 2+4+3=9
C,D,A,B 5+3+4=12
C,D,B,A 5+6+4=15

D,A,B,C 3+4+2=9
D,A,C,B 3+1+2=6
D,B,A,C 6+4+1=11
D,B,C,A 6+2+1=9
D,C,A,B 5+1+4=10
D,C,B,A 5+2+4=11

Hay dos posibles respuestas, aún hay más caminos posibles pero se descartaron ya que a simple vista son más largos (caros).

Este método es más tardado y complejo según el tamaño de la instancia, y te deja mucho marguen de error.

(c) Generar pseudocódigo o diagrama de flujo para ACO 

  • Diagrama de flujo

 

  • Pseudocodigo

  1. Inicio 
  2. Inicio de parámetros
  3. if (condición del Fin)
  4. Búsqueda de soluciones
  5. búsqueda local
  6. actualización de una feromona
  7. else (fin)
Suscribirse a: Entradas (Atom)