PA184 Heuristic Methods for Search and Optimization

Faculty of Informatics
Spring 2010
Extent and Intensity
2/0/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
Dario Landa-Silva, BEng, MSc, PhD (lecturer)
doc. Mgr. Hana Rudová, Ph.D. (lecturer)
Guaranteed by
prof. RNDr. Václav Matyáš, M.Sc., Ph.D.
Department of Computer Systems and Communications – Faculty of Informatics
Contact Person: doc. Mgr. Hana Rudová, Ph.D.
Timetable
Mon 26. 4. 8:00–9:50 B011, 14:00–17:50 B011, Tue 27. 4. 8:00–9:50 B011, 12:00–13:50 B011, Wed 28. 4. 8:00–9:50 B410, Thu 29. 4. 8:00–9:50 B011, 16:00–17:50 C511, Fri 30. 4. 10:00–11:50 B003, 13:00–16:50 B003
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
there are 36 fields of study the course is directly associated with, display
Course objectives
This course explores selected state-of-the-art heuristic search methods and their application to find solutions for complex optimisation and other search problems. The methods studied are selected from the latest specialised research literature. Students will achieve awareness of the latest advances in heuristic search methods research and will also implement some of these methods to solve a given problem. This course provides the knowledge and skills to design and implement solution procedures to solve a range of complex problems in industry and business.
Syllabus
  • Introduction: overview of the course, an insight into heuristics.
  • Principles of heuristic search: traditional techniques, motivation for heuristic search, basic concepts in heuristic search.
  • Local search: neighbourhood search, iterative improvement, escaping local optima.
  • Meta-heuristics: motivation for meta-heuristics, threshold acceptance, great deluge, simulated annealing.
  • Evolutionary algorithms: basic concepts, design of EAs, types of EAs.
  • Constraint handling: general considerations, rejecting infeasibility, repairing solutions, penalising infeasibility, enforcing feasibility, constraints as objectives.
  • Evaluating heuristic performance: fitness landscapes, empirical analysis of landscapes, experiments with heuristic search.
  • Hybrid heuristics: hybrids of SA, TS and GA, types of hybrid heuristics, examples of hybrids.
  • Software libraries for heuristics: programming frameworks, modelling languages, other development toolkits.
  • New ideas and future research.
Literature
  • Search methodologies : introductory tutorials in optimization and decision support techniques. Edited by Edmund Burke - Graham Kendall. New York: Springer, 2005, vi, 620. ISBN 0387234608. info
  • HOOS, Holger H. and Thomas STÜTZLE. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann / Elsevier, 2004. info
Teaching methods
Course is taught in a block of lectures during one or two weeks of the semester. Classical lectures are accompanied by workshops where students work hands-on putting in practice (programming) the techniques learned.
Assessment methods
Examination consists of the final written exam evaluated by 70 points and course work evaluated by 30 points. Completion of the course requires 55 points at least (A: 100-90, B 89-80, C 79-70, D 69-60, E59-55). The written exam includes: key concepts, description of algorithms, analysis and comparison of algorithms, constraint handling techniques. The coursework includes: implementation of algorithm(s) for a given problem, report and presentation.
Language of instruction
English
Further comments (probably available only in Czech)
Study Materials
The course is taught only once.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring2010/PA184