Skip to content

Metaheuristics

Part 4 · Heuristic algorithms · Chapter 32 · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Metaheuristics · App: TSP: simulated annealing and tabu search

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • execute by hand simulated annealing, tabu search, iterated local search and variable neighbourhood search, with given random numbers;

  • execute GRASP, large neighbourhood search and a genetic or memetic algorithm on small instances;

  • explain how each method escapes from a local optimum, and which parameters tune it;

  • compare the methods on the same instances, over several seeds;

  • say what metaheuristics do not give: a dual bound.

32.1 Metaheuristics

Definition 32.1: Metaheuristic

A metaheuristic is a general strategy that guides a local search beyond the first local optimum, to explore other regions of the set of feasible solutions.

  • A metaheuristic is a scheme, not an algorithm: an algorithm is obtained by choosing the representation, the neighbourhoods, the local search and the parameters.

  • Every metaheuristic balances intensification and diversification, defined in the chapter «Heuristic algorithms: definitions».

A local search stops in the first local optimum; a metaheuristic escapes from it by accepting worse solutions, by jumping to a new starting solution, or by combining several good solutions.

  • Overview

    Metaheuristics

    Open

  • 32.2 The problems and the assumptions

    Random numbers · The instances

    Open

  • How to escape from a local optimum · Simulated annealing

    The cooling schedule and the parameters · Examples · Infeasible solutions: simulated annealing with a penalty · An experiment on the medium TSP instance · Properties

    Open

  • 32.5 Tabu search

    Tabu search for the TSP, and the effect of the tenure

    Open

  • 32.6 Iterated local search

    Open

  • 32.7 Variable neighbourhood search

    Open

  • 32.8 GRASP

    Open

  • 32.9 Large neighbourhood search

    Adaptive large neighbourhood search

    Open

  • 32.10 Population-based methods: genetic and memetic algorithms

    Open

  • 32.11 Comparison and conclusions

    Intensification and diversification · Parameters and tuning · What these methods do not use

    Open

  • Typical mistakes · In summary

    In summary

    Open

  • References

    Open

Next: 32.2 The problems and the assumptions

Exercises on this chapter: Metaheuristics

In the interactive lab: TSP: simulated annealing and tabu search.