Direct Feature Evaluation in Black-Box Optimization Using Problem Transformations

Exploratory Landscape Analysis provides sample-based methods to calculate features of black-box optimization problems in a quantitative and measurable way. Many problem features have been proposed in the literature in an attempt to provide insights into the structure of problem landscapes and to use in selecting an effective algorithm for a given optimization problem. While there has been some success, evaluating the utility of problem features in practice presents some significant challenges. Machine learning models have been employed as part of the evaluation process, but they may require additional information about the problems as well as having their own hyper-parameters, biases and experimental variability. As a result, extra layers of uncertainty and complexity are added into the experimental evaluation process, making it difficult to clearly assess the effect of the problem features. In this article, we propose a novel method for the evaluation of problem features which can be applied directly to individual or groups of features and does not require additional machine learning techniques or confounding experimental factors. The method is based on the feature's ability to detect a prior ranking of similarity in a set of problems. Analysis of Variance (ANOVA) significance tests are used to determine if the feature has successfully distinguished the successive problems in the set. Based on ANOVA test results, a percentage score is assigned to each feature for different landscape characteristics. Experimental results for twelve different features on four problem transformations demonstrate the method and provide quantitative evidence about the ability of different problem features to detect specific properties of problem landscapes.