Heuristic optimization

Heuristic optimization seeks useful feasible solutions without necessarily providing a universal approximation ratio or a polynomial worst-case guarantee. Examples are local search, simulated annealing and tabu search. A claimed approximation algorithm needs a separate proved performance guarantee.

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.

Tabu search keeps a short-term memory of recently reversed moves or visited attributes and prohibits them temporarily, reducing cycling in local search. It can select the best admissible neighbor even when that neighbor worsens the objective; an aspiration rule permits a tabu move when it improves the best known solution. For allocations, transfers and exchanges maintain feasibility and recent reverse transfers can be tabu.

Simulated annealing accepts worse feasible solutions to escape a local minimum. Minimize an objective function $E(x)$, analogous to energy. Effective temperature $T>0$ has the same units as $E$, absorbing the Boltzmann constant; it controls exploration, rather than a material's thermodynamic temperature.^[ref]

Given current feasible point $x$, draw $y$ from a proposal distribution $q(x,y)$. For a symmetric proposal distribution, $q(x,y)=q(y,x)$, use the Metropolis–Hastings acceptance probabilityAccept with this conditional probability; on rejection retain $x$. Every downhill or equal-cost proposal is accepted. Draw a fresh uniform random variable $U$ on $(0,1)$ and accept if $U<a_T(x,y)$. The off-diagonal transition probability $P_T(x,y)=q(x,y)a_T(x,y)$ includes proposing $y$.^[ref]

For a maximization problem with objective function $f$, set $E=-f$: every improving proposed neighbor is accepted, and a worsening move of loss $\Delta =f(x)-f(y)>0$ has conditional probability $\exp (-\Delta /T)$ of acceptance, under the same symmetry assumption. Likelihood-power annealing uses precisely this sign convention for a log-likelihood. Retain the best feasible solution seen, since the current state can worsen even after a global minimum has been visited.

If the proposal distribution is asymmetric, use the full Metropolis–Hastings acceptance probability, for $q(x,y)>0$,A missing reverse proposal gives zero acceptance. Even a downhill proposal need not be accepted with probability one in this case. Choosing uniformly among a variable number of neighbors is generally asymmetric: $q(x,y)=1/d(x)$ and $q(y,x)=1/d(y)$ give the correction $d(x)/d(y)$, where $d$ is vertex degree.^[ref]

The useful idea is to separate exploring from insisting on improvement: an uphill move can open a route to a better feasible solution. Its usefulness depends on the proposal distribution, the scale of the objective function, and the cooling schedule for simulated annealing. Finite practical schedules carry no general guarantee of finding a global minimum.

To maximize a log-likelihood, use energy $-\ell$ and Boltzmann distribution proportional to $e^{\ell /T}=L^{1/T}$ at temperature $T>0$. Reversing this sign favors likelihood minima and can make the probability density function nonnormalizable. For Poisson observations with total $s$ and sample size $m$, with respect to $d\lambda$ the normalized probability density function isIts mean is $(s+T)/m$ and variance $(sT+T^2)/m^2$, so it concentrates at the maximum-likelihood estimate $s/m$ as $T\downarrow 0$. Cooling of equilibrium laws and convergence of a particular changing-temperature chain are different statements; the latter requires mixing or a direct chain argument.

For $m$ independent binomial distribution observations with fixed trial count $n$ and total successes $s$, the likelihood-power probability density function relative to $dp$ is $p^{s/T}(1-p{)}^{(mn-s)/T}$. Its normalized law is the displayed beta distribution. Its mean tends to $s/(mn)$ and its variance tends to zero as $T\downarrow 0$, including endpoint maxima. Energy for maximizing a log-likelihood is its negative; the opposite sign reverses the optimization.

Let $\bar{x}=m^{-1}{\sum }_i{x}_i$ and $S={\sum }_i(x_i-\bar{x}{)}^2>0$. With Lebesgue base measure $d\mu dv$ for $v={\sigma }^2$, the likelihood-power law has conditionalsThe joint law is proper for $T<m/3$, since its marginal $v$ is inverse-gamma distribution with shape $m/(2T)-3/2$ and scale $S/(2T)$. There is also a direct convergence proof for successive Gibbs sampling updates with deterministic $0<T_n\le m/10$ and $T_n\to 0$. Update ${\mu }_n$ from $v_{n-1}$, then $v_n$ from ${\mu }_n$. Inverse-gamma distribution moments and conditional normal moments giveThe coefficients of the preceding moments are bounded by $1/6$ and $1/8$, so these moments stay bounded from a finite deterministic initial variance. Letting $T_n\to 0$ gives $\mathbb{E}{v}_n\to S/m$ and $\mathbb{E}{v}_n^2\to (S/m{)}^2$. Also $\mathbb{E}({\mu }_n-\bar{x}{)}^2=T_n\mathbb{E}{v}_{n-1}/m\to 0$. Thus the iterates converge in mean square to the normal maximum-likelihood estimate.

Consider the chosen finite minimization problemOnly adjacent integers are neighbors. At each interior state propose left or right with probability $1/2$ each; at an endpoint propose its sole neighbor with probability $1/2$ and itself with probability $1/2$. This proposal distribution is symmetric, including at the endpoints. The local minimum at $1$ is relative to these allowed moves; $4$ is the unique global minimum.

At $1$, improving-only local search rejects both neighbors because $E(0)=2$ and $E(2)=4$ exceed $E(1)=1$. For simulated annealing, choose $T_{\ast }=1/\ln 2$, using the natural logarithm. Conditional on proposing $2$ from $1$, the acceptance probability isThe one-step transition probability is instead $P_{T_{\ast }}(1,2)=(1/2)(1/8)=1/16$. Both subsequent rightward proposals are downhill, so the conditional probability of the precise next three states being $2,3,4$, given $X_0=1$ and fixed $T_{\ast }$, isThis is one possible escape route, not the probability of eventually reaching $4$. Rejections, excursions toward $0$, and repeated attempts give many other sample paths. The calculation establishes possibility, without claiming a general performance advantage from a selected sample path.

For comparison, halving $T_{\ast }$ makes the uphill acceptance probability $1/64$; doubling it makes that probability $1/(2\sqrt{2})$. Cooling makes it harder to leave this local minimum, even though the stationary distribution increasingly favors the global minimum. That tension is the central scheduling problem.

On a finite state space $F$ with finite objective function values, the fixed-$T$ target is a Boltzmann distribution:The partition function $Z_T$ normalizes the weights but cancels from the Metropolis–Hastings acceptance probability. A short detailed balance proof explains the target. With symmetric $q$ and $x\ne y$,Summing over $x$ gives ${\pi }_T{P}_T={\pi }_T$, so this is a stationary distribution. On a finite state space, a connected graph of positive symmetric proposals makes the accepted Markov chain an irreducible Markov chain. Convergence from any starting state additionally requires an aperiodic Markov chain; one positive self-transition suffices under irreducibility. Replacing $q$ by $(I+q)/2$ ensures this. For asymmetric $q$, require connectivity through bidirectional proposals: one-way proposals are rejected.^[ref]

In the five-state barrier example for simulated annealing, $T_{\ast }=1/\ln 2$ gives exact Boltzmann weights $2^{-E(x)}$. Multiplying by $16$ givesFor the uphill edge, detailed balance is visible numerically:Thus the global minimum has the largest individual stationary probability, $16/33$, but is far from certain at this positive $T_{\ast }$. At $T_{\ast }/2$ the exact stationary distribution is $(16,64,1,16,256)/353$.

For any finite $F$, let $M$ be the set of global minima and $E_{\min }$ the smallest objective function value. Cancelling $e^{-E_{\min }/T}$ from numerator and denominator shows that each nonminimal state's weight tends to zero as $T\downarrow 0$, while every state in $M$ has equal weight. Therefore ${\pi }_T$ tends to the uniform distribution on $M$. This is a statement about a family of equilibrium probability distributions; it does not prove that a cooling Markov chain follows that family.

A cooling schedule for simulated annealing specifies successive effective temperatures and how many proposals to attempt at each. For example, $T_k=T_0{r}^k$ with $0<r<1$, using the geometric sequence, can define stages of equal chosen length. Changing $T$ changes the transition matrix: if the state probability distribution is ${\mu }_n$, then ${\mu }_{n+1}={\mu }_n{P}_{T_n}$, which generally differs from ${\pi }_{T_{n+1}}$. Time spent at one temperature must be compared with its mixing time before equilibrium intuition is justified.

In the five-state barrier example for simulated annealing, fixed $T_{\ast }>0$ gives a finite irreducible Markov chain, so $4$ is eventually visited with probability one. That unbounded-time statement gives no fixed finite deadline. Over any finite number $N$ of trials starting at $1$, the probability of staying at $1$ throughout isEach factor is the rejection probability at $1$. This is an explicit failure event even when every $T_n$ is positive: the best visited objective function value remains $1$, above the global minimum value $0$. More exploratory proposals can help cross a barrier; cooling before those moves occur can preserve a poor local minimum. Successful asymptotic schedules need additional analysis of the allowed moves and barriers.

Historically, Scott Kirkpatrick, Charles Daniel Gelatt Jr. and Mario P. Vecchi connected statistical mechanics with mathematical optimization in 1983. They adapted the Metropolis–Hastings algorithm to cooling searches with symmetric proposals and illustrated computer-design problems.^[ref]

Local search repeatedly improves a feasible solution within a specified neighborhood until no improving move remains. For an allocation, neighbors can transfer an item or exchange items between bidders while preserving the partition. A local optimum need not be a global optimum; restarting from several initial solutions can explore different basins.

An optimization neighborhood assigns to each feasible solution $x$ a set $N(x)$ of candidates reachable by the chosen elementary moves. It need not be a neighborhood in a previously chosen geometric metric, nor must reachability be symmetric. For minimization, a solution is locally optimal under these moves whenChanging $N$ can change that conclusion while leaving the objective function unchanged. Specifying the embedded local search is therefore part of specifying an iterated local search method.^[ref]

For a complete binary string example, let the feasible set contain all eight strings of length three. Assign $f(000)=0$, $f(111)=-1$, and $f(x)=1$ for the other six strings. With one-bit flips,so $000$ is a strict local optimum. Allowing flips of one or two bits adds $110,101,011$, but all six neighbors still cost $1$. Allowing three-bit flips finally reaches $111$, so $000$ ceases to be locally optimal. The best value in the entire feasible set is $-1$ throughout; the move rule changes what the local procedure can see.

For length $n$, the one-bit-flip neighborhood has $n$ members, while including all two-bit flips adds $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ members. A larger neighborhood may expose an improving move but cost more to examine. The corresponding directed graph has feasible solutions as vertices and a directed edge from $x$ to each member of $N(x)$. If this graph cannot reach a region from the initial solution, even repeated local moves cannot explore that region without a different move or a restart.

Iterated local search is a metaheuristic that alternates perturbation, local search and acceptance decisions. The local search improves candidates within a declared optimization neighborhood; perturbation helps reach other locally optimal solutions.^[ref]

For minimization, start with $s=\mathcal{L}(s_0)$ and generate $q=\mathcal{L}(P(s))$, where $\mathcal{L}$ performs local search and $P$ perturbs its input. Accepting only $f(q)<f(s)$ or accepting every candidate are two possible rules.^[ref]

For an original complete example, let feasible solutions be the integers $0$ through $6$, with neighbors differing by one and objective valuesStrictly improving local search starting at $0$ moves to $1$ and stops: its two neighbors have costs $4$ and $3$, both worse than $2$. Perturb the solution from $1$ to $4$, allowing a temporary rise to cost $4$. Local improvement then follows $4\to 5\to 6$, reaching cost $0$, which is the global minimum by inspection of the complete list. The perturbation escaped the first local minimum without requiring the local improvement rule itself to cross an uphill edge.

Perturbation and acceptance must work together: weak changes can return to the same local minimum. The authors’ travelling salesman problem comparison used ten runs of 120 seconds on a Pentium 266 MHz PC, illustrating why evaluation must specify the embedded search and computational budget.^[ref]

An iterated local search acceptance rule chooses the next current solution after a perturbation has been followed by local search. Let the current locally improved solution be $s$ and the new locally improved candidate be $q$, with a minimized objective function $f$. The decision concerns these search states, not just the potentially poor intermediate output of the local-search perturbation.^[ref]

One rule accepts only improvement:The paper calls this policy Better. Its current costs cannot increase, which follows immediately from the two cases. That property does not establish that the search will reach a global minimum. The RW rule instead retains the latest candidate regardless of cost, allowing movement among locally improved solutions.^[ref]

For an original numerical comparison, suppose $f(s)=10$. A perturbation temporarily raises the cost to18, and subsequent local search lowers it to12. Better rejects the candidate with cost12, while RW accepts it; neither decision is made by comparing10 with the intermediate18. If the same procedure instead reaches cost8, both accept.

A simulated annealing-type option accepts a worse candidate with probability $\exp [-(f(q)-f(s))/T]$, with $T>0$. At cost difference2 and $T=2$, this probability is $e^{-1}\simeq 0.368$. The temperature is a parameter of the rule, not a guarantee that a particular finite run escapes every trap.^[ref]

A permissive current-state rule can retain a candidate worse than an earlier result. Keeping a separate best-so-far solution preserves that result while allowing exploration. Report both the current-state acceptance policy and the best-result bookkeeping when comparing search runs.

A local-search perturbation deliberately changes the current solution before local search resumes. In iterated local search, the perturbation and improvement form a composite step: $s\mapsto \mathcal{L}(P(s))$, where $P$ changes the candidate and $\mathcal{L}$ applies the chosen local improvement procedure. The perturbation need not improve the objective function; a later iterated local search acceptance rule decides which improved candidate becomes current.^[ref]

A fully specified example shows why a weak perturbation can be ineffective. Let feasible solutions be the integers $0$ through $5$, with neighbors differing by one, and costsUse strictly improving, best-neighbor local search. Starting at5 is locally optimal: its only neighbor4 has cost3, above the current cost1. A one-step kick to4 is immediately undone by local improvement, which returns to5.

A different kick from5 to2 temporarily raises the cost to4, but the subsequent improving path is $2\to 1\to 0$, with costs $4\to 2\to 0$. The resulting candidate beats the old stopping point. These values are an original constructed example; they show how changing the perturbation can change which solution the same local search reaches.

Perturbation strength therefore concerns more than accepting a single worse local move. Too little change may repeatedly return to the same solution, while a nearly independent redraw can discard useful structure from the current candidate. Feasibility must also be handled explicitly: either the perturbation stays within the feasible set or the method specifies how an infeasible intermediate is repaired. Problem-specific moves and acceptance decisions must be evaluated together.^[ref]

A local search method that retains one current candidate and repeatedly chooses an improving neighbor of its objective. For a conflict-minimization constraint satisfaction problem, a candidate can assign all variables within their constraint domains while violating some inter-variable constraints; the objective counts those violations. Zero conflicts certifies a solution, while a positive-conflict local minimum need not certify impossibility. Plateaus and local minima motivate sideways moves, randomized choices and restarting. Prescribed variables must remain fixed in every initialization and move.

A repair method for a constraint satisfaction problem: choose a currently conflicted, movable variable, and assign a permitted value minimizing its number of violated constraints with the other variables held fixed. Tie handling can permit sideways moves. For the queens completion problem, keep prescribed rows fixed, select a conflicted unfixed row, and choose a column minimizing attacks. Never interpret failure to improve as proof that no solution exists.