Vidal's library
Title: The Ant System: Optimization by a colony of cooperating agents
Author: Marco Dorigo, Vittorio Maniezzo, and Alberto Colorni
Journal: IEEE Transactions on Systems, Man and Cybernetics, Part B
Volume: 26
Number: 1
Pages: 29--41
Year: 1996
DOI: 10.1109/3477.484436
Abstract: An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach to stochastic combinatorial optimization. The main characteristics of this model are positive feedback, distributed computation, and the use of a constructive greedy heuristic. Positive feedback accounts for rapid discovery of good solutions, distributed computation avoids premature convergence, and the greedy heuristic helps find acceptable solutions in the early stages of the search process. We apply the proposed methodology to the classical traveling salesman problem (TSP), and report simulation results. We also discuss parameter selection and the early setups of the model, and compare it with tabu search and simulated annealing using TSP. To demonstrate the robustness of the approach, we show how the ant system (AS) can be applied to other optimization problems like the asymmetric traveling salesman, the quadratic assignment and the job-shop scheduling. Finally we discuss the salient characteristics-global data structure revision, distributed communication and probabilistic transitions of the AS

Cited by 1101  -  Google Scholar

@Article{dorigo96a,
  author =	 {Marco Dorigo and Vittorio Maniezzo and Alberto
                  Colorni},
  title =	 {The Ant System: Optimization by a colony of
                  cooperating agents},
  journal =	 {{IEEE} Transactions on Systems, Man and Cybernetics,
                  Part B},
  year =	 1996,
  volume =	 26,
  number =	 1,
  pages =	 {29--41},
  abstract =	 {An analogy with the way ant colonies function has
                  suggested the definition of a new computational
                  paradigm, which we call ant system (AS). We propose
                  it as a viable new approach to stochastic
                  combinatorial optimization. The main characteristics
                  of this model are positive feedback, distributed
                  computation, and the use of a constructive greedy
                  heuristic. Positive feedback accounts for rapid
                  discovery of good solutions, distributed computation
                  avoids premature convergence, and the greedy
                  heuristic helps find acceptable solutions in the
                  early stages of the search process. We apply the
                  proposed methodology to the classical traveling
                  salesman problem (TSP), and report simulation
                  results. We also discuss parameter selection and the
                  early setups of the model, and compare it with tabu
                  search and simulated annealing using TSP. To
                  demonstrate the robustness of the approach, we show
                  how the ant system (AS) can be applied to other
                  optimization problems like the asymmetric traveling
                  salesman, the quadratic assignment and the job-shop
                  scheduling. Finally we discuss the salient
                  characteristics-global data structure revision,
                  distributed communication and probabilistic
                  transitions of the AS},
  url = 	 {http://jmvidal.cse.sc.edu/library/dorigo96a.pdf},
  doi = 	 {10.1109/3477.484436},
  cluster = 	 {17282795599717616620}
}
Last modified: Wed Mar 9 10:14:06 EST 2011