Related Experiment Videos
Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)
Nikolaus Hansen1, Sibylle D Müller, Petros Koumoutsakos
1Fachgebiet für Bionik, Technische Universität Berlin, Ackerstr. 71-76, 13355 Berlin, Germany. hansen@bionik.tu-berlin.de
Evolutionary Computation
|June 14, 2003
Summary
This study introduces an enhanced evolutionary optimization strategy, improving the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). The novel approach significantly reduces convergence time and enhances parallel processing capabilities for complex optimization problems.
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.