**Metaheuristics**

**Kenneth Sörensen**

kenneth.sorensen@ua.ac.be

kenneth.sorensen@ua.ac.be

What is a metaheuristic?

A metaheuristic is a

high-level

problem-independent

algorithmic

framework

that provides a set of guidelines or

strategies

to develop heuristic optimization algorithms.

Kenneth Sörensen and Fred Glover, Metaheuristics, Encyclopedia of Operations Research, Springer, Berlin, 2012 (to appear)

Fred Glover

University of Colorado & OptTek

Hundreds of publications

h-index > 50

Founding father of the field of metaheuristics

Tabu search, scatter search, path relinking, etc.

Optimization

Decision variables

Objective function

Constraints

The term is also used to refer to a problem-

specific

implementation

of a heuristic optimization algorithm according to the guidelines expressed in such a framework.

2^6 possible solutions

First, a simple heuristic

Oops

Maybe we need a metaheuristic

Tabu search

Use memory structures to guide the search

Tabu list (short-term)

Frequency memory

Elite memory

Aspiration

Etc

Evolutionary algorithms

use evolution as a metaphor for optimization

A whole new vocabulary!

Solution - chromosome

Objective function - fitness

Population

Genotypical - phenotypical encoding

Crossover, mutation, selection, ...

Etc

Ant colony optimization

model optimization as the behavior of ants

Models of nature that are relied upon for

inspiration

[in creating new metaheuristics] are ubiquitous, and it is easy to conjure up examples whose metaphorical possibilities have not yet been tapped. To take an excursion in the lighter side of such possibilities (though not too far from the lanes currently traveled), we may observe that a

beehive

offers a notable example of a system that possesses

problem solving abilities

. Bees

produce hives

of exceptional quality and complexity,

coordinate diverse tasks

among different types of individuals, perform

spatial navigation

, and communicate via multiple media. (It is perhaps

surprising

in retrospect that the behavior of bees has not been selected as a basis for one of the

“new” problem solving methods

.)

Fred Glover, 1997

Marco Dorigo

Marco Dorigo, Optimization, learning and natural algorithms, Ph. D. Thesis, Politecnico di Milano, Italy, 1992

The Reincarnation Algorithm

submitted to Journal of Heuristics in 2011

“RA utilizes the techniques of local and population based search to cover the wide search space in a limited time frame.

The system basically works with two sets of human population. One is salient population (called gurus) with higher fitness values and another is common population (called commoners) with low fitness values. The entire population of humans is dispersed evenly into many small subsets of communities. Humans are bound to perform karma or deeds that can upgrade or degrade their souls depending on the types of karma (either good or bad).

Population of commoners gets influenced by the population of their own community guru(s) and their closed ones to search locally for better fitness value. The best guru i.e. the guru with the best fitness value obtained so far for the entire population, influences gurus as well as commoners of all the communities. This algorithm also considers atheists in the same population who are not influenced by anyone but through their own self realization.

The search for better fitness value is termed as karma. RA uses karma and soul to handle input and output/fitness values respectively. The cycle of rebirth continues for many generations where karma of previous generation is carried forward to future generations through souls. Karma as discrete search space is heuristically updated in every generation based on reincarnation analogy to search for optimum solution.”

Intelligent Water Drops algorithm (IWD) is a swarm-based nature-inspired optimization algorithm, which has been inspired by natural rivers and how they find almost optimal paths to their destination. These near optimal or optimal paths follow from actions and reactions occurring among the water drops and the water drops with their riverbeds. In the IWD algorithm,

several artificial water drops cooperate to change their environment

in such a way that the optimal path is revealed as the one with the lowest soil on its links. The solutions are incrementally constructed by the IWD algorithm. Consequently, the IWD algorithm is generally a constructive population-based optimization algorithm.

Intelligent water drops?

Sometimes the metaphor makes no sense

No new metaphors, please

Focus on the problem

Do not develop a method without a problem

No black-box implementations of existing frameworks

Study the problem in detail

Know the literature on the problem and on related problems

Study the relationship between methods from the literature and the problem

Use the best parts from existing methods for your problems (e.g., matheuristics)

A metaphor can serve as inspiration

Never as justification!

Different types of optimization methods

Exact methods

Heuristic methods

Guarantee to find optimal solution

Slow - often only toy instances

Not very flexible

No guarantee to find optimal solution

Fast! = Real problems too!

Flexible

"Algorithms are conceived in analytic purity in the high citadels of academic research, heuristics are midwifed by expediency in the dark corners of the practitioner's lair ... and are accorded lower status."

Fred Glover, 1977

Metaphor-based metaheuristics

Get inspiration from some (natural) process

Make a random move

If it makes the solution better: accept it

If it makes the solution worse: accept with a certain probability, depending on the temperature

Deconstruction

Algorithm analysis & tuning

Frankenstein methods

How not to develop a metaheuristic

1. Take your favorite method

2. Add a component

3. While not working to

your satisfaction, go to 2

Develop any method you like, but determine

(a) the contribution of each component

(b) the optimal value of each parameter

Analyze your method

Deconstruct your method

Make sure each component matters

Find the best parameter settings

Use statistics!

Try to find out

why and how

your methods work

Use the best parts from different sub-areas of optimization (e.g., matheuristics)

Things should be as simple as possible, but no simpler

**Metaheuristics**

**Metaphors**

**Bad design**

**Good design**

What have we learned today?

1. It's all about optimization

(and nothing else)

2. Methods should be designed

according to accepted principles

3. Methods should be analyzed,

tested, and compared

An example: tabu search

Evolutionary algorithms

New methods?

Water network design optimization

A field in which improvements are possible

Methods tested on the WDND optimization problem

Genetic algorithm

Real-coded genetic algorithm

Memetic algorithm

Shuffled frog leaping algorithm

Cross entropy search

Scatter search

Differential evolution

Tabu search

Simulated annealing

Immune algorithm

Particle swarm harmony search

All are tested on two or three instances

All achieve "excellent" performance

None are better than a simple heuristic that can be described in two paragraphs.

Use design principles from the literature

There are not so many fundamentally different methods

Some tips

Use the standard optimization vocabulary

Stay within the existing taxonomy

No points are awarded for originality, only for performance

There are more than enough "novel methods"

It's all about optimization!

Interesting parallels can be found in the literature

(e.g., LNS is the constructive variant of ILS)

The metaphor exposed

Metaphors have been useful in exploring the possibilities of the research field

HOWEVER

Most "new" methods are just a repackaging of old ideas

The vocabulary is changed every time

Sometimes the relationship between the algorithm and the metaphor is shallow or non-existent

Sometimes the metaphor doesn't even make sense

Fly algorithm

Similar to particle swarm optimization, but

x% of the flies change velocity because of other flies

y% of the "flies" appear in random positions

Where is the relationship between the algorithm and reality?

**The metaphor exposed**