Skip to main content

2021 | Buch

Black Box Optimization, Machine Learning, and No-Free Lunch Theorems

insite
SUCHEN

Über dieses Buch

This edited volume illustrates the connections between machine learning techniques, black box optimization, and no-free lunch theorems. Each of the thirteen contributions focuses on the commonality and interdisciplinary concepts as well as the fundamentals needed to fully comprehend the impact of individual applications and problems. Current theoretical, algorithmic, and practical methods used are provided to stimulate a new effort towards innovative and efficient solutions. The book is intended for beginners who wish to achieve a broad overview of optimization methods and also for more experienced researchers as well as researchers in mathematics, optimization, operations research, quantitative logistics, data analysis, and statistics, who will benefit from access to a quick reference to key topics and methods. The coverage ranges from mathematically rigorous methods to heuristic and evolutionary approaches in an attempt to equip the reader with different viewpoints of the same problem.

Inhaltsverzeichnis

Frontmatter
Learning Enabled Constrained Black-Box Optimization
Abstract
This chapter looks at the issue of black-box constrained optimization where both the objective function and the constraints are unknown and can only be observed pointwise. Both deterministic and probabilistic surrogate models are considered: the latter, more specifically analysed, are based on Gaussian Processes and Bayesian Optimization to handle the exploration–exploitation dilemma and improve sample efficiency. Particularly challenging is the case when the feasible region might be disconnected and the objective function cannot be evaluated outside the feasible region; this situation, known as “partially defined objective function” or “non-computable domains”, requires a novel approach: a first phase is based on the SVM classification in order to learn the feasible region, and a second phase, optimization, is based on a Gaussian Process. This approach is the main focus of this chapter that analyses modelling and computational issues and demonstrates the sample efficiency of the resulting algorithms.
F. Archetti, A. Candelieri, B. G. Galuzzi, R. Perego
Black-Box Optimization: Methods and Applications
Abstract
Black-box optimization (BBO) is a rapidly growing field of optimization and a topic of critical importance in many areas including complex systems engineering, energy and the environment, materials design, drug discovery, chemical process synthesis, and computational biology. In this chapter, we present an overview of theoretical advancements, algorithmic developments, implementations, and several applications of BBO. Lastly, we point to open problems and provide future research directions.
Ishan Bajaj, Akhil Arora, M. M. Faruque Hasan
Tuning Algorithms for Stochastic Black-Box Optimization: State of the Art and Future Perspectives
Abstract
The focus of this paper lies on automatic and interactive tuning methods for stochastic optimization algorithms, e.g., evolutionary algorithms. Algorithm tuning is important because it helps to avoid wrong parameter settings, to improve the existing algorithms, to select the best algorithm for working with a real-world problem, to show the value of a novel algorithm, to evaluate the performance of an optimization algorithm when different option settings are used, and to obtain an algorithm instance that is robust to changes in problem specification. This chapter discusses strategical issues and defines eight key topics for tuning, namely, optimization algorithms, test problems, experimental setup, performance metrics, reporting, parallelization, tuning methods, and software. Features of established tuning software packages such as IRACE, SPOT, SMAC, and ParamILS are compared.
Thomas Bartz-Beielstein, Frederik Rehbach, Margarita Rebolledo
Quality-Diversity Optimization: A Novel Branch of Stochastic Optimization
Abstract
Traditional optimization algorithms search for a single global optimum that maximizes (or minimizes) the objective function. Multimodal optimization algorithms search for the highest peaks in the search space that can be more than one. Quality-Diversity algorithms are a recent addition to the evolutionary computation toolbox that do not only search for a single set of local optima, but instead try to illuminate the search space. In effect, they provide a holistic view of how high-performing solutions are distributed throughout a search space. The main differences with multimodal optimization algorithms are that (1) Quality-Diversity typically works in the behavioral space (or feature space), and not in the genotypic (or parameter) space, and (2) Quality-Diversity attempts to fill the whole behavior space, even if the niche is not a peak in the fitness landscape. In this chapter, we provide a gentle introduction to Quality-Diversity optimization, discuss the main representative algorithms, and the main current topics under consideration in the community. Throughout the chapter, we also discuss several successful applications of Quality-Diversity algorithms, including deep learning, robotics, and reinforcement learning.
Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, Jean-Baptiste Mouret
Multi-Objective Evolutionary Algorithms: Past, Present, and Future
Abstract
Evolutionary algorithms have become a popular choice for solving highly complex multi-objective optimization problems in recent years. Multi-objective evolutionary algorithms were originally proposed in the mid-1980s, but it was until the mid-1990s when they started to attract interest from researchers. Today, we have a wide variety of algorithms, and research in this area has become highly specialized. This chapter attempts to provide a general overview of multi-objective evolutionary algorithms, starting from their early origins, then moving in chronological order towards some of the most recent algorithmic developments. In the last part of the chapter, some future research paths on this topic are briefly discussed.
Carlos A. Coello Coello, Silvia González Brambila, Josué Figueroa Gamboa, Ma. Guadalupe Castillo Tapia
Black-Box and Data-Driven Computation
Abstract
Black box has been an important tool in studying computational complexity theory and has been used for establishing the hardness of problems. With an exponential growth in big data recently, data-driven computation has utilized black box as a tool for proving solutions to some computational problems. In this note, we present several observations on this new role of black box using reduction techniques in the computational complexity theory.
Rong Jin, Weili Wu, My T. Thai, Ding-Zhu Du
Mathematically Rigorous Global Optimization and Fuzzy Optimization
A Brief Comparison of Paradigms, Methods, Similarities, and Differences
Abstract
Mathematically rigorous global optimization and fuzzy optimization have different philosophical underpinnings, goals, and applications. However, some of the tools used in implementations are similar or identical. We review, compare and contrast basic ideas and applications behind these areas, referring to some of the work in the very large literature base.
Ralph Baker Kearfott
Optimization Under Uncertainty Explains Empirical Success of Deep Learning Heuristics
Abstract
One of the main objectives of science and engineering is to predict the future state of the world and come up with devices and strategies that would make this future state better. In some practical situations, we know how the state changes with time—e.g., in meteorology, we know the partial differential equations that describe the atmospheric processes. In such situations, prediction becomes a purely computational problem. In many other situations, however, we do not know the equation describing the system’s dynamics. In such situations, we need to learn this dynamics from data. At present, the most efficient way of such learning is to use deep learning—training a neural network with a large number of layers. To make this idea truly efficient, several trial-and-error-based heuristics were discovered, such as the use of rectified linear neurons, softmax, etc. In this chapter, we show that the empirical success of many of these heuristics can be explained by optimization-under-uncertainty techniques.
Vladik Kreinovich, Olga Kosheleva
Variable Neighborhood Programming as a Tool of Machine Learning
Abstract
Automatic programming is an efficient technique that has contributed to an important development in the artificial intelligence and machine learning fields. In this chapter, we introduce the technique called Variable Neighborhood Programming (VNP) that was inspired by the principle of the Variable Neighborhood Search (VNS) algorithm. VNP starts from a single solution presented by a program, and the search for a good quality global solution (program) continues by exploring different neighborhoods. The goal of our algorithm is to generate a good representative program adequate to a selected problem. VNP takes the advantages of the systematic change of neighborhood structures randomly or within a local search algorithm to diversify or intensify search through the solution space. To show its efficiency and usefulness, the VNP method is applied first for solving the symbolic regression problem (VNP-SRP) and tested and compared on usual test instances from the literature. In addition, the VNP-SRP method is tested in finding formulas for life expectancy as a function of some health care economic factors in 18 Russian districts. Finally, the VNP is implemented on prediction and classification problems and tested on real-life maintenance railway problems from the US railway system.
Nenad Mladenovic, Bassem Jarboui, Souhir Elleuch, Rustam Mussabayev, Olga Rusetskaya
Non-lattice Covering and Quantization of High Dimensional Sets
Abstract
The main problem considered in this paper is construction and theoretical study of efficient n-point coverings of a d-dimensional cube [−1, 1]d. Targeted values of d are between 5 and 50; n can be in hundreds or thousands and the designs (collections of points) are nested. This paper is a continuation of our paper (Noonan and Zhigljavsky, SN Oper Res Forum, 2020), where we have theoretically investigated several simple schemes and numerically studied many more. In this paper, we extend the theoretical constructions of (Noonan and Zhigljavsky, SN Oper Res Forum, 2020) for studying the designs that were found to be superior to the ones theoretically investigated in (Noonan and Zhigljavsky, SN Oper Res Forum, 2020). We also extend our constructions for new construction schemes that provide even better coverings (in the class of nested designs) than the ones numerically found in (Noonan and Zhigljavsky, SN Oper Res Forum, 2020). In view of a close connection of the problem of quantization to the problem of covering, we extend our theoretical approximations and practical recommendations to the problem of construction of efficient quantization designs in a cube [−1, 1]d. In the last section, we discuss the problems of covering and quantization in a d-dimensional simplex; practical significance of this problem has been communicated to the authors by Professor Michael Vrahatis, a co-editor of the present volume.
Jack Noonan, Anatoly Zhigljavsky
Finding Effective SAT Partitionings Via Black-Box Optimization
Abstract
In the present chapter we study one method for partitioning hard instances of the Boolean satisfiability problem (SAT). It uses a subset of a set of variables of an original formula to partition it into a family of subproblems that are significantly easier to solve individually. While it is usually very hard to estimate the time required to solve a hard SAT instance without actually solving it, the partitionings of the presented kind make it possible to naturally construct such estimations via the well-known Monte Carlo method. We show that the problem of finding a SAT partitioning with minimal estimation of time required to solve all subproblems can be formulated as the problem of minimizing a special pseudo-Boolean black-box function. The experimental part of the paper clearly shows that in the context of the proposed approach relatively simple black-box optimization algorithms show good results in application to minimization of the functions of the described kind even when faced with hard SAT instances that encode problems of finding preimages of cryptographic functions.
Alexander Semenov, Oleg Zaikin, Stepan Kochemazov
The No Free Lunch Theorem: What Are its Main Implications for the Optimization Practice?
Abstract
The chapter considers the recent but already classic theoretical result called No Free Lunch Theorem in the context of optimization practice. The No Free Lunch Theorem is probably the fundamental theoretical result of the Machine Learning field but its practical meaning and implication for practitioners facing “real life” industrial and design optimization problems are rarely addressed in the technical literature. This discussion is intended for a broad audience of mathematicians, engineers, and computer scientists and presents a probabilistic understanding of the theorem that can shed light to its meaning and impact in the industrial optimization practice.
Loris Serafino
What Is Important About the No Free Lunch Theorems?
Abstract
The No Free Lunch theorems prove that under a uniform distribution over induction problems (search problems or learning problems), all induction algorithms perform equally. As I discuss in this chapter, the importance of the theorems arises by using them to analyze scenarios involving nonuniform distributions, and to compare different algorithms, without any assumption about the distribution over problems at all. In particular, the theorems prove that anti-cross-validation (choosing among a set of candidate algorithms based on which has worst out-of-sample behavior) performs as well as cross-validation, unless one makes an assumption—which has never been formalized—about how the distribution over induction problems, on the one hand, is related to the set of algorithms one is choosing among using (anti-)cross validation, on the other. In addition, they establish strong caveats concerning the significance of the many results in the literature that establish the strength of a particular algorithm without assuming a particular distribution. They also motivate a “dictionary” between supervised learning and improving blackbox optimization, which allows one to “translate” techniques from supervised learning into the domain of blackbox optimization, thereby strengthening blackbox optimization algorithms. In addition to these topics, I also briefly discuss their implications for philosophy of science.
David H. Wolpert
Metadaten
Titel
Black Box Optimization, Machine Learning, and No-Free Lunch Theorems
herausgegeben von
Dr. Panos M. Pardalos
Varvara Rasskazova
Michael N. Vrahatis
Copyright-Jahr
2021
Electronic ISBN
978-3-030-66515-9
Print ISBN
978-3-030-66514-2
DOI
https://doi.org/10.1007/978-3-030-66515-9