= Metaheuristic
A \b[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.<Iterated Local Search by Helena R. Lourenço and others>[§1–2, guiding embedded heuristics and the modular framework]{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.
Back to article page
