Introducing Elitist Black-Box Models: When Does Elitist Behavior Weaken the Performance of Evolutionary Algorithms?

Area of Science:

• Theoretical Computer Science
• Artificial Intelligence
• Optimization Algorithms

Background:

• Black-box complexity theory bounds the performance of optimization algorithms.
• Existing models capture different aspects but may not fully represent real-world algorithms like evolutionary algorithms.
• Inspiration for new genetic algorithms and search heuristics is drawn from these theoretical bounds.

Purpose of the Study:

• Introduce a novel elitist black-box model for optimization.
• Analyze the computational complexity of this new model.
• Propose the p-Monte Carlo black-box complexity to account for probabilistic performance.

Main Methods:

• Developed a new elitist black-box model incorporating truncation selection.
• Defined and analyzed the elitist black-box complexity for various problem classes.
• Introduced and defined p-Monte Carlo black-box complexity.

Main Results:

• The elitist black-box complexity is shown to be exponentially larger than previous models for certain problems.
• This new model's complexity more closely aligns with the runtime of typical evolutionary algorithms.
• p-Monte Carlo black-box complexity can be exponentially smaller than Las Vegas complexity for certain function classes.

Conclusions:

• The proposed elitist black-box model offers a more realistic theoretical framework for evolutionary computation.
• The p-Monte Carlo complexity provides a valuable alternative measure for probabilistic optimization scenarios.
• These theoretical advancements can guide the design of more efficient search algorithms.