Fitness Landscape Analysis Metrics based on Sobol Indices and Fitness- And State-Distributions

Abstract

This paper proposes new Fitness Landscape Analysis (FLA) metrics as measures for problem difficulty in heuristic search. The sensitivity and variable interaction metrics are based on Sobol indices, a common technique in sensitivity analysis. The fitness- and state-variance and the fitness- and state-skewness metrics are based on the second and third central statistical moments. We compute metric values for around 550 continuous test functions in 2, 5 and 10 dimensions and compare it to well-established metrics (Fitness Distance Correlation, Autocorrelation, Information Content, Density-Basin Information and Partial Information Content). By conducting two-sample statistical tests (T-Test, F-Test, Kolmogorov-Smirnov Test, and Rank-Sum Test) for all combinations of FLA metrics, we demonstrate that our proposed metrics result in significantly different distributions. Thus, we can conclude that they reveal fitness landscape characteristics not captured by the existing metrics that were considered.