Scatter Search

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.

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.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<canvas id="landscape" width="300" height="260"></canvas>
<div class="status" id="status">{{initial_status}}</div>
<div class="btns">
  <button id="btn-combine" type="button">{{btn_combine}}</button>
  <button id="btn-update" type="button">{{btn_update}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="legend">
  <span class="dot ref"></span> {{legend_ref}}
  &nbsp;
  <span class="dot cand"></span> {{legend_cand}}
</div>

/* {{c_css_intro}} */
* { 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; }

// Code not found

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.

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 $b$ is kept small (typically $b \le 20$). All $\binom{b}{2}$ pairs are combined each iteration, so the per-iteration work scales as $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.

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.

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.