2020, Vol. 35
种群的初始化对差分进化算法的收敛性至关重要, 也会影响搜索高质量解的效率.高质量的初始种群可有效解决差分进化算法搜索能力差的问题.大部分的种群初始化都是采用随机产生的方法, 例如基于伪随机数发生器(pseudo-random number generator, PRNG)的方法和基于混沌数发生器(chaotic number generator, CNG)的方法等[1-2].随机方法必然导致初始种群中存在低质量的个体, 并且很难保证覆盖整个搜索空间, 从而需要更多的时间收敛到前景区域.
在随机法的基础上, 结合反向学习、局部搜索算法和基于中心点的采样方法等, 人们提出了一些新的种群初始化方法[3-7]. Bajer等[5]提出一种基于聚类与柯西突变的种群初始化方法, 通过识别搜索空间的前景区域, 从中选择高质量的初始个体, 并对个体进行柯西突变, 以保持个体的多样性. Poikolainen等[6]提出一种基于聚类的种群初始化方法, 利用Rosenbrock等局部搜索算法对局部空间进行探索, 选择局部最优解, 然后利用聚类算法探索整个搜索空间, 选择前景区域. Elsayed等[7]提出一种基于序列的启发式空间填充方法, 使得初始个体能够均匀覆盖整个搜索空间.目前提出的方法可有效提高搜索最优解的概率, 但是仍存在以下问题:
1) 需要大量的计算, 例如基于反向学习的种群初始化方法, 需要额外地对两个种群中的个体进行适应度函数的计算, 从而选择最优的个体作为初始种群个体;
2) 采用随机法产生的原始种群个体的质量决定着整个算法的性能;
3) 基于序列的种群初始化中的个体虽然能够覆盖整个搜索空间, 但是并未对前景空间中的个体和孤立个体进行区分, 导致种群中存在低质量的孤立个体, 从而影响搜索效率.
针对上述问题, 本文提出一种新的种群初始化方法, 该方法将基于决策变量划分的搜索空间划分方法与局部搜索和聚类相结合, 通过决策变量均匀划分得到能够均匀覆盖整个搜索空间的个体, 利用局部搜索方法对各子空间进行局部搜索得到局部最优的初始个体, 利用改进的Canopy算法结合K-means算法辨识搜索空间中前景区域, 以此为基础对局部搜索产生的局部最优个体进行筛选, 最终生成初始种群中的个体.采用该方法产生的初始种群可以覆盖整个搜索空间, 种群初始化过程中在追求个体多样性的同时, 又确保从前景区域中取得个体, 可有效提高差分进化算法的搜索能力, 提高差分进化算法的收敛性.
1 搜索空间的划分图 1为种群初始化方法的总体框图, 主要包括搜索空间划分、前景区域选择和初始种群的构建等, 本节主要对搜索空间的划分进行分析.
|
图 1 种群初始化方法总体框架图 |
差分进化算法的本质是一种多目标优化算法, 用于求解多维空间中的最优解.不失一般性, 多目标优化可用下式[8-9]表示:
|
(1) |
其中: f(x)为目标函数, x=[x1, x2, ..., xn]为候选解, 包含n个决策变量, 每个决策变量xi搜索域的取值范围为[ximin, ximax]; D为搜索空间.
1.2 决策变量搜索域的划分设[xmin, xmax]为n个决策变量搜索域的取值范围, xmin=[x1min, x2min, ..., xnmin]为n个决策变量最小值的集合, xmax=[x1max, x2max, ..., xnmax]为n个决策变量最大值的集合.为确保候选解均匀覆盖整个搜索空间, 首先需要对每个决策变量的搜索域进行均匀划分.
若将搜索域划分为q个子空间, 则需要q+1个子向量对[xmin, xmax]进行划分. q+1个子向量Sk可通过下式得到:
|
(2) |
其中l为两个子向量之间的间隔, 有
|
(3) |
搜索空间划分完成后, 从各个子空间中选择一个随机个体, 然后以该随机个体为初始点, 利用Hooke-Jeeves算法[10]对搜索空间进行探索, 选择局部最优的个体作为初始个体.
以一个初始点的探索过程为例, 具体的探索过程如下.
1) 给定初始点x1∈ D, 初始步长向量δ, 加速因子α ≥ 1, 缩减率β∈(0, 1), 精度ε>0, ej=(0, ..., 0, 1, 0, ..., 0)T, j=1, 2, ..., n.令y1=x1, k=1, j=1.
2) 轴向搜索.从参考点yj出发, 依次沿x各分量(即坐标轴)的方向以一定的步长寻找函数的下降点, 令
|
(4) |
当x的各个坐标轴遍历完成后, 若f(yn+1) < f(xk), 则进行模式搜索, 否则需重新调整步长进行轴向搜索.
3) 模式搜索.令xk+1=yn+1, 将y1=xk+1+α(xk+1-xk)作为新的参考点, 令k:=k+1, j=1.新的参考点确定完成后转到2)进行轴向搜索.
4) 调整步长.如果δ≤ε, 则停止搜索, xk即为初始个体; 否则, 令δ:=βδ, y1=xk, xk+1=xk, 同时令k:=k+1, j=1, 转2)继续新的轴向搜索.
从每个子空间中选择随机个体作为初始点, 可保证初始点能够均匀覆盖整个搜索空间.采用Hooke-Jeeves算法对搜索空间进行轴向和模式搜索, 可对最优解的数量和位置进行一个粗略的评估, 并将搜索得到的局部最优解作为下一步聚类的候选个体, 以提高参与聚类的初始个体的质量, 使得前景区域的选择更有指向性, 为前景区域的选择奠定基础.
2 前景区域的选择当候选个体确定后, 采用K-means聚类算法对候选个体进行聚类, K-means聚类算法是一种简单的迭代型聚类算法, 可将多个个体构成的个体集划分为k个簇, 使得同簇内个体间比较相似, 而不同簇个体间差异比较大, 每个簇代表一个前景区域. K-means聚类算法的运行速度比较快, 同时易于修改, 所以在实际中使用非常广泛[11-13].
在实际应用中K-means聚类算法也存在一些问题, 例如需要提前确定k值, 以及初始的k个聚类中心是随机选取的, 而候选个体中可能存在孤立个体, 如果将孤立个体作为初始聚类中心, 则会影响聚类结果.针对上述问题, 本文结合Canopy算法[14-15]对聚类过程进行修改, 改进后的算法聚类效果更好, 聚类准确性更高.
2.1 Canopy算法个体选择机制常规的Canopy算法首先给定候选个体集合与距离阈值T1和T2, T1为Canopy集合的半径, T2为非Canopy候选个体集合的半径, 且T1>T2, T1和T2的设定可通过交叉验证方式确定[16].然后从候选个体中随机选择个体xi作为Canopy, 同时将个体xi从候选个体中移除, 并利用下式计算候选个体中所有个体到xi的距离:
|
(5) |
其中xik表示个体xi的第k个决策变量, 且i≠j[14].将d小于T1的个体划到Canopy中, 同时将d小于T2的个体从候选个体中移除.重复该过程, 直到没有候选个体时结束.
为了保持算法的随机性, 需要随机选择个体作为Canopy, 不可避免地会选择孤立个体或者性能较差的个体, 从而降低算法的效率.为了提高将局部最优个体作为Canopy的概率, 同时避免孤立个体作为Canopy, 本文对Canopy算法的候选个体选择机制进行了修改.
针对选择局部最优个体的问题, 设计局部最优个体选择机制.首先, 计算各候选个体的适应度函数F(xi), 其中xi为第i个候选个体; 然后, 利用
|
(6) |
计算各候选个体的选择概率, 利用轮盘赌选择法[5]对候选个体进行选择.利用该方法可有效提高选择局部最优的个体作为Canopy的概率, 同时又保证了个体选择的随机性.
针对孤立个体问题, 设计孤立个体判别机制.当Canopy划分完成后, 假设生成m个Canopy, 每个Canopy即为一个簇, 每个簇中个体的数量为numi, i =1, 2, ..., m.若numi < numPoint, 则将第i个簇中个体判定为孤立个体, 将该簇及簇中的个体删除. numPoint为判定簇中个体是否为独立个体的阈值, 其值可根据候选个体的数量及实际的应用背景确定.当所有孤立个体及相应的簇都删除后, 剩余簇的数量即为K-means聚类算法的k值, 然后选择每个簇的中心点作为K-means聚类算法的初始中心点ci, i=1, 2, ..., k.
2.2 K-means聚类算法通过Canopy算法得到K-means聚类算法的k值和初始中心点后, 利用K-means算法进行进一步的聚类划分.根据Canopy算法生产的k个中心点ci, 形成k个簇Si, 根据下式计算候选个体到中心点的距离:
|
(7) |
并将候选个体分配到距离最小的簇中[11].
当候选个体划分完成后, 利用下式重新计算各个簇的中心点:
|
(8) |
其中: |Si|为第i个簇中包含候选个体的数量, 
当新的中心点计算完成后, 再次利用式(7)对簇进行重新划分, 循环此过程直到中心点不再发生变化或者达到设定的迭代次数, 此时K-means聚类过程结束.
3 初始种群的构建经过聚类后, 各个簇的中心点可能会集中在某个局部最优区域, 当对搜索空间进行探索时, 若该区域包含全局最优点, 则进化算法最终收敛于全局最优点; 若该区域不包含全局最优点, 则进化算法最终会收敛于该区域的某个局部最优点, 从而导致提前收敛.为了避免进化算法的提前收敛, 需保证初始种群中个体的多样性以及个体可覆盖整个搜索空间, 因此除了将K-means聚类后各个簇的中心点作为初始种群个体外, 还将采用以下方法对初始种群进行填充.
因为经过Hooke-Jeeves算法产生的候选个体是在搜索空间均匀划分的前提下得到的, 是对搜索空间的初步探索, 得到的候选个体可覆盖整个搜索空间, 并保持了个体间的多样性.首先, 将候选个体中已作为Canopy的个体剔除, 以避免初始种群个体的重复选择; 然后, 利用式(6)重新计算各候选个体的选择概率, 利用轮盘赌选择法对候选个体进行选择, 将得到的个体作为初始种群的个体, 直到达到初始种群所需的个体数量, 初始种群构建完成.
4 实验对比分析为了验证本文提出的种群初始化方法的有效性, 将提出的种群初始化方法应用于差分进化算法, 并与现有的种群初始化方法分别从算法运行时间、适应度函数和收敛性等方面进行对比分析.为了便于对比分析, 差分进化算法采用相同的控制参数, 设变异策略为DE / best / 1, 变异算子F=0.5, 交叉概率Cr=0.3, 最大迭代次数为200, 种群大小为30, 个体的维度为10, 每种算法独立运行100次.本实验的测试平台采用jMetal, jMetal是Java实现的一套多目标优化框架, 可较方便地实现各种多目标优化方法, 并在3.20 GHz Intel Core(TM) i5-3470 CPU的计算机上运行.
本实验选用测试函数集CEC2017进行测试, CEC2017包含30个测试函数, 其中包括3个单峰函数, 7个基本的多峰函数和20个混合函数, 混合函数由多个子函数构成.为了提高实验的测试效率, 本实验从中选择了前5个测试函数进行测试.
实验选择3个主流的种群初始化方法作对比分析, 包括基于聚类和柯西变异的种群初始化方法(population initialization based on clustering and cauchy mutation, PICCM)[5], 基于聚类的种群初始化方法(cluster-based population initialization, CBPI)[6]和基于序列的种群初始化方法(sequence-based deterministic initialization, SBDI)[7].
4.1 运行时间对比表 1为基于不同种群初始化方法的差分进化算法运行时间的均值与标准差, 运行时间单位为ms.综合分析表 1可知, 本文提出的基于搜索空间划分和局部寻优方法的种群初始化方法, 可有效减少差分进化算法的运行时间, 并有效减小了运行时间的标准差.例如函数f5, 本文提出的方法的运行时间为SBDI方法的3/4, 其标准差只有SBDI的1/4左右.主要原因在于, 虽然SBDI也对搜索空间进行了划分, 但是其搜索空间中个体的选择是随机的, 从而降低了算法的搜索效率.另外, CBPI和PICCM方法中, 均采用K-means聚类算法进行局部寻优, 而且CBPI也采用Rosenbrock等局部搜索算法对搜索空间进行搜索, 但是其局部搜索的初始个体是随机选择的, 并且不能保证覆盖搜索空间.~而本文提出的种群初始化方法, ~不仅对搜索空间进行了划分, 而且利用Hooke-Jeeves算法选择个子空间内局部最优的个体作为初始个体, 保证初始个体覆盖搜索空间, 同时具有局部最优特性.因此, 上述现有方法的运行时间要高于本文提出的方法, 并且标准差要大于本文提出的方法.
|
表 1 运行时间的均值与标准差 |
表 2为基于不同种群初始化方法的差分进化算法的适应度函数的均值与标准差.与运行时间的结果类似, 基于本文提出的种群初始化方法的差分进化算法, 具有更优的适应度均值和标准差.例如函数f4和f5的均值分别为15.8和16.2, 基本收敛于该函数的真实最小值, 而函数f1、f2和f3的均值与方差也优于其他方法.针对函数f2, 其均值为SBDI方法的3 %, 而标准差约为1 %.更小的适应度函数均值说明进化算法更有效地收敛于函数的最小值, 而更小的方差则说明进化算法的稳定性更优.主要原因在于利用Hooke-Jeeves算法选择局部最优的个体提高了空间探索的效率, 有利于得到局部最优的候选个体, 改进的Canopy算法结合K-means算法, 可进一步提高K-means算法初始个体的质量, 利于寻找各个簇内的局部最优个体, 从而使得进化算法收敛于全局最优解.
|
|
表 2 适应度函数的均值与标准差 |
图 2 ~图 6为采用不同种群初始化方法的差分进化算法分别对函数f1 ~ f5计算的收敛曲线对比, 由于适应度函数的取值范围较大, 为了便于对比, 采用对数函数对适应度函数值进行压缩.
|
图 2 函数f1的收敛曲线 |
|
图 3 函数f2的收敛曲线 |
|
图 4 函数f3的收敛曲线 |
|
图 5 函数f4的收敛曲线 |
|
图 6 函数f5的收敛曲线 |
由图 2~图 6可知, 采用本文提出的种群初始化方法的差分进化算法, 在迭代初始时具有更优的适应度函数值.例如, 与SBDI方法相比较, 函数f2最大可达到2.3个数量级, 与CBPI相比较, 最大可达到2个数量级, 说明经过空间划分以及利用Hooke-Jeeves算法局部寻优后, 初始种群中具有更优的个体.同时, 本文提出的方法具有更快的收敛速度并收敛于更小的适应度函数值, 主要原因在于改进后的Canopy算法进一步提高了K-means算法中初始中心的质量, 提高了聚类算法的效率.另外, 将K-means聚类的中心点与轮盘赌选择法得到的个体作为初始种群个体, 保证初始种群中个体的多样性以及个体可覆盖整个搜索空间, 从而提高差分进化算法收敛效率.
5 结论本文针对差分进化算法的种群初始化问题进行了研究, 将基于决策变量划分的搜索空间划分方法与Hooke-Jeeves算法局部搜索和改进的K-means聚类算法相结合, 提出了一种新的种群初始化方法.并将该种群初始化方法应用于差分进化算法中, 并与现有的具有代表性的种群初始化方法对CEC2017测试函数进行了实验对比.实验结果表明, 本文提出的种群初始化方法具有更短的运行时间、更小的适应度函数和更优的收敛特性, 有效地提高了差分进化算法的进化效率.
| [1] |
Borhan K, Li X D, Qin A K. A review of population initialization techniques for evolutionary algorithm[C]. Proceedings of the 2014 IEEE Congress on Evolutionary Computation. Beijing: Institute of Electrical and Electronics Engineers Inc, 2014: 2585-2592.
|
| [2] |
田红军, 汪镭, 吴启迪. 一种求解多目标优化问题的进化算法混合框架[J]. 控制与决策, 2017, 32(10): 1729-1738. (Tian H J, Wang L, Wu Q D. A hybrid framework of evolutionary algorithm for solving multi-objective optimization problems[J]. Control and Decision, 2017, 32(10): 1729-1738.) |
| [3] |
Mustafi D, Sahoo G. A hybrid approach using genetic algorithm and the differential evolution heuristic for enhanced initialization of the k -means algorithm with applications in text clustering[J]. Soft Computing, 2019, 23(15): 6361-6378. DOI:10.1007/s00500-018-3289-4 |
| [4] |
Yang Y H, Xu X B, He S B, et al. Cluster-based niching differential evolution algorithm for optimizing the stable structure of metallic clusters[J]. Computational Materials Science, 2018, 149: 416-423. DOI:10.1016/j.commatsci.2018.03.055 |
| [5] |
Bajer D, Martinović G, Brest J. A population initialization method for evolutionary algorithms based on clustering and cauchy deviates[J]. Expert Systems with Applications, 2016, 60(1): 294-310. |
| [6] |
Poikolainen I, Neri F, Caraffini F. Cluster-based population initialization for differential evolution frameworks[J]. Information Sciences, 2015, 297: 216-235. DOI:10.1016/j.ins.2014.11.026 |
| [7] |
Elsayed S, Sarker R, Coello C A. Sequence-based deterministic initialization for evolutionary algorithms[J]. IEEE Transactions on Cybernetics, 2017, 47(9): 2911-2923. DOI:10.1109/TCYB.2016.2630722 |
| [8] |
吴秀丽, 袁琦. 差分进化算法求解带批处理机的机器人制造单元调度问题研究[J]. 控制与决策, 2020, 35(1): 74-82. (Wu X L, Yuan Q. Differential evolution algorithm for soling robotic cell scheduling problem with batch-processing machines[J]. Control and Decision, 2020, 35(1): 74-82.) |
| [9] |
侯莹, 韩红桂, 乔俊飞. 基于参数动态调整的多目标差分进化算法[J]. 控制与决策, 2017, 32(11): 1985-1990. (Hou Y, Han H G, Qiao J F. Adaptive multi-objective differential evolution algorithm based on the dynamic parameters adjustment[J]. Control and Decision, 2017, 32(11): 1985-1990.) |
| [10] |
Tolga A, Egemen Y. Multiobjective Hooke-Jeeves algorithm with a stochastic Newton-Raphson-like step-size method[J]. Expert System with Application, 2019, 117(3): 166-175. |
| [11] |
Marco C, Aritz P, Jose A L. An efficient approximation to the K -means clustering for massive data[J]. Knowledge-Based Systems, 2017, 117(2): 56-69. |
| [12] |
Surya K, Tripti M, Vinay K J, et al. LeaderRank based k -means clustering initialization method for collaborative filtering[J]. Computers and Electrical Engineering, 2018, 69(6): 598-609. |
| [13] |
Jocelyn Z G, Ado A A, Abdelhak M G. Efficient K -means based clustering scheme for mobile networks cell sites management[J]. Computer and Information Sciences, 2018, 11: 1-8. |
| [14] |
Zhang G, Zhang C C, Zhang H Y. Improved K -means algorithm based on density Canopy[J]. Knowledge-Based Systems, 2018, 145(4): 289-297. |
| [15] |
Li J J, Zhang K, Yang X L, et al. Category preferred Canopy- K -means based collaborative filtering algorithm[J]. Future Generation Computer Systems, 2019, 93: 1046-1054. DOI:10.1016/j.future.2018.04.025 |
| [16] |
胡小建, 韦超豪. 基于Canopy和k -means算法的订单分批优化[J]. 合肥工业大学学报:自然科学版, 2017, 40(3): 414-419. (Hu X J, Wei C H. Order batching optimization based on Canopy and k -means algorithm[J]. Journal of Hefei University of Technology: Natura Science, 2017, 40(3): 414-419.) |