A new method for modeling the behavior of finite population evolutionary algorithms

Area of Science:

• Computational Intelligence
• Evolutionary Computation
• Algorithm Analysis

Background:

• Traditional Markov chain analysis for evolutionary algorithms (EAs) is computationally infeasible for large problems.
• Existing dynamic systems approaches do not quantify the likelihood of finding the optimal solution.

Purpose of the Study:

• To develop a more memory-efficient method for modeling finite population evolutionary algorithms.
• To provide a computationally tractable alternative to Markov chain analysis for EAs.
• To analyze selection pressure in fitness-proportionate selection within these models.

Main Methods:

• Developed an exact model for finite population EAs that requires less memory than Nix and Vose-style Markov chain models.
• Introduced approximate models that further reduce memory requirements.
• Examined selection pressure using fitness-proportionate selection based on the developed models.

Main Results:

• The proposed exact model is significantly more memory-efficient than traditional Markov chain models for EAs with population sizes much smaller than the search space.
• Approximate models offer further memory savings.
• Analysis of selection pressure indicates no strong bias towards higher fitness individuals on average, contrary to landscape expectations.

Conclusions:

• The presented modeling approach offers a computationally feasible method for analyzing the behavior of finite population evolutionary algorithms.
• The findings challenge the assumption of strong selection bias in fitness-proportionate selection under certain conditions.
• This work provides a practical tool for understanding and optimizing evolutionary algorithms.