Ant Colony Optimization and Constraint Programming

Christine Solnon is Associate Professor at the University of Lyon 1 and a member of the LIRIS laboratory. She is Vice- President of the AFPC; the French association for constraint programming.

• Foreword xiAcknowledgements xiiiChapter 1. Introduction 11.1. Overview of the book 2Chapter 2. Computational Complexity 72.1. Complexity of an algorithm 82.2. Complexity of a problem 102.3. Where the most difficult instances can be found 152.4. Solving NP-hard problems in practice 21PART I. CONSTRAINT PROGRAMMING 27Introduction to Part I 29Chapter 3. Constraint Satisfaction Problems 313.1. What is a constraint? 313.2. What is a constraint satisfaction problem? 333.3. Optimization problems related to CSPs 353.4. The n-queens problem 373.5. The stable marriage problem 433.6. Randomly generated binary CSPs 463.7. The car sequencing problem 473.8. Discussion 50Chapter 4. Exact Approaches 534.1. Construction of a search tree 534.2. Constraint propagation 574.3. Ordering heuristics 604.4. From satisfaction to optimization problems 634.5. Discussion 65Chapter 5. Perturbative Heuristic Approaches 695.1. Genetic algorithms 705.2. Local search 735.3. Particle swarm optimization 785.4. Discussion 80Chapter 6. Constructive Heuristic Approaches 856.1. Greedy randomized approaches 866.2. Estimation of distribution algorithms 886.3. Ant colony optimization 906.4. Discussion 91Chapter 7. Constraint Programming Languages 937.1. Constraint logic programming 947.2. Constraint programming libraries 967.3. Constraint-based local search 967.4. Discussion 99PART II. ANT COLONY OPTIMIZATION 101Introduction to Part II 103Chapter 8. From Swarm Intelligence to Ant Colony Optimization 1058.1. Complex systems and swarm intelligence 1068.2. Searching for shortest paths by ant colonies 1088.3. Ant system and the traveling salesman problem 1118.4. Generic ACO framework 116Chapter 9. Intensification versus Diversification 1259.1. ACO mechanisms for intensifying the search 1259.2. ACO mechanisms for diversifying the search 1279.3. Balancing intensification and diversification 1289.4. Measures of diversification/intensification 135Chapter 10. Beyond Static Combinatorial Problems 14110.1. Multi-objective problems 14110.2. Dynamic optimization problems 14510.3. Optimization problems over continuous domains 147Chapter 11. Implementation Issues 15111.1. Data structures 15111.2. Selection of a component with respect to probabilities 15411.3. Implementation of a local search procedure 15711.4. Computation of diversification/intensification measures 157PART III. CP WITH ACO 161Introduction to Part III 163Chapter 12. Sequencing Cars with ACO 16512.1. Notation 16512.2. A first pheromone structure for identifying good car sequences 16612.3. A second pheromone structure for identifying critical cars 17112.4. Combining the two pheromone structures 17312.5. Comparison of the different ACO algorithms 17412.6. Comparison of ACO with state-of-the-art approaches 17812.7. Discussion 182Chapter 13. Subset Selection with ACO 18513.1. Subset selection problems 18613.2. Description of Ant-SSP 18913.3. Instantiations of Ant-SSP with respect to two pheromone strategies 19213.4. Instantiation of Ant-SSP to solve CSPs 19613.5. Experimental results 19713.6. Discussion 202Chapter 14. Integration of ACO in a CP Language 20514.1. Framework for integrating ACO within a CP library 20614.2. Illustration of ACO-CP on the car sequencing problem 21014.3. Discussion 214Chapter 15. Conclusion 21515.1. Towards constraint-based ACO search 21515.2. Towards a reactive ACO search 216Bibliography 219Index 231

"In this volume, Solnon (U. of Lyon, France) introduces ant colony optimization and its application to a range of combinatorial problems, with a focus on constraint programming." (Book News, September 2010)