The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary Algorithms
Duc-Cuong Dang, Per Kristian Lehre · Proceedings of the Genetic and Evolutionary Computation Conference · 2024
While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy.