Metaheuristic

Metaheuristic

From Wikipedia, the free encyclopedia
  (Redirected from Heuristic algorithm)
Jump to: navigation, search

In computer science, metaheuristic designates a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. Metaheuristics make few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. However, metaheuristics do not guarantee an optimal solution is ever found. Many metaheuristics implement some form of stochastic optimization.

Other terms having a similar meaning as metaheuristic, are: derivative-free, direct search, black-box, or indeed just heuristic optimizer. Several books and survey papers have been published on the subject.[1][2][3][4][5][6][7]

Contents

[hide]

Different classifications of metaheuristics.

Metaheuristics are used for combinatorial optimization in which an optimal solution is sought over a discrete search-space. An example problem is the travelling salesman problem where the search-space of candidate solutions grows more than exponentially as the size of the problem increases, which makes an exhaustive search for the optimal solution infeasible. Additionally, multidimensional combinatorial problems, including most design problems in engineering such as form-finding and behavior-finding, suffer from the curse of dimensionality, which also makes them infeasible for exhaustive search or analytical methods. Popular metaheuristics for combinatorial problems include simulated annealing by Kirkpatrick et al.,[8] genetic algorithms by Holland et al.,[9] ant colony optimization by Dorigo,[10] scatter search[11] and tabu search[12] by Glover.

Metaheuristics are also used for problems over real-valued search-spaces, where the classic way of optimization is to derive the gradient of the function to be optimized and then employ gradient descent or a quasi-Newton method. Metaheuristics do not use the gradient or Hessian matrix so their advantage is that the function to be optimized need not be continuous or even differentiable. Popular metaheuristic optimizers for real-valued search-spaces include particle swarm optimization by Eberhart and Kennedy,[13] differential evolution by Storn and Price[14] and evolution strategies by Rechenberg[15] and Schwefel.[16]

Metaheuristics based on decomposition techniques have also been proposed for tackling hard combinatorial problems of large size.[17]

Timeline of main contributions.

Many different metaheuristics are in existence and new variants are continually being proposed. Some of the most significant contributions to the field are:

Mathematical analyses of metaheuristics have been presented in the literature, see e.g. Holland’s schema theorem[9] for the genetic algorithm, Rechenberg’s work[15] on evolution strategies, the work by Trelea,[59] amongst others, for analysis of particle swarm optimization, and Zaharie[60] for analysis of differential evolution. These analyses make a number of assumptions in regard to the optimizer variants and the simplicity of the optimization problems which limit their validity in real-world optimization scenarios. Performance and convergence aspects of metaheuristic optimizers are therefore often demonstrated empirically in the research literature. This has been criticized in the no free lunch set of theorems by Wolpert and Macready,[41] which, among other things, prove that all optimizers perform equally well when averaged over all problems. The practical relevance of the no free lunch theorems however is minor, because they will generally not hold on the collection of problems a practitioner is facing.

For the practitioner the most relevant issue is that metaheuristics are not guaranteed to find the optimum or even a satisfactory near-optimal solution. All metaheuristics will eventually encounter problems on which they perform poorly and the practitioner must gain experience in which optimizers work well on different classes of problems.

See also

Metaheuristic methods are, generally speaking, sub-fields of:

Sub-fields of metaheuristics include:

Other fields of interest:

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>