Essentials of Metaheuristics

Introduction

This is a set of lecture notes for an undergraduate class on metaheuristics. They were constructed for a course I taught in Spring of 2009, and I wrote them because, well, there’s a lack of undergraduate texts on the topic. As these are lecture notes for an undergraduate class on the topic, which is unusual, these notes have certain traits. First, they’re informal and contain a number of my own personal biases and misinformation. Second, they are light on theory and examples: they’re mostly descriptions of algorithms and handwavy, intuitive explanations about why and where you’d want to use them. Third, they’re chock full of algorithms great and small. I think these notes would best serve as a complement to a textbook, but can also stand alone as rapid introduction to the field. I make no guarantees whatsoever about the correctness of the algorithms or text in these notes. Indeed, they’re likely to have a lot of errors. Please tell me of any errors you find (and correct!). Some complex algorithms have been presented in simplified versions. In those cases I’ve noted it.

What is a Metaheuristic?

A common but unfortunate name for any stochastic optimization algorithm intended to be the last resort before giving up and using random or brute-force search. Such algorithms are used for problems where you don't know how to find a good solution, but if shown a candidate solution, you can give it a grade. The algorithmic family includes genetic algorithms, hill-climbing, simulated annealing, ant colony optimization, particle swarm optimization, and so on.