自适应协方差矩阵进化策略算法

程沙沙

[摘 要] 自适应协方差矩阵进化策略（CMA-ES）算法是Nikolaus Hansen等人提出的一种新的进化算法，通过模拟自然界生物进化过程，达到寻优目的。多个测试函数结果表明，该算法具有全局性能好、寻优效率高的特点，为解决高计算代价复杂工程优化问题的求解提供了新的途径。

[关键词] 优化算法；自适应协方差矩阵进化策略算法；测试函数

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2014 . 12. 057

[中图分类号] TP301.6 [文献标识码] A [文章编号] 1673 - 0194（2014）12- 0091- 03

本文拟通过测试基准函数来研究CMA-ES算法的全局性和高效性。

1 CMA-ES算法基本原理

CMA-ES算法通过动态的步长参数σ和动态的正定协方差矩阵C来引导种群的突变进化方向，其基本方程如下：

xk（g+1）=m（g）+σ（g）N（0，C（g））（1）

式中，xk（g+1）∈Rn是g+1代中的第k个个体；m（g）是g代种群适应度的平均值；σ（g）是g代种群进化的步长；C（g）是第g代种群进化的协方差矩阵。

具体实施步骤如下：

步骤1 启动Matlab环境下的优化程序，设置CMA-ES算法相关参数。

步骤2 从给定的或者随机产生的一个初始搜索点出发，以该初始点为搜索中心，按照一定的概率密度随机生成第一代种群（λ个），并评价该种群中所有个体的适应度。

步骤3 根据适应度大小选择适应度较好的μ个个体组成新的种群来更新进化策略参数σ和C。利用进化策略参数调整下一代种群的进化方向，从而进行突变生成下一代种群。

步骤4 对当前种群所有个体进行适应度评价，根据适应度大小选出最优解，对当前最优解进行收敛条件判断。如满足收敛条件则退出计算，当前最优解即为全局最优解；否则，返回步骤3。

受篇幅限制，CMA-ES算法基本原理详见文献。

2 算法测试

评定算法的优劣需要从算法的全局搜索能力和搜索效率两个方面进行研究。传统的优化算法寻优效率高，但是与初始点的选择很有关系，如果选择不当，很有可能找不到最优解或陷入局部最优。现代仿生类的优化算法全局性能好，能找到全局最优解，但是寻优过程中需要大量的函数评价次数。

国内外常采用的一些典型的测试基准函数来判断算法的优劣。本文中采用的函数及其表达式见表1。表1中的函数特征：U表示Unimodal，M表示Multimodal；S表示Separable，N表示Non-Separable。

在测试环境中，计算机配置为intel 2.40GHz处理器和2G内存，操作系统为Windows XP，计算软件采用了Matlab 2008。

2.1 全局搜索能力测试

全局搜索能力是指函数能够找到较高精度的最优解的能力。随着维数的增加，函数越不容易搜索到全局最优解。因此从不同维数测试函数的全局搜索能力是很有必要的。

CMA-ES算法的参数设置如下：种群数λ=4+[3ln n]；搜索空间的下限为lb=[-4，4，…，-4]，搜索空间的上限为ub=[4，4，…，4]；函数Sphere、Schwefel、Cigar、Tablet、Elli的初始步长设定为1，函数Rosen的初始步长设定为0.1；维数分别取2、5、10、20、30；收敛条件设定函数精度为10-10。每种函数在每种维数下分别测试10次，取最好的结果，见表2。

从表2可知，CMA-ES算法具有很好的搜索性能，能够达到比较高的精度。对不同复杂的函数，CMA-ES算法都能找到最优解，证明了CMA-ES算法的全局性能好。

2.2 寻优效率测试

函数的寻优效率是指函数寻找到全局最优解所需要的函数评价次数，提高寻优效率也就是要降低函数评价次数。维数的不同也会对函数的寻优效率有影响。本文以简单的球形函数Sphere为例，对比遗传算法（简称GA）和粒子群算法（简称PSO），来研究CMA-ES算法的寻优效率。

CMA-ES算法的参数设置如下：种群数λ=4+[3ln n]，初始步长为0.5（ub-lb），初始搜索点为X=lb+0.3（ub-lb）；

GA算法的参数设置为：变异概率Pm=0.2，交叉概率Pc=0.8，初始搜索点与CMA-ES算法相同；

PSO算法参数设置：学习因子C1=C2=2.0，种群数分别取10、20、30。

3种算法取相同的搜索空间：下限为lb=[-4，-4，…，-4]，上限为ub=[4，4，…，4]；维数分别取2、4、6、8、10；收敛条件设定函数精度为10-3。每种函数在不同参数和维数下分别测试10次，取最好的结果，如图1。

从图1可知，随着维数的增加，函数评价次数也相应增加。同时，CMA-ES算法在各个维数上的函数评价次数明显小于PSO算法和GA算法，在高维数上表现更为明显。由此说明CMA-ES算法的寻优效率高。

3 结 语

本文通过采用典型测试基准函数对CMA-ES算法在全局搜索能力和寻优效率两个方面性能进行研究。算例结果表明，CMA-ES算法具有全局性能好，寻优效率高的特点。本文方法对于高维度复杂的工程优化问题的适应性问题需进一步研究。

主要参考文献

[1]杨维，李岐强. 粒子群优化算法综述[J].中国工程科学，2004，6（5）： 87-94.

[2]武振兴.桁架结构优化的进化策略与高斯过程方法[D]. 南宁：广西大学，2011.