Abstract: Meta-heuristics are methods that sit on top of local search algorithms. They perform the function of avoiding or escaping a local optimum and/or premature convergence. The aim of this paper is to survey, compare and contrast meta-heuristics for local search. First, we present the technique of local search (or hill climbing as it is sometimes known). We then present a table displaying the attributes of all the different meta-heuristics. After this, we give a short description and discussion of each meta-heuristic with pseudo code. Finally, we describe why, in general, these techniques work and present some ideas of what is needed from the next generation of meta-heuristics.
Introduction
The core challenge in combinatorial optimization—encompassing problems like the Traveling Salesman Problem (TSP), Scheduling, and Boolean Satisfiability (SAT)—is the "Local Optimum" problem. Simple local search algorithms, such as hill-climbing, are efficient but inherently "greedy." They move to an adjacent better solution and terminate the moment no immediate improvement is found. This often leaves the algorithm trapped in a "valley" that is superior to its immediate surroundings but significantly inferior to the global peak.
This survey serves as a foundational "field guide" for researchers navigating the complex landscape of meta-heuristics developed primarily in the 1990s. It provides a rigorous taxonomy and standardized pseudo-code for the most influential algorithms designed to rescue local search from these sub-optimal traps.
Taxonomy of Meta-heuristics
The paper categorizes meta-heuristics into four primary "escape mechanisms" based on how they navigate the search space:
- Random Move Based: Algorithms like Simulated Annealing (SA) and Walksat introduce noise or "upward moves" to shake the algorithm out of local minima.
- Population Based: Methods like Genetic Algorithms (GA), Ant Colony Optimization (ACO), and Memetic Algorithms maintain multiple solutions simultaneously, allowing the search to explore different regions of the landscape in parallel.
- Neighbourhood Based: Tabu Search (TS) and Variable Neighbourhood Search (VNS) modify the search space itself—either by using memory to "ban" recently visited moves or by dynamically changing the definition of what a "neighbor" is.
- Weighted/Penalty Based: Guided Local Search (GLS) and GENET "fill in" local minima by penalizing specific features of the current solution, effectively forcing the algorithm to climb out of the valley and explore elsewhere.
Comparative Analysis of Meta-heuristics
A central contribution of this survey is the systematic mapping of algorithms against their defining attributes. This matrix helps engineers understand which mechanism (randomness, memory, or population) is best suited for a specific problem landscape.
Qualitatively, the authors observe that the success of an algorithm depends heavily on the "landscape" of the problem. For example, Guided Local Search (GLS) and Tabu Search are often superior for structured problems like the Quadratic Assignment Problem (QAP), while Walksat remains a gold standard for SAT problems due to its efficient handling of constraints.
Theoretical Foundations and Insights
The Proximate Optimality Principle (POP)
The authors argue that meta-heuristics are not merely random jumping; they work because, in most real-world problems, "good solutions have similar structures." This principle suggests that if a local optimum is found, the global optimum is likely to be located nearby in the search space.
Memory vs. Randomness
The survey highlights a historical shift from memoryless randomness (Simulated Annealing) toward "intelligent" memory. Tabu Search utilizes short-term memory to avoid cycles, while Guided Local Search employs long-term memory to learn which features of a solution are undesirable and should be avoided in future iterations.
The Power of Hybrids
The most successful modern approaches are often hybrids. For instance, Memetic Algorithms combine the global exploration capabilities of Genetic Algorithms with the surgical precision of local search, balancing broad exploration with deep exploitation.
Future Directions
While these methods are effective in practice, the authors identify several areas for future development:
- General Applicability: Many meta-heuristics require extensive "hand-tuning." There is a need for richer modeling languages (like EaCL or OPL) to apply these algorithms to industrial problems without massive code rewrites.
- Theoretical Guarantees: There remains a lack of theoretical guarantees regarding the time required to reach a global optimum for most meta-heuristics.
- Parallelism: Future meta-heuristics must be designed for large-scale computational grids to handle the increasingly massive datasets found in modern industrial applications.
Summary updated