Ant Colony Optimization and Constraint Programming

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