Decision support systems for the automatic selection of algorithms for continuous optimization problems

© 2013 Dr. Mario Andrés Muñoz AcostaIn many real world search and optimization problems, the objective is to minimize or maximize the output variable of a function by adjusting the values of the input variables. When both the input and output variables are real numbers, the problem is known as a continuous optimization problem. Such problems are ubiquitous in areas such as aerospace design, biotechnology, control systems, economics, signal processing and water management. Often, these problems exhibit one or more of the following properties: there may not be an explicit function to describe the problem; the first and second derivatives of the function are not available, useful or computable; or there is information that is not explicit in the problem description, such as randomness or uncertainty. Therefore, a solution can only be found by using numerical and iterative methods known as search algorithms. There are several search algorithms available in the literature. Each algorithm makes a set of assumptions about the relationship between input variables, and between the input and output variables. Empirical and theoretical work has established that unless these assumptions "match" the problem, the algorithm may not perform any better than a random search. Therefore, when solving a continuous optimization problem, an important step is to identify the search algorithm capable of identifying the best solution using the least number of function evaluations. In this thesis, we propose a decision support system for the automatic selection of search algorithms. The system uses machine learning models to identify the mapping between the set of problems and the set of algorithms. The inputs to the decision support system consist of exploratory landscape analysis measures, which are extracted by sampling the input variables of the function and calculating their response on the output variable. The output of the decision support system consists of an algorithm recommendation or algorithm selection. We have carried out a wide range of numerical experiments over well known benchmark functions to test the efficacy of the decision support system. First, we evaluated the accuracy of the exploratory landscape analysis measures in response to changes in the sample size, and to translational shifts and rotations of the function. Then, we proposed an improved exploratory landscape analysis method, by adapting a method used in discrete optimization problems to continuous problems. Next, we proposed, implemented and validated three alternative architectures for the decision support system, using three different machine learning models: regression, classification and preference learning. Finally, we evaluated the influence of the exploratory landscape analysis measures on the accuracy of the algorithm recommendation. The results over the benchmark functions show that the proposed system is robust under these experimental conditions. Accuracy values greater than 90% were achieved on instances of known problems, and greater than 60% were achieved on instances of unseen problems. The system always selects an algorithm that solves the problem. This corresponds to the best accuracy achieved for a decision support system for continuous optimization problems across a large set of validation data. Our approach has many advantages for complex problems, especially when the maximu