Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms.

Area of Science:

• Computer Science
• Artificial Intelligence
• Optimization

Background:

• The fitness level method analyzes evolutionary algorithms by dividing search spaces into fitness levels.
• Estimating hitting times using transition probabilities is common, but lower bounds are often imprecise.
• An open question is how to derive the tightest possible time bounds using fitness levels.

Purpose of the Study:

• To determine the tightest lower and upper time bounds achievable with the fitness level method.
• To establish a general framework for developing improved fitness level methods.

Main Methods:

• Combining drift analysis with the fitness level method.
• Formulating the tightest bound problem as a constrained multiobjective optimization problem.
• Deriving linear bounds from newly constructed metric bounds.

Main Results:

• The tightest metric bounds by fitness levels are constructed and proven for the first time.
• A framework for developing various linear bound methods is established.
• The framework is demonstrated to be effective for fitness landscapes with and without shortcuts.

Conclusions:

• The new approach provides tighter time bounds for elitist evolutionary algorithms.
• The established framework is versatile and applicable to different types of linear bounds and fitness landscapes.
• This research advances the analysis of evolutionary computation performance.