Ant Colony Optimization and Constraint Programming

Name: Ant Colony Optimization and Constraint Programming
Brand: Wiley-ISTE
Price: 140.99 EUR
Availability: OnlineOnly

Christine Solnon(Author)

Wiley-ISTE (Publisher)

Published on 4. March 2013

320 pages

E-Book

PDF with Adobe-DRM

System requirements

978-1-118-61966-7 (ISBN)

€140.99incl. 7% vat

System requirements

for PDF with Adobe-DRM

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

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 transition
2.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 satisfaction
3.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 checking
4.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. Discussion
Chapter 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
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.3.1. Pheromone structure
8.3.2. Construction of a Hamiltonian cycle by an ant
8.3.3. Pheromone updating step
8.3.4. Artificial versus real ants
8.4. Generic ACO framework
8.4.1. Pheromone structure and construction graph
8.4.2. Construction of combinations by ants
8.4.3. Improving combinations with local search
8.4.4. Pheromone updating step
8.4.5. Parameters of an ACO algorithm
Chapter 9. Intensification versus Diversification
9.2. ACO mechanisms for diversifying the search
9.3. Balancing intensification and diversification
9.4. Measures of diversification/intensification
9.4.1. The ?-branching factor
9.4.2. Resampling ratio
9.4.3. Similarity ratio
Chapter 10. Beyond Static Combinatorial Problems
10.1.2. Solving multi-objective problems with ACO
10.2. Dynamic optimization problems
10.2.1. Definition of dynamic optimization problems
10.2.2. Solving dynamic optimization problems with ACO
10.3. Optimization problems over continuous domains
10.3.1. Definition of continuous optimization problems
10.3.2. Solving continuous optimization problems with ACO
Chapter 11. Implementation Issues
11.1.2. Data structures associated with heuristic factors
11.1.3. Data structures associated with ants
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
11.4.1. Resampling ratio
11.4.2. Similarity ratio
PART III. CP WITH ACO
Introduction to Part III
Chapter 12. Sequencing Cars with ACO
12.2. A first pheromone structure for identifying good car sequences
12.2.1. Pheromone structure
12.2.2. Construction of a sequence by an ant
12.2.3. Pheromone laying step
12.3. A second pheromone structure for identifying critical cars
12.3.1. Pheromone structure
12.3.2. Construction of a sequence by an ant
12.3.3. Pheromone updating step
12.4. Combining the two pheromone structures
12.4.1. First pheromone structure
12.4.2. Second pheromone structure
12.4.3. Construction of a sequence by an ant
12.5. Comparison of the different ACO algorithms
12.5.1. Considered algorithms
12.5.2. Test suite
12.5.3. Parameter settings
12.5.4. Experimental results
12.6. Comparison of ACO with state-of-the-art approaches
12.6.1. Considered approaches
12.6.2. IDWalk
12.6.3. VFLS
12.6.4. Experimental set-up
12.6.5. Experimental results
12.7. Discussion
Chapter 13. Subset Selection with ACO
13.1. Subset selection problems
13.1.1. Maximum clique
13.1.2. Multidimensional knapsack
13.1.3. Maximum Boolean satisfiability
13.1.4. Maximum constraint satisfaction
13.1.5. Minimum vertex cover
13.1.6. Maximum common subgraph
13.1.7. Edge-weighted k-cardinality tree
13.2. Description of Ant-SSP
13.2.1. Construction of a combination by an ant
13.2.2. Pheromone laying step
13.3. Instantiations of Ant-SSP with respect to two pheromone strategies
13.3.1. The vertex pheromone strategy
13.3.2. The clique pheromone strategy
13.3.3. Comparison of the two strategies
13.4. Instantiation of Ant-SSP to solve CSPs
13.4.1. Heuristic factor
13.4.2. Local search
13.5. Experimental results
13.5.1. Randomly generated binary instances
13.5.2. Results on instances of the 2006 solver competition
13.6. Discussion
Chapter 14. Integration of ACO in a CP Language
14.1. Framework for integrating ACO within a CP library
14.1.1. Pheromone strategy
14.1.2. Construction of assignments
14.1.3. Pheromone updating step
14.2. Illustration of ACO-CP on the car sequencing problem
14.2.1. CSP model
14.2.2. Variable ordering heuristic
14.2.3. Pheromone strategies
14.2.4. Heuristic factor
14.2.5. Experimental results
14.3. Discussion
Chapter 15. Conclusion
15.1. Towards constraint-based ACO search
15.2. Towards a reactive ACO search
Bibliography
Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Ant Colony Optimization and Constraint Programming

Description

Reviews / Votes

More details

Other editions

Additional editions

Content

System requirements