A new taxonomy of global optimization algorithms

Jörg Stork, A. E. Eiben, Thomas Bartz-BeielsteinNat. Comput 2022 · OpenReview

TL;DR

This paper introduces a novel, comprehensive taxonomy for global optimization algorithms, addressing the lack of a unified framework for modern approaches like surrogate-based, nature-inspired, and hybrid methods. By analyzing core algorithm components and using intuitive analogies, it provides a clear understanding of their similarities and differences, aiding practitioners in selecting the most suitable algorithm for a given problem.

What Problem Does This Paper Address?

The field of global optimization (GO) has seen a surge in sophisticated algorithms, including nature-inspired metaheuristics, surrogate-based methods, and hyperheuristics. However, existing taxonomies struggle to keep pace with these advancements, often failing to integrate them into a broader context or highlight their interconnections. This makes it challenging for practitioners to navigate the vast landscape of available methods, understand their relative strengths and weaknesses, and select the most appropriate algorithm for a specific real-world optimization problem. The authors aim to bridge this gap by proposing a new, generalized taxonomy that categorizes algorithms based on fundamental search strategies and components.

Methods

The authors propose a new taxonomy based on five key algorithm design elements: initialization, generation, selection, control, and evaluation. They analyze existing GO algorithms and identify commonalities and differences in their search strategies. This analysis leads to the definition of five intuitive algorithm classes: Hill-Climber ("Mountaineer"), Trajectory ("Sightseer"), Population ("Team"), Surrogate ("Surveyor"), and Hybrid ("Chimera"). Each class is described using analogies to human behavior in pathfinding to enhance understanding, particularly for novices. The taxonomy is designed to be generalizable, connect different algorithm classes, and provide practical guidance for algorithm selection.

Datasets

Not discussed in the paper. The paper focuses on developing a conceptual framework and taxonomy rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unified Framework: The paper provides a much-needed unified framework for understanding the diverse landscape of modern global optimization algorithms, moving beyond fragmented classifications.
  • Component-Based Analysis: By breaking down algorithms into fundamental components (initialization, generation, selection, control), the taxonomy reveals deeper connections and similarities between seemingly disparate methods.
  • Intuitive Analogies: The use of human-like analogies (mountaineer, sightseer, team, surveyor, chimera) makes complex search strategies more accessible and understandable, especially for newcomers to the field.
  • Bridging Theory and Practice: The taxonomy aims to not only classify algorithms but also to provide practical guidance for practitioners in selecting the most appropriate algorithm based on problem characteristics.
  • Evolution of Taxonomies: The paper highlights the historical evolution of GO algorithm taxonomies, demonstrating how they have adapted (or failed to adapt) to new algorithmic paradigms.

Key Results

The paper's primary contribution is the proposed taxonomy itself, which categorizes global optimization algorithms into five intuitive classes: Hill-Climber, Trajectory, Population, Surrogate, and Hybrid. Each class is further detailed with subclasses and specific examples. The authors illustrate the interconnectedness of these classes through a feature overview diagram and a summary table of example algorithms. While no quantitative performance results are presented, the taxonomy is intended to facilitate better algorithm selection and understanding, ultimately leading to improved performance in practice.

Limitations and Future Work

The authors acknowledge that their taxonomy is a "new" proposal and that further refinement and validation might be necessary. While they provide intuitive analogies for understanding, the practical application of the taxonomy for algorithm selection is presented as a guideline, suggesting that further research could develop more concrete decision-making tools. Future work could involve empirically validating the proposed taxonomy by applying it to a wider range of optimization problems and comparing the performance of algorithms within and across the defined classes. Additionally, the authors point to exciting challenges in industry 4.0 and machine learning that require new optimization algorithm designs, suggesting that the taxonomy can serve as a foundation for developing these future methods.

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 automatic algorithm generation. The extracted features of algorithms, their main concepts, and search 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
@inproceedings{stork2022new,
  author = {Jörg Stork and A. E. Eiben and Thomas Bartz-Beielstein},
  title = {{A new taxonomy of global optimization algorithms}},
  booktitle = {Nat. Comput},
  year = {2022},
  url = {https://openreview.net/forum?id=BiHevWu7br},
}
Figure