How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism

Area of Science:

• Computational intelligence
• Optimization algorithms
• Population genetics

Background:

• Escaping local optima is a key challenge in function optimization.
• Fitness landscapes use hills and valleys to represent optimization problems.
• Valley difficulty is defined by length (Hamming distance) and depth (fitness drop).

Purpose of the Study:

• Compare runtimes of different stochastic search algorithms on tunable fitness valleys.
• Analyze how valley characteristics affect algorithm performance.
• Evaluate algorithm efficiency on rugged functions with consecutive valleys.

Main Methods:

• Define a class of fitness valleys with tunable length and depth.
• Compare runtime performance of (λ) Evolutionary Algorithm (EA), Metropolis algorithm, and Strong Selection Weak Mutation (SSWM) algorithm.
• Test algorithms on a rugged function composed of sequential valleys.

Main Results:

• The (λ) EA's runtime is critically dependent on valley length.
• Non-elitist algorithms (Metropolis, SSWM) show runtime dependence on valley depth.
• Both SSWM and Metropolis algorithms efficiently optimize rugged functions with consecutive valleys.

Conclusions:

• Valley length is a critical factor for elitist algorithms like (λ) EA.
• Valley depth is crucial for non-elitist algorithms, enabling efficient optimization.
• Metropolis and SSWM algorithms demonstrate robustness in optimizing complex, rugged landscapes.