Ant Colony Optimization

Ant Colony Optimization

Marco Dorigo - Thomas Stutzle

Preface: Ants exhibit complex social behaviors that have long since attracted the attention of human beings. Probably one of the most noticeable behaviors visible to us is the for- mation of so-called ant streets. When we were young, several of us may have stepped 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- come less urgent for most of us as we grow older and go to university, studying other subjects like computer science, mathematics, and so on. However, there are a con- siderable number of researchers, mainly biologists, who study the behavior of ants in 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, these and similar ideas have attracted a steadily increasing amount of research—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- niques based on ant behaviors. Their success is evidenced by the extensive array of dif- ferent problems to which they have been applied, and moreover by the fact that ACO algorithms are for many problems among the currently top-performing algorithms.

Overview of the Book 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 wide range of combinatorial optimization problems, and describes many of the avail- 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 working optimization algorithms. In chapter 2, the ACO metaheuristic is introduced and put into the general context of combinatorial optimization. Basic notions of complexity theory, such as - hardness, are given and other major metaheuristics are briefly overviewed.

Chapter 3 is dedicated to the in-depth description of all the major ACO algorithms currently available in the literature. This description, which is developed using the traveling salesman problem as a running example, is completed by a guide to imple- menting the algorithms. A short description of a basic C implementation, as well as pointers to the public software available at www.aco-metaheuristic.org/aco-code/, is given.

Chapter 4 reports on what is currently known about the theory of ACO algorithms.

In particular, we prove convergence for a specific class of ACO algorithms and we discuss the formal relation between ACO and other methods such as stochastic gra- dient descent, mutual-information-maximizing input clustering, and cross-entropy.

Chapter 5 is a survey of current work exploiting ACO to solve a variety of combi- natorial optimization problems. We cover applications to routing, assignment, sched- uling, and subset problems, as well as a number of other problems in such diverse fields as machine learning and bioinformatics. We also give a few ‘‘application prin- ciples,’’ that is, criteria to be followed when attacking a new problem using ACO.

Chapter 6 is devoted to the detailed presentation of AntNet, an ACO algorithm especially designed for the network routing problem, that is, the problem of building andmaintaining routing tables in a packet-switched telecommunication network.

Finally, chapter 7 summarizes the main achievements of the field and outlines some interesting directions for future research.

Each chapter of the book (with the exception of the last chapter) ends with the following three sections: bibliographical remarks, things to remember, and exercises.

- Bibliographical remarks, a kind of short annotated bibliography, contains pointers to further literature on the topics discussed in the chapter.

- Things to remember is a bulleted list of the important points discussed in the chapter.

- Exercises come in two forms, thought exercises and computer exercises, depending on the material presented in the chapter.

Finally, there is a long list of references about ACO algorithms that gives a lot of pointers to more in-depth literature.

Overall, this book can be read easily by anyone with a college-level scientific back- ground. The use of mathematics is rather limited throughout, except for chapter 4, which requires some deeper knowledge of probability theory. However, we assume that the reader is familiar with some basic notions of graph theory, programming, and probabilities. The book is intended primarily for (1) academic and industry researchers in operations research, artificial intelligence, and computational intelli- gence; (2) practitioners willing to learn how to implement ACO algorithms to solve combinatorial optimization problems; and (3) graduate and last-year undergraduate students in computer science, management science, operations research, and artificial intelligence.

Content

1 From Real to Artificial Ants 1

1.1 Ants’ Foraging Behavior and Optimization 1

1.2 Toward Artificial Ants 7

1.3 Artificial Ants and Minimum Cost Paths 9

1.4 Bibliographical Remarks 21

1.5 Things to Remember 22

1.6 Thought and Computer Exercises 23

2The Ant Colony Optimization Metaheuristic 25

2.1 Combinatorial Optimization 25

2.2 The ACO Metaheuristic 33

2.3 How Do I Apply ACO? 38

2.4 Other Metaheuristics 46

2.5 Bibliographical Remarks 60

2.6 Things to Remember 61

2.7 Thought and Computer Exercises 63

3Ant Colony Optimization Algorithms for the Traveling 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 Experimental Evaluation 84

3.7 ACO Plus Local Search 92

3.8 Implementing ACO Algorithms 99

3.9 Bibliographical Remarks 114

3.10 Things to Remember 117

3.11 Computer Exercises 117

4Ant Colony Optimization Theory 121

4.1 Theoretical Considerations on ACO 121

4.2 The Problem and the Algorithm 123

4.3 Convergence Proofs 127

4.4 ACO and Model-Based Search 138

4.5 Bibliographical Remarks 149

4.6 Things to Remember 150

4.7 Thought and Computer Exercises 151

5Ant Colony Optimization for -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 -Hard Problems 190

5.6 Machine Learning Problems 204

5.7 Application Principles of ACO 211

5.8 Bibliographical Remarks 219

5.9 Things to Remember 220

5.10 Computer Exercises 221

6AntNet: An ACO Algorithm for 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 AntNet and Stigmergy 252

6.6 AntNet, Monte Carlo Simulation, and Reinforcement Learning 254

6.7 Bibliographical Remarks 257

6.8 Things to Remember 258

6.9 Computer Exercises 259

7Conclusions and Prospects for the Future 261

7.1 What Do We Know about ACO? 261

7.2 Current Trends in ACO 263

7.3 Ant Algorithms 271

Appendix: Sources of Information about the ACO Field 275

References 277

Index 301