Quasi-bistability of walk-based landscape measures in stochastic fitness landscapes

Exploratory landscape analysis is a useful method for algorithm selection, parametrization and creating an understanding of how a heuristic optimization algorithm performs on a problem and why. A prominent family of fitness landscape analysis measures are based on random walks through the search space. However, most of these features were only introduced on deterministic fitness functions and it is unclear, under which conditions walk-based landscape features are applicable to noisy optimization problems. In this paper, we empirically analyze the effects of noise in the fitness function on these measures and identify two dominant regimes, where either the underlying problem or the noise are described. Additionally, we observe how step sizes and walk lengths of random walks influence this behavior.