DM812 – Metaheuristics

Second quarter 2008: Monday 10-12 and Thursday 8-10 starting November 3, 2008, in IMADA Seminarrum.

Lectures

Literature

Books

• [B1] Stochastic Local Search: Foundations and Applications, H. Hoos and T. Stützle, 2005, Morgan Kaufmann

• [B2] Handbook of Approximation Algorithms and Metaheuristics. T.F. Gonzalez, Chapman & Hall/CRC Computer and Information Science, 2007.

• [B3] Search methodologies: introductory tutorials in optimization and decision support techniques E.K. Burke & G. Kendall, 2005, Springer, New York

• [B4] Theoretical Aspects of Local Search. W. Michiels, E. Aarts, & J. Korst, Springer Berlin Heidelberg, 2007

• [B5] Ant Colony Optimization M. Dorigo and T. Stützle, 2004, The MIT Press.

• [B6] Handbook of Metaheuristics Handbook of Metaheuristics F. Glover & G. Kochenberger (ed.) Kluwer Academic Publishers, Norwell, MA, USA, 2002, 57

• [B7] Local Search in Combinatorial Optimization Local Search in Combinatorial Optimization, E. Aarts & J. Lenstra (ed.) John Wiley & Sons, New York, NY, USA, 1997

Articles

• [A1] Optimization by Simulated Annealing. S. Kirkpatrick, D. Gelatt & M. P. Vecchi. Science, 1983, 220, 671-680

• [A2] How to assess and report the performance of a stochastic algorithm on a benchmark problem: Mean or best result on a number of runs? M. Birattari and M. Dorigo (2005). Technical Report TR/IRIDIA/2005-007. IRIDIA, Université Libre de Bruxelles, Brussels, Belgium.

• [A3] A Racing Algorithm For Configuring Metaheuristics. Birattari, M.; Stützle, T.; Paquete, L. & Varrentrapp. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002), Morgan Kaufmann Publishers, 2002, 11-18

• [A4] Principles of scatter search. Martí, R.; Laguna, M. & Glover, F. European Journal of Operational Research, 2006, 169, 359 - 372

• [A5] Hybrid scatter search and path relinking for the capacitated p-median problem. Díaz, J. A. & Fernández, E. European Journal of Operational Research, 2006, 169, 570 - 585

• [A6] A scatter search heuristic for the capacitated clustering problem. Scheuerer, S. & Wendolsky, R. European Journal of Operational Research, 2006, 169, 533 - 547 (Presented by Martin.)

• [A7] A simple genetic algorithm for multiple sequence alignment Gondro, C. & Kinghorn, B. P. Genetics And Molecular Research, Funpec-Editora, 2007, 6, 964-982] (Presented by Magnus.)

• [A8] Simple Explanation of the No Free Lunch Theorem of Optimization. Ho, Y. & Pepyne, D. Cybernetics and Systems Analysis, 2002, 38, 292-298

• [A9] The No Free Lunch and Problem Description Length Schumacher, C.; Vose, M. D. & Whitley, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), Morgan Kaufmann Publishers, San Francisco, CA, USA, 2001, 565-570

• [A10] Mathematical runtime analysis of ACO algorithms: survey on an emerging issue Swarm Intelligence, Gutjahr, W. J. 2007, 1, 59-79 (presented by Rok.)

• [A11] Survey of Optimization by Building and Using Probabilistic Models Pelikan, M.; Goldberg, D. E. & Lobo, F. G. A Computational Optimization and Applications, 2002, 21, 5-20

• [A12] A Tutorial on the Cross-Entropy Method P.T. de Boer, D. Kroese, S. M. & Rubinstein, R. 2003

• [A13] BOA: The Bayesian optimization algorithm. Pelikan, M., Goldberg, D.E. (1999) Genetic and Evolutionary Computation Conference (GECCO-99), pp. 525-532. (presented by Ida.)

• [A14] Using Ant Agents to Combine Reactive and Proactive Strategies for Routing in Mobile Ad Hoc Networks. Ducatelle, F.; Caro, G. D. & Gambardella, L. International Journal of Computational Intelligence and Applications, 2005, 5, 169-184. (Presented by Ralph.)

• [A15] Ant colony optimization for continuous domains. Socha, K. & Dorigo, M. European Journal of Operational Research, 2008, 185, 1155 - 1173 (Presented by Kristian.)

• [A16] Simplex Method for Function Minimization. Nelder, J. A. & Mead, R. A The Computer Journal, 1965, 7, 308-313

• [A17] Particle swarm optimization. Marco Dorigo, Marco A. Montes de Oca, Andries Engelbrecht (2008) Scholarpedia, 3(11):1486,

• [A18] Strategies for the Parallel Implementation of Metaheuristics Cung, V.; Martins, S. L.; Ribeiro, C. C. & Roucairol. Essays and Surveys in Metaheuristics, Kluwer Academic Publishers, 2001.

Links

• Scatter Search and Path Relinking: references

• Object-oriented framework for population-based metaheuristics: ParadisEO

• Ant Colony Optimization with publically available software

• Estimation of Distribution Algorithms

• Cross Entropy Method

• Differential Evolution

• Particle Swarm Optimization particleswarm.info, swarmintelligence.org

• Standard Benchmark Functions in Continuous Optimization

Exam

Project assignment:

• Text (launched December 14, 2008)

Hand in deadline: Monday, January 19, 2008

Course Evaluation

Students’ Evaluation. Action plan in response to students’ evaluation.