Unbiased Black-Box Complexities of Jump Functions

Area of Science:

• Computer Science
• Artificial Intelligence
• Optimization

Background:

• Black-box optimization problems often feature fitness plateaus, which can significantly hinder algorithm performance.
• Understanding the complexity of these problems is crucial for developing efficient optimization strategies.

Purpose of the Study:

• To analyze the unbiased black-box complexities of jump functions with varying fitness plateau sizes.
• To investigate the existence and efficiency of optimization algorithms for challenging jump functions.

Main Methods:

• Analysis of unbiased black-box complexities for jump functions.
• Development of new analytical tools, including parent selection based on empirical expected offspring fitness.
• Evaluation of algorithms on jump functions with small, medium, and large fitness plateaus.

Main Results:

• Unbiased black-box complexities for jump functions with a (1/2 - ε) jump size are comparable to the OneMax function for arities 3 and higher.
• Polynomial time mutation-based algorithms are shown to exist even for the extreme jump function.
• The presence of large fitness plateaus does not necessarily preclude efficient optimization.

Conclusions:

• Efficient unbiased black-box optimization is achievable for a wider range of jump functions than previously thought.
• New analytical techniques provide deeper insights into the complexities of black-box optimization.
• The findings challenge the notion that large fitness plateaus inherently lead to intractable optimization problems.