University of Antwerp
Operations Research GroupANT/ORA hi<ory of meta˙uri<ics
Kenneth S]rensen Marc Se‰ux Fred Gloffir
ORBEL29 - Antwerp - 5-6 February 2015

A history of this talkHandbook of Heuristics (Springer)A history of this talkHandbook of Heuristics (Springer)A history of this talkHandbook of Heuristics (Springer)A history of this talkHandbook of Heuristics (Springer)A history of this talkHandbook of Heuristics (Springer)A history of this talkHandbook of Heuristics (Springer)

Methodology

I High-level perspective
I Not an annotated chronological bibliography
I Attempt to discover paradigm-shifts
I No futile attempts to adopt a neutral perspective

What is a heuristic?

x ∗ = arg max f (x)x∈X

Exact method

Heuristic

Optimization method withguarantee of optimality

Optimization method without
guarantee of optimality

What is a metaheuristic?

Metaheuristic ver. 1(framework)
A metaheuristic is a high-level,
problem-independent algorithmic
framework that provides a set ofguidelines or strategies to develop
heuristic optimization algorithms.

What is a metaheuristic?

Metaheuristic ver. 1(framework)
A metaheuristic is a high-level,problem-independent algorithmic
framework that provides a set ofguidelines or strategies to develop
heuristic optimization algorithms.

Metaheuristic ver. 2(algorithm)
The term is also used to refer toa problem-specificimplementation of a heuristic
optimization algorithm according
to the guidelines expressed insuch a framework.

Five periods of (meta)heuristics

1.
2.
3.
4.
5.

The pre-theoretical period
The early period
The method-centric period
The framework-centric period
The scientific period(until c. 1940)(c. 1940 – c. 1980)(c. 1980 – c. 2000)(c. 2000 – now)(the future)

The pre-theoretical period
I Optimization problems are all

around us
I The human mind is naturally

equipped with an incredibly
versatile heuristic solver

The pre-theoretical period
I Optimization problems are all

around us
I The human mind is naturally

equipped with an incredibly
versatile heuristic solver

Sörensen’s conjecture
In the real world, solving
optimization problems
using exact methods is awaste of resources.

The pre-theoretical period
I Optimization problems are all

around us
I The human mind is naturally

equipped with an incredibly
versatile heuristic solver
I It has meta-strategies(“meta-heuristics”) too, e.g.,learning by analogy
greedinessI most difficult firstI means-end-analysis (“localsearch”)
I don’t do something that failed in
the past (“tabu search”)
I ...
II

Sörensen’s conjecture
In the real world, solving
optimization problems
using exact methods is awaste of resources.

The early period

I After WWIII Coincides with development of OR
I “How to solve it” (1945)“Analogy”“Induction”
I “Auxiliary problem”
II

I High-level algorithmic ideas

1. Constructive heuristics
2. Regret algorithms

George Pólya

The early period
I Artificial

intelligence as
the basis forheuristic design
I Realizationthat someideas on thedesign ofheuristics canbe generalized

The method-centric period
I From the 60s: evolutionary methods

Evolution strategies (Schwefel, Rechenberg) – no population or
crossover
I Genetic algorithms (Holland, Goldberg): population + crossover
I Theoretical studies to “prove” convergence
I General sentiment: an all-powerful black-box optimizer withinreachI

I 1980s: another metaphor: simulated annealing
I 1980s: more AI-based methods

Local search
Threshold accepting
I Tabu search
I A few moreIIMeta-heuristics introduced
Discussion
Cmpur.
Printed& 0~s. Res. Vol. 13, No. 5, pp. 533-549.
in Great Britain. All rights reserved

FUTURE1986
Copyright

PATHS FOR INTEGER PROGRAMMINGARTIFICIAL INTELLIGENCE

00305-0548/86$3.00 + 0.00
1986 Pergamon Journals Ltd

AND LINKS TO

FRED GLOVER*Center for Applied Artificial Intelligence, Graduate School of Business, University of Colorado,Boulder, CO 80309, U.S.A.

Scope and Purpose--A summary is provided of some of the recent (and a few not-so-recent) developmentsthat offer promise for enhancing our ability to solve combinatorial optimization problems. Thesedevelopments may be usefully viewed as a synthesis of the perspectives of operations research and artificialintelligence. Although compatible with the use of algorithmic subroutines, the frameworks examined areprimarily heuristic, based on the supposition that effective solution of complex combinatorial structures insome cases may require a level of flexibility beyond that attainable by methods with formally demonstrable
convergence properties.
Abstract-Integer
programming has benetited from many innovations in models and methods. Some of thepromising directions for elaborating these innovations in the future may be viewed from a framework thatlinks the perspectives of artificial intelligence and operations research. To demonstrate this, four key areas
are examined: (1) controlled randomization, (2) learning strategies, (3) induced d~omposition and (4) tabu
search. Each of these is shown to have characteristics that appear usefully relevant to developments on thehorizon.

I. INTRODUCTIONInteger programming (IP) has gone through many phases in the last three decades, spurred by therecognition that its domain encompasses a wide range of important and challenging practicalapplications. Two of the more prominent landmarks in the development of the field haveundoubtedly been the emergence of the cutting plane and branch and bound approaches. As generalsolution strategies, these approaches have drawn on concepts from diverse areas including number
theory, group theory, logic, convex analysis, nonlin~r functions, and matroid theory [l-7].
From the theoretical side, cutting planes have received the greatest attention, though from a broad
perspective the distinction between cutting plane and branch and bound methods blurs. Indeed,branch and bound may be viewed as provisional cutting. From the practical side, the most effective
general purpose methods have relied heavily on branch and bound, conceiving branch and bound inits standard (narrower) sense, where the collection of provisional cuts derives simply fromconstraining integer variables to satisfy lower and upper bounds. Doses of cutting plane theory havebeen used to improve the basic branch and bound framework, chiefly by generating cuts to be added
before initiating the branch and bound process (or in some cases just prior to selecting a next branch)[S-14]. The cuts used, however, are typically those that are easily derived and generated. The more
labyrinthine and esoteric derivations have not so far demonstrated great practical utility.

“Meta” or “Modern”
heuristics?

The method-centric period
I General sentiment: metaheuristics asrecipes
I Neural networks
I New methods
IIGRASPAnt colony optimization

I Second half of the 1990s: disappointment

over reachability of über-powerful
black-box optimizers
I No free lunch theorem

1995
Metaheuristics
InternationalConference MIC

1995

The framework-centric period

I Introduction of hybrid metaheuristics(e.g., memetic algorithms)
I Mix-and-match of metaheuristic

components
I Realization that metaheuristics should beseen as frameworks, rather than methods.
I Matheuristics

2001

The metaphor-centric period

[54]
[9]
[11]
[10]

Bio-inspired (not SI-based) algorithms
Algorithm
AuthorAtmosphere clouds model
Yan and Hao
Biogeography-based optimization
Simon
Brain Storm Optimization
Shi
Differential evolution
Storn and Price
Dolphin echolocation
Kaveh and Farhoudi
Japanese tree frogs calling
Hernández and Blum
Eco-inspired evolutionary algorithm Parpinelli and Lopes
Egyptian Vulture
Sur et al.
Fish-school Search
Lima et al.
Flower pollination algorithm
Yang
Gene expression
Ferreira
Great salmon run
MozaffariGroup search optimizer
He et al.
Human-Inspired Algorithm
Zhang et al.
Invasive weed optimization
Mehrabian and Lucas
Marriage in honey bees
Abbass
OptBees
Maia et al.
Paddy Field Algorithm
Premaratne et al.
Roach infestation algorithm
HavensQueen-bee evolution
Jung
Shuffled frog leaping algorithm
Eusuff and Lansey
Termite colony optimization
Hedayatzadeh et al.
Physics and Chemistry based algorithms
Big bang-big Crunch
Zandi et al.
Black hole
Hatamlou
Central force optimization
FormatoCharged system search
Kaveh and TalatahariElectro-magnetism optimization
Cuevas et al.
Galaxy-based search algorithm
Shah-Hosseini
Gravitational search
Rashedi et al.
Harmony search
Geem et al.
Intelligent water drop
Shah-Hosseini
River formation dynamics
Rabanal et al.
Self-propelled particles
VicsekReference[67]
[56]
[55]
[57]
[33]
[28]
[45]
[59]
[14], [3][72], [76]
[19]
[43]
[26]
[80]
[42]
[1]
[41]
[48]
[25]
[30]
[18]
[27]
[79]
[24]
[21]
[34]
[13]
[53]
[50]
[23]
[52]
[49]
[64]

FISTER, YANG FISTER, BRES

Reference[69], [71]
[15]
[31]
[46]
[6]
[78]
[62]
[40]
[65]
[61]
[47]
[16]
[12]
[7]
[29]
[74]
[75]
[8]
[70]
[39]
[58]
[37], [38]
[5]
[22]
[44]
[35]
[77]
[68]
[63]

4

Swarm intelligence based algorithms
Algorithm
AuthorAccelerated PSO
Yang et al.
Ant colony optimization
DorigoArtificial bee colony
Karaboga and Basturk
Bacterial foraging
PassinoBacterial-GA Foraging
Chen et al.
Bat algorithm
Yang
Bee colony optimization
Teodorović and Dell’Orco
Bee system
Lucic and Teodorovic
BeeHive
Wedde et al.
Wolf search
Tang et al.
Bees algorithms
Pham et al.
Bees swarm optimization
Drias et al.
Bumblebees
Comellas and Martinez
Cat swarm
Chu et al.
Consultant-guided search
Iordache
Cuckoo search
Yang and Deb
Eagle strategy
Yang and Deb
Fast bacterial swarming algorithm Chu et al.
Firefly algorithm
Yang
Fish swarm/school
Li et al.
Good lattice swarm optimization
Su et al.
Glowworm swarm optimization
Krishnanand and Ghose
Hierarchical swarm model
Chen et al.
Krill Herd
Gandomi and Alavi
Monkey search
Mucherino and Seref
Particle swarm algorithm
Kennedy and Eberhart
Virtual ant algorithm
Yang
Virtual bees
Yang
Weightless Swarm Algorithm
Ting et al.
Other algorithms
Anarchic society optimization
Shayeghi and Dadashpour
Artificial cooperative search
Civicioglu
Backtracking optimization search Civicioglu
Differential search algorithm
CiviciogluThe metaphor-centric period

Reference[69], [71]
[15]
[31]
[46]
[6]
[78]
[62]
[40]
[65]
[61]
[47]
[16]
[12]
[7]
[29]
[74]
[75]
[8]
[70]
[39]
[58]
[37], [38]
[5]
[22]
[44]
[35]
[77]
[68]
[63]

Bio-inspired (not SI-based) algorithms
Algorithm
AuthorAtmosphere clouds model
Yan and Hao
Biogeography-based optimization
Simon
Brain Storm Optimization
Shi
Differential evolution
Storn and Price
Dolphin echolocation
Kaveh and Farhoudi
Japanese tree frogs calling
Hernández and Blum
Eco-inspired evolutionary algorithm Parpinelli and Lopes
Egyptian Vulture
Sur et al.
Fish-school Search
Lima et al.
Flower pollination algorithm
Yang
Gene expression
Ferreira
Great salmon run
MozaffariGroup search optimizer
He et al.
Human-Inspired Algorithm
Zhang et al.
Invasive weed optimization
Mehrabian and Lucas
Marriage in honey bees
Abbass
OptBees
Maia et al.
Paddy Field Algorithm
Premaratne et al.
Roach infestation algorithm
HavensQueen-bee evolution
Jung
Shuffled frog leaping algorithm
Eusuff and Lansey
Termite colony optimization
Hedayatzadeh et al.
Physics and Chemistry based algorithms
Big bang-big Crunch
Zandi et al.
Black holeHatamlou
Central force optimization
FormatoCharged system search
Kaveh and TalatahariElectro-magnetism optimization
Cuevas et al.
Galaxy-based search algorithm
Shah-Hosseini
Gravitational search
Rashedi et al.
Harmony search
Geem et al.
Intelligent water drop
Shah-Hosseini
River formation dynamics
Rabanal et al.
Self-propelled particles
Vicsek

4

Swarm intelligence based algorithms
Algorithm
Author
Accelerated PSO
Yang et al.
Ant colony optimization
DorigoArtificial bee colony
Karaboga and Basturk
Bacterial foraging
PassinoBacterial-GA Foraging
Chen et al.
Bat algorithm
Yang
Bee colony optimization
Teodorović and Dell’Orco
Bee system
Lucic and Teodorovic
BeeHive
Wedde et al.
Wolf search
Tang et al.
Bees algorithms
Pham et al.
Bees swarm optimization
Drias et al.
Bumblebees
Comellas and Martinez
Cat swarm
Chu et al.
Consultant-guided search
Iordache
Cuckoo search
Yang and Deb
Eagle strategy
Yang and Deb
Fast bacterial swarming algorithm Chu et al.
Firefly algorithm
Yang
Fish swarm/school
Li et al.
Good lattice swarm optimization
Su et al.
Glowworm swarm optimization
Krishnanand and Ghose
Hierarchical swarm model
Chen et al.
Krill Herd
Gandomi and Alavi
Monkey search
Mucherino and Seref
Particle swarm algorithm
Kennedy and Eberhart
Virtual ant algorithm
Yang
Virtual bees
Yang
Weightless Swarm Algorithm
Ting et al.
Other algorithms
Anarchic society optimization
Shayeghi and Dadashpour
Artificial cooperative search
Civicioglu
Backtracking optimization search Civicioglu
Differential search algorithm
Civicioglu

Reference
[67]
[56]
[55]
[57]
[33]
[28]
[45]
[59]
[14], [3][72], [76]
[19]
[43]
[26][80]
[42]
[1]
[41]
[48]
[25]
[30]
[18]
[27]

A ˚rk «ge in hi<ory
FISTER, YANG FISTER, BRES

[54]
[9]
[11]
[10]

[79]
[24]
[21]
[34]
[13]
[53]
[50]
[23]
[52]
[49]
[64]

Where are we now?

I Metaheuristics have lived up to

their promise: heavily used inreal-life systems
I Widespread agreement thatmetaheuristics are not recipes
I Still: not a lot of “solvers”, stilllargely an art

Where are we now?
Taxonomy of metaheuristics creates clarity
MHLocal Search

Randomness

MemoryConstructiveVNSEvolutionary

The future: the scientific period
I Growing up of the field of metaheuristics

as a science
Understanding the behavior ofmetaheuristics
I Adequate testing protocols
I Decomposition
I Knowledge > performanceI

I Development of powerful solvers todecrease development time
I A more natural language to formulate

optimization problems
I Availability of dedicated tools, including

exact methods and constraint
programmingA history of metaheuristics
Kenneth Sörensen, Marc Sevaux, Fred Glover
kenneth.sorensen@uantwerpen.be