Mutation rate matters even when optimizing monotonic functions.

Area of Science:

• Computer Science
• Artificial Intelligence
• Optimization Algorithms

Background:

• Evolutionary algorithms (EAs) are stochastic search algorithms inspired by biological evolution.
• Pseudo-Boolean functions are commonly used benchmarks for analyzing EA performance.
• Strictly monotonic functions represent a class where increasing input values strictly increases the output.

Purpose of the Study:

• To analyze the optimization performance of the (1+1) evolutionary algorithm on strictly monotonic pseudo-Boolean functions.
• To investigate the impact of the mutation rate parameter on optimization time.
• To identify conditions under which these functions are difficult to optimize.

Main Methods:

• Theoretical analysis of the (1+1) evolutionary algorithm's runtime.
• Mathematical proofs for different ranges of the mutation rate constant 'c'.
• Construction of specific strictly monotonic functions to demonstrate worst-case scenarios.

Main Results:

• For c < 1, the (1+1) EA optimizes strictly monotonic functions in Θ(n log n) iterations.
• For c = 1, an upper bound of O(n^(3/2)) iterations is established.
• For c ≥ 16, a function exists requiring 2^(Ω(n)) iterations, demonstrating a significant runtime increase.

Conclusions:

• The choice of the mutation rate constant 'c' critically affects the (1+1) EA's efficiency on strictly monotonic functions.
• A small change in 'c' can lead to a super-polynomial increase in optimization time.
• This highlights the sensitivity of EA performance to parameter tuning.