Abstract: Research on a new meta-heuristic for optimization is often initially focused on proof-of-concept applications [1]. In the early 1990s, ant colony optimization (ACO) [2] was introduced by M. Dorigo and colleagues as a novel nature-inspired meta-heuristic for the solution of hard combinatorial optimization (CO) problems. According to Papadimitriou and Steiglitz [3], a CO problem P = (S, f) is an optimization problem in which, given a finite set of solutions S (also called search space) and an objective function f : S → R that assigns a positive cost value to each of the solutions, the goal is either to find a solution of minimum cost value, or — as in the case of approximate solution techniques — a good enough solution in a reasonable amount of time. The ACO algorithms belong to the class of meta-heuristics and therefore follow the latter goal. The central component of an ACO algorithm is a parameterized probabilistic model, which is called the pheromone model. The pheromone model consists of a vector of model parameters T called pheromone trail parameters. The pheromone trail parameters Ti ∈ T , which are usually associated to components of solutions, have values τi , called pheromone values [1]. The ACO approach attempts to solve an optimization problem by repeating the following two steps: • Candidate solutions are constructed using a pheromone model, that is, a parameterized probability distribution over the solution space; • The candidate solutions are used to modify the pheromone values in a way that is deemed to bias future sampling toward high quality solutions.
Publication Year: 2008
Publication Date: 2008-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 30
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot