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