10
$\begingroup$

  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!

|cite|improve this question
$\endgroup$
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tim May 4 '12 at 13:36
  • $\begingroup$ @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. $\endgroup$ – Arnold Neumaier May 4 '12 at 14:40
  • $\begingroup$ Thanks! I wonder if metaheuristic only makes use of function values and is derivative free? $\endgroup$ – Tim May 4 '12 at 16:41
  • $\begingroup$ @Tim: Probably yes; I don't know of anything actually called metaheuristic that uses gradients. $\endgroup$ – Arnold Neumaier May 4 '12 at 17:50
7
$\begingroup$

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.

Here is a good link if you want to read more about some other metaheuristic techniques

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! I am not sure I understand "A heuristic is a pretty good rule. A metaheuristic is a pretty good rule for finding pretty good rules." For example, are Simulated annealing, particle swarm, ant colony and tabu search heuristic or metaheuristic? If they are one of the two, what are their counterparts for the other? $\endgroup$ – Tim May 4 '12 at 17:07
  • $\begingroup$ What you should understand from this quote is that both heuristics and metaheuristics are not exact nor proved, thus "pretty good rule". A metaheuristic is at a higher level than a heuristic, and it's through several successive iteration that you can find a set of parameters that will solve a problem correctly. If you knew what this set of parameters was from the beginning, you would just have to write a heuristic to solve the problem. But since you don't know, you have to use an algorithm to find these parameters for your heuristic: a metaheuristic. Hope that clarifies. $\endgroup$ – Charles Menguy May 4 '12 at 17:11
  • $\begingroup$ And the algorithms I gave here are all metaheuristics, and you can find more details on the link I gave. I'm not sure exactly what you mean for counterparts. $\endgroup$ – Charles Menguy May 4 '12 at 17:12
  • $\begingroup$ By counterparts, I mean, for example, if the algorithms are all metaheuristics, then the heuristics that they operate on must be themselves plus specific values for their adjustable parameters? $\endgroup$ – Tim May 4 '12 at 17:13
  • $\begingroup$ Take for example simulated annealing. What it does in the end is a search on a Markov chain. The heuristic's "rule" would be to assume that a state in the Markov chain is the solution. What the metaheuristic does is it will look for convergence in the Markov chain to find the optimal state which describes the solution. In general I think you shouldn't try too hard to make the distinction: use heuristics when there is a "relatively" simple solution that can be easily computed, and use metaheuristics when the solution space is too large and you need to be smarter about solving the problem. $\endgroup$ – Charles Menguy May 4 '12 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.