Ant Colony.qxd 6/9/04 12:15 PM Page 1 Ant Colony Optimization Marco Dorigo and Thomas Stützle A n t C The complex social behaviors of ants have been much studied by science, and computer scientists are now finding that o these behavior patterns can provide models for solving difficult combinatorial optimization problems. The attempt to lo develop algorithms inspired by one aspect of ant behavior, the ability to find what computer scientists would call shortest n Ant Colony y paths, has become the field of ant colony optimization (ACO), the most successful and widely recognized algorithmic O p technique based on ant behavior. This book presents an overview of this rapidly growing field, from its theoretical inception t i Optimization to practical applications, including descriptions of many available ACO algorithms and their uses. m The book first describes the translation of observed ant behavior into working optimization algorithms. The ant iz a colony metaheuristic is then introduced and viewed in the general context of combinatorial optimization. This is followed t i by a detailed description and guide to all major ACO algorithms and a report on current theoretical findings. The book o n surveys ACO applications now in use, including routing, assignment, scheduling, subset, machine learning, and bioin- formaticsproblems. AntNet, an ACO algorithm designed for the network routing problem, is described in detail. The Marco Dorigo and Thomas Stützle authors conclude by summarizing the progress in the field and outlining future research directions. Each chapter ends with bibliographic material, bullet points setting out important ideas covered in the chapter, and exercises. Ant Colony Optimizationwill be of interest to academic and industry researchers, graduate students, and practitioners who wish to learn how to implement ACO algorithms. Marco Dorigo is research director of the IRIDIA lab at the Université Libre de Bruxelles and the inventor of the ant colony optimization metaheuristic for combinatorial optimization problems. He has received the Marie Curie Excellence Award for his research work on ant colony optimization and ant algorithms. He is the coauthor of Robot Shaping(MIT Press, 1998) and Swarm Intelligence. Thomas Stützle is Assistant Professor in the Computer Science Department at D o Darmstadt University of Technology. r i g o A Bradford Book a n d “Marco Dorigo and Thomas Stützle impressively demonstrate that the importance of ant behavior reaches far beyond the S t sociobiological domain. Ant Colony Optimizationpresents the most successful algorithmic techniques to be developed ü t on the basis of ant behavior. This book will certainly open the gates for new experimental work on decision making, z l e division of labor, and communication; moreover, it will also inspire all those studying patterns of self-organization.” Bert Hölldobler, Professor of Behavioral Physiology and Sociobiology, Biozentrum, University of Würzburg, Germany “Inspired by the remarkable ability of social insects to solve problems, Dorigo and Stützle introduce highly creative new technological design principles for seeking optimized solutions to extremely difficult real-world problems, such as network routing and task scheduling. This is essential reading not only for those working in artificial intelligence and optimization, but for all of us who find the interface between biology and technology fascinating.” Iain D. Couzin, Princeton University and University of Oxford The MIT Press Massachusetts Institute of Technology Cambridge, Massachusetts 02142 http://mitpress.mit.edu 0-262-04219-3 ,!7IA2G2-aecbjc!:t;K;k;K;k Ant Colony Optimization Ant Colony Optimization Marco Dorigo Thomas Stu¨tzle A Bradford Book The MIT Press Cambridge, Massachusetts London, England 62004MassachusettsInstituteofTechnology Allrightsreserved.Nopartofthisbookmaybereproducedinanyformbyanyelectronicormechanical means(includingphotocopying,recording,orinformationstorageandretrieval)withoutpermissionin writingfromthepublisher. ThisbookwassetinTimesNewRomanon3B2byAscoTypesetters,HongKong.Printedandboundin theUnitedStatesofAmerica. LibraryofCongressCataloging-in-PublicationData Dorigo,Marco. Antcolonyoptimization/MarcoDorigo,ThomasStu¨tzle. p. cm. ‘‘ABradfordbook.’’ Includesbibliographicalreferences(p.). ISBN0-262-04219-3(alk.paper) 1.Mathematicaloptimization. 2.Ants–Behavior–Mathematicalmodels. I.Stu¨tzle,Thomas. II.Title. QA402.5.D64 2004 519.6—dc22 2003066629 10 9 8 7 6 5 4 3 2 1 To Serena and Roberto To Maria Jose´ and Alexander Contents Preface ix Acknowledgments xiii 1 From Real to Artificial Ants 1 1.1 Ants’ Foraging Behaviorand Optimization 1 1.2 Toward Artificial Ants 7 1.3 Artificial Ants and Minimum Cost Paths 9 1.4 BibliographicalRemarks 21 1.5 Thingsto Remember 22 1.6 Thoughtand Computer Exercises 23 2 The Ant ColonyOptimization Metaheuristic 25 2.1 Combinatorial Optimization 25 2.2 The ACOMetaheuristic 33 2.3 How Do I Apply ACO? 38 2.4 Other Metaheuristics 46 2.5 BibliographicalRemarks 60 2.6 Thingsto Remember 61 2.7 Thoughtand Computer Exercises 63 3 Ant ColonyOptimization Algorithms for theTraveling Salesman Problem 65 3.1 The Traveling Salesman Problem 65 3.2 ACO Algorithms for the TSP 67 3.3 Ant System and Its Direct Successors 69 3.4 Extensions of Ant System 76 3.5 Parallel Implementations 82 3.6 ExperimentalEvaluation 84 3.7 ACO Plus Local Search 92 3.8 Implementing ACO Algorithms 99 3.9 BibliographicalRemarks 114 3.10 Thingsto Remember 117 3.11 Computer Exercises 117 4 Ant ColonyOptimization Theory 121 4.1 Theoretical Considerationson ACO 121 4.2 The Problem and theAlgorithm 123 4.3 ConvergenceProofs 127 viii Contents 4.4 ACO and Model-Based Search 138 4.5 BibliographicalRemarks 149 4.6 Things to Remember 150 4.7 ThoughtandComputerExercises 151 5 Ant ColonyOptimization forNP-Hard Problems 153 5.1 Routing Problems 153 5.2 Assignment Problems 159 5.3 Scheduling Problems 167 5.4 Subset Problems 181 5.5 Application of ACO to Other NP-Hard Problems 190 5.6 Machine Learning Problems 204 5.7 Application Principles of ACO 211 5.8 BibliographicalRemarks 219 5.9 Things to Remember 220 5.10 ComputerExercises 221 6 AntNet: An ACO Algorithmfor Data Network Routing 223 6.1 The Routing Problem 223 6.2 The AntNet Algorithm 228 6.3 The Experimental Settings 238 6.4 Results 243 6.5 AntNetand Stigmergy 252 6.6 AntNet, Monte Carlo Simulation, and ReinforcementLearning 254 6.7 BibliographicalRemarks 257 6.8 Things to Remember 258 6.9 ComputerExercises 259 7 Conclusions and Prospects for theFuture 261 7.1 WhatDo We Knowabout ACO? 261 7.2 Current Trends in ACO 263 7.3 Ant Algorithms 271 Appendix: Sources ofInformationabout the ACO Field 275 References 277 Index 301 Preface Ants exhibit complex social behaviors that have long since attracted the attention of humanbeings.Probablyoneofthemostnoticeablebehaviorsvisibletousisthefor- mationofso-calledantstreets.Whenwewereyoung,severalofusmayhavestepped on such an ant highway or may have placed some obstacle in its way just to see how the ants would react to such disturbances. We may have also wondered where these ant highways lead to or even how they are formed. This type of question may be- comelessurgentformostofusaswegrowolderandgotouniversity,studyingother subjects like computer science, mathematics, and so on. However, there are a con- siderablenumberofresearchers,mainlybiologists,whostudythebehaviorofantsin detail. One of the most surprising behavioral patterns exhibited by ants is the ability of certain ant species to find what computer scientists call shortest paths. Biologists have shown experimentally that this is possible by exploiting communication based only on pheromones, an odorous chemical substance that ants may deposit and smell. It is this behavioral pattern that inspired computer scientists to develop algo- rithms for the solution of optimization problems. The first attempts in this direction appeared in the early ’90s and can be considered as rather ‘‘toy’’ demonstrations, though important for indicating the general validity of the approach. Since then, theseand similar ideashaveattracted asteadilyincreasingamountofresearch—and ant colony optimization (ACO) is one outcome of these research e¤orts. In fact, ACO algorithms are the most successful and widely recognized algorithmic tech- niquesbasedonantbehaviors.Theirsuccessisevidencedbytheextensivearrayofdif- ferentproblemstowhichtheyhavebeenapplied,andmoreoverbythefactthatACO algorithms are for many problemsamong the currently top-performing algorithms. Overview of theBook This book introduces the rapidly growing field of ant colony optimization. It gives a broad overview of many aspects of ACO, ranging from a detailed description of the ideas underlying ACO, to the definition of how ACO can generally be applied to a widerangeofcombinatorialoptimizationproblems,anddescribesmanyoftheavail- able ACO algorithms and their main applications. The book is divided into seven chapters and is organized as follows. Chapter 1 explains how ants find shortest paths under controlled experimental conditions, and illustrates how the observation of this behavior has been translated into workingoptimization algorithms.