OneMax Is Not the Easiest Function for Fitness Improvements

Area of Science:

• Computer Science
• Artificial Intelligence
• Evolutionary Computation

Background:

• The (1,λ)-EA is a population-based metaheuristic. The (1:s+1) success rule is a parameter control mechanism for managing its population size.
• Previous research indicated that the (1:s+1) rule can fail for large 's' on simple fitness landscapes, with OneMax conjectured as the most susceptible.

Purpose of the Study:

• To investigate the performance of the self-adjusting (1,λ)-EA with the (1:s+1) success rule on different fitness landscapes.
• To disprove the conjecture that the OneMax benchmark is the most challenging landscape for this parameter control mechanism.

Main Methods:

• Theoretical analysis of the (1:s+1) success rule's performance on the OneMax and Dynamic BinVal benchmark functions.
• Demonstration of specific parameter settings (s and ɛ) and initial conditions (ɛn zero-bits) to highlight performance differences.

Main Results:

• The conjecture that OneMax is the hardest landscape for the (1:s+1) rule is disproven.
• The self-adjusting (1,λ)-EA with the (1:s+1) rule can efficiently optimize OneMax from a near-optimal starting point.
• However, the same setup fails to find the optimum in polynomial time on the Dynamic BinVal benchmark, indicating a more severe problem.

Conclusions:

• OneMax is not the most difficult fitness landscape for the (1:s+1) success rule, contrary to prior conjecture.
• The effectiveness of the (1:s+1) rule depends not only on the landscape's ease of reducing distance to the optimum but also on the availability of fitness-improving steps.