Iterated local search

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]