Source-linked AI summary
Review of Metaheuristics and Generalized Evolutionary Walk Algorithm
Xin-She Yang
TL;DR
Large-scale nonlinear optimization lacks agreed algorithm-selection guidance, particularly for NP-hard problems. The paper reviews nature-inspired metaheuristics, analyzes their exploration–exploitation components, and proposes GEWA; it reports preliminary efficiency comparable to other metaheuristics while identifying unresolved theory and comparison questions.
Problem
Large-scale nonlinear global optimization lacks an agreed algorithm-selection guideline, and efficient algorithms may not exist for NP-hard problems.
Method
The paper surveys nature-inspired metaheuristics, analyzes their components, and proposes GEWA as a generalized framework combining random exploration, local random walks, and elitist selection.
Results
Preliminary studies report that GEWA is as efficient as many other metaheuristic algorithms.
Takeaways & Limitations
GEWA offers a simple unified view of metaheuristic search through global exploration, local search, and selection of the best solutions with elitism.
Takeaways & Limitations
No universally better algorithm exists across all optimization functions, and convergence for most metaheuristics remains mathematically unproved.
Abstract
from arXiv · showhide
Metaheuristic algorithms are often nature-inspired, and they are becoming very powerful in solving global optimization problems. More than a dozen of major metaheuristic algorithms have been developed over the last three decades, and there exist even more variants and hybrid of metaheuristics. This paper intends to provide an overview of nature-inspired metaheuristic algorithms, from a brief history to their applications. We try to analyze the main components of these algorithms and how and why they works. Then, we intend to provide a unified view of metaheuristics by proposing a generalized evolutionary walk algorithm (GEWA). Finally, we discuss some of the important open questions.
1 Introduction
The paper frames optimization algorithm choice as problem-dependent, especially for large-scale nonlinear global problems where no agreed selection guideline exists. It introduces metaheuristics as stochastic trial-and-error methods that seek good solutions without guaranteeing optimality.
- Problem setting: Large-scale nonlinear global optimization lacks an agreed guideline for choosing an algorithm, and efficient algorithms may not exist for NP-hard problems.
- Problem formulation: Optimization problems commonly specify design variables, objective functions, and equality or inequality constraints.
- Algorithm types: Optimization algorithms range from conventional deterministic methods to modern metaheuristics.
- Algorithm types: Gradient-based methods can work extremely well on smooth unimodal problems but perform poorly when the objective function is discontinuous.
- Stochastic search: Heuristic and metaheuristic methods use trial and error to find quality solutions in reasonable time without guaranteeing optimal solutions.
2 Metaheuristics
Metaheuristics operate beyond simple heuristics by balancing local exploitation with global exploration, often through randomization. Their purpose is to find feasible solutions practically, although optimality and performance are not guaranteed.
- Core principles: Metaheuristics combine local search and global exploration, with randomization often generating solution variety.
- Core principles: Randomization helps metaheuristics move from local search toward global optimization.
- Practical purpose: Metaheuristics seek good feasible solutions within acceptable times because complex problems make exhaustive search impractical.
- Search components: Diversification explores the search space globally, whereas intensification exploits information around a currently good local region.
- Classification: Population-based methods use multiple solutions, while trajectory-based methods move a single solution through the search space.
3 Overview of Metaheuristics
The overview traces metaheuristics from evolutionary and trajectory-based methods to swarm, immune, harmony, and other nature-inspired algorithms. It emphasizes broad empirical success while noting that no universally superior algorithm exists.
- History: Heuristic problem-solving has historical roots in trial and error, including examples associated with Archimedes and wartime code-breaking.
- Evolutionary algorithms: Genetic algorithms formalized Darwinian evolution through crossover, mutation, fitness, and selection, and became widely used for optimization.
- Evolutionary algorithms: Evolutionary strategies used mutation and selection for aerospace optimization and initially omitted crossover.
- Trajectory and memory: Simulated annealing introduced trajectory-based search inspired by metal annealing, while tabu search added explicit memory to modern metaheuristics.
- Higher-level methods: Memetic algorithms can be viewed as hyper-heuristics because they combine multi-generation co-evolution and self-generation.
- Nature-inspired expansion: Ant colony optimization, artificial immune systems, particle swarm optimization, harmony search, differential evolution, and cross-entropy expanded nature-inspired approaches.
- Comparative evidence: Particle swarm optimization has many variants and evidence of superiority over traditional search and genetic algorithms for some problems, but the evidence is not conclusive.
- Comparative evidence: The no-free-lunch theorems state that an algorithm outperforming another on some functions will underperform it on others, so no universally better algorithm exists.
4 Characteristics of Metaheuristics
Metaheuristic efficiency is associated with nature-inspired selection and two complementary search characteristics: intensification and diversification. Their balance governs the trade-off between local convergence and global exploration.
- Natural inspiration: Metaheuristic efficiency is attributed partly to imitating successful natural features, especially selection of the fittest.
- Search characteristics: Intensification searches locally and intensively, whereas diversification explores the search space globally.
- Search trade-offs: Too little exploration can trap a search in local optima, while too little exploitation can slow convergence.
- Selection: Survival-of-the-fittest selection updates the current best, while elitism preserves the best solutions for later generations.
5 Importance of Randomisation
Metaheuristics balance diversification and intensification through randomisation, local search, selection, and controlled reduction of randomness. Their implementations differ, but these components jointly shape exploration, exploitation, and convergence.
- Balance and implementation: Exploration and exploitation are often intertwined, and implementation choices can affect performance, making validation and testing important.Different algorithms use different mechanisms to balance these activities, with no universal distinction between them.
- Diversification: Diversification combines randomisation with deterministic procedures to distribute newly generated solutions across the feasible search space.Uniform sampling is common, while long-tailed random walks such as Lévy flights can produce larger steps.
- Diversification: Mutation increases differences from existing solutions, while crossover limits over-diversification by recombining parts of existing solutions.These operators provide a more elaborate diversification mechanism than simple randomisation.
- Intensification: Exploitation generates solutions locally and intensively around promising or better solutions, using random walks with appropriately small step sizes.Large steps increase diversification but reduce intensification by moving beyond the region of interest.
- Random-walk control: Lévy flights improve random-walk exploration by drawing step sizes from a long-tailed distribution that permits larger movements.The paper links long-tail distributions to increased step size and travel distance.
- Random-walk control: Walking around the current best solution provides a more selective form of local search than walking around any good solution.This replaces the generic local-walk formulation with a best-centered one.
- Selection: Selection mechanisms retain high-quality solutions, discard poor ones, and use elitism or probabilistic criteria to improve evolving populations.Elitism is particularly noted for multimodal and multi-objective problems, while randomisation can remove worse solutions.
- Randomness reduction: Randomness should generally decrease as better solutions emerge, although algorithms may instead control it through mutation rates or acceptance probabilities.Particle swarm optimisation reduces randomness as particles approach the global best; simulated annealing reduces acceptance probability.
6 The Generalized Evolutionary Walk Algorithm (GEWA)
GEWA is proposed as a generic global-optimisation framework combining global randomisation, local random walks, and selection with elitism. Preliminary studies report efficiency comparable to many metaheuristics, while the method uses two algorithm-dependent parameters and requires careful balance of search components.
- 6 The Generalized Evolutionary Walk Algorithm (GEWA): Effective GEWA search requires frequent early global exploration, continued sparse exploration to escape local traps, and efficient local search.The paper identifies the balance between global and local search as paramount.
- 6 The Generalized Evolutionary Walk Algorithm (GEWA): GEWA combines global exploration by randomisation, intensive local search by random walk, and selection of the best solutions with elitism.The algorithm is presented as a generalized framework for global optimisation, with pseudocode shown in Figure 1.
- 6 The Generalized Evolutionary Walk Algorithm (GEWA): The local random walk is centered on the current global best g* to exploit information from the best solution found so far.The walk uses Gaussian noise and a step-length vector related to the scales of the independent variables.
- 6 The Generalized Evolutionary Walk Algorithm (GEWA): GEWA initializes n walkers, evaluates their fitness, identifies the current best, iterates until a stopping criterion, and replaces worst solutions during evolution.Randomisation is conditionally applied using the control parameter α.
- 6 The Generalized Evolutionary Walk Algorithm (GEWA): GEWA has two algorithm-dependent parameters: population size n and randomisation control parameter α, typically chosen near 0.25–0.7.The paper notes that too few walkers are inefficient, whereas too many may slow convergence.
- 6 The Generalized Evolutionary Walk Algorithm (GEWA): The balance between intensification and diversification is controlled by α, while the step-size-to-scale ratio is typically 0.001–0.01.Selection of the best solutions and elitism are also identified as important design issues.
- 6 The Generalized Evolutionary Walk Algorithm (GEWA): Preliminary studies report that GEWA is as efficient as many other metaheuristic algorithms and has a simple working mechanism.The paper states that detailed comparative analysis will be reported elsewhere.
7 Open Problems
The paper identifies unresolved theoretical and methodological questions about why metaheuristics work, how their components interact, and how algorithm performance should be compared. It also highlights open directions involving mathematical analysis, nature-inspired design, and more complex self-regulating algorithms.
- Mathematical explanations for metaheuristic success remain difficult, making the reasons these algorithms work an unresolved open problem.
- Convergence has been mathematically analyzed for simulated annealing and particle swarm optimisation, but not proved for the other algorithms discussed.
- The interactions among randomisation and deterministic components are only partly understood, including how to measure whether their balance has been reached.
- No-Free-Lunch theorems have been proved for single-objective optimisation, while their status and implications for multiobjective optimisation remain open.
- There is no agreed performance measure for comparing algorithms, although absolute objective value and functional evaluations are widely used.
- A future research direction is developing more complex metaheuristics that more closely mimic natural systems and become self-regulating, self-evolving, and intelligent.