Português English
Contact

List | CMP268

Heuristic search methods

Professor: Marcus Ritt
Prerequisites: –
Hours: 60 hs
Credits: 4
Semesters: First semester
Undergraduate Enrollment: The enrollment must be made as Special Student
Page Link: http://www.inf.ufrgs.br/~mrpritt/hsc

SUMMARY

Introduction to heuristic and meta-heuristic search methods: design, calibration, evaluation, and comparison. Case studies of applications of heuristic search methods.

OBJECTIVES

The students are familiar with the main principles of heuristic search methods. They are able to apply heuristic search methods, and evaluate them adequately.

PROGRAM

I. Implementation and evaluation of heuristic methods

1) Parameter setting
2) Statistical evalution
3) Comparison of heuristic methods
4) Implementation techniques

II. Heuristic search methods

1. Constructive heuristics
2. Local search
3. Construction-based meta-heuristics
GRASP, Ant colony optimization
4. Local search-based metaheurístics
Simulated Annealing, Tabu Search, Variable neighborhood search, Threshold acceptance, Late acceptance methods, Guided local search, Particle swarm optimization, Large neighborhood search
5. Metaheuristics based on recombination of solutions
Genetic and memetic algorithms, scatter search
6. Hybridization of meta-heuristics and hyper-heuristics

III. Special Topics

1. Multi-objective heuristics
2. Heuristics for continuous problems
3. Tools and frameworks for heuristic search
4. Parallelization of heuristics
5. Fitness landscape analysis

EVALUATION

Students will be evaluated by their homework assignments (1/3), an individual student project (1/3), and a final exam (1/3).

BIBLIOGRAPHY

Michalewicz, Fogel, “How to solve it: modern heuristics”, Springer, 2004.
Hoos, Stützle, “Stochastic Local Search : Foundations & Applications”. Morgan Kaufmann, 2004.
Zäpl, Braune, Bögl, “Metaheuristic search concepts”, Springer, 2010
Talbi (Ed.), “Parallel Combinatorial Optimization”, Wiley, ISBN-978-0-471-72101-7, USA, 2006.
Talbi, “Metaheuristics: from design to implementation”, Wiley, 2009.