Introduction

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.

Try It: Escape Local Optima

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">Tour length:</span> <strong id="tourLen">โ€”</strong>
    &nbsp;|&nbsp; <span id="label-best">Best:</span> <strong id="bestLen">โ€”</strong>
    &nbsp;|&nbsp; <span id="label-iter">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">Run Local Search</button>
    <button id="btnPerturb" type="button">Perturb + Re-optimize</button>
    <button id="btnAuto" type="button">Auto-run ILS</button>
    <button id="btnReset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ILS on a small 8-city TSP instance (fixed city positions for reproducibility).
// Local search = 2-opt; perturbation = double-bridge (4-opt move that 2-opt cannot undo).
// History canvas tracks tour length over ILS iterations.

const CITIES = [
  [40,40],[140,30],[260,50],[290,110],[240,180],[130,200],[40,160],[20,100]
];
const N = CITIES.length;

// Euclidean distance
function dist(a, b) {
  const dx = CITIES[a][0]-CITIES[b][0], dy = CITIES[a][1]-CITIES[b][1];
  return Math.sqrt(dx*dx+dy*dy);
}
function tourLen(t) {
  let d=0; for(let i=0;i<N;i++) d+=dist(t[i],t[(i+1)%N]); return d;
}
function randTour() {
  const t=[...Array(N).keys()]; for(let i=N-1;i>0;i--){const j=Math.floor(Math.random()*(i+1));[t[i],t[j]]=[t[j],t[i]];} return t;
}

// 2-opt local search (full pass until no improvement)
function twoOpt(tour) {
  let t=[...tour], improved=true;
  while(improved){
    improved=false;
    for(let i=0;i<N-1;i++) for(let j=i+2;j<N;j++){
      if(j===N-1&&i===0) continue;
      const d0=dist(t[i],t[i+1])+dist(t[j],t[(j+1)%N]);
      const d1=dist(t[i],t[j])+dist(t[i+1],t[(j+1)%N]);
      if(d1<d0-1e-9){
        let l=i+1,r=j; while(l<r){[t[l],t[r]]=[t[r],t[l]];l++;r--;}
        improved=true;
      }
    }
  }
  return t;
}

// Double-bridge perturbation: splits tour into 4 segments and reconnects differently.
// This is the canonical perturbation for TSP-ILS (cannot be undone by 2-opt).
function doubleBridge(tour) {
  // Pick 4 cut positions in sorted order
  const pos = [];
  while(pos.length<4){ const p=1+Math.floor(Math.random()*(N-1)); if(!pos.includes(p)) pos.push(p); }
  pos.sort((a,b)=>a-b);
  const [a,b,c,d] = pos;
  // Segments: [0..a-1] A, [a..b-1] B, [b..c-1] C, [c..d-1] D, [d..N-1] E
  // Reconnect as A + C + B + D + E (double bridge)
  return [
    ...tour.slice(0,a),
    ...tour.slice(b,c),
    ...tour.slice(a,b),
    ...tour.slice(c,d),
    ...tour.slice(d)
  ];
}

// โ”€โ”€ State โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let currentTour, bestTour, bestLen, history, iterCount, autoTimer, phase;

function init() {
  currentTour = randTour();
  bestTour = [...currentTour];
  bestLen = tourLen(currentTour);
  history = [bestLen];
  iterCount = 0;
  phase = 'random';
  stopAuto();
  render();
  updateInfo();
  document.getElementById('phase').textContent = 'Start: random tour. Click Run Local Search.';
}

// โ”€โ”€ Drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const hCanvas = document.getElementById('history');
const hCtx = hCanvas.getContext('2d');

function drawTour(tour, color) {
  ctx.beginPath();
  ctx.strokeStyle = color; ctx.lineWidth = 1.8;
  ctx.moveTo(CITIES[tour[0]][0], CITIES[tour[0]][1]);
  for(let i=1;i<N;i++) ctx.lineTo(CITIES[tour[i]][0], CITIES[tour[i]][1]);
  ctx.closePath(); ctx.stroke();
}
function render() {
  ctx.clearRect(0,0,canvas.width,canvas.height);
  // Draw best tour faintly
  if(phase!=='random') drawTour(bestTour, 'rgba(29,53,87,0.18)');
  // Draw current tour
  const col = phase==='perturbed' ? '#e07000' : phase==='optimized' ? '#0a7d33' : '#1d3557';
  drawTour(currentTour, col);
  // Draw cities
  for(let i=0;i<N;i++){
    ctx.beginPath();
    ctx.arc(CITIES[i][0],CITIES[i][1],5,0,2*Math.PI);
    ctx.fillStyle = '#1d3557'; ctx.fill();
    ctx.fillStyle = '#fff'; ctx.font='bold 9px system-ui';
    ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(i+1, CITIES[i][0], CITIES[i][1]);
  }
}
function renderHistory() {
  const w=hCanvas.width, h=hCanvas.height;
  hCtx.clearRect(0,0,w,h);
  if(history.length<2) return;
  const mn=Math.min(...history)*0.97, mx=Math.max(...history)*1.01;
  const pad=8;
  hCtx.strokeStyle='#1d3557'; hCtx.lineWidth=1.5;
  hCtx.beginPath();
  history.forEach((v,i)=>{
    const x=pad+(w-2*pad)*i/(history.length-1);
    const y=h-pad-(h-2*pad)*(v-mn)/(mx-mn);
    i===0?hCtx.moveTo(x,y):hCtx.lineTo(x,y);
  });
  hCtx.stroke();
  // Mark best
  const bi=history.indexOf(Math.min(...history));
  const bx=pad+(w-2*pad)*bi/(history.length-1);
  const by=h-pad-(h-2*pad)*(history[bi]-mn)/(mx-mn);
  hCtx.beginPath(); hCtx.arc(bx,by,4,0,2*Math.PI);
  hCtx.fillStyle='#0a7d33'; hCtx.fill();
  // axis label
  hCtx.fillStyle='#888'; hCtx.font='10px system-ui'; hCtx.textAlign='left';
  hCtx.fillText('Tour length history', pad, 12);
}
function updateInfo() {
  document.getElementById('tourLen').textContent = Math.round(tourLen(currentTour));
  document.getElementById('bestLen').textContent = Math.round(bestLen);
  document.getElementById('iterCount').textContent = iterCount;
  renderHistory();
}

// โ”€โ”€ Actions โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function runLS() {
  currentTour = twoOpt(currentTour);
  const len = tourLen(currentTour);
  if(len < bestLen){ bestLen=len; bestTour=[...currentTour]; }
  history.push(len);
  iterCount++;
  phase='optimized';
  render(); updateInfo();
  document.getElementById('phase').textContent =
    fmt('2-opt local search complete. Tour = %round%. Best = %round2%.', { round: Math.round(len), round2: Math.round(bestLen) });
}
function runPerturb() {
  // Perturb from best (ILS canonical: always perturb from best or current)
  currentTour = doubleBridge([...bestTour]);
  const pLen = tourLen(currentTour);
  phase='perturbed';
  render();
  document.getElementById('phase').textContent =
    fmt('Double-bridge perturbation applied. Length = %round%. Re-optimizingโ€ฆ', { round: Math.round(pLen) });
  // Then immediately re-optimize
  setTimeout(()=>{ runLS(); }, 60);
}

// Auto-run ILS loop
let autoRunning=false;
function startAuto() {
  if(autoRunning) return;
  autoRunning=true;
  document.getElementById('btnAuto').textContent='Stop ILS';
  document.getElementById('btnLS').disabled=true;
  document.getElementById('btnPerturb').disabled=true;
  function step(){
    if(!autoRunning) return;
    currentTour = doubleBridge([...bestTour]);
    currentTour = twoOpt(currentTour);
    const len = tourLen(currentTour);
    if(len < bestLen){ bestLen=len; bestTour=[...currentTour]; }
    history.push(len);
    iterCount++;
    phase = len<bestLen+0.1 ? 'optimized' : 'perturbed';
    render(); updateInfo();
    document.getElementById('phase').textContent =
      fmt('ILS iteration %iterCount%. Tour = %round%. Best = %round2%.', { iterCount: iterCount, round: Math.round(len), round2: Math.round(bestLen) });
    if(iterCount < 60) autoTimer=setTimeout(step, 120);
    else stopAuto();
  }
  autoTimer=setTimeout(step,80);
}
function stopAuto() {
  autoRunning=false; clearTimeout(autoTimer);
  document.getElementById('btnAuto').textContent='Auto-run ILS';
  document.getElementById('btnLS').disabled=false;
  document.getElementById('btnPerturb').disabled=false;
}

document.getElementById('btnLS').addEventListener('click', runLS);
document.getElementById('btnPerturb').addEventListener('click', runPerturb);
document.getElementById('btnAuto').addEventListener('click', ()=>{ autoRunning?stopAuto():startAuto(); });
document.getElementById('btnReset').addEventListener('click', init);

init();
Result
Console

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.

The Real Complexity

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(n22n)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/iterated-local-search/Content licensed under CC BY-NC 4.0.