PS-AAS: Portfolio Selection for Automated Algorithm Selection in Black-Box Optimization - Reproducibility Repository

Zenodo (CERN European Organization for Nuclear Research)

Abstract

This repository contains the code and data for the paper "PS-AAS: Portfolio Selection for Automated Algorithm Selection in Black-Box Optimization" To ease reproducibility, the repository has been separated into multiple folders, each containing the materials needed for a subset of the work. This readme serves to connect these folders, following the ordering as seen in the paper. Part 1: Performance data collection (Performance_Data and Data_Collection folders) For the raw data, please see the Performance_Data folder. The files for collecting this data are in the Data_Collection folder. The data for this paper is based on a set of 324 configurations of the Modular CMA-ES, run on the BBOB test suite. The specific configurations are listed in the 'dt_grid' csv. Note that this data and code is reused with permission from the paper "The Importance of Landscape Features for Performance Prediction of Modular CMA-ES Variants" by A. Kostovska et al. (CC 4.0 licence, https://doi.org/10.5281/zenodo.5947075) The code used to generate the performance data relies on the 'ioh' package for accessing the problems and logging performance and uses the 'modcma' package for the CMA-ES. The script 'data_collection' can be run to collect the required performance data (this will create ~8 GB of data, which is added as 'zips' in the folder). It should be noted that this script does not properly handle seeds, and thus re-running can lead to slight differences in the resulting data. The data can then be processed using the R-script 'Data_processing', which uses IOHanalyzer (version 0.1.7+, installed from https://github.com/IOHprofiler/IOHanalyzer) to extract the required AUC and function values, based on the extracted version of the data from the 'zips' folder (please extract this folder and name it 'Data' for this script to work). This processing will create the data in the remaining sub-folders. Note that the working directory of this script should be set to the directory which contains 'Data' as its subfolder. As a final note, the human-selected (greedy-auc) portfolios are created in this 'Data_processing' file as well. # Part 2: Algorithm performance prediction (Algorithm performance prediction folder) We next merge the problem landscape (Taken from Q. Renau et al. Exploratory Landscape Analysis is Strongly Sensitive to the Sampling Strategy, CC4.0 licence) and algorithm performance data (from previous step) to create the ML-ready data for training the performance prediction regression models. The code for this part is available in the 1-data_preprocess.ipynb Jupiter notebook. The 2-train_predict_shapley_RForest.py code trains the regression models, stores predictions on the test folds and stores the shapley values for both the train and test fold. The results of executing this code are available in the ./results/results_modCMA/RForest_no_rescale ./results/results_modCMA/performance_tables folders. The 3-process_shapley.ipynb notebook merges the shapley files from the previous step and aggregates them accross the different problem instances. The results of executing this notebook are available in the ./results/results_modCMA/shapley_merged folder The requirements.txt file contains the python dependencies required to execute the code. # Part 3: SELECTOR The SELECTOR methodology takes as input meta-representations of the 324 CMA-ES configurations, and produces subsets of configurations which are representative and non-redundant. These meta-representations can be Shapley representations aggregated across all problems, Shapley representations for individual problems, or performance2vec representations. The scripts dom_mis_run_shap.py, dom_mis_run_per_problem.py and dom_mis_run_p2v.py handle these representations, respectively. What they do is they read in the meta-representations, construct graphs based on several similarity thresholds, and run the Maximal Independent Set(MIS) and Dominating Set(DS) algorithms. The algorithms are run for each combination of meta-representation, budget and dimensions separately. Since the algorithms are stohastic in nature, they can be run several times and produce different subsets of nodes. The subset of nodes in the graph selected by each of the algorithms for each scenario is saved in a seperate file of the form "results_{meta_representation_name}/{algorithm}/budget_{budget}_dim_{dimension}_sim_{similarity}_run_{run}". The notebook graph_visualizations_for_paper.ipynb can be used to recreate the figures demonstrating the sensitivity analysis with regard to the similarity thresholds presented in the manuscript. The requirements.txt file contains the python dependencies required to execute the code. Python 3.7 or 3.8 is recommended to be used. The experiments were run on Ubuntu 21.10 OS. The notebook has been refactored to remove the analysis not reported in the paper. The dom_mis_run_5_times.sh file enables running the experiments in a centralized manner. It calls the python scripts which run the SELECTOR methodology with the SHAP, Performance2Vec and the personalized meta-representations. # Part 4: Selecting data-driven porfolios (PORTFOLIOS folder) This part parse the output from the SELECTOR and makes one dataset with the following columns: budget, dim, sim, run, and portfolio. Each row represent a seelcted portfolio for a fixed budget, dim, and sim. Run corresponds to different seeds.These are the portfolios to be evaualted. The R script generated_portfoliios.R is performing this using the input data that is the outcome from SELECTOR. The personalized portfolios can be generated using the per problem results retun by SELECTOR. They can be parse using the generate_personalzied_portfolio.R script. Both scripts should be run from the ../PORTFOLIOS directory to reporduce the results. The files: p2v_dominant_portfolio.txt, p2v_mis_portfolio.txt, shapley_dominant_portfolio.txt, shapley_mis_portfolio, and shapley_mis_personalzied.txt contain the selected potrfolios. The scripts were originally run with "R version 4.0.2 (2020-06-22)". Other R versions should also work. # Part 5: Algorithm selector (Algorithm selector folder) After selecting the algorithm portfolios for evaluation, we build the algorithm selector and calculate the loss for each of them. The algorithm portfolios from the previous step are available in the ./algo_portfolios folder. The build_algorithm_selector.ipunb Jupiter notebook builds the algorithm selector and calculates the loss (data is stored in the ../AS_table folder) and produces boxplots with AS loss for each of the evaluated scenarios (boxplots available in the ./AS_loss_boxplots folder). The requirements.txt file contains the python dependencies required to execute the code. # Part 6: Error decomposition The requirements.txt file contains the python dependencies required to execute the code. The error decomposition (and the creation of the greedy per-function portfolio) are located in the 'Error_decomposition_incl_figure' notebook, which contains comments detailing the process. This notebook makes use of the data from the algorithm selectors ('AS_table' folder), as well as the created portfolios ('Portfolio' folder). This notebook also contains the code to generate figures 2 and 3 from the paper. # Remainder Some additional figures created by the various scripts have been added in the Figures folder for more convenient access.

Authors 9

1. Ana Kostovska

   Jožef Stefan Institute · Jožef Stefan International Postgraduate School

   Affiliation as printed

   Jožef Stefan Institute

2. Gjorgjina Cenikj

   Jožef Stefan Institute · Jožef Stefan International Postgraduate School

   Affiliation as printed

   Jožef Stefan Institute

3. Diederick Vermetten Aachen

   Leiden University

   Affiliation as printed

   Leiden University

4. Anja Jankovič

   Sorbonne Université

   Affiliation as printed

   Sorbonne Université

5. Ana Nikolikj

   Jožef Stefan Institute · Jožef Stefan International Postgraduate School

   Affiliation as printed

   Jožef Stefan Institute

6. Urban Škvorc

   Jožef Stefan Institute · Jožef Stefan International Postgraduate School

   Affiliation as printed

   Jožef Stefan Institute

7. Peter Korošec

   Jožef Stefan Institute · Jožef Stefan International Postgraduate School

   Affiliation as printed

   Jožef Stefan Institute

8. Carola Doerr

   Sorbonne Université

   Affiliation as printed

   Sorbonne Université

9. Tome Eftimov

   Jožef Stefan Institute · Jožef Stefan International Postgraduate School

   Affiliation as printed

   Jožef Stefan Institute