1
$\begingroup$

I have a general question: Is random search a heuristic or a metaheuristic. Actually, as far as I understand, metaheuristics define a general principle to approximately solving an optimization problem that is applicable to a big variety of problems. Thus, I would infer, that random search is also a metaheuristic, as it can be applied to (almost?) every optimization problem. I would argue that in a nuthshell, it is not really different from evolutionary algorithms or particle swarm optimization. All of the don't make use of problem-specific characteristics as a heuristic usually does.

Edit: By random search I am refering to a method that just randomly samples a fixed number of points in the solution space and at the end uses the best solution after evaluating all those solutions.

What is your take on this?

Improve this question
$\endgroup$
8
  • $\begingroup$ What do you mean with random search? Just choosing a random solution from a pre-defined neighborhood structure? $\endgroup$
    – PeterD
    Jun 6 at 15:46
  • $\begingroup$ @PeterD: Thanks Peter for the good remark. I edited my question to describe what I mean by random search $\endgroup$
    – PeterBe
    Jun 6 at 15:48
  • 2
    $\begingroup$ I would vote for metaheuristic. $\endgroup$
    – prubin ♦
    Jun 6 at 15:51
  • $\begingroup$ I would also vote for metaheuristic since this logic can be applied to a broad range of optimization problems. However, I would not agree on your statement that they are not really different from evolutionary algorithms and PSO. There is a reason why these algorithms give SOTA results for some problems, something that would be hardly (or most often not) achievable by just randomly searching in the solution space. $\endgroup$
    – PeterD
    Jun 6 at 16:05
  • 2
    $\begingroup$ @fontanf True, but I think etymology prevails: heuristics are specific to a given problem, metaheuristics are generic (hence "meta"). In which case I agree with prubin. $\endgroup$
    – Kuifje
    Jun 6 at 20:56

1 Answer 1

Reset to default
3
$\begingroup$

I think the answer depends on what school you belong to. I've heard many define metaheuritics as generic heuristics in the sense that they can be applied to a broad range of optimization problems. In the way I was taught, however, metaheuritic are algorithms built on top of heuristics. These heuristics can be generic or problem specific, typically parameterized and often randomized, but all have in common that they take some input and produce a single solution. The job of the metaheuristic is then to iteratively select which heuristic to run (e.g., one that constructs a new solution, or one that combine/improve old) and which data to input (e.g., updating pseudo-costs, tabu lists or probability distributions) to strike a balance between climbing local peaks (local optimization) and not being caught in the neighborhood of one forever (diversification).

In this perspective, your description of random search is perhaps the simplest possible metaheuristic in existence as it only uses one heuristic (constructive random selection) and reruns it repeatedly where only the internal state of the random number generator changes from run to run. In some sense it represent an extreme in the metaheuristic space of algorithms with 100% diversification and 0% local optimization. Simplistic as it is, however, it is guaranteed to find the optimal solution in finite time if the solution space is finite, which is a theoretical property often sought in metaheuristics.

Improve this answer
$\endgroup$
13
  • $\begingroup$ Thanks Henrik for your answer (I upvoted it). The other question I have is what is the differece between a local optimization method (like gradient descent and newton method) and a (meta)heuristic. Actually the heuristic also finds the local optimum. Is it actually the randomness that makes a heuristic not being labeled as a local optimizaiton method? $\endgroup$
    – PeterBe
    Jun 7 at 9:21
  • 1
    $\begingroup$ I think you will find it helpful to read the answers to or.stackexchange.com/questions/709/… $\endgroup$
    – Henrik Alsing Friberg
    Jun 8 at 7:09
  • $\begingroup$ @Hendrik: Thanks Hendrik for your answer. Any comment about my other question about the differece between a local optimization method (like gradient descent and newton method) and a (meta)heuristic. The link does not answer this question as far as I see. $\endgroup$
    – PeterBe
    Jun 28 at 8:07
  • 1
    $\begingroup$ Exactly. Newton-type methods are not exact algorithms for non-convex problems, but as I said, they can be exact methods for other types of problems (e.g., strongly convex) depending on implementation details (see, e.g., this list of failure scenarios that needs to be addressed). $\endgroup$
    – Henrik Alsing Friberg
    Jul 6 at 10:47
  • 1
    $\begingroup$ I like your categorization although I think it is more common to denote (2) as constructive heuristics and (4) as local search heuristics. See, e.g., en.wikipedia.org/wiki/Constructive_heuristic. The best constructive heuristics, however, are usually those that are more problem specific ;-) $\endgroup$
    – Henrik Alsing Friberg
    Jul 24 at 5:35

Your Answer

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.