Introduction

Most search algorithms face the same dilemma: explore widely and waste time on bad territory, or exploit the best solution you know and get stuck in a local optimum. Scatter search, introduced by Fred Glover in the 1970s and formalized in the 1990s, offers a principled middle path.

The central idea is simple: keep a small reference set of solutions — not just the best ones, but also the most diverse ones. Then systematically combine pairs or subsets of that reference set to generate new candidate solutions. Improvement methods polish each new candidate, and the reference set is updated whenever something better or more diverse arrives.

This balance of quality and diversity is what separates scatter search from plain greedy algorithms: it is designed to cross solution components that no single greedy descent would ever assemble, yet it does not wander randomly — every combination is guided by the structure of the best solutions found so far.

Combine Elite Solutions

The canvas below shows a simple 2D landscape — darker means lower cost (better). Five colored dots are the current reference set: the algorithm's elite solutions. Click Combine to generate new candidates by interpolating between reference-set pairs, then Update set to replace the worst members with any improvements.

<!-- Scatter Search interactive demo — landscape canvas + control buttons -->
<p class="hint">Five red dots form the <b>reference set</b> — the elite solutions. Click <b>Combine</b> to interpolate between all pairs (blue dots). Then click <b>Update set</b> to replace the worst members with better or more diverse candidates.</p>
<canvas id="landscape" width="300" height="260"></canvas>
<div class="status" id="status">Press Combine to generate candidates.</div>
<div class="btns">
  <button id="btn-combine" type="button">Combine</button>
  <button id="btn-update" type="button">Update set</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="legend">
  <span class="dot ref"></span> Reference set
  &nbsp;
  <span class="dot cand"></span> Candidates
</div>

/* Layout and color styles for the scatter search demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border-radius: 8px; border: 1px solid #cdd9e3; cursor: crosshair; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { font-size: .82rem; color: #555; display: flex; align-items: center; gap: .3rem; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.dot.ref { background: #e63946; }
.dot.cand { background: #457b9d; }

/* Scatter Search demo — reference set + combination + update logic */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

const W = 300, H = 260;
const canvas = document.getElementById('landscape');
const ctx = canvas.getContext('2d');

/* Cost function: sum of sinusoids with two local minima and one global minimum */
function cost(x, y) {
  const nx = x / W, ny = y / H;
  /* Two wells plus sinusoidal noise; global min near (0.72, 0.65) in normalized coords */
  return (
    0.6 * Math.sin(nx * Math.PI * 2.5) * Math.sin(ny * Math.PI * 2.5) +
    0.4 * Math.sin(nx * Math.PI * 1.2 + 0.8) * Math.sin(ny * Math.PI * 1.8 + 0.5) -
    0.9 * Math.exp(-((nx - 0.72) ** 2 + (ny - 0.65) ** 2) * 20) -
    0.5 * Math.exp(-((nx - 0.28) ** 2 + (ny - 0.35) ** 2) * 18)
  );
}

/* Draw the cost landscape as a heatmap — darker = lower cost = better */
function drawBackground() {
  const img = ctx.createImageData(W, H);
  let minC = Infinity, maxC = -Infinity;
  const vals = new Float32Array(W * H);
  for (let y = 0; y < H; y++) for (let x = 0; x < W; x++) {
    const c = cost(x, y); vals[y * W + x] = c;
    if (c < minC) minC = c; if (c > maxC) maxC = c;
  }
  for (let i = 0; i < W * H; i++) {
    const t = 1 - (vals[i] - minC) / (maxC - minC); /* t=1 means low cost (dark), t=0 means high cost (light) */
    const r = Math.round(20 + t * 180), g = Math.round(40 + t * 190), b = Math.round(80 + t * 140);
    img.data[i * 4] = r; img.data[i * 4 + 1] = g; img.data[i * 4 + 2] = b; img.data[i * 4 + 3] = 255;
  }
  ctx.putImageData(img, 0, 0);
}

/* Reference set: REF_SIZE elite solutions maintained across iterations */
const REF_SIZE = 5;
let refSet = [];
let candidates = [];

function initRefSet() {
  /* Initial reference set — scattered across the canvas for diversity */
  refSet = [
    { x: 40,  y: 40  },
    { x: 260, y: 30  },
    { x: 150, y: 130 },
    { x: 50,  y: 220 },
    { x: 240, y: 200 }
  ].map(p => ({ ...p, cost: cost(p.x, p.y) }));
  candidates = [];
}

function drawDot(x, y, color, radius) {
  ctx.beginPath(); ctx.arc(x, y, radius, 0, Math.PI * 2);
  ctx.fillStyle = color; ctx.fill();
  ctx.strokeStyle = '#fff'; ctx.lineWidth = 1.5; ctx.stroke();
}

function render() {
  drawBackground();
  /* Draw candidate solutions (blue, smaller) */
  for (const c of candidates) drawDot(c.x, c.y, '#457b9d', 5);
  /* Draw reference set members (red, larger) */
  for (const r of refSet) drawDot(r.x, r.y, '#e63946', 7);
}

/* Generate candidates by linearly interpolating between all ref-set pairs */
function combine() {
  candidates = [];
  for (let i = 0; i < refSet.length; i++) {
    for (let j = i + 1; j < refSet.length; j++) {
      const a = refSet[i], b = refSet[j];
      /* Three interpolation points between each pair */
      for (const t of [0.33, 0.5, 0.67]) {
        const x = Math.round(a.x + t * (b.x - a.x));
        const y = Math.round(a.y + t * (b.y - a.y));
        candidates.push({ x, y, cost: cost(x, y) });
      }
    }
  }
  render();
  setStatus('Candidates generated — press Update set.', 'info');
}

/* Update ref set — keep best by cost while enforcing minimum distance for diversity */
function updateRefSet() {
  if (candidates.length === 0) { setStatus('No candidates yet — press Combine first.', 'info'); return; }
  const pool = [...refSet, ...candidates];
  pool.sort((a, b) => a.cost - b.cost);
  /* Greedy diversity rule — minimum pixel distance between retained members */
  const newRef = [pool[0]];
  for (const p of pool.slice(1)) {
    const minDist = Math.min(...newRef.map(r => Math.hypot(r.x - p.x, r.y - p.y)));
    if (minDist > 20) newRef.push(p);
    if (newRef.length === REF_SIZE) break;
  }
  /* Fill remaining slots if not enough diverse points found */
  let idx = 1;
  while (newRef.length < REF_SIZE && idx < pool.length) {
    if (!newRef.includes(pool[idx])) newRef.push(pool[idx]);
    idx++;
  }
  const prevBest = Math.min(...refSet.map(r => r.cost));
  const newBest = Math.min(...newRef.map(r => r.cost));
  refSet = newRef;
  candidates = [];
  render();
  if (newBest < prevBest - 0.001) {
    setStatus(i18nFmt('Reference set improved! Best cost: %val%', { val: newBest.toFixed(3) }), 'ok');
  } else {
    setStatus('Reference set updated (no improvement this round).', 'info');
  }
}

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

document.getElementById('btn-combine').addEventListener('click', combine);
document.getElementById('btn-update').addEventListener('click', updateRefSet);
document.getElementById('btn-reset').addEventListener('click', () => {
  initRefSet(); render(); setStatus('Press Combine to generate candidates.', 'info');
});

/* Initialize and draw on load */
initRefSet();
render();
setStatus('Press Combine to generate candidates.', 'info');
Result
Console

Notice how the reference set gradually clusters near the global minimum (the darkest region) while a diversity rule keeps solutions from collapsing to a single point. That tension — converge on quality, preserve diversity — is the engine of scatter search.

The Real Complexity

Scatter search targets combinatorial optimization problems — scheduling, routing, design — many of which are NP-hard. Against such problems it offers no guarantee of finding the global optimum; what it offers instead is a systematic structure that outperforms naive search.

  • Reference-set size bb is kept small (typically b≤20b \le 20). All (b2)\binom{b}{2} pairs are combined each iteration, so the per-iteration work scales as O(b2)O(b^{2}) — modest even when each evaluation is expensive.
  • Combination method: new candidates are built as convex or linear combinations of parent solutions plus structured perturbations. This is the key difference from random restarts: the search is guided by the geometry of known-good solutions.
  • Improvement method: each generated candidate is polished by a local search before evaluation. The quality of this local search determines how quickly the reference set improves.
  • Diversification generator: the initial population is spread deliberately across the space, preventing the algorithm from ignoring entire regions from the start.

Because scatter search is a heuristic, its quality depends heavily on the choice of combination and improvement methods. In the best cases — logistics, circuit design, bioinformatics — it has matched or beaten exact solvers on benchmark instances of hundreds of variables.

Where It Matters

Any problem where you can define a solution, measure its quality, and mix two solutions to get a third is a candidate for scatter search:

  • Vehicle routing: combine the routes of two good driver schedules to discover shorter combined tours — a staple benchmark for metaheuristics.
  • Telecom network design: Glover and colleagues applied scatter search to bandwidth allocation and topology optimization, cutting costs well below greedy baselines.
  • Bioinformatics: sequence alignment and protein-structure problems benefit from the method's ability to cross high-quality partial alignments.
  • Hyperparameter tuning in machine learning: the reference set holds high-performing model configurations; combinations explore the joint space of learning rate, depth, regularization, and so on.
  • VLSI circuit placement: mixing two good chip layouts often yields a third that inherits the best subregions of each.

Scatter search is closely related to genetic algorithms — both maintain a population and recombine members — but scatter search uses a smaller, more carefully maintained reference set and deterministic combination rules instead of crossover and mutation operators.

Conclusion

Scatter search distills a powerful lesson: the answer to a hard optimization problem often hides between the best answers you already know. By keeping a small, carefully curated reference set and combining its members in a structured way, the algorithm reaches regions of the search space that neither a greedy descent nor a random walk would ever find.

It carries no optimality certificate — for most of its target problems, P vs NP makes such a certificate computationally out of reach. But in practice, scatter search and its successors (path relinking, GRASP with scatter) are among the most reliable metaheuristics for combinatorial problems where solutions can be meaningfully combined. The insight that diversity + quality = reach is one of the most transferable ideas in all of optimization.

Share this article

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

Comments

Loading comments...

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