The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms

Area of Science:

• Computer Science
• Artificial Intelligence
• Optimization

Background:

• The runtime of evolutionary algorithms (EAs) is influenced by fitness landscape characteristics, but the precise relationship remains unclear.
• Prior work classified pseudo-Boolean problems based on local optima sparsity and fitness valley density, but this classification was incomplete.

Purpose of the Study:

• To generalize previous work and establish a complete hierarchy for classifying all pseudo-Boolean functions based on fitness landscape structure.
• To analyze the impact of this new hierarchy on the runtime of EAs and understand problem complexity.

Main Methods:

• Developed a generalized hierarchy, denoted Slo[Formula: see text], for all pseudo-Boolean functions.
• Analyzed the consistency of the hierarchy with existing EA runtime results.
• Investigated the effect of random perturbations on function classification.

Main Results:

• The proposed hierarchy (Slo[Formula: see text]) is consistent with known EA runtime behaviors.
• Problem classes with high local optima sparsity and low fitness valley density exhibit exponential black-box complexity.
• Random perturbations can alter a function's classification, with some perturbed problems remaining efficiently optimizable.

Conclusions:

• The complete hierarchy provides a more comprehensive framework for understanding EA performance based on fitness landscapes.
• This framework helps identify computationally hard problems and predict EA efficiency.
• The study offers insights into how noise and perturbations affect optimization landscapes.