ACS: Ant Colony System Optimization

by Luca Maria Gambardella and Marco Dorigo

Ant Colony Optimization: ants inspired systems for combinatorial optimization


The ant colony optimization metaheuristic (ACO, Dorigo, Di Caro and Gambardella 1999) is a population-based approach to the solution of combinatorial optimization problems. The basic ACO idea is that a large number of simple artificial agents are able to build good solutions to hard combinatorial optimization problems via low-level based communications. Real ants cooperate in their search for food by depositing chemical traces (pheromones) on the floor. An artificial ant colony simulates this behavior. Artificial ants cooperate by using a common memory that corresponds to the pheromone deposited by real ants. The artificial pheromone is accumulated at run-time through a learning mechanism. Artificial ants are implemented as parallel processes whose role is to build problem solutions using a constructive procedure driven by a combination of artificial pheromone, problem data and a heuristic function used to evaluate successive constructive steps). Although this is an interesting and promising result, it remains clear that ant colony optimization (ACO), as well as other metaheuristics, in many cases cannot compete with specialized local search methods. A current trend is therefore to associate with the metaheuristic a local optimizer, giving birth to so-called hybrid methods.
Recently, we have proposed many ant based algorithms to solve different types of combinatorial optimization problems such as symmetric and asymmetric traveling salesman problems (Ant-Q Gambardella and Dorigo 95, ACS Gambardella and Dorigo 96/97) the sequential ordering problem (HAS-SOP Gambardella and Dorigo 1997, HAS-SOP2000 Gambardella and Dorigo 2000 ) the quadratic assignment problem (HAS-QAP Gambardella Taillard and Dorigo 1999) and the vehicles routing problem (MACS-VRPTW Gambardella Taillard and Agazzi 1999)

References
(here is a selected publications list, see also other papers on the same subject and the ACO web page )

ACO: Ant Colony Optimization

  • Dorigo M., G. Di Caro and L. M. Gambardella. Ant Algorithms for Discrete Optimization. Artificial Life, 5,2, pp. 137-172, 1999.
  • Maniezzo V, Gambardella L.M., De Luigi F. Ant Colony Optimization, New Optimization Techniques in Engineering, by Onwubolu, G. C., and B. V. Babu, Springer-Verlag Berlin Heidelberg, 101-117, 2004.

    Ant-Q and ACS for the Traveling Salesman Problems (symmetric and asymmetric)

  • Gambardella L.M, Dorigo M., Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem, Twelfth International Conference on Machine Learning, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, 1995, pp. 252-260.
  • Gambardella L.M, Dorigo M., Solving Symmetric and Asymmetric TSPs by Ant Colonies, ICEC96, Proceedings of the IEEE Conference on Evolutionary Computation, Nagoya, Japan, May 20-22, 1996
  • Dorigo M., Gambardella L.M, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem , IEEE Transactions on Evolutionary Computation Vol. 1,No. 1,pp. 53-66, 1997

    HAS-QAP: Quadratic Assignment Problem

  • Gambardella L.M, Taillard E., Dorigo M., Ant colonies for the Quadratic Assignment Problem , Journal of the Operational Research Society, 50, pp.167-176, 1999

    HAS-SOP: Sequential Ordering Problem

  • Gambardella L.M,,Dorigo M., HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem , Technical Report IDSIA,11,1997, HAS-SOP Page
  • Gambardella L.M, Dorigo M., An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem, INFORMS Journal on Computing, vol.12(3), pp. 237-255, 2000

    MACS-VRPTW: Vehicle Routing Problem with Time Windows

  • Gambardella L.M, Taillard E., Agazzi G., MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows , In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization. McGraw-Hill, UK, pp. 63-76, 1999 (Also available as Technical Report IDSIA-06-99 , IDSIA, Lugano, Switzerland)
    MACS-VRPTW Page