Ant colony optimization is a metaheuristic which has been successfully applied to a wide range of combinatorial optimization problems. The author describes this metaheuristic and studies its efficiency for solving some hard combinatorial problems, with a specific focus on constraint programming. The text is organized into three parts. The first part introduces constraint programming, which provides high level features to declaratively model problems by means of constraints. It describes the main existing approaches for solving constraint satisfaction problems, including complete tree search approaches and metaheuristics, and shows how they can be integrated within constraint programming languages.
The second part describes the ant colony optimization metaheuristic and illustrates its capabilities on different constraint satisfaction problems.
The third part shows how the ant colony may be integrated within a constraint programming language, thus combining the expressive power of constraint programming languages, to describe problems in a declarative way, and the solving power of ant colony optimization to efficiently solve these problems.
Table of Contents:
Foreword xi
Acknowledgements xiii
Chapter 1. Introduction 1
1.1. Overview of the book 2
Chapter 2. Computational Complexity 7
2.1. Complexity of an algorithm 8
2.2. Complexity of a problem 10
2.3. Where the most difficult instances can be found 15
2.4. Solving NP-hard problems in practice 21
PART I. CONSTRAINT PROGRAMMING 27
Introduction to Part I 29
Chapter 3. Constraint Satisfaction Problems 31
3.1. What is a constraint? 31
3.2. What is a constraint satisfaction problem? 33
3.3. Optimization problems related to CSPs 35
3.4. The n-queens problem 37
3.5. The stable marriage problem 43
3.6. Randomly generated binary CSPs 46
3.7. The car sequencing problem 47
3.8. Discussion 50
Chapter 4. Exact Approaches 53
4.1. Construction of a search tree 53
4.2. Constraint propagation 57
4.3. Ordering heuristics 60
4.4. From satisfaction to optimization problems 63
4.5. Discussion 65
Chapter 5. Perturbative Heuristic Approaches 69
5.1. Genetic algorithms 70
5.2. Local search 73
5.3. Particle swarm optimization 78
5.4. Discussion 80
Chapter 6. Constructive Heuristic Approaches 85
6.1. Greedy randomized approaches 86
6.2. Estimation of distribution algorithms 88
6.3. Ant colony optimization 90
6.4. Discussion 91
Chapter 7. Constraint Programming Languages 93
7.1. Constraint logic programming 94
7.2. Constraint programming libraries 96
7.3. Constraint-based local search 96
7.4. Discussion 99
PART II. ANT COLONY OPTIMIZATION 101
Introduction to Part II 103
Chapter 8. From Swarm Intelligence to Ant Colony Optimization 105
8.1. Complex systems and swarm intelligence 106
8.2. Searching for shortest paths by ant colonies 108
8.3. Ant system and the traveling salesman problem 111
8.4. Generic ACO framework 116
Chapter 9. Intensification versus Diversification 125
9.1. ACO mechanisms for intensifying the search 125
9.2. ACO mechanisms for diversifying the search 127
9.3. Balancing intensification and diversification 128
9.4. Measures of diversification/intensification 135
Chapter 10. Beyond Static Combinatorial Problems 141
10.1. Multi-objective problems 141
10.2. Dynamic optimization problems 145
10.3. Optimization problems over continuous domains 147
Chapter 11. Implementation Issues 151
11.1. Data structures 151
11.2. Selection of a component with respect to probabilities 154
11.3. Implementation of a local search procedure 157
11.4. Computation of diversification/intensification measures 157
PART III. CP WITH ACO 161
Introduction to Part III 163
Chapter 12. Sequencing Cars with ACO 165
12.1. Notation 165
12.2. A first pheromone structure for identifying good car sequences 166
12.3. A second pheromone structure for identifying critical cars 171
12.4. Combining the two pheromone structures 173
12.5. Comparison of the different ACO algorithms 174
12.6. Comparison of ACO with state-of-the-art approaches 178
12.7. Discussion 182
Chapter 13. Subset Selection with ACO 185
13.1. Subset selection problems 186
13.2. Description of Ant-SSP 189
13.3. Instantiations of Ant-SSP with respect to two pheromone strategies 192
13.4. Instantiation of Ant-SSP to solve CSPs 196
13.5. Experimental results 197
13.6. Discussion 202
Chapter 14. Integration of ACO in a CP Language 205
14.1. Framework for integrating ACO within a CP library 206
14.2. Illustration of ACO-CP on the car sequencing problem 210
14.3. Discussion 214
Chapter 15. Conclusion 215
15.1. Towards constraint-based ACO search 215
15.2. Towards a reactive ACO search 216
Bibliography 219
Index 231
