Ant Colony Optimization and Constraint Programming

Klappentext 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. Zusammenfassung 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. Inhaltsverzeichnis 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 Chap...

List 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

About the author

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.

Summary

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.

Report

"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)

Product details

• Authors: Solnon, C Solnon, Christine Solnon
• Assisted by: Narendra Jussien (Editor)
• Publisher: Wiley, John and Sons Ltd
• Languages: English
• Product format: Hardback
• Released: 07.01.2010
• EAN: 9781848211308
• ISBN: 978-1-84821-130-8
• No. of pages: 320
• Series: ISTE; ISTE
• Subjects: Natural sciences, medicine, IT, technology > IT, data processing > IT; Informatik, computer science, Programmierung u. Software-Entwicklung, Programming & Software Development, Programmierung (EDV)