Subject: Metaheuristics: origin and definition

From: "J.K. Hao" <[email-masked]>
Date: Tue, 20 Jul 1999 16:00:23 +0200

Dear Colleagues and Friends,

Following my last posting about the origins and definition of the
word "metaheuristics", many colleagues and friends have taken
time to answer me. Thanks a lot.

It seems that the question interests many people, so
I'd like to write a short note on the topic, but before that,
I compiled in this mail the answers I received (sorry if I forget
anything).

Best regards,

ATTENTION: New address from 1st September 1999
_________________________________________________________
Prof. Jin-Kao Hao
LERIA, Universite d'Angers, U.F.R Sciences, 2 Bd. Lavoisier,
49045 Angers, France
email: [email-masked] or [email-masked]
http://www.site-eerie.ema.fr/~hao/group.html
_________________________________________________________

**********************************************************
Glover Fred wrote:

> Jin-Kao,
>     I fear I am the culprit in originating the term "metaheuristics".  For
> background and a rough attempt to explain the term, see the discussion of
> metaheuristics in the first chapter of the book Tabu Search by Manuel
> Laguna and me (Kluwer Academic Publishers).  Originally, it was written
> "meta-heuristics" (and still sometimes is).
>     But as usual, such things grow well beyond their origins, and the
> remarkable deluge of innovative work over the last decade or so has been
> responsible for putting the area "on the map".  So, independent of the
> happenstance of coining the term, the field itself has been invented by
> many.
>     Fred

Pablo Moscato -D- wrote:

> Dear Jin-Kao,
> (with copy to Fred Glover)
>
> By large the word ``metaheuristic'' got acceptance due to the work of Fred
> Glover. I believe I have first heard it from him. The formal definition
> might be ``a top-level strategy that guides an underlying ad-hoc heuristic
> for a giving problem''. For instance, Tabu Search is a metaheuristic,
> since it guides a basic local search heuristic. Since the neighborhood
> definition is ad-hoc designed, it fits well the defintion above. Same for
> memetic algorithms.
>
> Both the words ``metaheuristics'' and ``memetic algorithms'' have been
> entered the ``on-line dictionary on computing''. I recall a similar
> discussion we had with David Johnson and Fred Glover two years ago.
>
> I do not know when Fred used the term for the first time. I believe I have
> also seen it in the following reference, but I can not recall if it refers
> to the same thing.
>
> LANGUAGE AND A PROGRAM FOR STATING AND SOLVING COMBINATORIAL PROBLEMS
> J.L. LAURIERE, ARTIFICIAL INTELLIGENCE, 10: (1) 29-127 1978
>
> Best wishes,
>
> Pablo

"J.K. Hao" wrote:

> Dear Pablo,
>
> Thank you for your answer.
>
> I checked J-L. Lauriere's AI 78 paper. He used the
> word "metaheuristics" two times (pp 31 and 62),
> but in a context different from that of Fred Glover.
>
> Best regards,
>
> Jin-Kao

Eric Taillard wrote:

> Cher Jin-Kao,
>
> Les questions que vous posez sont interessantes et, ayant
> travaille dans le domaine depuis longtemps, je vais essayer d'y
> repondre.
>
> Je ne sais pas exactement qui a propose pour la premiere fois le
> terme de "meta-heuristique", mais je pense que le terme a du etre
> invente pour la "Meta-Heuristics International Conference (MIC)"
> qui s'est tenue a Breckenridge (Colorado, USA) du 22 au 26
> juillet 1995.
>
> Dans le volume qui est paru a l'issue de cette conference
> (Meta-heuristics: Theory & Applications, edite par I. H. Osman,
> J.P. Kelly, Kluwer, 1996) on trouve une definition des
> meta-heuristiques (que je ne partage PAS):
>
> "A meta-heuristic is an iterative generation process which guides
> a subordinate heuristic by combining intelligently different
> concepts for exploring and exploiting the search spaces using
> learning strategies to structure information in order to find
> efficiently near-optimal solutions"
>
> En effet, pour moi, cette definition est a la fois trop vague
> (que veut dire "intelligemment", "exploitation de l'espace de
> recherche", "presque optimales") et trop restrictive (pourquoi
> une meta-heuristique devrait etre iterative, basee sur un
> strategie d'apprentissage). Par exemple le recuit simule ne
> serait pas une meta-heuristique selon cette definition car il ne
> s'agit pas d'un processus d'apprentissage (au contraire,
> puisqu'il peut etre represente comme un processus markovien!)
>
> Pour moi, une heuristique est une methode, concue pour un
> probleme generique d'optimisation donne, qui produit une solution
> non necessairement optimale lorsqu'on lui fournit des donnees
> correspondant a un exemple de ce probleme.
>
> Une meta-heuristique peut etre definie de maniere similaire, mais
> d'un niveau d'abstraction plus eleve: Une meta-heuristique est un
> ensemble de concepts, concus pour l'optimisation combinatoire,
> qui permettent d'aider a la conception de methodes heuristiques
> pour un probleme generique d'optimisation.
>
> En quelque sorte on a le schema suivant:
>
>                  Heuristique            Meta-heuristique
>
> Domaine          Un probleme generique  Optimisation
> d'application:   d'optimisation         combinatoire
>
> "Fonctionnement" Un algorithme          Un ensemble de concepts
>
> Donnees          Un exemple de          Un probleme
>                  probleme               generique
>
> Resultat         Une solution           Une heuristique
>                  approchee
>
> J'espere ainsi avoir quelque peu contribue a clarifier le terme
> de meta-heuristique. Je serais tres interesse par connaitre les
> diverses reponses que l'on vous aura faites!
>
> Meilleures salutations,
>
> ----------------------------------------
> Eric Taillard
> IDSIA, Corso Elvezia 36, 6900 Lugano, Switzerland.
> [email-masked]
> http://www.idsia.ch/~eric

Stefan Voss wrote:

> Dear Colleagues and Friends,
>
> Concerning the discussion on meta-heuristics please find here a statement from
>
> the recent meta-heuristics book, which is a second in a row (see the
> references below).
>
> Best regards
> Stefan
>
> A meta-heuristic is an iterative master process that guides
> and modifies the operations of subordinate heuristics to efficiently produce
> high-quality solutions. It may manipulate a complete (or incomplete) single
> solution
> or a collection of solutions at each iteration. The subordinate heuristics
> may be high (or low) level procedures, or a simple local search, or just a
> construction method. The family of meta-heuristics includes, but is not
> limited
> to, adaptive memory procedures, tabu search, ant systems, greedy randomized
> adaptive search, variable neighborhood search, evolutionary methods,
> genetic algorithms, scatter search, neural networks, simulated annealing, and
> their hybrids.
>
> Meta-heuristics provide decision-making managers with robust tools that
> obtain high-quality solutions, in reasonable time horizons, to important
> applications in business, engineering, economics and science. Finding exact
> solutions in these applications still poses a real challenge despite the
> impact of
> recent advances in computer technology and the great interactions between
> computer science, management science / operations research and mathematics.
>
> S. Voss, S. Martello, I.H. Osman and C. Roucairol (eds.)
> Meta-Heuristics:Advances and Trends in Local Search Paradigms for
> Optimization,
> Kluwer Academic Publishers, Boston, 1999.
>
> I.H. Osman and J.P. Kelly (eds.), Meta-Heuristics: Theory & Applications,
> Kluwer Academic Publishers, Boston, 1996.
>
> ***************************************************
> Prof. Dr. Stefan Voss
> Technische Universitaet Braunschweig
> Institut fuer Wirtschaftswissenschaften
> Abteilung Allg. BWL, Wirtschaftsinformatik
> und Informationsmanagement
> Abt-Jerusalem-Str. 7, D-38106 Braunschweig, Germany
> Tel.: +49 / 531 391 3210 ,  FAX: +49 / 531 391 8144
> e-mail: [email-masked]
> http://www.winforms.phil.tu-bs.de/winforms/
> http://www.winforms.phil.tu-bs.de/winforms/staff/svoss/svoss.html

***************************************************

Harvey Greenberg wrote:

> Fred Glover invented the term.  See the Mathematical Programming Glossary
> at http://www.cudenver.edu/~hgreenbe/
>
> Thanks,
> Harvey
> [email-masked]
> http://www.cudenver.edu/~hgreenbe/

> Andy Connor wrote:

> Try the following references;
>
> An Introduction to Metahuristics
> I H Osman
> Operational Research Tutorial Papers 1995, pp 92-122
>
> Metaheuristics: A Bibliography
> I H Osman & G Laporte
> Annals of operational Research, Vol 63, 1996, pp513-628
>
> Regards,
>
> Andy Connor
> Research Associate, Cambridge Engineering Design Centre
> http://www.cus.cam.ac.uk/~amc50/home.html

Rafael Marti wrote:

> Dear colleague,
>
> In the book "Meta-Heuristics:Theory and Applications" edited by Osman and
> Kelly (Kluwer academic publishers) the first paper is an overview of these
> methods and includes a definition of metaheuristics.
>
> Regards,
>
> Rafael Marti
> Dpto de Estadistica e I.O.
> Universidad de Valencia
> SPAIN
> tel. 3864314 / fax 3864735
> [email-masked]
> http://www.uv.es/~rmarti
>

Luis Cavique wrote:

> Dear Hao
>
> +ACI-The meta-heuristic term was coined in the same paper that introduced the
> term tabu search (Glover 1986) and has come widely applied in the
> literature...+ACI- in the book Tabu Search, Fred Glover and Laguna 1997, page
> 17.
>
> regards
> Luis  Cavique
>
> Prof. Adjunto EST- IPS     lcavique+AEA-est.ips.pt
> EST -  Instituto Politecnico de Setubal
> Rua Vale de Chaves,  Estefanilha
> 2910 SETUBAL  PORTUGAL
> tel.351 (65) 790000       http://www.est.ips.pt/
>
> PhD Student  IST-UTL  p1184+AEA-alfa.ist.utl.pt
> CESUR - Instituto Superior Tecnico
> Av. Rovisco Pais
> 1000 LISBOA   PORTUGAL
> tel.351 (1) 8418394       http://www.ist.utl.pt/

CHELOUAH Rachid wrote:

> Bonjour Mr Jin-Kao Hao,
>
> pour l'origine du mot metaheuristic :
>
> Le mot "heuristique" vient du grec heurein (découvrir) et qualifie tout ce
> qui sert à la découverte, à l'invention et à la recherche.
>
> j'espere que j'ai repondu a votre question
>
> Cordialement
>
> Rachid CHELOUAH
>
>  +----------------------------------------------------------+
>    Laboratoire Modélisation et Optimisation des Systèmes en Electronique
>    Département GENIE ELECTRIQUE ET INFORMATIQUE INDUSTRIELLE
>    rue d'Eragny, Neuville sur Oise,
>    95031 CERGY-PONTOISE, FRANCE
>    Phone:           +33 1 01 34 25 69 23
>    Fax:             +33 1 01 34 25 69 20
>    E-mail:          [email-masked]
> +----------------------------------------------------------+
>