Introduction

Imagine you are hiking in fog and trying to find the lowest valley. You walk downhill until you can go no further — but the hollow you are standing in might not be the deepest one. You are stuck in a local optimum, and without information about the wider landscape you have no way to know.

Local search algorithms face exactly this problem. They tweak a candidate solution one step at a time, accepting changes only when they improve the objective. They are fast and practical — but they routinely stop at local optima that are far from the global best.

Guided Local Search (GLS), introduced by Christos Voudouris and Edward Tsang in 1995, adds a simple but powerful twist: every time the search gets stuck, it penalizes the features of the current solution. Penalized features carry an extra cost in future evaluations, so the optimum the algorithm was happy with a moment ago suddenly looks worse — and the search moves on.

The result is a meta-heuristic: a strategy that guides an underlying local search without knowing the problem's structure in advance. GLS has found near-optimal solutions for some of the hardest combinatorial problems we know, including the Travelling Salesman Problem.

Escape the Trap

The landscape below has several valleys. Plain local search drops into the nearest one and stops. Guided Local Search adds penalties to the features it keeps visiting — raising their effective cost and forcing the search out of a trap.

<!-- Demo: plain local search vs. Guided Local Search on a 1-D cost landscape -->
<p class="hint">The bars show a cost landscape — lower is better. <b>Plain local search</b> slides downhill and gets trapped in a local optimum. <b>Guided Local Search</b> penalizes that position (red highlight), raising its augmented cost, so the search is pushed toward a deeper valley.</p>
<div id="landscape-wrap">
  <canvas id="landscape" width="500" height="140"></canvas>
</div>
<div id="penalty-row">
  <span class="row-label">Penalties:</span>
  <div id="penalty-cells"></div>
</div>
<div id="pos-row">
  <span class="row-label">Position:</span>
  <span id="pos-display">—</span>
</div>
<div class="status" id="status">Click a button to start.</div>
<div class="btns">
  <button id="btn-plain" type="button">Run plain local search</button>
  <button id="btn-gls" type="button">Run guided local search</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Styles for the GLS landscape demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#landscape-wrap { overflow-x: auto; margin-bottom: .4rem; }
canvas { display: block; max-width: 100%; border-radius: 8px; background: #f4f7fa; }
#penalty-row, #pos-row { display: flex; align-items: center; gap: .5rem; margin: .25rem 0; font-size: .85rem; }
.row-label { font-weight: 600; color: #555; min-width: 80px; }
#penalty-cells { display: flex; gap: 3px; flex-wrap: wrap; }
.pcell { width: 32px; height: 26px; display: flex; align-items: center; justify-content: center;
         font: 700 12px ui-monospace, monospace; border-radius: 5px;
         background: #e8eef3; border: 1px solid #cdd9e3; color: #1d3557; }
.pcell.active { background: #e63946; border-color: #c92f3c; color: #fff; }
#pos-display { font-weight: 700; font-size: .95rem; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// GLS demo: 1-D cost landscape with penalty-guided escape from local optima

// Fixed 10-position cost landscape: local opt at pos 2 (cost 3), global opt at pos 9 (cost 2)
// Values represent relative costs (lower = better). Positions 0-9.
const COSTS = [7, 5, 3, 4, 8, 4, 7, 3, 5, 2];
const N = COSTS.length;

// Penalty weight — scales how much each penalty increment raises the augmented cost
const LAMBDA = 2;

// Penalty counters — one per position
const penalties = new Array(N).fill(0);

// Augmented cost = original cost + lambda * penalty at that position
function augCost(pos, pen) {
  return COSTS[pos] + LAMBDA * pen[pos];
}

// 1-D neighbors: only adjacent positions
function neighbors(pos) {
  const nb = [];
  if (pos > 0) nb.push(pos - 1);
  if (pos < N - 1) nb.push(pos + 1);
  return nb;
}

// Canvas drawing: bars + penalty overlay + current-position dot
const canvas = document.getElementById('landscape');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const PAD = 20;
const maxC = Math.max(...COSTS);

function barX(i) { return PAD + i * ((W - 2 * PAD) / (N - 1)); }
function barY(cost) { return H - PAD - (Math.min(cost, maxC + 3) / (maxC + 3)) * (H - 2 * PAD); }

let animId = null;

function draw(highlightPos, pen) {
  ctx.clearRect(0, 0, W, H);
  // Draw one bar per position
  for (let i = 0; i < N; i++) {
    const x = barX(i);
    const baseCost = COSTS[i];
    const baseY = barY(baseCost);
    const augC = COSTS[i] + LAMBDA * pen[i];
    const augY = barY(augC);
    // Blue bar = original cost
    ctx.fillStyle = i === highlightPos ? '#e63946' : '#c8d6e5';
    ctx.fillRect(x - 13, baseY, 26, H - PAD - baseY);
    // Red overlay = additional cost from penalties
    if (pen[i] > 0) {
      ctx.fillStyle = 'rgba(230,57,70,0.3)';
      ctx.fillRect(x - 13, augY, 26, baseY - augY);
    }
    // Position index below each bar
    ctx.fillStyle = '#555';
    ctx.font = '11px ui-monospace, monospace';
    ctx.textAlign = 'center';
    ctx.fillText(i, x, H - 4);
  }
  // Connect bar tops with a profile line
  ctx.beginPath();
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2;
  for (let i = 0; i < N; i++) {
    const x = barX(i), y = barY(COSTS[i]);
    i === 0 ? ctx.moveTo(x, y) : ctx.lineTo(x, y);
  }
  ctx.stroke();
  // Red dot marks the current search position
  if (highlightPos !== null) {
    ctx.beginPath();
    ctx.arc(barX(highlightPos), barY(COSTS[highlightPos]) - 9, 6, 0, 2 * Math.PI);
    ctx.fillStyle = '#e63946';
    ctx.fill();
  }
}

function updatePenaltyCells(pen, highlightPos) {
  const container = document.getElementById('penalty-cells');
  container.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const d = document.createElement('div');
    d.className = 'pcell' + (i === highlightPos && pen[i] > 0 ? ' active' : '');
    d.textContent = pen[i];
    container.appendChild(d);
  }
}

function setStatus(msg, cls) {
  const s = document.getElementById('status');
  s.textContent = msg;
  s.className = 'status ' + (cls || '');
}

function setPosDisplay(pos) {
  document.getElementById('pos-display').textContent =
    pos !== null ? i18nFmt('pos %pos% — cost %cost%', { pos: pos, cost: COSTS[pos] }) : '—';
}

function disableButtons(disabled) {
  document.getElementById('btn-plain').disabled = disabled;
  document.getElementById('btn-gls').disabled = disabled;
}

function reset() {
  if (animId) { clearTimeout(animId); animId = null; }
  const pen = new Array(N).fill(0);
  draw(null, pen);
  updatePenaltyCells(pen, null);
  setPosDisplay(null);
  setStatus('Click a button to start.', '');
  disableButtons(false);
}

// Plain local search: always move to the cheaper neighbor, stop when stuck
function buildPlainSteps() {
  // Build the step list for the plain local search animation
  const pen = new Array(N).fill(0);
  let pos = 0;
  const steps = [{ pos, pen: [...pen], msg: i18nFmt('Starting at position %pos%.', { pos }), cls: 'info' }];
  for (let iter = 0; iter < 30; iter++) {
    const nb = neighbors(pos);
    const best = nb.reduce((a, b) => COSTS[a] <= COSTS[b] ? a : b);
    if (COSTS[best] >= COSTS[pos]) {
      steps.push({ pos, pen: [...pen], msg: i18nFmt('Stuck at position %pos% (cost %cost%) — local optimum, cannot escape.', { pos, cost: COSTS[pos] }), cls: 'bad' });
      break;
    }
    pos = best;
    steps.push({ pos, pen: [...pen], msg: i18nFmt('Now at position %pos% (cost %cost%).', { pos, cost: COSTS[pos] }), cls: 'info' });
  }
  return steps;
}

// Guided Local Search: inner LS + penalize the trapped position + re-run LS
function buildGLSSteps() {
  // Build the step list for the GLS animation
  // GLS penalizes the current position (its single feature in this 1-D demo)
  // after each inner local search that gets stuck.
  const pen = new Array(N).fill(0);
  let pos = 0;
  const globalBest = COSTS.indexOf(Math.min(...COSTS));
  const steps = [{ pos, pen: [...pen], msg: i18nFmt('Starting at position %pos%.', { pos }), cls: 'info' }];
  for (let iter = 0; iter < 20; iter++) {
    // Inner local search using augmented cost (original + penalty contribution)
    for (let inner = 0; inner < 15; inner++) {
      const nb = neighbors(pos);
      const aug = p => COSTS[p] + LAMBDA * pen[p];
      const best = nb.reduce((a, b) => aug(a) <= aug(b) ? a : b);
      if (aug(best) >= aug(pos)) break;
      pos = best;
    }
    // Penalize the current local-optimum position to raise its augmented cost
    pen[pos]++;
    steps.push({ pos, pen: [...pen], penalized: pos, msg: i18nFmt('Trapped at position %pos% — penalty raised to %p%. Augmented cost now higher.', { pos, p: pen[pos] }), cls: 'info' });
    // Re-run inner LS after penalizing — the raised cost may now allow escape
    for (let inner = 0; inner < 15; inner++) {
      const nb = neighbors(pos);
      const aug = p => COSTS[p] + LAMBDA * pen[p];
      const best = nb.reduce((a, b) => aug(a) <= aug(b) ? a : b);
      if (aug(best) >= aug(pos)) break;
      pos = best;
    }
    steps.push({ pos, pen: [...pen], msg: i18nFmt('Now at position %pos% (cost %cost%).', { pos, cost: COSTS[pos] }), cls: pos === globalBest ? 'ok' : 'info' });
    if (pos === globalBest) {
      steps.push({ pos, pen: [...pen], msg: i18nFmt('Global optimum found at position %pos% (cost %cost%)!', { pos, cost: COSTS[pos] }), cls: 'ok' });
      break;
    }
  }
  return steps;
}

function runAnimation(steps, isGLS) {
  let i = 0;
  disableButtons(true);
  function tick() {
    if (i >= steps.length) { disableButtons(false); return; }
    const step = steps[i++];
    draw(step.pos, step.pen);
    updatePenaltyCells(step.pen, isGLS ? step.penalized : null);
    setPosDisplay(step.pos);
    setStatus(step.msg, step.cls);
    animId = setTimeout(tick, 700);
  }
  tick();
}

document.getElementById('btn-plain').addEventListener('click', () => {
  reset();
  setTimeout(() => runAnimation(buildPlainSteps(), false), 50);
});
document.getElementById('btn-gls').addEventListener('click', () => {
  reset();
  setTimeout(() => runAnimation(buildGLSSteps(), true), 50);
});
document.getElementById('btn-reset').addEventListener('click', reset);

reset();
Result
Console

Click Run plain local search to see it stop at a local optimum. Then click Run guided local search to watch penalties accumulate (shown in the penalty row) and the search escape to a deeper valley. Each penalty increment raises the augmented cost of the current position, making a neighbor look better and causing a move.

The Real Complexity

GLS does not solve hard problems in polynomial time — it is a heuristic, not an exact algorithm. Its complexity picture has several layers:

  • Each local search step runs in the time the underlying move evaluation takes — often O(1)O(1) or O(n)O(n) with incremental tricks, making individual steps very cheap.
  • No guarantee of optimality. Because the search landscape for NP-hard problems like the Travelling Salesman Problem has exponentially many local optima, GLS cannot promise to find the global best. It can, however, escape many of the traps that plain local search cannot.
  • The penalty function is the key. At each local optimum, GLS picks the feature ii that maximizes ci1+pi\frac{c_i}{1 + p_i}, where cic_i is the feature's original cost and pip_i its current penalty count. This utility measure favors features that are expensive and have been penalized least — intuitively, the ones most "worth" escaping. The augmented cost used by local search becomes g(s)=f(s)+λ∑ipi⋅Ii(s)g(s) = f(s) + \lambda \sum_i p_i \cdot I_i(s), where λ\lambda balances exploration against exploitation.
  • Empirical near-optimality. On benchmark TSP instances with thousands of cities, GLS with Lin–Kernighan moves finds solutions within 1–2% of the known optimum — competitive with the best exact methods for practical purposes.
  • Open questions. There is no general theorem about how many penalty steps GLS needs to escape all local optima on an arbitrary landscape. The interaction between the penalty parameter λ\lambda and the problem instance is an active research question.

The broader takeaway: GLS is a practical answer to the limits of computation. When P vs NP tells us we cannot expect an efficient exact algorithm, penalty-guided search is one of our best tools for finding solutions that are good enough.

Where It Matters

Guided Local Search is not a toy — it is used in real systems that need good solutions to NP-hard problems fast:

  • Vehicle routing: GLS and its variants drive many state-of-the-art solvers for the Vehicle Routing Problem, which underlies delivery logistics for millions of packages a day.
  • Job scheduling: penalizing bottleneck operations guides the search away from schedules that repeatedly overload the same machine.
  • Network design: penalizing expensive or congested links helps find low-cost network topologies without exhaustive enumeration.
  • Constraint satisfaction: penalty-based guidance is a natural fit for problems where violating constraints can be treated as costly features — the same idea as in SAT solvers that use clause-weight penalties.
  • Combinatorial auctions: bidding configurations are solutions; GLS has been applied to winner-determination problems where exact algorithms are too slow.

Whenever you face a problem where local search gets stuck and exact methods are too slow, GLS is a strong first meta-heuristic to reach for — alongside simulated annealing and tabu search, which share the goal of escaping local optima but use different mechanisms.

Conclusion

Guided Local Search has a beautiful philosophy: instead of pretending a local optimum is good enough, penalize it. Every trap the algorithm falls into leaves a mark — a small increment to the cost of the features that defined that trap — and those marks collectively reshape the landscape so the next search runs differently.

No theorem guarantees this works in the worst case. But for the hard combinatorial problems that matter in practice — routing, scheduling, network design — GLS consistently finds solutions that are within a few percent of the best known, orders of magnitude faster than any exact algorithm could.

That is the pragmatic lesson when P vs NP blocks the door to efficient exact solutions: accumulate knowledge about where you have been, penalize the features that kept you there, and let the augmented landscape guide you somewhere better.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

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