一种基于多种群协作进化的自适应差分进化算法研究∗

周 頔

（四川文理学院智能制造产业技术研究院 达州 635000）

1 引言

差分进化（Differential Evolution，DE）是1995年提出的一种启发式随机搜索的智能优化算法［1］。由于DE算法通过群体内个体之间的合作与竞争产生的群体智能指导优化搜索，其原理简单，可对在连续空间内进行随机、并行、有效的全局搜索，具有较强的鲁棒性、稳健性以及强大的全局寻优能力，所以该算法越来越受到学术界和工程界的广泛关注，在约束优化计算、信号处理、环境保护和运筹学以及NP问题等多个领域得到广泛的应用。

然而由于DE算法是通个体之间的差分矢量进行变异、交叉和选择来实现寻优，所以它存在着早熟收敛、易陷入局部最优和寻优效率不高等缺陷。近年来，许研究者针对这些存在的缺陷，提出了很多的改进 DE 算法［2～12］。Lee等［2］采用适应性步长局部搜索策略来确定DE 算法合适的缩放比例因子，目的是为了加速算法搜索。方强等［3］将单纯形寻优操作引入DE 算法，以提高算法的搜索精度。张雪霞等［4］基于二次规划法，提出一种改进的DE 算法。Brest 等［5］提出一种改进的 DE 算法，以自适应调节算法的参数缩放因子和交叉概率。吴亮红等［6］提出一种基于双种群结构的伪并行DE 算法，以提高DE算法的收敛速率和全局搜索能力。Gong等［7］利用正交设计法来改进DE 算法的收敛速度，提高其综合寻优性能。Ali等［8］将惩罚函数加入DE算法，用于较好地求解约束条件问题。贾东立等［9］将混沌变异和高斯变异用作局部搜索策略，基于混沌理论和高斯局部优化方法，提出一种新的混合DE算法。葛延峰等［10］通过改进个体差异信息和适度值取值范围，提出一种改进自适应DE 算法。曲福恒等［11］利用并行多个策略与参数组合来提高个体多样性，提出了一种改进的差分进化算法。陈华等［12］提出一种可自动调节缩放因子和交叉概率因子的自适应DE算法。

这些改进的DE 算法能够较好地服了DE 算法的陷入局部最优和早熟收敛性问题，但算法的局部搜索能力、收敛速度和寻优精度还有待进一步加强。本文为了充分利用局部搜索策略，协同进化机制以及多种群进化等优点，提出一种改进的多种群协作自适应差分进化（MSDPIDE）算法，通过函数优化验证MSDPIDE算法的有效性。

2 基本差分进化算法

DE 算法采用了遗传算法的基本框架，同时借鉴了Nelder-Mead 单纯形方法，设计了独特的差分变异算子［5］。DE 算法包括变异操作、交叉操作和选择操作［13～14］。

2.1 初始化

其中xjmin和xjmax分别表示种群中个体的下界和上界。rand 是［0，1］区间上的均匀随机数发生器。

2.2 变异操作

变异操作是DE 算法与遗传算法的不同之处。在DE算法中，主要是对父代的差分矢量进行变异，不同的两个个体（）构成矢量对。不同的DE算法方法如下:

1）DE/rand/1/bin

2）DE/rand/2/bin

3）DE/best/1/bin

4）DE/rand/2/bin

5）DE/current-to-best/1

2.3 交叉操作

均匀交叉变异产生的个体xk和种群中的第i个个体，用来补偿上一步的变异搜索，进而产生试验向量xG。本文采用二项式交叉方法。具体交叉操作的方程为

其中，jrand∊{1,2,…,D}是一个随机整数，用来保证目标个体至少有一个分量进行了交叉操作。交叉概率CR ∈［0，1］。

2.4 选择操作

DE算法选择个体xG和适应度更好的个体，作为子代个体。选择的的标准如下:

3 多种群协作自适应差分进化（MSDPIDE）算法

3.1 局部搜索策略

为了提高DE 算法个体产生策略的多样性，避免DE 算法早熟收敛问题，本文采用局部搜索策略来调整自适应DE 算法搜索。假设当前DE 算法种群规模为 NP ，最优解为。随机选择个体x=(x1,x2,…,xD)，采用下列等式对最优解xtgbest 进行局部搜索，产生新的个体。

其中，j=1,2,3…,D ，U(-1,1)表示-1～1 之间均匀分布的随机数。

3.2 多种群协作进化

将种群个体分成N 个子群体，用于代替单一种群在可行解空间中进行搜索，促进个体间的交换信息。在算法迭代中，为了增加算法的搜索速度，降低算法的复杂度，首先基于不同策略，协同进化各个子种群，然后按子种群中个体适应度值排序，获得每个子种群的最优个体，更新每个子群体的最差个体，并评价适应度值。接着重新合并N个子种群为一个种群，再随机分为N 个子群体，再得每个子种群的最优个体。并进行最优个体的比较，把优秀个体保留下来，实现不同群体间动态交换信息。这样能促进各个种群并行进化，保持优秀个体进化的稳定性，避免过早收敛现象。

3.3 MSDPIDE算法思想与描述

由于自适应DE算法存在不能及时更新进化策略，所以基于局部搜索策略，改进自适应DE 算法。针对求解问题，动态产生独立进化的子种群，增强子种群个体间的信息交换，保持种群的多样性；通过利用群体之间的对等的相互移民策略均衡全局探索能力和收敛速度之间的矛盾，使得算法在合理的计算复杂度下具有较高的全局收敛率。

MSDPIDE算法的具体步骤如下:

第一步:初始化算法各参数:这些参数包括种群大小N 、迭代次数Tmax、交叉概率CR、缩放因子F 、自变量的下界和上界、初始衰减率α 以及初始增长率 β 等。

第二步:随机生成初始种群，t=1。

第三步:评价每个个体得适应度值，找出最优个体。

第四步:判断最优解是否满足要求。若是输出最优解；否则，执行第五步。

第五步:按照式（2）～（6），进行变异操作。

第六步:按照式（7），进行交叉操作。

第七步:按照式（8），对进行选择操作。

第八步:对最优个体根据式（9），进行局部搜索。

第九步:新的种群生成后，令t =t +1，转第三步继续进行。

4 数值实验研究

4.1 测试函数

为了验证MSDPIDE 算法在高维复杂优化函数中的性能，Benchmarks 函数被选作对算法进行测试。本文选用的9 个经典测试函数和变量范围，如表1 所示，其全局最优值均为0。同时MSDPIDE 算法与DE 算法和CADE算法［16］进行比较。

表1 Benchmarks测试函数集

4.2 运行环境与参数设置

实验开发环境如下:Matlab 2012a，运行于I5 CPU 2.20GHz，4.0GB 内存台式电脑。实验参数设置如下:种群规模NP=100，函数维数为1000，群个数n=3，缩放因子 F =0.60，交叉概率CR=0.80，最大进化代数为Tmax=500，每个算法独立运行20次。

4.3 实验结果与分析

DE 算法、CADE 算法和 MSDPIDE 算法运行 20次的求解Benchmarks 测试函数，测试结果的最大最优值、最小最优值和平均最优值，如表2所示。

表2 连续20次的运行结果

从表2 中可以看出，根据MSDPIDE 算法和DE算法求解这9 个函数的结果，除DE 算法求解 f9函数获得较好的结果外，MSDPIDE 求解 f1、f2、f3、f4、f5、f6、f7、f8函数均比DE 算法的求解效果好。MSDPIDE 算法与 ACDE 比较，ACDE 算法能够较好地求解 f3和 f5函数，MSDPIDE 能够较好地求解 f1、f2、f4、f6、f7、f8和 f9函数，且性能比ACDE算法好。综上可知，本文提出的MSDPIDE算法在1000 维的高维复杂基准函数测试中表现得更为稳定，求解精度更高，能够解决高维多极函数的复杂优化问题。

5 结语

针对实际工程应用中的高维复杂函数优化问题，提出了利用局部搜索策略提高个体多样性，成功地避免了算法的早熟收敛，提高了全局寻优能力，保证个体之间能够进行充分高效的信息交换。利用自适应调节机制，以平衡局部搜索与全局搜索。通过对9个典型benchmark函数进行测试结果表明，该MSDPIDE 算法比DE 和CADE 算法总体性能优。MSDPIDE 算法寻优能力强，搜索精度高，稳定性好，更适于处理高维函数优化问题。