Techniques for Improving Black Box Algorithm Selection Approaches

黑盒算法選擇的改進技術

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date9 Jun 2020

Abstract

The doctoral thesis presents three approaches for the black box algorithm selection problem. The approaches are: 1) sequential algorithm portfolio (SAP); 2) Bayesian sequential learnable evolutionary algorithm (BSLEA); and 3) convolutional neural network (CNN) based approach. The first two approaches adopt conventional machine learning models to suggest optimization algorithms and the CNN based approach adopts the deep learning technique.

To depict the characteristics of optimization problems, researchers use exploratory landscape analysis (ELA) techniques to extract different landscape features. However, sampling strategies can significantly affect the properties of ELA features. To obtain high quality ELA features, we propose a new methodology of constructing algorithm based ELA features. This type of features is used in our SAP.

SAP belongs to the inter-disciplinary fields of algorithm portfolio and algorithm selection. It uses a set of pre-trained predictors to predict the most suitable algorithm and a termination algorithm to automatically stop the optimization algorithms. SAP tries to answer two questions: 1) when to stop an optimization algorithm; and 2) which algorithm is the most suitable one. It is easy to implement and can incorporate any optimization algorithm. We experimentally compare SAP with two state-of-the-art algorithm portfolio approaches and single optimization algorithms. The result shows that SAP is a well-performing algorithm portfolio approach.

BSLEA adopts a Bayesian approach to suggest optimization algorithms. The framework of BSLEA can be described as follows: In the beginning, a default algorithm is selected to run on the given unknown problem. A Bayesian approach is used to measure the similarity between problems. The most similar problem to the given problem is selected. Then the best algorithm for solving it is suggested for the second run. To decide the best algorithm in the ith run, a Bayesian formulation is used to integrate the knowledge gained in the previous i-1 runs. The process repeats until n algorithms have been run. The best solution out of n runs is recorded. We conduct several experiments to evaluate the new approach. It is compared with several single optimization algorithms with and without restarts and two portfolio approaches using random selection. The results indicate that our new approach is better than these approaches.

Deep learning, which has been shown to perform well on various classification and regression tasks, is adopted in our CNN based approach. This approach is very different from existing algorithm selection approaches. It does not use any existing human-defined ELA features. Our deep learning architecture is based on convolutional neural network and follows the main architecture of visual geometry group. This architecture has previously been applied to many different types of 2-D data. Moreover, we also propose a novel method to extract landscape information from the optimization problems and save the information as 2-D images. In the experimental section, we conduct three experiments to investigate the classification and optimization capability of our approach on the black box optimization benchmarking (BBOB) functions. The results indicate that our new approach can effectively solve the algorithm selection problem.