Iterated Local Search

Imagine you are hiking in thick fog, trying to reach the highest peak. You walk uphill until every direction goes down — but you might be standing on a foothill, not the summit. That is the dilemma facing every local search algorithm.

Local search is one of the oldest tricks in optimization: start with any solution, look at nearby alternatives, move to a better one, and repeat until no neighbor is an improvement. It is fast and simple, but it stops the moment it hits a local optimum — a solution that is better than all its neighbors yet far from the global best.

Iterated Local Search (ILS), formalized by Helena Lourenço, Olivier Martin and Thomas Stützle in 2002, adds one elegant idea: when you are stuck, perturb the current best solution to jump to a different region of the search space, then run local search again from there. Keep the best result you have seen so far and repeat. The loop is:

1. Build an initial solution and run local search to a local optimum.
2. Perturb — make a structured random move that is larger than a single local-search step.
3. Run local search again from the perturbed solution.
4. Accept or reject the new local optimum as the new baseline (often: keep it if it is better, or use a mild acceptance criterion).
5. Go to step 2.

Despite its simplicity, ILS consistently matches or beats far more elaborate algorithms on hard problems like the Traveling Salesman Problem. The power lies in exploring multiple basins of attraction in the solution landscape, guided by memory of the best solution found so far.

Below is a small tour problem: 8 cities placed on a grid. The algorithm must visit each city exactly once and return to the start, minimizing total distance. Local search alone will quickly find a tour — but it will get stuck.

<div id="app">
  <canvas id="canvas" width="320" height="220"></canvas>
  <div id="info">
    <span id="label-len">{{label_tour_length}}</span> <strong id="tourLen">—</strong>
    &nbsp;|&nbsp; <span id="label-best">{{label_best}}</span> <strong id="bestLen">—</strong>
    &nbsp;|&nbsp; <span id="label-iter">{{label_iterations}}</span> <strong id="iterCount">0</strong>
  </div>
  <div id="history-wrap"><canvas id="history" width="320" height="60"></canvas></div>
  <div class="btns">
    <button id="btnLS" type="button">{{btn_run_ls}}</button>
    <button id="btnPerturb" type="button">{{btn_perturb}}</button>
    <button id="btnAuto" type="button">{{btn_auto_run}}</button>
    <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
  <div id="phase"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
#app { display: flex; flex-direction: column; gap: .45rem; }
canvas { display: block; border-radius: 10px; background: #f0f4f8; }
#history-wrap { }
#history { background: #f8fafc; border-radius: 8px; }
#info { font-size: .85rem; color: #444; }
#phase { font-size: .82rem; font-weight: 600; min-height: 1.3em; color: #1d3557; }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Click Run Local Search to see the algorithm polish a random tour to a local optimum. Then click Perturb + Re-optimize to shake the tour with a random double-bridge move and run local search again. Watch the tour length history — each perturbation may escape a trapped valley and reach a shorter tour. Auto-run ILS repeats the loop automatically so you can see the improvement curve over many iterations.

ILS is designed for NP-hard problems — problems like the Traveling Salesman Problem or scheduling where no known algorithm finds the optimum in polynomial time for all inputs.

Why local optima are the real obstacle

A local optimum is a solution where every small change makes things worse. On a rugged landscape with millions of local optima, a pure local search will halt at the first one it reaches. The fraction of local optima that are close to globally optimal is typically tiny — most are mediocre traps.

What ILS actually does

• Perturbation kicks the solution out of its current basin of attraction. Too small a kick and you land back in the same basin; too large and you lose all the structure the local search found. The art is calibrating the kick size to cross basin boundaries without destroying good structure.
• Local search polishes the perturbed solution back to a local optimum in the new region.
• Acceptance criterion decides whether the new local optimum replaces the current baseline. Simple ILS keeps the better one; more sophisticated variants accept slightly worse solutions (like simulated annealing) to avoid premature convergence.

Theoretical status

ILS has no polynomial-time optimality guarantee — it is a heuristic. For the TSP, the best known exact algorithms still run in exponential time (Held-Karp: $O(n^{2} 2^{n})$), and ILS is not an exception. However, it is provably effective at escaping local optima in landscapes where basins of attraction are well-separated, and empirically it finds solutions within a few percent of optimal on benchmark TSP instances with hundreds of cities.

The key insight is that local optima are not uniformly distributed: on structured problems, good local optima cluster near the global optimum in solution space. ILS exploits this by using the best local optimum as a launching pad for the next perturbation, biasing the search toward promising regions without exhaustive enumeration.

The "perturb-and-polish" loop is one of the most widely deployed optimization strategies because NP-hard problems appear everywhere practical decisions are made:

• Vehicle routing and logistics: delivery companies use ILS variants to plan routes for fleets of vehicles. UPS, FedEx and others run ILS-related algorithms daily on instances with thousands of stops, saving millions of dollars in fuel. (See the related Traveling Salesman Problem article.)
• Production scheduling: assigning jobs to machines, shifts to workers, or courses to classrooms is a combinatorial explosion — ILS finds near-optimal schedules orders of magnitude faster than exhaustive search. See also scheduling.
• Electronic design automation: placing components on a chip and routing wires between them is an optimization problem where ILS-based tools are the industry standard.
• Protein structure prediction: folding a protein sequence into its 3D shape is a rugged energy landscape with countless local minima. ILS-style perturbations help escape false energy wells.
• Software engineering: automated test-data generation and search-based software engineering use ILS to explore program input spaces efficiently.

What makes ILS attractive in practice is its simplicity: it requires only a local search procedure and a perturbation operator, both of which are usually easy to design for a specific problem. More elaborate algorithms (genetic algorithms, ant colony optimization, simulated annealing) often require more parameter tuning for comparable results.

Iterated Local Search embodies a principle that shows up across optimization, evolution, and even human problem-solving: when you are stuck, make a structured jump and try again.

Pure local search is fast but myopic — it polishes whatever solution it starts from and cannot see past the nearest hill. ILS adds a second loop that deliberately disturbs the current best, trading a temporary loss of quality for the chance to escape a mediocre basin and find a better one. Over many iterations, this simple strategy explores a far wider slice of the solution landscape than any single run of local search could.

The surprise is how competitive it remains. On the Traveling Salesman Problem and dozens of other NP-hard benchmarks, ILS matches or beats algorithms that are far more complex to implement. The lesson is not that sophisticated methods are unnecessary — sometimes they are — but that the fundamental obstacle in hard optimization is the local-optimum trap, and a well-designed perturbation addresses that obstacle directly.

If you want to solve a hard combinatorial problem in practice, ILS is almost always worth trying first.