Meaning of (meta)heuristic methods

1. For optimization, from Wikipedia:

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.

• I wonder how to tell whether an optimization method is metaheuristic or not? For example,

(1) Is the simplex method for linear programming metaheuristic?

(2) Are the majority of nonlinear programming methods such as gradient descent, Lagrangian multiplier method, penalty methods, Interior point methods (barrier methods), metaheuristic?

(3) Are all gradient-free methods, such as Nelder–Mead method or downhill simplex method, metaheuristic?

• What are some optimization methods that are not metaheuristic?

2. More generally (going beyond optimization) for problem solving techniques, from Wikipedia:

Heuristic refers to experience-based techniques for problem solving, learning, and discovery. Where an exhaustive search is impractical, heuristic methods are used to speed up the process of finding a satisfactory solution. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgment, or common sense.

In more precise terms, heuristics are strategies using readily accessible, though loosely applicable, information to control problem solving in human beings and machines.

I wonder how to understand the meaning of "heuristic"?

• how can I tell whether a "problem solving,learning, and discovery" technique is heuristic or not?

• What are some "problem solving,learning, and discovery" techniques that are not heuristic?

Thanks and regards!

Heuristic is something that works in many cases in practice, though there is no detailed argument for why it should work well.

Metaheuristics is not an algorithm but a general heuristic scheme or idea that can be used inside specific algorithms.

For example, the simplex algorithm for linear programming is neither heuristics nor metaheuristics, as it has a well-established convergence theory. The sqame holds for sequential quadtatic programming or interior point methods. (Interior point methods are a general scheme, but not heuristic and hence not a metaheuristics, as there is a quite strong theory associated with it.)

The Nelder-Mead = downhill simplex algorithm for minimizing a function is heuristics (it actually may fail on quite simple problems in higher dimensions), and tabu search is metaheuristics (as quite a lot of diverse algorithms can be written that employ tabu search, but are otherwise of quite different quality.

• Thanks! (1) So to tell whether a method is metaheuristic, is to see if it has a theory regarding to when it converges to the true optimizer? If a method doesn't have such a theory yet, then is it meatheuristic? If one day there is a theory for it, will it become from metaheuristic to non-metaheuristic? (2) "Other terms having a similar meaning as metaheuristic, are: derivative-free, direct search, black-box, or indeed just heuristic optimizer." I wonder if metaheuristic only makes use of function values and is derivative free? Is it "search" method in your reply to my another question? – Tim May 4 '12 at 13:36
• @Tim: metaheuristic means: (i) no convergence theory, and (ii) no definite recipe for proceeding but rather general principles. - derivative-free (= direct search = black box; different names for the same from different historical roots) can be heuristic or not; it just tells about the input that the user must provide. – Arnold Neumaier May 4 '12 at 14:40
• Thanks! I wonder if metaheuristic only makes use of function values and is derivative free? – Tim May 4 '12 at 16:41
• @Tim: Probably yes; I don't know of anything actually called metaheuristic that uses gradients. – Arnold Neumaier May 4 '12 at 17:50

I won't iterate over simplex and Nelder-Mead since @ArnoldNeumaier gave already a very good explanation, but wanted to add my 2 cents.

One of the best quote I've heard some time ago to describe the difference between heuristic and metaheuristic: A heuristic is a pretty good rule. A metaheuristic is a pretty good rule for finding pretty good rules.

You should just see it as a way to find good heuristics for specific problems; basically if you ask yourself one of the following questions you are talking about a metaheuristic:

• How should I tweak the parameters of this heuristic to improve performance on that problem?
• Is this heuristic better than that heuristic?

There is a bunch of metaheuristics you can use for problem solving,learning, and discovery, namely:

I find that most metaheuristics are somewhat inspired by natural phenomenons, which are hard to rigorously explain, but have good convergence properties.