 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]

Iterated Local Search (ILS) is a metaheuristic optimization algorithm used for solving combinatorial and continuous optimization problems. It is particularly effective for NP-hard problems. The method combines local search with a mechanism to escape local optima through perturbation, followed by a re-optimization of the solution. ### Key Components of Iterated Local Search: 1. **Initial Solution**: The algorithm starts with an initial feasible solution, which can be generated randomly or through some heuristics.