Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Metaheuristics and metaphors

No description
by

Kenneth Sörensen

on 12 December 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Metaheuristics and metaphors

Metaheuristics
Kenneth Sörensen
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
Full transcript