Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)
Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)
复制标题
DOI：
10.1162/106365603321828970
复制
发表时间：
2003-03-01
影响因子：
6.8
通讯作者：
Koumoutsakos, P
中科院分区：
文献类型：
--
作者：
Hansen, N;Muller, SD;Koumoutsakos, P
提出了一种基于协方差矩阵自适应去随机化进化策略（CMA-ES）的进化优化策略。这种新方法的目的是减少收敛到最优所需的代数。减少代数，即，如果需要大的群体大小，则算法的时间复杂度是重要的：（1）减少噪声的影响;（2）改进全局搜索特性;以及（3）在（高度）并行机器上实现算法。我们的方法导致在一个高度并行的算法，规模有利的大量处理器。这是通过有效地结合来自大群体的可用信息来实现的，从而显着减少了适应协方差矩阵所需的代数。CMA-ES的原始版本被设计为在小群体中可靠地适应协方差矩阵，但它不能有效地利用大群体。我们的修改规模的效率，人口规模高达10 n，其中n是问题的尺寸。该方法已被应用于大量的测试问题，表明在许多情况下，CMA-ES可以提前从二次到线性的时间复杂度。
This paper presents a novel evolutionary optimization strategy based on the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). This new approach is intended to reduce the number of generations required for convergence to the optimum. Reducing the number of generations, i.e., the time complexity of the algorithm, is important if a large population size is desired: (1) to reduce the effect of noise; (2) to improve global search properties; and (3) to implement the algorithm on (highly) parallel machines. Our method results in a highly parallel algorithm which scales favorably with large numbers of processors. This is accomplished by efficiently incorporating the available information from a large population, thus significantly reducing the number of generations needed to adapt the covariance matrix. The original version of the CMA-ES was designed to reliably adapt the covariance matrix in small populations but it cannot exploit large populations efficiently. Our modifications scale up the efficiency to population sizes of up to 10n, where n is the problem dimension. This method has been applied to a large number of test problems, demonstrating that in many cases the CMA-ES can be advanced from quadratic to linear time complexity.