The Ant Colony Optimization Metaheuristic
The MIT Press eBooksPublished 4 June 2004
Citations1,418
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
This chapter contains sections titled: Combinatorial Optimization, The ACO Metaheuristic, How Do I Apply ACO?, Other Metaheuristics, Bibliographical Remarks, Things to Remember, Thought and Computer Exercises
Keywords
Computer ScienceEngineering
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Ant system: optimization by a colony of cooperating agents
11,908 Citations1996Marco Dorigo, Vittorio Maniezzo +1 more
IEEE Transactions on Evolutionary ComputationAnt colony system: a cooperative learning approach to the traveling salesman problem
7,994 Citations1997Marco Dorigo, Luca Maria Gambardella
The results show that the ACS outperforms other nature-inspired algorithms such as simulated annealing and evolutionary computation, and it is concluded comparing ACS-3-opt, a version of the ACS augmented with a local search procedure, to some of the best performing algorithms for symmetric and asymmetric TSPs.
Oxford University Press eBooksSwarm Intelligence
6,415 Citations1999Eric Bonabeau, Marco Dorigo +1 more
This chapter discusses Ant Foraging Behavior, Combinatorial Optimization, and Routing in Communications Networks, and its application to Data Analysis and Graph Partitioning.
INFORMS Journal on ComputingTabu Search—Part II
5,643 Citations1990Fred Glover
The elements of staged search and structured move sets are characterized, which bear on the issue of finiteness, and new dynamic strategies for managing tabu lists are introduced, allowing fuller exploitation of underlying evaluation functions.
Artificial LifeAnt Algorithms for Discrete Optimization
2,819 Citations1999Marco Dorigo, Gianni A. Di +1 more
An overview of recent work on ant algorithms, that is, algorithms for discrete optimization that took inspiration from the observation of ant colonies' foraging behavior, and the ant colony optimization (ACO) metaheuristic is presented.
Distributed Optimization by Ant Colonies
2,580 Citations1992Alberto Colorni, Marco Dorigo +3 more
A distributed problem solving environment is introduced and its use to search for a solution to the travelling salesman problem is proposed.
BiosystemsAnt colonies for the travelling salesman problem
1,991 Citations1997Marco Dorigo, Luca Maria Gambardella
An artificial ant colony capable of solving the travelling salesman problem (TSP) is described, an example of the successful use of a natural metaphor to design an optimization algorithm.
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
Scientific AmericanThe Connection Machine
1,614 Citations1987W. Daniel Hillis
The Connection Machine describes a fundamentally different kind of computer that Daniel Hillis and others are now developing to perform tasks that no conventional, sequential machine can solve in a reasonable time.
Journal of Artificial Intelligence ResearchAntNet: Distributed Stigmergetic Control for Communications Networks
1,582 Citations1998Gianni A. Di, Marco Dorigo
AntNet is a distributed, mobile agents based Monte Carlo system that was inspired by recent work on the ant colony metaphor for solving optimization problems, and showed superior performance under all the experimental conditions with respect to its competitors.
Journal of Insect BehaviorThe self-organizing exploratory pattern of the argentine ant
918 Citations1990J. L. Deneubourg, Serge Aron +2 more
A minimal model shows how the exploratory pattern may be generated by the individual workers' simple trail-laying and -following behavior, illustrating how complex collective structures in insect colonies may be based on self-organization.
NatureInspiration for optimization from social insect behaviour
906 Citations2000Eric Bonabeau, Marco Dorigo +1 more
Research in social insect behaviour has provided computer scientists with powerful methods for designing distributed control and optimization algorithms that tend to exhibit a high degree of flexibility and robustness in a dynamic environment.
MAX-MIN Ant System and local search for the traveling salesman problem
825 Citations2002Thomas Stützle, Holger H. Hoos
The results clearly show that MAX-MIN Ant System has the property of effectively guiding the local search heuristics towards promising regions of the search space by generating good initial tours.
ePubWU Institutional Repository (Wirtschaftsuniversität Wien)A new rank based version of the Ant System. A computational study.
802 Citations1997B. Bullnheimer, Richard F. Hartl +1 more
It turns out that the new rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior.
IEEE Transactions on Knowledge and Data EngineeringThe ant system applied to the quadratic assignment problem
745 Citations1999Vittorio Maniezzo, A. Colorni
A distributed heuristic algorithm that was inspired by the observation of the behavior of ant colonies is described and its use for the quadratic assignment problem is proposed.
Adaptive BehaviorAnt-Based Load Balancing in Telecommunications Networks
744 Citations1997Ruud Schoonderwoerd, Owen Holland +2 more
A novel method of achieving load balancing in telecommunications networks using ant-based control, which is shown to result in fewer call failures than the other methods, while exhibiting many attractive features of distributed control.
Elsevier eBooksAnt-Q: A Reinforcement Learning approach to the traveling salesman problem
601 Citations1995Luca Maria Gambardella, Marco Dorigo
Ant-Q algorithms were inspired by work on the ant system (AS), a distributed algorithm for combinatorial optimization based on the metaphor of ant colonies and are applied to the solution of symmetric and asymmetric instances of the traveling salesman problem.
Solving symmetric and asymmetric TSPs by ant colonies
502 Citations2002Luca Maria Gambardella, Marco Dorigo
ACS is presented, a distributed algorithm for the solution of combinatorial optimization problems which was inspired by the observation of real colonies of ants and is able to find good solutions to these problems.
Journal of the Operational Research SocietyAnts can colour graphs
501 Citations1997Davide Costa, Alain Hertz
An evolutionary search procedure for tackling assignment type problems that repeatedly constructs feasible solutions of the problem under study by taking account of two complementary notions, namely the trace factor and the desirability factor is presented.
Applying the ANT System to the Vehicle Routing Problem
412 Citations1999B. Bullnheimer, Richard F. Hartl +1 more
A recently proposed metaheuristic, the Ant System, is used to solve the Vehicle Routing Problem in its basic form, i.e., with capacity and distance restrictions, one central depot and identical vehicles.
Operations Research LettersA new adaptive multi-start technique for combinatorial global optimizations
351 Citations1994Kenneth D. Boese, Andrew B. Kahng +1 more
This work motivates a new adaptive multi-start paradigm for heuristic global optimization, wherein starting points for greedy descent are adaptively derived from the best previously found local minima.
INFORMS journal on computingExact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem
340 Citations1999Vittorio Maniezzo
Two new techniques for solving the Quadratic Assignment Problem are introduced, one of which is a heuristic technique, defined in accordance with the Ant System metaphor, and includes as a distinctive feature the use of a new lower bound at each constructive step.
AntNet: A Mobile Agents Approach to Adaptive Routing
286 Citations1999Gianni A. Di
AntNet is an adaptive, distributed, mobile-agents-based algorithm which was inspired by recent work on the ant colony metaphor which is applied to a datagram network and compared with both static and adaptive state-of-the-art routing algorithms.
Oxford University Press eBooksFrom Natural to Artificial Swarm Intelligence
281 Citations1999Eric Bonabeau, Marco Dorigo +1 more
Ant-like agents for load balancing in telecommunications networks
274 Citations1997Ruud Schoonderwoerd, Owen Holland +1 more
A novel method of achieving load balancing in telecommunications networks using an ant-based system, shown to drop fewer calls than the other methods, while exhibiting many attractive features of distributed control.
Artificial Neural Nets and Genetic AlgorithmsImprovements on the Ant-System: Introducing the MAX-MIN Ant System
259 Citations1998Thomas Stützle, Holger H. Hoos
This paper describes in detail the improvements on Ant system, discusses the addition of local search to MMAS, and reports on the computational results, showing that the system also improves over other variations of Ant system.
Journal of Insect BehaviorModulation of trail laying in the antLasius niger (Hymenoptera: Formicidae) and its role in the collective selection of a food source
258 Citations1993R Beckers, Jean‐Louis Deneubourg +1 more
Simulations of this model showed that the observed modulation of trail laying with respect to food source quality is sufficient in itself to account for the systematic selection of the richer source seen in the experiments.
Ants and reinforcement learning: a case study in routing in dynamic networks
228 Citations1997Devika Subramanian, Peter Druschel +1 more
Two new distributed routing algorithms for data networks based on simple biological "ants" that explore the network and rapidly learn good routes, using a novel variation of reinforcement learning are investigated, and they scale well with increase in network size-using a realistic topology.
Lecture notes in computer scienceAnt Colony Optimization for the Total Weighted Tardiness Problem
221 Citations2000Matthijs den Besten, Thomas Stützle +1 more
An application of the Ant Colony Optimization (ACO) metaheuristic to the single machine total weighted tardiness problem is presented obtaining a novel ACO algorithm that uses a heterogeneous colony of ants and is highly effective in finding the best-known solutions on all instances of a widely used set of benchmark problems.
Lecture notes in computer scienceParallelization strategies for Ant Colony Optimization
175 Citations1998Thomas Stützle
The empirical tests are performed applying MAX-MIN Ant System, one of the most efficient ACO algorithms, to the Traveling Salesman Problem and show that using parallel independent runs is very effective.
Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles)Local Search Algorithms for Combinatorial Problems - Analysis, Improvements and New Applications
166 Citations1999Thomas Stützle
Lecture notes in computer scienceAnt colonies for adaptive routing in packet-switched communications networks
164 Citations1998Gianni A. Di, Marco Dorigo
Comp compelling evidence is presented that AntNet, when measuring performance by standard measures such as network throughput and average packet delay, outperforms the current Internet routing algorithm (OSPF), some old Internet routing algorithms (SPF and distributed adaptive Bellman-Ford), and recently proposed forms of asynchronous online BellMan-Ford (Q-routing and Predictive Q- routing).
Applied optimizationParallelization Strategies for the Ant System
150 Citations1998B. Bullnheimer, Gabriele Kotsis +1 more
Two parallelization strategies for an Ant System implementation are developed and evaluated: the synchronous parallel algorithm and the partially asynchronous parallel algorithm.
Two Ant Colony Algorithms for Best-Effort Routing in Datagram Networks
138 Citations1998Gianni A. Di, Marco Dorigo
Two versions of AntNet, a novel approach to adaptive learning of routing tables in wide area best-effort datagram networks, are presented, showing superior performance with respect to the current Internet routing algorithm (OSPF), some improved old Internet routing algorithms, and recently proposed forms of asynchronous online Bellman-Ford.
An ant colony optimization approach for the single machine total tardiness problem
131 Citations2003Andreas Bauer, B. Bullnheimer +2 more
This work considers a machine scheduling problem with one machine, the Single Machine Total Tardiness Problem, and applies the ant colony optimization metaphor, a recently developed meta-heuristic that has proven its potential for various other combinatorial optimization problems.
Lecture notes in computer scienceAn island model based ant system with lookahead for the shortest supersequence problem
123 Citations1998René Michel, Martin Middendorf
An Ant Colony Optimisation (ACO) algorithm for the Shortest Common Supersequence (SCS) problem, which has applications in production system planning, mechanical engineering and molecular biology is introduced.
The Max-Min ANT System and Local Search for Combinatorial Optimization Problems
121 Citations1999Thomas Stützle, Holger H. Hoos
The computational results show that this algorithm can be used to efficiently find near-optimal solutions to hard combinatorial optimization problems and that it is one of the best methods for the solution of structured quadratic assignment problems.
Advances in Complex SystemsAdaptive Agent-Driven Routing and Load Balancing in Communication Networks
114 Citations1998Martin Heusse, Dominique Snyers +2 more
This paper presents an unified overview of a new family of distributed algortithms for routing and load balancing in dynamic communication networks that combine the ideas of online asynchronous distance vector routing with adaptive link state routing.
RePEc: Research Papers in EconomicsRouting in Telecommunications Networks with ``Smart'' Ant-Like Agents
103 Citations1998Eric Bonabeau, Florian Hénaux +4 more
HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem
102 Citations1997Luca Maria Gambardella, Marco Dorigo
Experimental results on a set of twenty-three test problems taken from the TSPLIB show that HAS-SOP outperforms existing methods both in terms of solution quality and computation time.
TUbilio (Technical University of Darmstadt)Improvements on Ant-System: Introducing MAX-MIN Ant System
52 Citations1996Thomas Stützle, Holger H. Hoos
INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGYTraveling Salesman Problem: A Case Study
45 Citations2012Leena Jain, Mr. Amit Bhanot
This linear problem solved by open source software is presented for solving traveling salesman problem and assignment based integer linear formulation presented.
Behavior of the Ant Colony Algorithm for the Set Covering Problem
26 Citations2000Dmitry Alexandrov, Yury Kochetov
The Ant Colony approach for the classical Set Covering problem is developed, using three randomized greedy heuristics: GRASP heuristic and two asymptotically exact heuristic Random Neighborhood and Random Covering Set.