Analysis of convergence of an evolutionary algorithm with self-adaptation using a stochastic Lyapunov function

Area of Science:

• Computational intelligence
• Optimization algorithms
• Evolutionary computation

Background:

• Evolutionary algorithms (EAs) are powerful optimization tools.
• Understanding the convergence properties of EAs is crucial for their effective application.
• Self-adaptation mechanisms in EAs adjust parameters during the search process.

Purpose of the Study:

• To analyze the convergence of evolutionary algorithms with self-adaptation.
• To investigate the role of stochastic Lyapunov functions and martingale theory in EA convergence analysis.
• To compare the convergence velocity of self-adaptive EAs with optimal deterministic algorithms.

Main Methods:

• Application of a novel technique based on stochastic Lyapunov functions.
• Development of the analysis within the framework of martingale theory.
• Investigation of an evolutionary algorithm with two parameter types: fitness and control parameters.
• Numerical validation using Monte-Carlo simulations with 0.999 confidence.

Main Results:

• Demonstrated convergence of both fitness and control parameters to the optimum.
• Established that the convergence velocity is asymptotically exponential.
• Showed similarity in convergence velocity to optimal deterministic algorithms for unimodal functions.
• Numerically validated theoretical martingale inequalities.

Conclusions:

• The stochastic Lyapunov function and martingale theory provide a robust framework for analyzing EA convergence.
• Self-adaptive evolutionary algorithms exhibit efficient convergence properties.
• The findings offer theoretical insights into the behavior of self-adaptive EAs, particularly for unimodal optimization problems.