Metaheuristic optimisation entered the mainstream of computing in the 1980s as a pragmatic answer to a hard fact: many of the problems industry most wanted solved were combinatorial, NP-hard, and far too large for exact methods to touch within any usable timeframe. Simulated annealing, genetic algorithms, and tabu search emerged within a few years of one another, each offering solutions good enough for practical use inside the compute and time budgets of the day. Four decades on, those same families of methods quietly run a great deal of the infrastructure around us. We think their durability is worth examining, both for what it says about the methods and for where it points next.
A pragmatic response to intractable problems
Three foundational methods anchor the period. Simulated annealing borrowed the physics of slow cooling to escape local optima (Kirkpatrick, Gelatt, & Vecchi, 1983). Genetic algorithms recast search as population-based recombination and selection (Goldberg, 1989). Tabu search added adaptive memory, steering search away from recently visited regions and toward unexplored ones (Glover, 1986). Each reflected the constraints of its moment. Exact optimisation was intractable at the problem sizes practitioners cared about, so the research question shifted from finding the provably optimal solution to finding a strong solution within a fixed budget. Methods that answered that question well earned their place, and they have kept it.
Where the methods actually live now
Forty years later, metaheuristics sit inside systems most people never think about. University and examination timetabling, vehicle routing and last-mile delivery, staff rostering, production scheduling, resource assignment, and radio spectrum allocation all rely on heuristic search to produce workable plans at scale. We worked on one such problem directly in the 1990s, assigning frequencies to tens of thousands of radio transmitters while holding interference within tolerance, a task that remains a textbook case of large-scale combinatorial optimisation. Demand for these solutions has grown rather than receded. Logistics networks, cloud workloads, and energy systems have only made the underlying problems larger and the value of good-enough-fast solutions higher.
No single method wins outright
A formal result clarified what practitioners had already observed: averaged across all possible problems, no optimisation method outperforms any other (Wolpert & Macready, 1997). Performance is earned on specific problem structures, not in general. Simulated annealing may suit one landscape, an evolutionary method another, tabu search a third. That finding reframed the field’s ambition. Rather than chasing a single best algorithm, researchers began combining methods so that the strengths of one cover the weak spots of another. Memetic algorithms fused population search with local refinement. Matheuristics married exact mathematical programming with heuristic guidance. Hyper-heuristics raised the level of abstraction again, selecting or generating heuristics automatically for the instance at hand (Burke et al., 2013).
What we are still learning
Hybridisation raised a harder question than it settled. Knowing that a mixture can outperform its components says little about which mixture, for which problem, configured how. Much current research addresses exactly that composition problem. Machine learning now informs choices that metaheuristics once made by hand, learning which moves to favour, which instances resemble which, and where search effort pays off (Bengio, Lodi, & Prouvost, 2021). Automated algorithm configuration and selection have turned tuning from craft into a measurable, repeatable process. We read this as continuity rather than replacement. Learning components are augmenting the metaheuristic scaffolding built in the 1980s, not discarding it, and the most capable systems we see in practice are hybrids of hybrids: classical search, mathematical programming, and learned heuristics working in concert.
For applied work, the lesson of forty years is steady. Understand the problem’s structure first, choose or compose methods to fit it, and treat the optimiser as something to be measured and improved rather than settled once. Forty years on, the core techniques have aged remarkably well. Composition is where the interesting work now lies.