Recent Advances in Meta-features for Automated Single-Objective Black-Box Optimization

Date: 11.09.2024, 15:30-17:00

Room: 26-25/105

Speakers

• Gjorgjina Cenikj
• Ana Nikolikj
• Tome Eftimov

Motivation

Algorithm selection aims to identify the best algorithm for a given problem instance, leveraging the strengths of different algorithms across various problems. However, selecting the optimal algorithm for an unseen instance is a complex challenge, attracting substantial research interest. This tutorial surveys key contributions to algorithm selection in single-objective continuous black-box optimization. It explores current efforts in using representation learning to derive meta-features for optimization problems, algorithms, and their interactions. Additionally, it examines the application of machine learning models for automated algorithm selection, configuration, and performance prediction. By analyzing these advancements, the tutorial highlights existing gaps in the field and proposes directions for enhancing meta-feature representations to improve algorithm selection efficacy.

The tutorial will provide an overview of the recent trends in learning techniques for meta-features that can describe problem characteristics, algorithm characteristics, and algorithm-problem interactions (i.e., trajectory-based features). All of them will be presented in the single-objective black-box optimization scenario with opportunities to be transferred to other learning tasks. The problem landscape features are independent of any specific algorithm’s behavior on a problem instance. Various methods have been developed to capture the characteristics of single-objective continuous optimization problems, categorized into high-level features, like those in Fitness Landscape Analysis (FLA), and low-level features, such as those in Exploratory Landscape Analysis (ELA), Topological Landscape Analysis (TLA), and deep learning-based approaches. High-level features are human-interpretable, while most low-level features are considered black-box features, which can enhance machine learning tasks. Algorithm features describe the characteristics of specific algorithm instances and can be derived from various sources, including source code, performance metrics, graph embeddings, and configuration settings. Additionally, trajectory-based features capture the interactions between the problem instance and the optimization algorithm by using samples generated during the algorithm’s execution, providing a dynamic representation of this relationship. Machine learning models trained on these features can address algorithm selection tasks through multi-class classification, multi-label classification, regression, or ranking approaches. We will also provide a comprehensive comparison of machine learning techniques for algorithm selection using those features in single-objective optimisation. 

The tutorial will follow our survey article on meta-features for automated algorithm selection for black-box single objective continuous optimisation ( https://arxiv.org/abs/2406.06629).

Outline

1. Introduction to an automated algorithm selection (AAS) pipeline
2. Calculating/Learning problem landscape features
3. Exploratory Landscape Analysis 
4. Topological Landscape Analysis 
5. Deep Learning-based features
6. Feature used by Convolution Neural Networks 
7. Features learned using a point cloud transformer 
8. DoE2Vec features learned by using a variation autoencoder 
9. TransOpt features learned by using a transformer 
10. Deep-ELA features 
11. Calculating/Learning algorithm features
12. Algorithm Features Based on Source Code 
13. Algorithm Features Based on Performance 
14. Algorithm Features Based on Problem Landscape Features used by Performance Prediction Models 
15. Algorithm Features Using Graph Embeddings 
16. Learning trajectory-based features
17. Trajectory-based features Based on Internal Algorithm Parameters 
18. Trajectory-based ELA features 
19. DynamoRep features 
20. Opt2Vec features
21. Iterative-based ELA features
22. Local Optima Networks 
23. Search Trajectory Networks 
24. Probing trajectories 
25. Machine Learning techniques for AAS 

Speakers