49

After some research about algorithms I found two terms which confuses me. I've read at least 20 papers and yet, there aren't any clear definition about either. I hope someone can help me tell the difference between heuristics and metaheuristics algorithms. And if possible, add the source of it.

ps: I already know what the meaning is of the words, but I don't know what the exact difference is between them in computer science.

thanks in advance

3
  • It really depends on context. Heuristics are useful rules that approximate the perfect answer/behavior. Without context, adding meta on to it doesn't give it any special meaning, it just means that it's meta, i.e. heuristics about heuristics. May 4, 2012 at 9:00
  • This is in the context of algorithms
    – Nico Liu
    May 4, 2012 at 9:21
  • 2
    It still depends on context, in a way that means you will never get a straight answer, because they are not straightly defined. In AI circles, a heuristic is a "good guess" function used as a building block of a larger (usually search) algorithm. A meta-heuristic is sort of a "good guess" system in itself that keeps refining its guesses. But that's just my take-- these things are so undefined that even papers doing comparative evaluations of heuristics vs meta-heuristics either don't define, or offer only loose definitions. Basically, you know one when you see one.
    – Novak
    May 6, 2012 at 1:34

3 Answers 3

78

You could think of a heuristic like an approximate (not approximation) solution to a problem. The difference between approximate and approximation is that the first is about getting a good guess of the solution of a problem, but that you don't really know how good it is. The second is about getting a solution for which you can prove how close it is to the optimal solution.

So, heuristics are often problem-dependent, that is, you define an heuristic for a given problem. Metaheuristics are problem-independent techniques that can be applied to a broad range of problems. An heuristic is, for example, choosing a random element for pivoting in Quicksort. A metaheuristic knows nothing about the problem it will be applied, it can treat functions as black boxes.

You could say that a heuristic exploits problem-dependent information to find a 'good enough' solution to a specific problem, while metaheuristics are, like design patterns, general algorithmic ideas that can be applied to a broad range of problems.

8
  • 2
    Do you also have a source about this?
    – Nico Liu
    May 9, 2012 at 7:58
  • 3
    There is a great introductory book on meta-heuristics by El-Ghazali Talbi. It states more or less this same opinion in the introduction. Check it out. May 10, 2012 at 15:27
  • So, since what you said, NSGAII is a meta-heuristic algorithm since it could be applicable to many problems even with my own complex problem, but if i write my own algorithm exploiting my own complex problem's information, it means that is an heuristic algorithm? Have I got the meaning and differences? (Sorry for bad English)
    – Aerox
    Jun 10, 2015 at 15:43
  • 1
    @Aerox, NSGAII is a variant on genetic algorithms, hence generally problem-independent. As Touki said, a specific implementation of a meta-heuristic (as opposed to the abstract implementation found in a book) is also a meta-heuristic, even if you have to make decisions related to representation, cost functions, etc., which are often problem-dependent. Still, in this cases, you are "instancing" a meta-heuristic in your own problem, like filling a template. The difference is that you are not exploiting information specific to the structure of the problem to design a one time solution. Jun 11, 2015 at 16:29
  • 1
    @Aerox, not sure if I understand your statement. If the algorithm exploits information (either implicit or explicit) about the structure of the problem that is not common to a broad range of (optimization) problems, then its a specific heuristic. As I said before, differences are subtle and the border is rather blurry. Jun 12, 2015 at 20:55
14

In order to give a proper quotation, relative to Alejandro answer:

« A metaheuristic is a high-level problem-independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms [...] A problem-specific implementation of a heuristic optimization algorithm according to the guidelines expressed in a metaheuristic framework is also referred to as a metaheuristic » (Sörensen, Glover on http://scholarpedia.org/article/Metaheuristics)

To be fully complete. We should distinguish between exact, approximate and heuristics algorithms. An exact algorithm finds an exact solution. An approximate algorithm should find an approximate solution, within an acceptable time, as well as indicate its discrepancy range with the supposed optimal solution. An heuristics simply find a good-enough solution, within an acceptable time.

By the way, Alejandro quicksort's example does not appear fully adequate for two or three different reasons.

  1. In fact, heuristics and metaheuristics are part of optimization's field. The problem they try to tackle is therefore of searching an optimum, not of sorting.
  2. Heuristics are generally use when the problems you want to tackle is too complex, in the computational sense - which is not the case of sorting problem.
  3. What was pointed at through the quicksort example, if I understand it well, is the random element. In principle, you can have deterministic heuristics - I never encountered a deterministic metaheuristics, but probably one could code it. It might be a bit "playing with words" but, the random element more properly characterizes "stochastic search" than (meta)heuristics.
4
  • 1
    Hum, i think A star is a possible deterministic heuristics ?
    – reyman64
    Jan 30, 2015 at 10:22
  • 1
    @Touki, +1 for your insightful additions. Just want to point that, even if a constipated example, you can formulate sorting as finding the permutation that minimizes the number of inversions. With that formulation, you can apply any combinatorial meta-heuristic (say, GAs or SA) to solve it. Of course, Quicksort would work much better because it exploits the problem structure. In this sense, maybe Quicksort itself can be considered an heuristic for the problem of sorting. I know, it's not a useful formulation in practice, but serves the purpose of pointing the differences. Jun 11, 2015 at 16:34
  • As a side, see Nelder-Mead as an example of an algorithm that IMHO can be considered a meta-heuristic (broad applicability to a wide range of black box optimization problems), and its completely deterministic. Is heuristic because, contrary to say, the Simple method it doesn't guarantee to converge to the global optimum. Dec 21, 2016 at 10:37
  • "The problem they try to tackle is therefore of searching an optimum, not of sorting." That is it! Good answer! It should be marked as the solution for this problem. Aug 10, 2022 at 15:10
6

For a detailed explanation, see:

Sörensen, K. (2015). Metaheuristics—the metaphor exposed. International Transactions in Operational Research, 22(1), 3-18.

A metaheuristic is a high-level problem-independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. The term is also used to refer to a problem-specific implementation of a heuristic optimization algorithm according to the guidelines expressed in such a framework (Sörensen, 2015).

The heuristics are the guidelines, metaheurstics is the framework that uses those.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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