Skip to content

Review: Iterated Local Search

Citation

  • Lourenço, H. R., Martin, O. C. & Stützle, T. (2003). Iterated local search. In Handbook of Metaheuristics (F. Glover & G. Kochenberger, eds.), pp. 320–353. Kluwer.
  • DOI

Abstract

Iterated local search is a simple and general metaheuristic that builds a walk through the space of local optima of a problem. From the current local optimum it applies a perturbation, runs a local search to reach a new local optimum, and accepts or rejects the result by an acceptance criterion. The method is a biased sampling of the set of local optima and consistently outperforms random restart; its performance turns on the strength of the perturbation and the choice of acceptance criterion.

A plain local search relaxes a solution to the nearest local optimum and stops. On large instances the local optima it reaches cluster at a fixed percentage above the true optimum, and random restart rarely does better because good local optima are rare under uniform sampling. Iterated local search (ILS) escapes this by searching the space of local optima directly, through a walk rather than by resampling from scratch.

One ILS step has three parts. From the current local optimum \( s^\ast \), a perturbation produces an intermediate solution \( s' \); a local search from \( s' \) reaches a new local optimum \( s^{\ast\prime} \); and an acceptance criterion decides whether the walk moves to \( s^{\ast\prime} \) or falls back to \( s^\ast \). Iterating this is a biased sampling of the local optima that is far more effective than random restart. The perturbation strength is the key control: too small and the local search returns to \( s^\ast \), so little is explored; too large and the intermediate solution is effectively random, so the method degrades to random restart. The authors' rule of thumb is that "a good perturbation transforms one excellent solution into an excellent starting point for a local search." Acceptance criteria range from accept-only-if-better (descent in the space of local optima) to simulated-annealing-like rules that sometimes accept worse solutions; perturbations are randomized or made adaptive to avoid short cycles, and adding memory of past optima can help further.

Relevance to Hifuku

Iterated local search is the template behind Hifuku's variation operators. Hifuku's per-niche behavior has the ILS shape: it perturbs an elite with a tree move and keeps the result when it improves the niche, which is a perturbation followed by an accept-if-better step in the space of good trees. The move mix follows the ILS perturbation-strength principle directly: small branch moves (slide, scale) refine within a local optimum, larger topology moves (NNI, SPR) push into new ground, and the Lévy-distributed heavy-tailed relocation levy_jump_move is a strong perturbation for escaping when local refinement stalls, the ILS answer to a search that has converged.

The difference is that ILS follows a single walk toward one optimum, whereas Hifuku keeps a diverse archive and maps the whole landscape (illumination, not optimization). ILS names the ancestry of Hifuku's moves rather than the engine itself: the survey places elites by a keep-if-better rule across many niches, not along one iterated-local-search trajectory. See also Basin Hopping (Wales & Doye 1997) and Lévy Flights (Viswanathan et al. 1999) for the neighboring moves in the same family.