• PDF / 876,499 Bytes
• 24 Pages / 595.276 x 790.866 pts Page_size
• 40 Downloads / 245 Views

DOWNLOAD

REPORT

---

(0123456789().,-volV)(0123456789(). ,- volV)

A new taxonomy of global optimization algorithms Jo¨rg Stork1

•

A. E. Eiben2 • Thomas Bartz-Beielstein1

Accepted: 6 November 2020  The Author(s) 2020

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. Keywords Metaheuristics  Surrogate  Hybrid optimization  Evolutionary computation  Taxonomy

1 Introduction Modern applications in industry, business, and information systems require a tremendous amount of optimization. Global optimization (GO) tackles various severe problems emerging from the context of complex physical systems, business processes, and particular from applications of artificial intelligence. Challenging problems arise from industry on the application level, e.g., machines regarding manufacturing speed, part quality or energy efficiency, or on the business level, such as optimization of production

& Jo¨rg Stork [email protected] A. E. Eiben [email protected] Thomas Bartz-Beielstein [email protected] 1

Technische Hochschule Ko¨ln, Steinmu¨llerallee 1, 51643 Gummersbach, Germany

2

Vrije Universiteit Amsterdam, 1081 HV Amsterdam, The Netherlands

plans, purchase, sales, and after-sales. Further, they emerge from areas of artificial intelligence and information engineering, such as machine learning, e.g., optimization of standard data models such as neural networks for different applications. Their complex nature connects all these problems: they tend to be expensive to solve, and with unknown objective function properties, as the underlying mechanisms are often not well described or unknown. Solving optimization problems of this kind relies necessarily on performing costly computations, such as simulations, or even real-world experi