Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)

Area of Science:

• Computational Intelligence
• Optimization Algorithms
• Machine Learning

Background:

• The standard Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is effective for small populations but inefficient with large ones.
• Large populations are crucial for noise reduction, improved global search, and parallel computation in optimization.
• Existing CMA-ES versions struggle to efficiently leverage information from large populations, limiting scalability.

Purpose of the Study:

• To develop a novel evolutionary optimization strategy that reduces the number of generations for convergence.
• To enhance the efficiency of CMA-ES for large population sizes, enabling better utilization of parallel computing resources.
• To improve the time complexity of the CMA-ES algorithm, particularly for high-dimensional problems.

Main Methods:

• A novel evolutionary optimization strategy is proposed, building upon the derandomized evolution strategy with covariance matrix adaptation (CMA-ES).
• The method efficiently incorporates information from large populations to accelerate covariance matrix adaptation.
• Modifications allow the strategy to scale effectively to population sizes up to 10n, where n is the problem dimension.

Main Results:

• The proposed method significantly reduces the number of generations required for convergence compared to the original CMA-ES.
• The algorithm demonstrates favorable scaling with a large number of processors, resulting in a highly parallel implementation.
• Applied to numerous test problems, the strategy often advances CMA-ES from quadratic to linear time complexity.

Conclusions:

• The novel CMA-ES strategy offers substantial improvements in convergence speed and parallel scalability.
• This approach effectively utilizes large populations, overcoming limitations of previous CMA-ES versions.
• The method provides a significant advancement for complex, large-scale optimization tasks, particularly in parallel computing environments.