Metaheuristic

A metaheuristic is a general strategy for coordinating heuristic optimization procedures across a range of problems. It specifies such choices as how to generate candidates, escape a stalled search or retain promising solutions, while a particular problem still supplies its representation, feasible set and objective function. For example, iterated local search combines a problem-specific local improvement procedure with perturbation and acceptance decisions.^[ref]

To make the distinction concrete, consider minimizing $f(x)=(x^2-4{)}^2$ over the integers from $-3$ through $3$. A local improvement rule can inspect the feasible values $x-1$ and $x+1$ and move to a strictly lower cost. Starting at $-2$ gives cost $0$ and no improving local move. A metaheuristic may perturb this candidate to $1$; local improvement then reaches $2$, also with cost $0$. The representation and objective are particular to the example, while the perturb-and-improve pattern is reusable. Escaping a local stopping point need not discover a better value: here both reached solutions are already globally optimal, because $f$ is a square.

Simulated annealing supplies a different acceptance strategy, and tabu search uses memory to restrict selected revisits. These method names do not by themselves establish a universal approximation ratio or a proof that a finite run finds a global minimum. An evaluation should state the permitted moves, termination rule and computation budget, so that a reusable strategy is not confused with a guarantee for every implementation.