Ant Colony Optimization and Constraint Programming E-Book

Christine Solnon

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 317

Veröffentlichungsjahr: 2013

Beschreibung

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.

Leseprobe

Table of Contents

Foreword

Acknowledgements

Chapter 1. Introduction

1.1. Overview of the book

Chapter 2. Computational Complexity

2.1. Complexity of an algorithm

2.2. Complexity of a problem

2.3. Where the most difficult instances can be found

2.4. Solving -hard problems in practice

PART I. CONSTRAINT PROGRAMMING

Introduction to Part I

Chapter 3. Constraint Satisfaction Problems

3.1. What is a constraint?

3.2. What is a constraint satisfaction problem?

3.3. Optimization problems related to CSPs

3.4. The n-queens problem

3.5. The stable marriage problem

3.6. Randomly generated binary CSPs

3.7. The car sequencing problem

3.8. Discussion

Chapter 4. Exact Approaches

4.1. Construction of a search tree

4.2. Constraint propagation

4.3. Ordering heuristics

4.4. From satisfaction to optimization problems

4.5. Discussion

Chapter 5. Perturbative Heuristic Approaches

5.1. Genetic algorithms

5.2. Local search

5.3. Particle swarm optimization

5.4. Discussion

Chapter 6. Constructive Heuristic Approaches

6.1. Greedy randomized approaches

6.2. Estimation of distribution algorithms

6.3. Ant colony optimization

6.4. Discussion

Chapter 7. Constraint Programming Languages

7.1. Constraint logic programming

7.2. Constraint programming libraries

7.3. Constraint-based local search

7.4. Discussion

PART II. ANT COLONY OPTIMIZATION

Introduction to Part II

Chapter 8. From Swarm Intelligence to Ant Colony Optimization

8.1. Complex systems and swarm intelligence

8.2. Searching for shortest paths by ant colonies

8.3. Ant system and the traveling salesman problem

8.4. Generic ACO framework

Chapter 9. Intensification versus Diversification

9.1. ACO mechanisms for intensifying the search

9.2. ACO mechanisms for diversifying the search

9.3. Balancing intensification and diversification

9.4. Measures of diversification/intensification

Chapter 10. Beyond Static Combinatorial Problems

10.1. Multi-objective problems

10.2. Dynamic optimization problems

10.3. Optimization problems over continuous domains

Chapter 11. Implementation Issues

11.1. Data structures

11.2. Selection of a component with respect to probabilities

11.3. Implementation of a local search procedure

11.4. Computation of diversification/intensification measures

PART III. CP WITH ACO

Introduction to Part III

Chapter 12. Sequencing Cars with ACO

12.1. Notation

12.2. A first pheromone structure for identifying good car sequences

12.3. A second pheromone structure for identifying critical cars

12.4. Combining the two pheromone structures

12.5. Comparison of the different ACO algorithms

12.6. Comparison of ACO with state-of-the-art approaches

12.7. Discussion

Chapter 13. Subset Selection with ACO

13.1. Subset selection problems

13.2. Description of Ant-SSP

13.3. Instantiations of Ant-SSP with respect to two pheromone strategies

13.4. Instantiation of Ant-SSP to solve CSPs

13.5. Experimental results

13.6. Discussion

Chapter 14. Integration of ACO in a CP Language

14.1. Framework for integrating ACO within a CP library

14.2. Illustration of ACO-CP on the car sequencing problem

14.3. Discussion

Chapter 15. Conclusion

15.1. Towards constraint-based ACO search

15.2. Towards a reactive ACO search

Bibliography

Index

First published 2010 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc. Adapted and updated from Optimisation par colonies de fourmis published 2008 in France by Hermes Science/Lavoisier © LAVOISIER 2008

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

John Wiley & Sons, Inc.

27-37 St George’s Road

111 River Street

London SW19 4EU

Hoboken, NJ 07030

UK

USA

www.iste.co.uk

www.wiley.com

© ISTE Ltd 2010

The rights of Christine Solnon to be identified as the author of this work have been asserted by her in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Solnon, Christine.

[Optimisation par colonies de fourmis. English]

Ant colony optimization and constraint programming / Christine Solnon.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-130-8

1. Constraint programming (Computer science) 2. Mathematical optimization. 3. Swarm intelligence. 4. Ant algorithms. I. Title.

QA76.612.S6513 2010

005.1′16--dc22

2009050443

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-130-8

Foreword

Combinatorial optimization has a very special place in computer science. On the one hand, this field addresses fundamental problems such as scheduling, resource allocation and vehicule routing, which are central to our economies. On the other hand, combinatorial optimization problems are extremely hard from a computational complexity standpoint: it is very unlikely that an efficient algorithm able to solve all these problems efficiently exists and that a single approach would outperform all others in this field. Different combinatorial problems, or even different instances of the same application, may be solved by very different techniques or by a combination of some of them. Moreover, whatever the approach considered, solving a combinatorial optimization problem usually requires a significant amount of programming and experimentation work.

In this book, Christine Solnon focuses on Ant Colony Optimization (ACO), a relatively recent approach for solving combinatorial problems. The topic is relevant: during the last decade, ACO has gradually evolved from an intellectual curiosity to a metaheuristic that has obtained outstanding results on some applications. This is the case, for example, of scheduling in assembly lines: a particularly difficult application for which ACO is able to solve a large class of instances with a very impressive efficiency and success rate. The scientific article published by the author on this subject was, indeed, a true revelation for many researchers.

However, this book does not introduce ACO in an isolated way, but provides an overview of many approaches. The first part of the book provides a short but excellent summary of the state of the art, with a focus on constraint satisfaction problems. Not only does this presentation clearly identify ACO contributions, but it also highlights the similarities, differences and synergies between existing approaches and ACO. Indeed, a truly innovative contribution of this book is to show how ACO compares to approaches as varied as greedy algorithms, local search and constraint programming.

The second part is a very didactic presentation of ACO. It shows us that ACO is a metaheuristic which produces collective intelligence from individual behaviors and local interactions. It provides an intuitive presentation of the various ACO components and a detailed overview of diversification and intensification mechanisms used by ants to sample the search space and converge towards the best solutions.

The book is organized around a broad vision of constraint programming: the idea that constraint programming defines the combinatorial structure of an application in a declarative way, and that this structure can be exploited by different solution algorithms. This view allows the author to communicate the benefits of ACO in a much more general way than the existing literature; the last part of the book is a good illustration of this. The application chapters are a goldmine for readers interested in acquiring a deep understanding of ACO. The last chapter provides a glimpse of the future of this metaheuristic and allows us to imagine many other connections.

In brief, Christine Solnon has written an effective book which targets both students and researchers wishing to acquire a thorough knowledge of the principles underlying ACO as well as industrialists in search of new solutions for their combinatorial optimization problems. It also communicates a comprehensive approach for solving combinatorial problems based on constraint programming, and allows us to establish judicious connections between several areas. This book is short, well written and full of ideas. It makes us curious to learn even more.

Pascal Van Hentenryck

Professor of Computer Science

Brown University

Acknowledgements

This book is the result of many interactions with many different people; it is impossible to mention them all here. Each of them have laid trails that have influenced me. At the moment of writing these acknowledgements, it is difficult to put these trails into order.

However, I would like to express my particular gratitude to Narendra Jussien who encouraged me to write this book; Pascal van Hentenryck who wrote the preface; Patrick Albert for his moral support; the IBM/Ilog society for its financial support; Pierre-Antoine Champin, Yves Deville and Serge Fenet who read preliminary versions of this book; and the Master and PhD students Inès Alaya, Madjid Khichane, Olfa Sammoud, Sébastien Sorlin and Arnaud Stuber. Each of them will recognize their trails.

Many thanks to Lucas, Léo and Lison, who train me to juggle with constraints every day of my life!

Chapter 1

Introduction

The ability of ant colonies to form paths for carrying food is rather fascinating. When considering the scale of ants, this path-finding problem is complex: ants only have a local perception of their environment, they do not have maps and they do not use GPS. The problem is solved collectively by the whole colony: paths actually emerge from a huge number of elementary interactions.

This collective problem-solving mechanism has given rise to a metaheuristic – that is, a generic approach for solving problems – referred to as ant colony optimization (ACO). The first ACO algorithm was initially proposed by Dorigo in 1992 to solve the traveling salesman problem, the goal of which is to find the shortest tour that passes through a given set of cities. Since this pioneering work, ant colony optimization has been used to solve many complex combinatorial optimization problems.

These combinatorial problems are challenging for computer scientists since solving them may involve the review of a huge number (usually exponential) of combinations. Most people will be familiar with the combinatorial explosion phenomenon, which transforms an apparently simple problem into a tricky brain teaser as soon as the size of the problem to be solved is increased.

For example, let us consider pentamino puzzles. The goal of such puzzles is to tile a figure with a given set of pentaminoes (shapes composed of five adjacent squares) without overlapping, as illustrated in Figure 1.1.

Figure 1.1.Example of pentamino puzzle; the solution is displayed in dashed lines

When the number of pentaminoes is small enough, these problems are rather easily solved by a systematic review of all possible combinations. However, when the number of pentaminoes is slightly increased, the number of different combinations to review increases so drastically that the problem can no longer be solved by a simple enumeration. For larger problems, even the most powerful computer cannot enumerate all combinations within a reasonable amount of time.

The challenge of solving these problems clearly goes beyond puzzles. This combinatorial explosion phenomenon also occurs in many industrial problems such as scheduling activities, planning a production or packing objects of different volumes into a finite number of bins. It is therefore highly important to design algorithms that are actually able to solve these difficult combinatorial problems.

This book examines the ability of ant colony optimization for solving these complex combinatorial problems. This study is carried out within the context of constraint programming, which allows us to describe combinatorial problems in a declarative way by means of constraints.

1.1. Overview of the book

The book comprises three parts, described in the following sections.

As a preamble to these three parts, we introduce combinatorial problems and discuss computational complexity issues in Chapter 2. The goal is to provide a clear understanding of the challenge: as the combinatorial explosion cannot be avoided, we have to design intelligent approaches which are able to restrain or get around it.

1.1.1. Constraint programming

The first part of this book provides an overview of different existing approaches for solving combinatorial problems within the context of constraint programming.

We introduce constraint satisfaction problems in Chapter 3, which provide a framework for modeling combinatorial problems in a declarative way by means of constraints.

We then describe three main types of approaches that may be used to solve constraint satisfaction problems.

Exact approaches are described in Chapter 4, where we explore the space of combinations in a systematic way until either a solution is found or inconsistency is proven. In order to (try to) restrain combinatorial explosion, these approaches structure the set of all combinations in a tree and use pruning techniques to reduce the search space and ordering heuristics to define the order in which it is explored.

Heuristic approaches get around combinatorial explosion by deliberately ignoring some combinations. We discuss the two main types of heuristic approaches:

– Perturbative heuristic approaches (Chapter 5) build new combinations by modifying existing combinations by applying cross-over and mutation operators for genetic algorithms, applying elementary transformations for local searches or moving with respect to a given velocity for particle swarm optimization.

– Constructive heuristic approaches (Chapter 6) use a stochastic model to generate new combinations in an incremental way. This model is static for greedy (randomized) algorithms. It is dynamic and evolves with respect to previous experience for estimation of distribution algorithms and ant colony optimization.

In Chapter 7 we introduce some constraint programming languages. These languages allow the user to describe a combinatorial problem in a declarative way by means of constraints. This problem can then be solved by embedded solving algorithms such as those described in Chapters 4, 5 and 6.

1.1.2. Ant colony optimization

The second part of this book describes ant colony optimization. As for other heuristic approaches described in Chapters 5 and 6, ant colony optimization only explores part of the space of all combinations and uses (meta-) heuristics to guide the search towards the most promising areas while deliberately ignoring others.

Ant colony optimization borrows its features from the collective behavior of ant colonies and, more particularly, from their collective ability to find the shortest path between two points. We therefore begin the second part in Chapter 8 with a description of mechanisms which allow ant colonies to converge towards the shortest paths. We then describe the Ant System, the first ant-based algorithm introduced by Dorigo in 1992 to solve the traveling salesman problem, and we describe the generic framework of ant colony optimization for solving static combinatorial optimization problems.

Beyond the ant metaphor, we describe the mechanisms which allow artificial ants to converge towards solutions in Chapter 9 and, more particularly, those used to balance diversification and intensification:

– Diversification aims to ensure a good sampling of the search space and therefore reduce the risk of ignoring an area which actually contains a solution. This is mainly ensured by use of a stochastic model to construct new combinations.

– Intensification aims to guide the search towards the best combinations. It is ensured by a reinforcement mechanism which exploits past constructions to progressively bias the stochastic model.

In Chapter 10, we describe some extensions of ACO that have recently been proposed to solve continuous problems (where some variables may be defined over continuous numerical intervals), dynamic problems (where data may change during the solution process) and multi-objective optimization problems (where several objective functions require to be optimized).

We conclude this second part with Chapter 11, where we provide hints for implementing ACO algorithms.

1.1.3. Constraint programming with ant colony optimization

Algorithms based on ant colony optimization have proven to be very effective for solving many combinatorial optimization problems. In this book we focus on their ability to solve constraint satisfaction problems, which constitute a generic class of combinatorial problems.

We first illustrate (Chapter 12) the abilities of ant colonies in the car sequencing problem, a real-world industrial problem that is very often used to evaluate constraint programming languages. This problem involves scheduling cars along an assembly line, while satisfying capacity constraints which ensure that the different work units on the assembly line are not overloaded. We show that ant colony optimization obtains very competitive results for this challenging problem.

We study the abilities of ant colonies to solve generic constraint satisfaction problems, for which we do not have any specific knowledge of the constraints used, in Chapter 13. Again, we show that ant colony optimization is able to resolve complex problems in an efficient manner.

We show how to integrate ant colony optimization into a constraint programming library in Chapter 14. This integration allows us to benefit from existing procedures for modeling, verifying and propagating constraints. The tree-based exploration of the search space, usually employed in constraint programming languages, is however replaced by a stochastic exploration guided by previous experiments using the basic principles of ant colony optimization.

Chapter 15 concludes with details of future research which could be carried out for a better integration of ant colony optimization into a constraint programming language.

Chapter 2

Computational Complexity

A problem is said to be combinatorial if it can be resolved by the review of a finite set of combinations. Most often, this kind of solving process is met with an explosion of the number of combinations to review. This is the case, for example, when a timetable has to be designed. If there are only a few courses to schedule, the number of combinations is rather small and the problem is quickly solved. However, adding a few more courses may result in such an increase of the number of combinations that it is no longer possible to find a solution within a reasonable amount of time.

This kind of combinatorial explosion is formally characterized by the theory of computational complexity, which classifies problems with respect to the difficulty of solving them. We introduce algorithm complexity in section 2.1, which allows us to evaluate the amount of resources needed to run an algorithm. In , we introduce the main and describe the problems we are interested in within this classification. We show that some instances of a problem may be more difficult to solve than others in or, in other words, that the input data may change the difficulty involved in finding a solution in practice. We introduce the concepts of and which may be used to characterize instance hardness. Finally, in , we provide an overview of the main approaches that may be used to solve combinatorial problems.