The metaheuristic train a family of algorithms of optimization aiming at solving problems of difficult optimization (often resulting from the fields of the Operations research, Ingénierie or Artificial intelligence) for which one does not know more effective traditional method.

The métaheuristiques ones are generally iterative algorithms Stochastique S, which progress towards a total optimum, i.e. the total extremum of a function, by sampling of a function objective. They behave like algorithms of research, trying to learn how the characteristics from a problem in order to find an approximation of the best solution of it (in a way close to the algorithms of approximation).

There exists a great number of metaheuristic different, energy of the simple local research to complex algorithms of total research. These methods use an high level of abstraction however, enabling them to be adapted to a broad range of different problems.

General information

Terminologies

One speaks about méta , of the Greek “beyond” (to include/understand here “with more an high level”), heuristic , of the Greek ευρισκειν/ heuriskein , which means “to find”. Indeed, these algorithms want to be generic methods being able to optimize a broad range of different problems, without requiring deep changes in the algorithm employed.

A slightly different terminology considers that the méta-heuristic are the shape of algorithms of stochastic optimization, hybrids with a local research. The term méta is thus taken with the direction where the algorithms can gather several Heuristique S. One primarily meets this definition in the literature concerning the algorithms évolutionnaires, where it is used to indicate a specialization. Within the framework of the first terminology, a hybrid Algorithme évolutionnaire with a local research will be rather indicated under the term of algorithm memetic .

The métaheuristiques ones are often inspired by natural systems, which they are taken in Physique (case of the Recuit simulated), in Biologie of the evolution (case of the genetic algorithms) or in ethology (case of the algorithms of colonies of ants or of the Optimization by particulate swarms).

Nomenclature

The goal of métaheuristique is to solve a given problem of Optimization: she seeks a mathematical object (a Permutation, a Vecteur, etc) minimizing (or maximizing) a function objective , which describes the quality of a solution with the problem.

The whole of the possible solutions forms the space of research . The space of research is at least limited, but can be also limited by a whole of forced .

The métaheuristiques ones handle one or more solutions, with the research of the optimum , the best solution with the problem. The successive iterations must make it possible to pass from a solution of bad quality to the optimal solution. The algorithm stops after having reached a criterion of stop , generally consisting of the attack of the assigned execution time or of a required precision.

A solution or a whole of solutions is sometimes called a state , that the métaheuristique one makes evolve/move via transitions or movements . If a new solution is built starting from an existing solution, it is its close . The choice of the vicinity and the structure of data the representative can be crucial.

When a solution is associated with only one value, one speaks about problem mono-objective , when it is associated with several values, of problem multi-objectives (or multi-criteria ). In this last case, one seeks a whole of not dominated solutions (the “face of Pareto”), solutions among which one can decide if a solution is better than another, none not being systematically lower than the others on all the objectives.

In certain cases, the sought-after goal is explicitly to find a whole of “satisfactory” optima. The algorithm must then find the whole of the solutions of good quality, without necessarily limiting itself to the only optimum: one speaks about multimode methods .

General concepts

The métaheuristiques ones do not require particular knowledge on the problem optimized to function, the fact of being able to associate one (or several) values with a solution is the only necessary information.

In practice, they should be used only on problems not being able to be optimized by mathematical methods. Used instead of Heuristic S specialized, they generally show less good performances.

The métaheuristiques ones are often employed in optimization Combinatoire, but one also meets of it for continuous or mixed problems (problems with discrete and continuous variables ).

Certain metaheuristic are theoretically “convergent” under certain conditions. It is then guaranteed that the total optimum will be found in a finished time, the probability this of making increasing asymptotically with time. This guarantee amounts considering that the algorithm behaves at worst the like a pure random research (probability of trying all the solutions tending towards 1). However, the requirements are seldom checked within the framework of real applications. In practice, the principal condition of convergence is to consider that the algorithm is ergodic (that it can reach any solution with each movement), but one is often satisfied quasi - ergodicity (if the métaheuristique one can reach any solution in a finished number of movements).

General organization

Generally, the métaheuristiques ones are articulated around several concepts:

• Vicinity;
• Diversification/exploration;
• Intensification/exploitation;
• Memory and training.

Vicinity

The vicinity of a solution is a subset of solutions which it is possible to reach by a series of transformations given. Sometimes by extension one indicates by the term “vicinity” the whole of the transformations considered.

A simple vicinity for the Problème of the sales representative will be, for example, the whole of the solutions which it is possible to build by permuting two cities in a given solution.

The concept of vicinity is undoubtedly the general principle more used for the designs of heuristic. For the combinative problems, the vicinity has an significant impact on the behavior of the métaheuristiques ones, whereas for continuous problems, the concept even of vicinity is more difficult to encircle.

Although there only exists very little of theoretical results on the adequacy between a vicinity and a given discrete problem, it can be possible to calculate empirical indicators of them, like the roughness . The most traditional techniques concerning the definition of a vicinity turn around the concepts of Permutation S, of chains of ejections and partial optimizations.

Intensification, diversification, training

The diversification (or exploration, synonym used almost indifferently in the literature of the algorithms évolutionnaires) indicates the processes aiming at collecting information on the optimized problem. The intensification (or exploitation) aims at using information already collected to define and traverse the interesting zones of the Espace of research. The memory is the support of the training, which makes it possible the algorithm to hold account only zones where the total optimum is likely to be, thus avoiding the local optima.

The métaheuristiques ones progress in an iterative way, by alternating phases of intensification, diversification and training, or by mélant these concepts more closely. The starting state is often by chance selected, the algorithm proceeding then until a criterion of stop is reached.

The concepts of intensification and diversifications are dominating in the design of the métaheuristiques ones, which must reach a delicate balance between these two dynamic of research. The two concepts are thus not contradictory, but complementary, and there exist many strategies mélant at the same time one and the other of the aspects.

Classification

Course and population

Metaheuristic the most traditional is those founded on the concept of course. Accordingly, the algorithm makes evolve/move only one solution on the space of research to each iteration. The concept of Voisinage is then paramount.

Most known in this class are the Recuit simulated, the Recherche with taboos, the Recherche with variable vicinity, the method GRASP or the method of sound effects.

In this classification, the other approach uses the concept of population. The métaheuristique one handles a whole of solutions in parallel, with each iteration.

One can quote the genetic algorithms, the Optimization by particulate swarms, the algorithms of colonies of ants.

The border is sometimes fuzzy between these two classes. One can thus consider that a simulated annealing where the temperature drops by stages, has a structure with population. Indeed, in this case one handles a whole of points to each stage, it acts simply of a particular sampling procedure.

Use of memory

The métaheuristiques ones use the history of their research to guide optimization with the following iterations.

In the simplest case, they are limited to consider the state of research to an iteration given to determine the next iteration: it is then about a Markovian Decision-making process, and one will speak about method without memory . It is the case of the majority of the methods of local research.

Many metaheuristic use a more advanced memory, than it is on the short term (solutions visited recently, for example) or on the long run (memorizing of a whole of synthetic parameters describing research).

Function static or dynamic objective

The majority of metaheuristic use the function objective in the state, and make evolve/move their behavior of research of the optimum. However, certain algorithms, like the guided Local research, modify the representation of the problem, by incorporating the information collected during research, directly within the function objective.

It is thus possible to classify the métaheuristiques ones according to whether they use a static function objective (which remains unchanged throughout optimization) or dynamic (when the function objective is modified during research).

Many structures of vicinity

The majority of metaheuristic used within the framework of the problems of combinative optimization use only one structure of vicinity. However, of the methods as the Recherche with variable vicinity makes it possible to change structure in the course of research.

Implicit, clarifies, direct

By considering the métaheuristiques ones as iterative methods using an objective sampling of the function as training bases (definition more particularly adapted to metaheuristic to populations) appears the problem of the choice of sampling.

In the very large majority of the cases, this sampling is done on a random basis, and can thus be described via a Probability distribution. There then exist three classes the métaheuristiques ones, according to the approach used to handle this distribution.

The first class is that of the implicit methods , where the probability distribution is not known a priori . It is the case for example genetic algorithms, where the choice of sampling between two iterations does not follow a given law, but is function of local rules.

By opposition, one can thus classify the explicit methods , which use a selected probability distribution to each iteration. It is the case of the algorithms with estimate of distribution.

In this classification, simulated annealing occupies a particular place, since one can consider that it samples the function objective by directly using this one like probability distribution (best solutions having a larger probability to be drawn). It is thus neither explicit nor implicit, but rather “direct”.

Évolutionnaire or not

One finds sometimes a classification presenting the stochastic algorithms of optimizations as being “évolutionnaires” (or “evolutionists”) or not. The algorithm will be regarded as belonging to the class of the algorithms évolutionnaires if it handles a population via operators , according to a given general algorithm.

This way of presenting the métaheuristiques ones has an adapted nomenclature: one will speak operators for any action modifying the state about one or more solutions. An operator building a new solution will be called generating , whereas an operator modifying an existing solution is called mutateur .

Accordingly, the general structure of the algorithms évolutionnaires connects stages of selection , reproduction (or crossing ), of change and finally of replacement . Each stage uses more or less specific operators.

Taxonomy of hybridization

One speaks about hybridization when the métaheuristique one considered is made up of several methods being distributed the tasks of research. The taxonomy of the metaheuristic hybrids separates in two parts: a hierarchical classification and a classification punt . Classification is applicable to the deterministic methods as well as with the métaheuristiques ones.

Hierarchical classification is based on the level (low or high) of hybridization and on its application (out of relay or competitor). In a hybridization of low level , a function given of métaheuristique (for example, the change in an algorithm évolutionnaire) is replaced by another métaheuristique (for example a research with taboo). In the case of the high level , the “normal” inner working of metaheuristic is not modified. In a hybridization in relay , the métaheuristiques ones are launched the ones after the others, each one fascinating in entry the exit produced by the preceding one. In competition (or Co-evolution ), each algorithm uses a series of co-operating agents units.

This first classification releases four general classes:

• low level & relay (shortened LRH in English),
• low level & Co-evolution (shortened LCH ),
• high level & relay ( HRH ),
• high level & Co-evolution ( HCH ).

The second part releases several criteria, being able to characterize hybridizations:

• if hybridization is done between several authorities of same métaheuristique, it is homogeneous , if not, it is heterogeneous ;
• if the methods seek in all the space of research, one will speak about total hybridization , if they are limited to under-parts of space, of partial hybridization ;
• if the concerned algorithms work all to solve the same problem, one will speak about general approach , if they are launched on different problems, of hybridization specialized .

These various categories can be combined, hierarchical classification being most general.

Applications

The métaheuristiques ones are often employed for their facility of programming and handling. They are indeed easily adaptable to any type of problem of optimization. However, they are most judiciously employed on problems of difficult optimization , where more traditional methods of optimization (deterministic methods, in particular) show their limits.

In a general way, one can consider that problems showing the following characteristics are rather favourable with the use of metaheuristic:

• Np-complétude,
• many local optima,
• discontinuities,
• forced strong,
• not Dérivabilité,
• prohibitory time computing of the function objective,
• desired approximate solution,
• etc

Tests

To test métaheuristique, a first stage consists in using especially conceived mathematical functions. The algorithms are evaluated on the basis of whole of functions, more or less difficult, then compared between them.

The métaheuristiques ones being generally stochastic, the tests must in theory be repeated a great number of times, then exploited via methods Statistique S. Cependant, this practice remains relatively not very widespread in the specialized literature.

Real problems

In an special issue of the scientific magazine European Newspaper off Operational Research , devoted to the applications of metaheuristic, the editors noted that the majority of the 20 articles published were it in two fields: problems of Logistic scheduling and . The methods the most used belong to the family of the algorithms évolutionnaires, often hybrids with methods of Local research.

Some examples of concrete problems, optimized via the métaheuristiques ones:

• problems of turned of vehicles,
• optimization of Network X mobile UMTS,
• Management of the air traffic,
• optimization of the loading plans of the hearts of nuclear reactors,
• etc

Advantages and disadvantages

The métaheuristiques ones being very general practitioners, they can be adapted to any type of problem of optimization which can be reduced to a “block box”. They are often less powerful than exact methods on certain types of problems. They do not guarantee either the discovery of the total optimum in a finished time. However, a great number of real problems is not optimizable effectively by approaches purely Mathématiques, the métaheuristiques ones can then be used with profit.

The concept of effectiveness generally refers to two contradictory objectives: the Speed and the Precision. Speed is often measured of many evaluations of the function objective, which is most of the time the greediest part in computing times. The precision refers to the Distance between the optimum found by the métaheuristique one and the real optimum, either from the point of view of the solution, or of that of the value. Very often, a fast algorithm is not very precise, and conversely.

Generally, a choice must be made as for the criterion of adequate stop. A number of evaluation or an assigned time is often used, but one can also choose to reach a given value of the function objective (the goal being then to find a solution associated). It is also possible to choose criteria dependant on the behavior of the algorithm, like a minimal dispersion of the population of points or a suitable internal parameter. In any event, the choice of the criterion of stop will influence the quality of optimization.

The use of metaheuristic can appear relatively simple, in first approach, but it is often necessary to adapt the algorithm to the optimized problem. First of all, mainly within the framework of the combinative Optimization, the choice of the representation of the handled solutions can be crucial. Then, the majority of metaheuristic have parameters whose adjustment is not necessarily commonplace. Lastly, to obtain good performances generally passes by a stage of adaptation of the various stages of the algorithm (initialization, in particular). In practice, only the know-how and the experiment of the user make it possible to manage these problems.

It is allowed that, from a very general point of view, no métaheuristique is really better than another. Indeed, métaheuristique cannot claim to be more effective on all the problems, although some authorities (i.e. the algorithm him even, but also a choice of parameters and a given implementation) can be more adapted than of others on certain classes of problems. This observation is described by the theorem of the No free buffet (“not of dining free”).

In last analysis, it is sometimes possible that the choice of the representation of the solutions, or more generally of the methods associated with metaheuristic, has more influence on the performances than the type of algorithm itself. In practice, however, the métaheuristiques ones are shown more powerful than the methods of exhaustive course or purely random research.

Alternatives

List the métaheuristiques ones

Metaheuristic the most known is:

• the evolutionary algorithms, among which:
• the strategies of evolution,
• the genetic algorithms,
• the algorithms with differential evolution,
• the algorithms with estimate of distribution,
• the artificial immune systems,
• the recombining of way (Path relinking in English)
• the Reheated simulated,
• the algorithms of colonies of ants,
• algorithms of Optimization by particulate swarms,
• the Research with taboos,
• the method GRASP.

There exists a very great number of other metaheuristic, more or less known:

• the Algorithm of the kangaroo,
• the Method of Fletcher and Powell,
• the Method of the sound effects,
• the stochastic Tunnelisation,
• the Climbing of hills with random restartings,
• etc

Research in the field being very active, it is impossible to produce an exhaustive list of different metaheuristic from optimization. Specialized literature watch a great number of alternatives and hybridizations between methods, particularly in the case of the algorithms évolutionnaires.

History

• 1952 : the first work on the use of stochastic methods for optimization.

• 1954: Barricelli carries out the first simulations of the process of evolution and uses them on general problems of optimization.
• 1965: Rechenberg designs the first using algorithm of the strategies of evolution .
• 1966: Fogel, Owens and Walsh propose the Programmation évolutionnaire .
• 1970: Hastings proposes the Algorithme of Metropolis-Hastings, making it possible to sample import-which probability distribution.
• 1970: John Horton Conway conceives the Jeu of the life, the cellular Automate most known to date.
• 1975: working on the cellular automats, Holland proposes the genetic first algorithms .
• 1980: Smith uses the genetic Programmation.
• 1983: being based on work of Hastings, Kirkpatrick, Gelatt and Vecchi conceive the Recuit simulated .
• 1985: independently of those, Černý proposes the same algorithm.
• 1986: The first mention of the term méta-heuristics is made by Fred Glover, when designing Recherche taboo :

Research with taboo can be seen like a " méta-heuristique" , superimposed on another heuristics. The approach aims at avoiding the local optima by a strategy of prohibition (or, more generally, of penalization) of certain movements.

• 1986 : Farmer, Packard and Perelson work on the artificial immune systems .
• 1988: the first conference on the genetic algorithms is organized with the university of Illinois with Urbana-Champaign.
• 1988: work on the collective behavior of the ants finds an application in Artificial intelligence.
• 1988: Koza deposits its first patent on the genetic programming.
• 1989: Goldberg publishes one of the most known books on the genetic algorithms.
• 1989: Evolver , the first software of optimization by genetic algorithms is published by the company Axcelis .
• 1989: the term Algorithme memetic appears.
• 1990: The algorithms of colony of ants are proposed by Marco Dorigo, in its thesis of doctorate.
• 1993: the term “Evolutionary Computation” (Calculation évolutionnaire in French) is spread, with the publication of the review éponyme, published by the Massachusetts Institute off Technology.
• 1995: Feo and Resende propose the method GRASP (for Greedy randomized adaptive search procedure , “procedure of adaptive random avid research” in French).
• 1995: Kennedy and Eberhart conceive the Optimization by particulate swarms .
• 1996: Mühlenbein and Paaß propose the algorithms with estimate of distribution .
• 1997: Storn and Price propose a Algorithme with differential evolution.
• 1997: Rubinstein conceives the method of the cross entropy.
• 1999: Boettcher proposes the Optimization extrêmale.
• 2000: first interactive genetic algorithms.

Extensions

The métaheuristiques ones, of share their nature flexible, lend themselves particularly to extensions. One can thus find adaptations for problems more complex than optimization mono-objective:

• problems multi-objectives (several contradictory objectives must be optimized in concert),
• multimode optimization (several optima must be found),
• optimization in dubious environment (a noise is present on the value returned by the function objective, or on the passage of the parameters to this one),
• hybridizations between metaheuristic,
• hybridizations with exact methods,
• dynamic problems (the function objective changes during the time of optimization),
• management of strongly non-linear constraints,
• combination of the preceding problems,
• etc

References

Sources

• Jacques Teghem and Marc Pilrot (editors), Optimization approached in operations research , Hermes, treated I2C, May 2002. ISBN 2746204622
• Yann Colette, Patrick Siarry, Optimization multi-objective , ED. Eyrolles, Paris, 2002, Stitched, 322 pages, ISBN 2-212-11168-1.
• Johann Dréo, Alain Petrowski, Eric Taillard, Patrick Siarry, Métaheuristiques for difficult optimization, French, ED. Eyrolles, Paris, September 2003, Stitched, 356 pages, ISBN 2-212-11368-4.
• Pierre Collet, Jean-Philippe Fox, Introduction to Stochastic Optimization Algorithms , in Handbook off Research one Nature-Inspired Computing for Economics and Management , published by J. - P. Fox, IDEA Group Inc, September 2006, Connected, 1100 pages, ISBN 1591409845.
• Christian Blum, Andrea Roli, Metaheuristics in combinatorial optimization: Overview and conceptual comparison , ACM Computing Surveys, volume 35, number September 3rd, th and th 2003, pages 268-308.

More

Bibliography:

• Bibliography of introduction to metaheuristic (2003) the

Sites general practitioners:

• EU/ME, the european chapter one metaheuristics
• Metaheuristic network

Software and Framework S:

• selected List of software for the development metaheuristic (2006)

Random links:

Saint-Aubin (Indre) | Count of the characters Unicode (34000-34FFF) | Thomas de Brotherton | Bielorussia-Russia in football | Stephan Célérier