Local-search perturbation

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]