分布模型和关联模型的自适应差分进化算法

周美玲，张胜敏，李 征

（1.开封大学 软件学院，河南 开封475000；2.河南大学 计算机与信息工程学院，河南 开封475001）

0 引 言

差分进化算法的性能主要由缩放因子和交叉率两个控制参数决定［1－4］。其中缩放因子用于调整搜索步长，交叉率则控制新个体相较于父代个体变化的强度［5，6］。传统的差分进化算法依据问题本身的特性和调试经验来取值，但这种方法的效果有限，不适于复杂优化问题［7－10］。为了使得参数取值更好适应算法的性能，一些学者提出了各自的参数自适应差分进化算法，其中最具代表性的算法有Brest等［11］设计的动态调整参数的jDE算法，以及Qin等［12］提出的自适应调整参数和变异算子的SaDE 算法。虽然这些参数自适应差分进化算法的种群中每一个新个体使用的缩放因子是动态变化的，但对于个体中的每一维则是不变的，由于各维变量的寻优程度以及它们之间的关联性往往不同，赋予其同等的搜索尺度显然是不合适的；且已有算法中缩放因子和交叉率的变化总是独立进行的，而差分进化的公式表明交叉率决定着新个体的哪些维变量受缩放因子的影响，因此二者必然是非独立的。为此，提出了一种基于双模型的自适应差分进化算法 （double－model－based self－adaptive differential evolution，DMSaDE），分布模型是在自适应差分进化算法SaDE 的基础上，对每一维变量采用不同的缩放因子进行统计，对构成的缩放因子矩阵进行主成分分析，在主元空间下进行估计和采样；关联模型是将交叉率划分为不同的取值区间，不同的缩放因子向量对应于不同的交叉率区间，认为交叉率和缩放因子之间的关系是非线性的，并通过学习机制和核支持矢量机建立。

1 相关描述

自适应差分进化算法SaDE［12］对进化过程中参数取值和变异算子的选择均进行了自适应的调整。其相比于jDE算法［11］，所采用的参数取值规则对经验知识依赖更小，并且调整过程具有一定的学习能力。为此，采用和SaDE 算法类似的策略，在其基础上来应用所提出的两个模型。

对于一个最小化优化问题f（x），x＝ （x1，x2，…，xn），n为变量维数，x∈可行域S，SaDE 采用DE／rand／1、DE／rand－to－best／2、DE／rand／2 和DE／current－to－rand／1 这4种候选变异算子，它们具有不同的全局探索能力和局部搜索能力，SaDE在初始阶段赋予它们同等的选中概率用于某一新个体的生成，然后一定代数LP内不断的进行统计，例如当前为第t代，则统计t－1，t－2，…，t－LP代。统计内容为各个策略所生成新个体优于父代个体的数量以及差于父代个体的数量，再根据二者的比例调整各个变异算子的概率，如式 （1）所示

该算法假设合适的交叉率参数CR 和缩放因子F 取值均分别服从某一高斯分布模型，但二者模型的构建方法有所不同。SaDE在周期LP内采用与变异算子相同的标准处理交叉率参数CR，即对于每一个变异算子记录各自生成更优个体时的CR 取值。然后计算各自的CR 序列的中间值，以该中间值作为高斯分布模型的均值，再赋予设定的方差取值。而对于缩放因子F，SaDE则只建立了一个针对所有变异算子的高斯分布模型，并且均值和方差的取值均是依据经验设定的。在这两个高斯分布模型的基础上，每个个体所需的参数取值均通过模型采用来完成。

2 双模型自适应差分进化算法的设计

设计的差分进化算法DMSaDE 采用DE／rand／1、DE／rand－to－best／1、DE／best／1这3种变异算子，如式 （2）～式 （4）所示，以及二元交叉算子，如式 （5）所示

其中，xi为父代个体，xb为当前所得最优个体，xr1、xr2、xr3为互不相同且不同于xi和xb，从当前种群中随机选择的3个个体，j0为随机选中的一维变量，用以保证子代个体不同于父代个体。

2.1 缩放因子分布模型的设计

DMSaDE与SaDE相比，将缩放因子也纳入了自学习调整的范畴，并且针对不同变异算子建立了独立的基于分布模型的学习策略。缩放因子分布模型的具体操作步骤如下：

（1）初始状态下每一个体的每一维独立的在区间［0.1，0.95］内随机生成缩放因子，构成缩放因子向量，若生成的新个体优于父代个体则记录该向量。在LP代后第k个变异算子可以得到nk个缩放因子向量，i＝1，2，…，nk，用这些向量构成一个n×nk维的矩阵Mk；

（2）计算矩阵Mk每一行的均值，得到均值向量，然后按照式 （6）计算协方差矩阵Ck

（3）求取Ck的特征值以及特征向量，，…，，并使得特征值≥≥…≥，再按照贡献率大于85%的准则确定主元数量为p，即对应前p 个特征值；

（4）将矩阵Mk中各个缩放因子向量按照式 （7）投影到前p 个主元方向上，并据此计算所有向量在各个主元上的上边界和下边界

（5）按照式 （8）确定一个n维超立方体Hk，即为对进化起促进作用的缩放因子向量所在的分布空间，再按照式（9）计算原始向量与投影向量之间的残差Ek，该残差用于修正噪声环境下分布空间Hk的误差。此后每隔g 代，利用最近的LP 代结果构建矩阵Mk，并计算分布空间Hk和残差Ek

其中，α为上下界的修正因子，设置为0.05。

当变量维数n 过高时，若每一维均独立考虑则所得矩阵过于庞大而难以计算。故在每次计算时，将n 维变量随机的划分为等长度的c 类，每一类对应一个缩放因子元素，即得到c×nk维的矩阵Mk。这样Fk的第i 个元素 （i＝1，2，…，c）即用于第i类中所有维变量使用。基于上述分布模型，新个体所用缩放因子的产生方法为：设当前选中的是第k个变异算子，在分布空间Hk所限定范围内通过均匀随机采样得到向量Yk，再将残差Ek设定为零均值高斯分布的方差向量，即gauss（0，Ek），并用其产生误差ek，按照式 （10）即得到最终的缩放因子向量

其中，rj为0.1和0.95之间的一个随机数。

2.2 关联模型的设计

缩放因子通过影响搜索方向和搜索步长最终产生一个临时变异个体，但最终的子代个体则是利用交叉率控制变异个体的保留程度而获得的。可见子代个体的质量是在两方面参数的复杂作用下决定的，并且两参数之间存在着复杂的联系。关联性模型认为这一联系是非线性的，并采用核支持矢量机进行描述，更适于处理小样本问题，还能避免维数爆炸的问题［13］。此处采用的核函数为高斯核函数，如式 （11）所示

关联模型的具体操作步骤如下：

（1）与分布模型相同，在初始的LP代内，交叉率CR在 ［0，1）范围内随机取值，在关联模型建立起来后则以缩放因子向量为输入，用模型来预测交叉率，关联模型每隔g 代更新一次；

（2）记录子代个体优于父代个体时对应的缩放因子向量和交叉率，每个变异算子分开记录，这样LP代后得到缩放因子矩阵Mk和交叉率向量CRk；

（3）将交叉率的取值范围 ［0，1）划分为l个等长区间，再将不同区间的交叉率依次标记为1，2，…，l，由此向量CRk转换为标记向量Lk；

（5）在预测阶段，对于一个属于第k 个变异算子的缩放因子向量，依次用l个分类器进行分类，当在第m 个分类器上决策函数输出为1时，即判定交叉率取值属于第m个区间，在此区间内随机生成一个值作为预测所得的交叉率；

（6）预测中可能存在所有分类器结果显示输入向量不属于任何一类的情况，此时若某些区间尚无训练样本，则优先在这些区间随机生成CR，否则在 ［0，1）内随机生成。

2.3 算法流程描述

基于上述两模型的改进，DMSaDE 的算法的具体流程如下：

（1）在t＝0代，先将问题的解可行域归一化，然后随机生成种群A，其中每个个体的每一维在 ［0，1］之间随机生成，求取每个个体的目标函数值，并存储当前最优结果f（x＊）；

（2）当t＜LP 时，等概率选取变异算子，随机生成所需的缩放因子向量和交叉率；

（3）当t＝LP ＋i＊g 时，i＝0，1，2，…，采用SaDE算法中的策略更新变异算子的选择概率，用前述方法建立或更新分布模型和关联模型，并用所得分布空间Hk和残差Ek求取缩放因子向量，以及用核支持矢量机预测交叉率；

（4）当t＞LP且t≠LP＋i＊g 时，采用SaDE算法中的策略更新变异算子的选择概率，并用当前的分布模型和关联模型来生成差分进化所需的参数；

（5）在每一代中，根据当前获取的参数取值和变异算子生成新的个体，若新个体优于父代个体，则存储相应的参数取值，记录被使用的变异算子；

（6）将每代中新生成的个体集合记为B，混合集合A和B，将所有个体的目标函数值升序排列，选取前A 个个体组成下一代种群，用排序在第一个的个体更新当前最优结果f（x＊）；

（7）当最大函数调用次数时，则去执行步骤 （2）～步骤 （6），否者输出f（x＊）。

3 性能验证与分析

为了验证提出的算法性能，使用了2008 年CEC 大尺度全局优化问题竞赛［14］上采用的4 个函数Shifted Schwefel’s Problem 2.21、Shifted Rosenbrock’s Function、Shifted Rastrigin’s Function、Shifted Griewank’s Function，以及提出SaDE 算法的文献 ［12］所采用的Shifted Schwefel’s Problem 1.2with noise和Shifted noncontinuous Rastrigin’s function 共计6个标准目标函数 （对应标记Fun1～Fun6）进行测试，它们的变量维数均有两种情况，分别为30和100维。依据文献 ［14］中的标准，算法在每个目标函数上均独立运行25次，算法的停止条件为达到最大函数调用次数，30和100维的调用次数分别为1.5×105和5×105。DMSaDE 的相关参数设置为：种群A 为100，参数LP为50，代数间隔g 为20，变量维数划分数量c在30维时为30，100维时为25，交叉率的区间数目l为10，高斯核函数的方差σ为1。

3.1 算法对比测试

对所提算法DMSaDE 和SaDE 算法进行了对比测试，结果如表1和表2。其中SaDE 的相关参数按照文献 ［12］所述进行设置。为了更好的说明测试结果，统计了两项指标，分别为25次测试所得最优值的均值和t检验。其中t检验的结果为 “＋”表示DMSaDE 所得结果优于SaDE 的置信区间为95%，而 “－”则表示二者所得结果来至于同一个分布，在统计上无差异。

表1 DMSaDE和SaDE在30维时的测试结果

表2 DMSaDE和SaDE在100维时的测试结果

表中的结果可知，DMSaDE 在整体性能上优于SaDE，其在30维时有3 个目标函数所得最优值均值是显著小于SaDE的 （即t检验结果为 “＋”），而在100维时达到了5个。且在其余的目标函数上二者也是在统计上无差异的，处于同一优化水平，未出现SaDE 结果显著优于DMSaDE的情况，故提出的两个模型显著提高了原有SaDE 算法的性能。

3.2 算法自身分析

分布模型和关联模型是DMSaDE 的主要改进内容。在分布模型中，缩放因子向量是在主元空间下进行分布估计的，而变量维数也被划分为c类。在关联模型中，非线性映射采用了高斯核函数的支持矢量机，而交叉率输出也被划分为了l个区间。为分析模型中上述步骤对算法性能的影响，设计了一系列对比算法。对比算法Algorithm1将分布模型中的主元空间映射步骤取消，直接求取各维上缩放因子的均值和方差，再建立多维高斯分布模型。当变量为100 维时，DMSaDE 和Algorithm1 在函数Fun1、Fun2、Fun5上的测试结果见表3。

表3 主元空间映射对算法性能的影响

从表3可知，DMSaDE 的性能更佳，说明直接建立分布模型的Algorithm1受变量维之间耦合的影响，并不能有效揭示高质量缩放因子的分布情况。

对比算法Algorithm2和Algorithm3则分别采用多项式核的支持矢量机和线性支持矢量机来表述缩放因子与交叉率之间的关联性。同样对100维变量下的函数Fun1、Fun2和Fun5进行测试，结果见表4。

表4 支持矢量机对算法性能的影响

测试结果显示，采用核函数的支持矢量机的测试结果明显好于线性支持矢量机的测试结果，而高斯核的测试结果又略优于多项式核的结果，证实了缩放因子与交叉率之间的关系是非线性的。

对于两个划分类数c和区间数l，以100维的函数Fun3为测试对象，取类数c为2、5、10、20和50，取区间数l为2、5、10、15和20。类数c和区间数l 的盒图测试结果分别如图1和图2所示。

从图1可以看出，当类数c过小时，各维之间的缩放因子并未得到有效的区分，从而导致算法的性能较差；从图2中可知，对于区间数l，其取值过小时，交叉率近似于在整个范围内均匀随机选取，即不同缩放因子对应的交叉率取值是随机的，交叉率和缩放因子之间并未建立正真的联系；当l的取值过大时，区间被划分的过于细小，缩放因子所映射的类数过多，使得支持矢量机的准确性和泛化能力有所下降。

图1 类数c对算法性能影响的测试结果

图2 区间数l对算法性能影响的测试结果

4 结束语

设计的两个模型进一步提高自适应差分进化算法的性能。其中提出的缩放因子分布模型将各维的缩放因子取值独立考虑，反映了变量中各维之间的差异性；提出的交叉率关联模型相比于已有算法，不再独立的进行调整，而是建立了缩放因子向量与交叉率之间的非线性关系。6 组标准函数的测试结果表明了提出算法的改进是有效的，在多数函数上获得了更好的结果，而其余函数的测试结果也保持在了同等水平上；基于主成分分析技术的主元空间建模是分布模型的重要环节，而核函数下的支持矢量机能更好反映参数之间的复杂关系。

［1］Brest J，Boskovic B，Zumer V.An improved self－adaptive differential evolution algorithm in single objective constrained realparameter optimization ［C］／／IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2010：1－8.

［2］SHEN Jiajie，JIANG Hong，WANG Su.Improved binary differential evolution algorithm based on velocity probability and adaptive speed value ［J］.Computer Engineering and Design，2014，35 （4）：1395－1401 （in Chinese）. ［沈佳杰，江红，王肃.基于速度概率和自适应速度值的差分进化算法 ［J］.计算机工程与设计，2014，35 （4）：1395－1401.］

［3］SUN Chengfu，ZHANG Yahong，CHEN Jianhong，et al.Improved differential evolution based on Gaussian disturbance and immune search strategy ［J］.Journal of Nanjing University（Nat Sci Ed），2013，49 （2）：202－209 （in Chinese）. ［孙 成富，张亚红，陈剑洪，等.基于高斯扰动和免疫搜索策略的改进差分进化算法 ［J］.南京大学学报 （自然科学版），2013，49 （2）：202－209.］

［4］WANG Congjiao，WANG Xihuai，XIAO Jianmei.Improved differential evolution algorithm based on dynamic adaptive strategies［J］.Computer Science，2013，40 （11）：265－270 （in Chinese）.［王丛佼，王锡淮，肖健梅.基于动态自适应策略的改进差分进化算法［J］.计算机科学，2013，40（11）：265－270.］

［5］Das S，Suganthan PN.Differential evolution：A survey of the state－of－the－art［J］.IEEE Transactions on Evolutionary Computation，2011，15 （1）：4－31.

［6］ZHANG Guijun， HE Yangjun，GUO Haifeng，et al.Differential evolution algorithm for multimodal optimization based on abstract convex underestimation ［J］.Journal of Software，2013，24 （6）：1177－1195 （in Chinese）. ［张贵军，何洋军，郭海锋，等.基于广义凸下界估计的多模态差分进化算法 ［J］.软件学报，2013，24 （6）：1177－1195.］

［7］JIANG Liqiang，QIANG Hongfu，LIU Guangbin.Modified differential evolution for dynamic optimization problems ［J］.Mini－micro Systems，2013，34 （12）：2837－2840 （in Chinese）.［姜立强，强洪夫，刘光斌.求解动态优化问题的改进差分进化算法［J］.小型微型计算机系统，2013，34 （12）：2837－2840.］

［8］ MENG Hongyun，ZHANG Xiaohua，LIU Sanyang. A differential evolution based on double populaitons for constrained multi－objective optimization problem ［J］.Chinese Journal of Computers，2008，31 （2）：228－235 （in Chinese）. ［孟红云，张小华，刘三阳.用于约束多目标优化问题的双群体差分进化算法 ［J］.计算机学报，2008，31 （2）：228－235.］

［9］Basak A，Das S，Tan KC.Multimodal optimization using a biobjective differential evolution algorithm enhanced with mean distance－based selection ［J］.IEEE Transactions on Evolutionary Computation，2013，17 （5）：666－685.

［10］ZENG Yurong，WANG Lin，DUN Caixia.Simple and effective hybrid differential evolution algorithm for solving traveling salesman problem ［J］.Application Research of Computers，2012，29 （12）：4455－4458 （in Chinese）. ［曾宇容，王林，顿彩霞.一种简单有效的求解TSP 的混合差分进化算法［J］.计算机应用研究，2012，29 （12）：4455－4458.］

［11］Brest J，Greiner S，Boskovic B，et al.Self－adapting control parameters in differential evolution：A comparative study on numerical benchmark problems ［J］.IEEE Transactions on Evolutionary Computation，2006，10 （6）：646－657.

［12］Qin A，Huang V，Suganthan P.Differential evolution algorithm with strategy adaptation for global numerical optimization ［J］.IEEE Transactions on Evolutionary Computation，2009，13 （2）：398－417.

［13］ZHOU Dexin，SONG Mingyu，ZHAN Xianglin.Research of aircraft units testability based on improved extended dependency model［J］.Computer Measurement and Control，2012，20 （12）：3176－3178 （in Chinese）. ［周德新，宋明瑜，詹湘琳.基于改进扩展关联模型的飞机组件测试性研究 ［J］.计算机测量与控制，2012，20 （12）：3176－3178.］

［14］Tang K，Yao X，Suganthan PN，et al.Benchmark functions for the CEC，2008special session and competition on large scale global optimization ［R］.Nature Inspired Computation and Applications Laboratory，USTC，China，2007.