
Ant Colony Optimization and Constraint Programming
Description
Alles über E-Books | Antworten auf Fragen rund um E-Books, Kopierschutz und Dateiformate finden Sie in unserem Info- & Hilfebereich.
Reviews / Votes
"In this volume, Solnon (U. of Lyon, France) introduces ant colonyoptimization and its application to a range of combinatorialproblems, with a focus on constraint programming." (BookNews, September 2010)More details
Other editions
Additional 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
File format: PDF
Copy-Protection: Adobe-DRM (Digital Rights Management)
System requirements:
- Computer (Windows; MacOS X; Linux): Install the free reader Adobe Digital Editions prior to download (see eBook Help).
- Tablet/smartphone (Android; iOS): Install the free app Adobe Digital Editions or the app PocketBook before downloading (see eBook Help).
- E-reader: Bookeen, Kobo, Pocketbook, Sony, Tolino and many more (only limited: Kindle).
The file format PDF always displays a book page identically on any hardware. This makes PDF suitable for complex layouts such as those used in textbooks and reference books (images, tables, columns, footnotes). Unfortunately, on the small screens of e-readers or smartphones, PDFs are rather annoying, requiring too much scrolling.
This eBook uses Adobe-DRM, a „hard” copy protection. If the necessary requirements are not met, unfortunately you will not be able to open the eBook. You will therefore need to prepare your reading hardware before downloading.
Please note: We strongly recommend that you authorise using your personal Adobe ID after installation of any reading software.
For more information, see our eBook Help page.