Description |
1 online resource (248 pages) |
Series |
ISTE |
|
ISTE
|
Contents |
Cover; Title Page; Cpoyright Page; Table of Contents; Foreword; Acknowledgements; Chapter 1. Introduction; 1.1. Overview of the book; 1.1.1. Constraint programming; 1.1.2. Ant colony optimization; 1.1.3. Constraint programming with ant colony optimization; Chapter 2. Computational Complexity; 2.1. Complexity of an algorithm; 2.2. Complexity of a problem; 2.2.1. The P class; 2.2.2. The NP class; 2.2.3. NP-complete problems; 2.2.4. NP-hard problems; 2.2.5. Undecidable problems; 2.2.6. Complexity of optimization problems; 2.3. Where the most difficult instances can be found |
|
2.3.1. Phase transition2.3.2. Search landscape; 2.4. Solving NP-hard problems in practice; 2.4.1. Exploitation of particular cases; 2.4.2. Approximation algorithms; 2.4.3. Heuristics and metaheuristics; 2.4.4. Structuring and filtering the search space; PART I. CONSTRAINT PROGRAMMING; Introduction to Part I; Chapter 3. Constraint Satisfaction Problems; 3.1. What is a constraint?; 3.1.1. Definition of a constraint; 3.1.2. Arity of a constraint and global constraints; 3.2. What is a constraint satisfaction problem?; 3.2.1. Complexity of CSPs; 3.3. Optimization problems related to CSPs |
|
3.3.1. Maximizing constraint satisfaction3.3.2. Constrained optimization; 3.4. The n-queens problem; 3.4.1. Description of the problem; 3.4.2. First CSP model; 3.4.3. Second CSP model; 3.4.4. Third CSP model; 3.4.5. Influence of the model on the solution process; 3.5. The stable marriage problem; 3.5.1. Description of the problem; 3.5.2. CSP model; 3.6. Randomly generated binary CSPs; 3.7. The car sequencing problem; 3.7.1. Description of the problem; 3.7.2. CSP model; 3.8. Discussion; Chapter 4. Exact Approaches; 4.1. Construction of a search tree; 4.2. Constraint propagation |
|
4.2.1. Forward checking4.2.2. Maintaining arc consistency; 4.3. Ordering heuristics; 4.3.1. Heuristics for choosing variables; 4.3.2. Heuristics for choosing values; 4.3.3. Randomized restart; 4.4. From satisfaction to optimization problems; 4.5. Discussion; Chapter 5. Perturbative Heuristic Approaches; 5.1. Genetic algorithms; 5.1.1. Basic principles; 5.1.2. Using GAs to solve CSPs; 5.2. Local search; 5.2.1. Basic principles; 5.2.2. Metaheuristics based on LS; 5.2.3. Using LS to solve CSPs; 5.3. Particle swarm optimization; 5.3.1. Basic principles; 5.3.2. Using PSO to solve CSPs |
|
5.4. DiscussionChapter 6. Constructive Heuristic Approaches; 6.1. Greedy randomized approaches; 6.1.1. Basic principles; 6.1.2. Using greedy randomized algorithms to solve CSPs; 6.2. Estimation of distribution algorithms; 6.2.1. Basic principles; 6.2.2. Using EDAs to solve CSPs; 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 |
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. 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 |
Notes |
Chapter 8. From Swarm Intelligence to Ant Colony Optimization |
|
Print version record |
Subject |
Constraint programming (Computer science)
|
|
Mathematical optimization.
|
|
Swarm intelligence.
|
|
Ant algorithms.
|
|
COMPUTERS -- Programming -- Open Source.
|
|
COMPUTERS -- Software Development & Engineering -- General.
|
|
COMPUTERS -- Software Development & Engineering -- Tools.
|
|
Ant algorithms
|
|
Constraint programming (Computer science)
|
|
Mathematical optimization
|
|
Swarm intelligence
|
Form |
Electronic book
|
ISBN |
9781118557563 |
|
1118557565 |
|
9781118619667 |
|
1118619668 |
|