= Iterated local search
\b[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.<Iterated Local Search by Helena R. Lourenço and others>[§2–3, general framework and components]{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.<Iterated Local Search by Helena R. Lourenço and others>[§3.3, Better and RW acceptance criteria]{ref}
For an original complete example, let feasible solutions be the integers $0$ through $6$, with neighbors differing by one and objective values
$$
(f(0),f(1),\ldots,f(6))=(4,2,3,5,4,1,0).
$$
Strictly 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\to5\to6$, 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.<Iterated Local Search by Helena R. Lourenço and others>[§3.3.1, Table 3 and caption]{ref}
Back to article page
