A new Taxonomy of Continuous Global Optimization Algorithms

Jörg Stork, A. E. Eiben, Thomas Bartz-BeielsteinarXiv 2018 · DOI · OpenReview

Abstract

Surrogate-based optimization, nature-inspired metaheuristics, and hybrid combinations have become state of the art in algorithm design for solving real-world optimization problems. Still, it is difficult for practitioners to get an overview that explains their advantages in comparison to a large number of available methods in the scope of optimization. Available taxonomies lack the embedding of current approaches in the larger context of this broad field. This article presents a taxonomy of the field, which explores and matches algorithm strategies by extracting similarities and differences in their search strategies. A particular focus lies on algorithms using surrogates, nature-inspired designs, and those created by design optimization. The extracted features of components or operators allow us to create a set of classification indicators to distinguish between a small number of classes. The features allow a deeper understanding of components of the search strategies and further indicate the close connections between the different algorithm designs. We present intuitive analogies to explain the basic principles of the search algorithms, particularly useful for novices in this research field. Furthermore, this taxonomy allows recommendations for the applicability of the corresponding algorithms.

The Problem: Navigating the Algorithm "Zoo"

The landscape of global optimization (GO) algorithms has exploded in recent decades. Driven by massive increases in computational power, researchers have developed a vast array of nature-inspired metaheuristics, data-driven surrogate models, and automated hyperheuristics.

However, existing taxonomies—many dating back to the 1960s and 80s—have failed to keep pace. They often fail to integrate modern hybrid approaches or demonstrate how different methods relate to one another. Consequently, practitioners face an overwhelming "zoo" of algorithms, making it difficult to choose the right strategy for real-world, computationally expensive, or "black-box" problems where the underlying mathematical structure is unknown.

A Bottom-Up Taxonomy

Instead of simply listing algorithms by name, this research proposes a bottom-up approach. Any optimization algorithm can be deconstructed into four fundamental design elements:

  • Initialization: Where the search begins.
  • Generation: How new candidate solutions are created.
  • Selection: How the algorithm decides which solutions survive to the next iteration.
  • Control: How parameters are tuned and adapted during the search.

Based on how algorithms handle these elements, they are grouped into five intuitive classes, described using human pathfinding analogies:

  1. Hill-Climbing ("The Mountaineer"): Focuses on greedy exploitation to reach the nearest peak (e.g., Gradient Descent).
  2. Trajectory ("The Sightseer"): Maintains a single candidate but uses exploration rules to escape local optima (e.g., Simulated Annealing).
  3. Population ("The Team"): Uses multiple candidates sharing information to explore and exploit simultaneously (e.g., Particle Swarm Optimization).
  4. Surrogate ("The Surveyor"): Builds a topological map (a data-driven regression model) to predict where the best solutions lie, saving on expensive real-world evaluations.
  5. Hybrid ("The Chimera"): Combines elements from different classes or uses machine learning to generate new configurations dynamically.

Architecture and Real-World Application

Modern optimization often involves layers of abstraction between the algorithm and the physical process. As shown in the architecture below, surrogate models act as intermediaries, providing a "cheap" mathematical approximation of expensive computational models or real-world industrial processes.

The architecture of modern optimization systems, illustrating the flow between algorithms, surrogate models, and real-world applications.

Key Insights

  • Algorithms as Modular Components: Despite biologically-inspired names, most modern algorithms are configurations of the same core search operators. Recognizing this modularity makes the field easier to navigate.
  • The Rise of the "Chimera": The future of optimization lies in automated hyperheuristics—systems that dynamically mix and match search operators to suit the specific problem at hand.
  • Surrogates are Essential: For physical systems where a single evaluation might take hours, "Surveyor" algorithms are the only viable choice, as they optimize a model rather than querying the expensive process directly.

Practical Selection Guidelines

The taxonomy provides a decision framework for practitioners based on problem features:

  • Unimodal + Cheap to evaluate: Use Hill-Climbers.
  • Black-box + Small evaluation budget: Use Surrogate-based methods.
  • Complex/Noisy + Large evaluation budget: Use Population-based methods.
  • Unknown landscape + Need versatility: Use Hybrid methods.

Future Challenges

Algorithm design must now evolve to meet the demands of Industry 4.0, requiring algorithms that run continuously on dynamic, communicating hardware. Furthermore, the training of massive machine learning models requires search strategies that are both sample-efficient and computationally inexpensive. A significant hurdle remains the lack of realistic, real-world benchmark problems to properly validate these modern approaches in practice.

Summary updated

Abstract

Surrogate-based optimization, nature-inspired metaheuristics, and hybrid combinations have become state of the art in algorithm design for solving real-world optimization problems. Still, it is difficult for practitioners to get an overview that explains their advantages in comparison to a large number of available methods in the scope of optimization. Available taxonomies lack the embedding of current approaches in the larger context of this broad field. This article presents a taxonomy of the field, which explores and matches algorithm strategies by extracting similarities and differences in their search strategies. A particular focus lies on algorithms using surrogates, nature-inspired designs, and those created by design optimization. The extracted features of components or operators allow us to create a set of classification indicators to distinguish between a small number of classes. The features allow a deeper understanding of components of the search strategies and further indicate the close connections between the different algorithm designs. We present intuitive analogies to explain the basic principles of the search algorithms, particularly useful for novices in this research field. Furthermore, this taxonomy allows recommendations for the applicability of the corresponding algorithms.
BibTeX
@misc{stork2018new,
  author = {Jörg Stork and A. E. Eiben and Thomas Bartz-Beielstein},
  title = {{A new Taxonomy of Continuous Global Optimization Algorithms}},
  year = {2018},
  eprint = {1808.08818},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1808.08818},
}
Figure