= Local-search perturbation
A \b[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.<Iterated Local Search by Helena R. Lourenço and others>[§2, framework; §3.2, perturbation]{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 costs
$$
(f(0),f(1),\ldots,f(5))=(0,2,4,5,3,1).
$$
Use 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\to1\to0$, with costs $4\to2\to0$. 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.<Iterated Local Search by Helena R. Lourenço and others>[§3.2, perturbation strength; §3.5, interaction of components]{ref}
Back to article page
