Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

ACO

ACO (“Ant Colony Optimization”) es una metaheurística bioinspirada para resolver problemas de optimización.
by

Pamela Ayala

on 20 June 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ACO

Tabla de Valores
Se utilizan ciertos valores que están probados para dar buenos resultados:

α=1 β=2 a 5 p=0.5 m=n

Según la instancia varían los valores.
Cada hormiga mantiene una memoria Μ la cual contiene las ciudades visitadas en el orden correspondiente.
a) Definir vecindario factible
b) Permite calcular distancia del tour τ

Actualización de los caminos de feromonas

Se va bajando el valor de feromonas en todos los arcos no escogidos por una constante y se va añadiendo feromonas en las rutas que las hormigas utilizaron.

Evaporación

0<p<1 p previene la acumulación de feromonas, permitiendo olvidar malas decisiones

Depósito de feromonas
Los arcos más usados y tours más cortos reciben más feromona, por lo tanto son más probables de ser escogidos.

es la cantidad de feromona.






C =largo del tour Τ

Ants System
Comenzamos definiendo τ como el deseo de visitar la ciudad j después de la i.
Tour de construcción
1. Se ponen aleatoriamente m hormigas en los nodos.
2. La hormiga k aplica la regla probabilística de elección (“random proportional rule”)
3. La probabilidad de que la hormiga k en ciudad i visite la ciudad j.



Ant Colony Optimization
Pamela Ayala Nagore 141947
Paola Duez Berra 141752
Alejandra Quintos Lima 141425
Índice
Introducción a ACO
Algoritmo ACO para PAV (Ants System)
Algoritmo ACO para CVPR
Ventajas y Desventajas
Bibliografía
Introducción
Ruteo de vehículos
Bibliografía
PAV
Ventajas y Desventajas
Alonso, S., Cordón, O., Fernández de Viana, I., & Herrera, F. (s.f.). La Metaheurística de Optimización Basada en Colonias de Hormigas: Modelos o Nuevos Enfoques. Obtenido de http://sci2s.ugr.es/publications/ficheros/OCH%20Modelos%20y%20Nuevos%20Enfoques%20(Chapter).pdf
Barcos, L., Rodríguez, V., & Álvarez, M. (s.f.). Algoritmo basado en la optimización mediante colonias de hormigas para la resolución del problema de transporte de carga de varios orígenes a varios destinos. Obtenido de http://www-cenit.upc.es/robuste/papers/colonia%20hormigas.pdf
Bonabeau, E. (s.f.). Inspiration for optimization from social insect behaviour. Obtenido de http://cognition.ups-tlse.fr/_guyt/documents/articles/35.pdf
C. Ponce, J., Padilla, F., Padilla, A., & A. Meza, M. (s.f.). ACHPM: Algoritmo de Optimización con Colonia de Hormigas para el Problema de la Mochila. Obtenido de http://www.iiisci.org/journal/CV$/risci/pdfs/C821AF.pdf
Di Caro , G. (s.f.). The Ant Colony Optimization (ACO) Metaheuristic: a Swarm Intelligence Framework for Complex Optimization Tasks. Obtenido de http://www.idsia.ch/~gianni/Lectures/BertinoroLectureACO.pdf
Dorgio, M., & Stutzle, T. (2004). Ant Colony Optimization. London: MIT Press.
Dorigo , M., & Stutzle, T. (s.f.). The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances.
Dorigo, M. (1996). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. Obtenido de http://www.idsia.ch/~luca/acs-ec97.pdf
Dorigo, M. (2007). Ant Colony Optimization. Obtenido de http://www.scholarpedia.org/article/Ant_colony_optimization
Dorigo, M., & Di Caro, G. (s.f.). The Ant Colony Optimization Meta-Heuristic. Obtenido de ftp://ftp.itam.mx/pub/alfredo/ROBOTICS/Swarm/dorigo99ant.pdf
Dorigo, M., & Socha, K. (s.f.). An Introduction to Ant Colony Optimization. Obtenido de http://iridia.ulb.ac.be/IridiaTrSeries/rev/IridiaTr2006-010r003.pdf
Dorigo, M., Gambardella, L., & Birattari, M. (September de 2006). Ant Colony Optimization and Swarm Intelligence: 5th International Workshop. Obtenido de http://books.google.com.mx/books?hl=en&lr=&id=uxpbGzztM0EC&oi=fnd&pg=PA1&dq=ant+colony+optimization&ots=sv7o70cJA-&sig=4WiCEyrcXJVz854ul2zW4Mb7A8Q#v=onepage&q=ant%20colony%20optimization&f=false
Gambardella, L., & Dorigo, M. (s.f.). Ant colonies for the traveling salesman problem. Obtenido de http://www.idsia.ch/~luca/acs-bio97.pdf
Tan, W.F., L.S. Lee, Z.A. Majid, H.V. Seow (2012). Ant Colony Optimization for Capacitated Vehicle Routing Problem. Journal of Computer Science 8
Wong, E., Summers, P., Ku, R., & Xie, P. (2011). Ant Colony Optimization. Obtenido de http://www.math.ucla.edu/~wittman/10c.1.11s/Lectures/Raids/ACO.pdf


ACO (“Ant Colony Optimization”) es una metaheurística bioinspirada para resolver problemas de optimización.
Se ponen diversas hormigas que se comunican a base de feromonas para encontrar una buena solución.
Una hormiga artificial en ACO son procedimientos estocásticos constructivos que poco a poco crean una solución añadiendo componentes de solución a una solución parcial en construcción.
Pseudocódigo del “Algoritmo de hormigas”
Capturar Parámetros
Inicializar los rastros de feromonas
Colocar hormigas en posición inicial
Repetir
Para
K desde 1
Hasta
el número de hormigas
Hacer
Construir la solución para la hormiga K
Seleccionar la mejor solución
Actualizar los rastros de feromonas
Hasta
Alcanzar el número de ciclos

GRACIAS!
El análisis teórico es difícil.
Secuencias de decisiones aleatorias (dependiente).
La distribución de la probabilidad cambia por iteración.
La investigación es mas experimental que teórica.
El tiempo de convergencia es incierto (pero la convergencia es garantizada).
Retroalimentaciones positivas por descubrir rápidamente las buenas soluciones.
Eficiente para el Problema del Agente Viajero y problemas similares.
Puede ser usado en aplicaciones dinámicas (adaptarse a cambios como nuevas distancias etc.)
Vecindario factible de hormigas k estando en la ciudad i (ciudades que k no ha visitado)
Heurísticas
Una vez que una hormiga (k) termina de construir una solución (pero antes que las demás hormigas diseñen la suya), la solución de dicha hormiga se mejora aplicando una heurística. Para el trabajo se decidió emplear la heurística de “mejora de tours” (2-opt).

Evaporación de feromonas
La concentración de feromonas se ve reducida en todos los arcos por el siguiente factor:


donde
θ=constante fija

0≤p<1


L =Longitud de la solución de la hormiga k
Entre más largo sea el arco, se evaporan más feromonas.

CVRP=Capacitated Vehicle Routing Problem
Las principales tareas dentro del algoritmo son: construcción de la solución, empleo de técnicas heurísticas y los rastros de feromona.
Depósito de Feromonas
construcción de la solución
Cada hormiga construye una solución sin violar las restricciones propias del problema .

Cuando la elección del siguiente cliente lleva a una solución no factible, se inicia una nueva ruta que parte desde el depósito.
Sólo las mejores y las hormigas elitistas podrán depositar feromona.




Donde:











Los valores más usuales:
m = n -> hormigas artificiales (n es el número de nodos (ciudades)
α=2, β=5; γ=9
ρ=0.8, θ=30
Tamaño de la lista de candidatos: n/3 entero
σ=3 hormigas elitistas
donde L es la longitud de una solución inicial (factible).

El único valor que se actualiza durante la ejecución del algoritmo es el asociado a las feromonas.
Actualización de la feromona
Los rastros de feromona son actualizados a través de mecanismos de evaporación y depósito de feromonas.
Para el problema de CVRP, se propone una estrategia elitista.
i
Parámetros que determinan la influencia relativa de caminos de feromonas e información heurística.
Valor heurístico dado a-priori
α,β
k
k
k
k
ij ij
ij
ij i0 0j ij
k
Una hormiga k situada en la ciudad i seleccionará a la ciudad j (situada en un vecindario factible) por medio de la siguiente distribución de probabilidad:



Donde:
η =1/d es el valor heurístico asociado
τ denota la concentración de feromonas en el arco que conecta i con j
μ =d +d -d los ahorros

Full transcript