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.

An overview of the rapidly growing field of ant colony optimization that describes theoretical findings, the major algorithms, and current applications. The complex social behaviors of ants have been much studied by science, and computer scientists are now finding that these behavior patterns can provide models for solving difficult combinatorial optimization problems. The attempt to develop algorithms inspired by one aspect of ant behavior, the ability to find what computer scientists would call shortest paths, has become the field of ant colony optimization (ACO), the most successful and widely recognized algorithmic technique based on ant behavior. This book presents an overview of this rapidly growing field, from its theoretical inception to practical applications, including descriptions of many available ACO algorithms and their uses. The book first describes the translation of observed ant behavior into working optimization algorithms. The ant colony metaheuristic is then introduced and viewed in the general context of combinatorial optimization. This is followed by a detailed description and guide to all major ACO algorithms and a report on current theoretical findings. The book surveys ACO applications now in use, including routing, assignment, scheduling, subset, machine learning, and bioinformatics problems. AntNet, an ACO algorithm designed for the network routing problem, is described in detail. The authors conclude by summarizing the progress in the field and outlining future research directions. Each chapter ends with bibliographic material, bullet points setting out important ideas covered in the chapter, and exercises. Ant Colony Optimization will be of interest to academic and industry researchers, graduate students, and practitioners who wish to learn how to implement ACO algorithms.

The series of biannual international conferences “ANTS – International C- ference on Ant Colony Optimization and Swarm Intelligence”, now in its sixth edition, was started ten years ago, with the organization of ANTS’98. As some readers might recall, the ?rst edition of ANTS was titled “ANTS’98 – From Ant Colonies to Arti?cial Ants: First International Workshop on Ant Colony Op- mization. ” In fact, at that time the focus was mainly on ant colony optimization (ACO), the ?rst swarm intelligence algorithm to go beyond a pure scienti?c interest and to enter the realm of real-world applications. Interestingly, in the ten years after the ?rst edition there has been a gr- ing interest not only for ACO, but for a number of other studies that belong more generally to the area of swarmintelligence. The rapid growth of the swarm intelligence ?eld is attested by a number of indicators. First, the number of s- missions and participants to the ANTS conferences has steadily increased over the years. Second, a number of international conferences in computational - telligence and related disciplines organize workshops on subjects such as swarm intelligence, ant algorithms, ant colony optimization, and particle swarm op- mization. Third, IEEE startedorganizing,in 2003,the IEEE SwarmIntelligence Symposium (in order to maintain unity in this growing ?eld, we are currently establishingacooperationagreementbetweenIEEE SISandANTSsoastohave 1 IEEE SIS in odd years and ANTS in even years). Last, the Swarm Intelligence journal was born.

This book constitutes the joint refereed proceedings of six workshops, EvoWorkshops 2003, held together with EuroGP 2003 in Essex, UK in April 2003. The 63 revised full papers presented were carefully reviewed and selected from a total of 109 submissions. In accordance with the six workshops covered , the papers are organized in topical sections on bioinformatics, combinatorial optimization, image analysis and signal processing, evolutionary music and art, evolutionary robotics, and scheduling and timetabling.

This title presents a large variety of models and algorithms dedicated to the resource-constrained project scheduling problem (RCPSP), which aims at scheduling at minimal duration a set of activities subject to precedence constraints and limited resource availabilities. In the first part, the standard variant of RCPSP is presented and analyzed as a combinatorial optimization problem. Constraint programming and integer linear programming formulations are given. Relaxations based on these formulations and also on related scheduling problems are presented. Exact methods and heuristics are surveyed. Computational experiments, aiming at providing an empirical insight on the difficulty of the problem, are provided. The second part of the book focuses on several other variants of the RCPSP and on their solution methods. Each variant takes account of real-life characteristics which are not considered in the standard version, such as possible interruptions of activities, production and consumption of resources, cost-based approaches and uncertainty considerations. The last part presents industrial case studies where the RCPSP plays a central part. Applications are presented in various domains such as assembly shop and rolling ingots production scheduling, project management in information technology companies and instruction scheduling for VLIW processor architectures.

This book constitutes the refereed proceedings of the 5th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2008, held in Paris, France, in May 2008. The 18 revised long papers and 22 revised short papers presented together with 3 invited talks were carefully reviewed and selected from 130 submissions. The papers describe current research in the fields of constraint programming, artificial intelligence, and operations research to explore ways of solving large-scale, practical optimization problems through integration and hybridization of the fields' different techniques.

Heuristics are strategies using readily accessible, loosely applicable information to control problem solving. Algorithms, for example, are a type of heuristic. By contrast, Metaheuristics are methods used to design Heuristics and may coordinate the usage of several Heuristics toward the formulation of a single method. GRASP (Greedy Randomized Adaptive Search Procedures) is an example of a Metaheuristic. To the layman, heuristics may be thought of as ‘rules of thumb’ but despite its imprecision, heuristics is a very rich field that refers to experience-based techniques for problem-solving, learning, and discovery. Any given solution/heuristic is not guaranteed to be optimal but heuristic methodologies are used to speed up the process of finding satisfactory solutions where optimal solutions are impractical. The introduction to this Handbook provides an overview of the history of Heuristics along with main issues regarding the methodologies covered. This is followed by Chapters containing various examples of local searches, search strategies and Metaheuristics, leading to an analyses of Heuristics and search algorithms. The reference concludes with numerous illustrations of the highly applicable nature and implementation of Heuristics in our daily life. Each chapter of this work includes an abstract/introduction with a short description of the methodology. Key words are also necessary as part of top-matter to each chapter to enable maximum search engine optimization. Next, chapters will include discussion of the adaptation of this methodology to solve a difficult optimization problem, and experiments on a set of representative problems.