A Dynamic Control Method of Population Size Based on Euclidean Distance

1.   引言

自然计算(natural computation)是指受自然现象启发而发展起来的智能算法，如人工神经网络、进化计算、群智能、人工免疫系统、量子计算等^[1]。自然计算具有自组织、自学习、自适应能力，能够学习运用自然规律、模拟自然系统甚至社会系统的演变过程，在复杂优化问题求解、智能控制与机器人控制、网络通信与信息安全、社会经济、生态环境、航空航天与军事等领域的应用非常广^[2]。

自然计算方法是基于种群的优化方法，其中，种群规模对算法的搜索能力和算法计算成本有较大影响。种群规模越大，搜索范围越大，则全局最优解存在概率越高，同时增加计算成本；而种群规模小可以降低计算成本，但是可能导致种群无法搜索到更多有效区域^[1]。所以，如何恰当地控制种群规模来平衡算法的全局和局部搜索能力，成为自然计算方法应用亟待解决的问题。

针对此问题，已经存在很多控制种群规模的方法。种群分组是最简单的控制种群规模的方法，Sun等人^[3]将种群分为主群和从群，平衡算法的多样性；为保证算法的全局勘探能力，夏学文等人^[4]提出了具备反向学习和局部学习能力相结合的粒子群优化算法；文献[5]提出了基于多种群的自适应迁移PSO算法(Muti-population based Self-adaptive Migration PSO, MSMPSO)，对初始种群等分，为各子种群分配相应的加速因子而平衡算法；文献[6]通过高斯函数递减惯性权重来平衡粒子群优化算法的全局搜索和局部搜索能力，提出了基于高斯函数递减惯性权重的粒子群优化算法(Particle Swarm Optimization algorithms with Decreasing Inertia Weight based on Gaussian function, GDIWPSO)；Xu等人^[7]利用双种群的思想，提高了收敛精度和收敛速度。过大的规模会降低算法效率，然而通过种群分组后，过小的种群规模又会导致算法过早收敛。文献[8]已经证明不同的进化阶段需要不同的种群规模，因此，动态控制种群规模更为关键。可变种群规模的遗传算法^[9]使用离散Logistic模型控制种群规模；Affenzeller等人^[10]根据算法实际难易程度来调整实际的种群大小；Wang等人^[11]采用可变的人口规模机制，自适应地调整人口规模；文献[12]更是对种群规模从确定性、适应性和自适应方法3个方面进行综述，进一步说明动态控制种群规模的优越性。同时，大多文献采用距离判定法作为种群规模动态控制的先验方法，应用最为广泛的是欧氏距离判定方法。欧氏距离较多应用于机器学习中的特征提取、特征选择、分类。Patel等人^[13]基于欧氏距离进行特征排序与子集的选择；Bouley等人^[14]用欧几里得矩阵定义整体几何构型，利用多维展开技术从距离上重建点集；Alguliyev等人^[15]提出基于欧氏距离平方度量的加权共识聚类方法，提高了聚类精度。通过在特征提取、特征选择、分类等方面的应用，欧式距离可以很好地解释样本间的属性差异，扩展应用到自然计算中，可以理解为个体间的相似度，个体距离越小越相似，则个体间可交互信息越缺乏价值，以此来判定个体对算法的有效性，从而进行增删个体的操作控制种群规模来提高算法性能。例如，基于改进小生境粒子群算法的多模函数优化^[16]、基于欧氏距离的黑洞寻优算法^[17]、基于欧氏距离与多种搜索策略的人工蜂群算法^[18]均是根据欧氏距离判定个体间的位置从而进行增删个体的操作。这些算法分别侧重提高算法收敛速度、精度，以及对算法探索和开发能力的平衡，欠缺对算法性能综合性的考量。

为此，本文提出一种基于欧氏距离的种群规模动态控制方法(a dynamic control method of Population Size based on Euclidean Distance, EDPS)，并将该方法分别运用于3种不同的自然计算方法中，通过对收敛性分析，并在测试函数仿真实验及对实验数据进行非参数检验，验证本文提出的方法的有效性和普适性，能更好地平衡算法的探索和开发能力。

2.   基于核心圆域动态控制种群规模的优化策略

2.1   欧氏距离

欧氏距离计算的是$D$维空间中两点之间的真实距离，是通常采用的一个距离定义。在自然计算方法中，基于欧氏距离的相似性度量^[19]用来判定个体的相似程度，距离越近就越相似，可利用的有效信息就越匮乏，更易使算法陷入局部最优，算法全局搜索能力减弱。

本文计算初始种群的全局最优点与种群平均适应度值点间的欧氏距离，以此作为核心圆域的初始半径，初始半径可定义为

其中，$X_{{\text{gbest}}_s}$表示初始种群全局最优位置，$X_{{\text{avg}}_s}$是种群中适应度值最接近平均值的个体的位置，分别为$X_\text{gbest}, X_\text{avg}$的第$s$个分量。

2.2   动态控制策略

基于核心圆域动态控制种群规模的主要思想为：建立核心圆域，核心圆域的圆心为每次迭代的全局最优点，半径为初始半径$r$间隔$K$代线性递减；迭代前期圆域范围较大，增强全局搜索能力，若圆域内的个体数超过$\theta$倍的种群个体数，则随机删除圆域内20%的个体，同时圆域外增加等量个体，增加个体多样性；迭代后期，随着半径线性递减，圆域范围缩小，进行局部搜索，若圆域外个体数超过$\theta$倍的种群个体数，则将圆域外个体按年龄参数^[20]降序排位，删除前20%的个体。其中，$K$是控制种群规模的激活阈值，为了平衡算法全局和局部搜索能力，$K$应该取较小值，使得迭代前后期有较显著的差异，增强种群多样性，不易陷入局部最优；$\theta$是进行增删个体的判定阈值，理论上，前期进行全局搜索，核心圆域范围较大，圆域内个体数目应多于圆域外的；后期进行局部搜索，接近全局最优，核心圆域范围缩小，因此，在这里设置增删个体的判定阈值的范围为[1/2, 1)；年龄参数，即个体优化迭代次数，年龄较大的个体到后期缺失探索的有效性，将其删除降低迭代后期收敛到局部最优的概率，保证了种群整体的活性。激活阈值$K$和增删个体的判定阈值$\theta$的具体取值由第2部分实验证明给出。

动态控制流程如图1所示。其中，$\text{ni}, \text{no}$分别表示核心圆域的内外个体数；$\text{nidec}, \text{nodec}$分别表示核心圆域内外的删除个体数；$i$是种群迭代的当前代数；${\text{rem}}()$取余操作，是控制种群规模操作判定的前提条件。

图  1  动态控制流程图

下载: 全尺寸图片 幻灯片

2.3   基于Sigmoid函数的半径非线性递减

Sigmoid函数大多用于最小均方误差(Least Mean Squar，LMS)自适应滤波算法，解决固定步长的LMS算法在收敛速度和稳态误差之间存在的矛盾^[21,22]。针对此矛盾，许多学者提出了变步长LMS算法，例如，基于Sigmoid函数的变步长LMS自适应滤波算法^[23-25]，在初始阶段采用大步长因子加快收敛速度，收敛后采用小步长因子降低稳态误差^[26]。本文对核心圆域半径步长自适应调整的主要思想是，在算法早期搜索过程中，采用大半径扩大圆域的范围，提高算法多样性；局部搜索阶段采用小半径，增强算子的有效性，提高收敛精度。而自然界中种群的随机性可用正态分布或近似正态分布来描述，但是由于正态分布函数的计算成本高，而Sigmoid函数与正态分布函数的形式类似，且公式简单，计算成本低。

综上分析，本文选取Sigmoid函数作为替代函数。引入如式(2)的参数$c$，使初始半径$r$随激活阈值$K$变化而变化，半径$R$变化公式见式(3)。

其中，$f\left( {x_{\text{gbest}}} \right)$是当前全局最优个体适应度值，由于$c$是(0, 1)之间的数，初始核心圆域较小会使得个体大多分布在圆域外，直接进行删除个体操作，破坏种群多样性，因此，半径$R$在此基础上扩大1.5倍。

在迭代前期，种群会较快地收敛到全局最优点附近，而后期在其附近进行精细搜索，因此，控制核心圆域半径的参数$c$以及递减的步长都应遵循由大到小递减的规律。根据式(2)、式(3)，全局最优个体的适应度值随着迭代的进行逐渐减小，参数$c$也减小，半径$R$在逐渐变小的同时，变小的速度也随之缓慢，符合Sigmoid函数变化规律及种群搜索的运动规律。

2.4   反向学习策略分析

反向学习策略在2005年由Tizhoosh提出，该策略广泛应用于各类算法中，有效地提高了求解全局最优的效率^[27,28]。对高维复杂函数而言，各维相互间的信息干扰，会使得某些变优的维度被变差的维度所影响，变异效率降低，相较于多次的变异，逐维变异避免了维度间的干扰，变异效率更高，得到的变异解通常更好。因此，本文采用逐维重心反向策略^[29]，设当前迭代次数的最优个体

${\text{Gbest}} = \left( {{\text{Gbest}}_1,{\text{Gbest}}_2, \cdots ,{\text{Gbest}}_D} \right)$在第$i$维的反向解为${{{\rm{Gb}}\breve{{\rm{e}}} {\rm{st}}}} \;=\; \left( {{{\rm{Gb}}\breve{{\rm{e}}} {\rm{st}}}}_1,\;{\text{Gbest}}_2, \;\cdots ,\;{{{\rm{Gb}}\breve{{\rm{e}}} {\rm{st}}}}_i, \cdots , {\text{Gbest}}_D \right)$，其中，${{{\rm{Gb}}\breve{{\rm{e}}} {\rm{st}}}}_i$见式(4)

其中，$k$是均匀分布在区间[0,1]的随机数，式(5)是重心$M$定义方式，$M_i$是重心$M$^[30]在第$i$维的分量。

2.5   算法实现策略

算法：基于欧氏距离动态控制种群规模的自然计算方法

步骤1　设置${{{\rm{PS}}_{\rm{max}},\, {\rm{PS}}_{\rm{min}}}}$, $K$。初始化种群${\text{pop}} \in \left[ {{{{\rm{pop}}_{\rm{max}},\,{\rm{pop}}_{\rm{min}}}}} \right]$，计算初始化种群所有个体的适应度值${\text{fitness}}$，令${\text{fitnessbest}} \leftarrow \min \left( {{\text{fitness}}} \right)$，计算初始半径$r$；

步骤2　若达到算法终止条件，则返回最优解；否则，转步骤3；

步骤3　判断是否达到激活阈值$K$，若满足，转步骤4；否则，转步骤6；

步骤4　若圆域内个体数>$\theta$×种群数，则圆域内删除20%的个体，同时圆域外增加等量个体；

步骤5　若圆域外个体数>$\theta$×种群数，则将圆域外个体按年龄降序排序，删除前20%的个体；

步骤6　根据具体算法对个体更新；

步骤7　对全局最优逐维反向变异，式(4)；

步骤8　迭代次数增加1次，转步骤2。

具体算法流程如图2所示。

图  2  算法流程图

下载: 全尺寸图片 幻灯片

3.   算法收敛性分析

文献[31]表明，目前算法收敛性的分析还不够充分。同时，理论依据多来源于对生物群落社会性的模拟，与其相关的数学分析比较缺乏，这导致现有研究还存在许多不足，缺乏具备普遍意义的理论性分析^[32]。因此，本文在此对算法的收敛性进行分析。

定义1　(最小优化问题)令$\min \left\{ f\left( x \right)|\forall x \in S, 0 \lt f\left( x \right) \lt + \infty \right\}$为最小优化问题，其中$S$为问题的可行域。在可行域内的所有元素对应的适应度值集合中的最小元素即为最小优化问题的最优解。

定义2　设$\left\{ {{y^{(t)}},t \ge 0} \right\}$为一组取值离散的随机变量，离散值的集合为$L = \left\{ j \right\}$，则称$L$为状态空间。若对于任意的$t \ge 1$, ${i^{(k)}} \in L(k \le t + 1)$有

称$\left\{ {{y^{\left( t \right)}},t \ge 0} \right\}$为马尔可夫链^[33]。

定义3　(个体状态和个体状态空间)个体状态由个体运动过程中的位置构成，记为$x$，其中$x \in Y$, $Y$表示可行解空间。每个个体在迭代过程中的所有可能状态组成个体的状态空间，记为$X$，其中$X = \left\{ {x\left| {x \in Y} \right.} \right\}$。

定义4　(种群状态和种群状态空间)算法在一次迭代中，所有个体的状态构成本次迭代的种群状态，记为$\varphi {\text{ = }}\left( {{x_1},{x_2}, \cdots ,{x_i}} \right),\left( {i = 1,2, \cdots ,{N_\varphi }} \right)$，其中${x_i}$为本次迭代中第$i$个个体的状态。种群的所有状态组成该种群的状态空间，记为

定义5　(种群规模)在种群迭代过程中，第$t$代的种群规模为第$t$次迭代中种群的个体数量总和，记为${N^t}$。

定义6　(渐进收敛准则)对于一般的优化问题$\lt Y,f \gt$，采用随机优化算法$Z$，第$t$次迭代的结果为${x_t}$，下一次迭代结果则为${x_{t + 1}} = Z\left( {{x_t},\zeta } \right)$，其中，$Y$为问题的可行解空间，$f$为该算法的适应度函数，$\zeta$为该算法在第$t$次迭代之前曾经搜索过的解。文献[34]在Lebesgue测度空间中，搜索的下界被定义为

其中，$v(x)$为集合$X$上的Lebesgue测度，则最优解可定义为

其中，$\xi \gt 0$。如果算法$Z$在迭代过程中找到了${R_{\xi ,M}}$中的一个点，即认为算法$Z$找到了可以接受的全局最优点或近似全局最优点，全局最优适应度值或近似全局最优适应度值即为$\sigma$^[34]。

条件1　$f\left( {Z\left( {x,\zeta } \right)} \right) \le f(x)$，且若$\zeta \in Y, f\left( {Z\left( {x,\zeta } \right)} \right) \le f(\zeta )$

条件2　对$\forall A \in Y,\;{\rm{s.t}}.{\text{ }}v\left( A \right) \gt 0$，有：$\displaystyle\prod\limits_{t = 0}^\infty {\left( {1 - {v_t}\left( A \right)} \right)} = 0$

其中，${v_t}\left( A \right)$为算法$Z$在第$t$次迭代搜索到的解在空间$A$上的概率测度。

渐进收敛算法同时满足条件1与条件2。

定理1　在EDPS算法中，种群规模缩减概率为

其中，${N^t} \gg {N^{t + 1}}$。所以在迭代过程中，种群规模更新为

证明　种群在算法迭代过程中，根据圆域内外个体的分布比例来对整个种群进行个体的均衡配比操作。圆域外个体通过年龄排序进行删减，从而达到控制种群规模的效果，加快收敛速度。圆域外个体占种群全部个体的相对比例为

一旦圆域外个体总数相对比例超过$\theta$，种群便开始缩减，所以有

如果圆域外个体总数相对比例并不超过$\theta$，种群便会维持在上一次迭代的水平，所以得到种群规模更新规则

证毕

定理2　对于任意渐进收敛算法，EDPS不会破坏该算法的渐进收敛性。

证明　对于任意渐进收敛算法，算法收敛的充要条件是符合条件1与条件2，任意渐进收敛算法必符合上述两个条件。根据条件1，最佳个体适应度值序列$\left( {x_{{\text{gbest}}}^{(1)},x_{{\text{gbest}}}^{(2)}, \cdots ,x_{{\text{gbest}}}^{(t)}} \right)$为单调非递增序列，所以对$\forall i \gt j$有$f\left( {x_{{\text{gbest}}}^i} \right) \le f\left( {x_{{\text{gbest}}}^j} \right)$成立。根据条件2，$\mathop {\lim }\limits_{t \to \infty } x_{{\text{gbest}}}^t = X_{\text{gbest}}$成立，其中$x_{\rm{gbest}}$为该问题的最优解。根据EDPS算法，种群会依概率$P = \dfrac{{f_{\text{worse}}\left( x \right) - f_{\text{best}}\left( x \right)}}{{f_{\text{worse}}\left( x \right) - \left( {\displaystyle\sum\limits_{i = 1}^n {f\left( {x_i} \right)} } \right)/n}}\left( {1 - \theta } \right)$收缩，但圆域外部种群只收缩圆域外部个体总数的20%，即在种群收缩过程中恒有${N^t} \ge {N^{t + 1}} \gt 0$。种群的收缩过程是在减少劣质个体对整个种群的影响，并不会改变$x_{\text{gbest}}$的位置，所以经过EDPS缩减后的种群依然符合条件2，有$\mathop {\lim }\limits_{t \to \infty } P\left( {{x^t} \in Y,x_{{\text{gbest}}}^t = X_{\text{gbest}}} \right) = 1$，即对于任意渐进收敛算法在经过EDPS优化后，依然符合收敛条件。证毕

定理3　任意渐进收敛算法在经过EDPS优化后，以概率为1收敛。

证明　由定理1可知，在算法迭代过程中，种群依概率$P = \dfrac{{f_{\text{worse}}\left( x \right) - f_{\text{best}}\left( x \right)}}{{f_{\text{worse}}\left( x \right) - \left( {\displaystyle\sum\limits_{i = 1}^n {f\left( {x_i} \right)} } \right)/n}}\left( {1 - \theta } \right)$缩减，随着渐进迭代算法的进化，种群缩减概率$P$逐渐递减 。在删除圆域外个体的过程中，并不会改变$x_{\rm{gbest}}$的值。在EDPS迭代过程中有

其中，${N_{{\text{gbest}}}}$为找到最优解时的种群规模，${N_{{\text{start}}}}$为初始种群规模。${N_{{\text{gbest}}}}$在迭代过程中并不改变$x_{\text{gbest}}$，所以在种群规模为${N_{{\text{gbest}}}}$时，依然有

整个种群的缩减并不改变$x_{\rm{gbest}}$的引导位置，即EDPS不改变任意渐进收敛算法的渐进收敛性。EDPS以概率1收敛。 证毕

4.   仿真实验与结果分析

为检验EDPS的综合性能，将其运用到3种不同的自然计算方法中：粒子群优化算法(Particle Swarm Optimization, PSO)，遗传算法(Genetic Algorithm, GA)，差分进化算法(Differential Evolution algorithm, DE)。对应的3种新算法是EDPS+PSO, EDPS+GA和EDPS+DE，并与PSO, GA, DE进行对比。采用通用标准测试函数(Sphere, Rosenbrock, Dixon-price, Powell, Ackley, Levy, Sum squares, Griewank, Rastrigin, Schwefel 2.22, Step)^[35]来验证其对不同算法的改进效果。所有测试函数的维数均取30维。各算法对测试函数分别执行30次，取平均结果。

4.1   参数设置

改进的PSO中涉及的参数有3个，分别是种群规模、惯性权重、学习因子。按照文献[36]的参数设置，令惯性权重$\omega$由0.9到0.4线性递减，学习因子$c_1 = c_2 = 2$。遗传算法中涉及的参数是种群规模、交叉概率$P_c$、变异概率$P_m$，令$P_c=0.70， P_m=0.05$。差分进化算法中涉及的参数是种群规模、缩放因子$F = 0.5$，交叉概率$C_r = 0.9$。本文中涉及的参数有种群规模的下界${\text{PS}}_{\min}$、种群规模的上界${\text{PS}}_{\max}$、激活阈值$K$。PSO, GA, DE中的种群规模${\text{PS}}_{\max}$都设为100。

4.2   不同改进点实验结果分析

为验证不同方面对EDPS的改进效果，主要从以下3处进行对比分析：

(1)激活阈值$K$对算法的影响；

(2)增删个体的判定阈值$\theta$的取值对算法的影响；

(3)增删的个体数对算法的影响；

在此考虑篇幅问题，只选用经典测试函数F₁和F₅，验证改进方法与PSO算法结合的性能。

通过表1激活阈值的数据可以看出，随着$K$的增大，算法对单峰和多峰函数效果越好，但是当激活阈值$K$取30之后，收敛精度没有显著提高，且当$K$由40增加到50时，算法在单峰和多峰函数上的寻优精度都有所下降。因此，本文的激活阈值$K$取值为40。观察表中判定阈值，在单峰函数F₁和多峰函数F₅上，$\theta$为4/5时的平均寻优结果最佳。因此，本文中$\theta$取值为4/5。

表  1  函数F₁和F₅基于激活阈值K和判定阈值θ的平均结果

		F1	F5
激活阈值K	K=0	2.4785×10–9	2.2471×10–04
	K=10	2.7143×10–19	2.3246×10–09
	K=20	5.4301×10–23	3.2744×10–11
	K=30	1.1969×10–24	5.4805×10–12
	K=40	1.1569×10–24	3.7871×10–12
	K=50	1.7930×10–24	5.0300×10–12
判定阈值θ	θ=1/2	2.9332×10–24	6.7745×10–12
	θ=2/3	2.0541×1024	4.8624×10–12
	θ=3/4	3.5091×10–24	3.2218×10–12
	θ=4/5	3.9844×10–25	2.5269×10–12
	θ=5/6	2.1254×10–24	6.2672×10–12

下载: 导出CSV 

| 显示表格

对圆域内外个体的增删个数的选择，首先对比3种情况对算法的影响：在原圆域内外个体数的基础上随机增删、随机增删(0, 1/2)的原圆域内外个体、增删个体数取前两种情况取值区间内的随机值。根据图3可以明显看出，随机增删个体数的取值范围小于半数的算法收敛效果更好，其次是对总数的随机取值，这是由于增删过半数的个体，在收敛前期，通过删除圆域内个体，增加圆域外个体，虽然提高了各种群多样性，但是影响算法的收敛速度；而在收敛后期，删除多数圆域外较差个体，又极大程度地破坏了种群多样性，影响算法收敛精度；而对总数的随机取值，虽然收敛精度有所提高，但是降低了算法的鲁棒性。实验在(0,1/2]随机取值的基础上，又进行了较准确的增删个体数的对比，分别为原圆域内外个体数的10%, 20%, 30%, 40%和50%。通过观察对比单峰函数F₁和多峰函数F₅的收敛曲线，都清晰地表明，当增删的个体数为总体的20%时，算法的性能最佳，且不同取值情况在不同性质的函数上的优劣等级相同，更证明了较确切的增删个体在算法的收敛精度和鲁棒性方面都有积极的作用。

图  3  增删的不同个体数的收敛图

下载: 全尺寸图片 幻灯片

4.3   与PSO结合的算法对比分析

为说明本文算法的优势，将EDPS+PSO与PSO、自适应动态控制种群规模的自然计算方法(Self-adaptive Dynamic Control strategy of Population Size, SaDCPS+PSO)^[1]、MSMPSO^[5]、GDIWPSO^[6]这3个运用种群策略的粒子群算法进行对比。表2和图4是EDPS+PSO与其他算法对比的数据及收敛图，考虑到篇幅问题，只选取部分测试函数收敛图展示。表2的Mean和Std分别表示独立运行函数30次得到的结果的平均值和标准差，括号内数字表示算法在某一个函数上的性能排名，如果两个算法的Mean值相同，则认为标Std较小的更优。位于表格最后的Num表示算法在11个测试函数中取得最优的次数，Ave.R表示算法的平均排名，T.R表示算法总的排名，若两种算法的Ave.R值相同，则认为Num大的算法较优；由于此实验中EDPS+PSO在11个测试函数上的效果均优于其他算法，使得PSO与MSMPSO无法以Mean比较优劣，因此按照这两个算法的Std平均排名确定最终的T.R。考虑到篇幅问题，仅对相关的PSO算法进行了性能排名。

表  2  适应度值的平均值与标准差

测试函数		PSO	SaDCPS+PSO	MSMPSO	GDIWPSO	EDPS+PSO
F1	Mean Std	0.0048(5) 0.0036	5.2678E-05(2) 1.9733E-04	0.0035(4) 0.0048	5.4229E-04(3) 6.9283E-04	4.2030E-22(1) 5.4355E-22
F2	Mean Std	321.6227(5) 757.5841	305.9853(4) 612.6810	37.8965(2) 20.8848	295.3553(3) 646.0457	1.1286(1) 1.2517
F3	Mean Std	11.4856(3) 57.4760	35.6888(5) 96.4784	1.6279(2) 1.3055	15.3413(4) 59.2914	0.6667(1) 5.3114E-13
F4	Mean Std	7.1478(4) 18.5511	24.8610(5) 39.5939	0.0869(2) 0.1725	6.5236(3) 21.1265	3.5356E-06(1) 1.6043E-06
F5	Mean Std	2.8480(3) 0.6077	0.0794(2) 0.3244	4.2122(5) 1.8981	3.2137(4) 0.4853	4.0041E-12(1) 3.1655E-12
F6	Mean Std	0.3953(2) 0.3879	4.7684(5) 8.2253	0.6478(3) 0.4967	0.7580(4) 0.4689	4.8769E-23(1) 6.2365E-23
F7	Mean Std	0.0037(2) 0.0041	6.6792(4) 35.8988	0.6468(3) 0.6773	10.1297(5) 29.9757	1.1530E-14(1) 2.8465E-14
F8	Mean Std	0.0364(2) 0.0198	0.0824(3) 0.2486	0.6663(5) 0.2804	0.2826(4) 0.1051	0.0133(1) 0.0205
F9	Mean Std	41.3446(5) 12.1342	17.7337(2) 13.9827	24.1869(3) 10.0910	45.9872(4) 14.3957	1.3145E-14(1) 5.7943E-15
F10	Mean Std	2.0873(4) 4.0499	3.0617(5) 4.6183	1.4784(3) 1.1296	1.4486(2) 4.4262	6.0354E-07(1) 1.0596E-06
F11	Mean Std	0.0069(2) 0.0083	0.4674(4) 0.1805	1.1304(5) 1.2018	0.1760(3) 0.1348	1.8818E-21(1) 3.2949E-21
Num		0	0	0	0	11
Ave.R		3.36	3.18	3.36	3.54	1
T.R		3	2	4	5	1

下载: 导出CSV 

| 显示表格

图  4  收敛曲线

下载: 全尺寸图片 幻灯片

为了更直观地比较EDPS+PSO的改进性能，观察图4，EDPS+PSO相比较其他4种算法有非常显著的优势。在PSO, SaDCPS+PSO, MSMPSO, GDIWPSO在函数F₅, F₇上的差异较小，而EDPS+PSO在这4个测试函数上均表现出与其他算法的较大差异。在大多函数上EDPS+PSO迭代到5000次仍然有明显的下降趋势，而其他算法迭代到1000次左右就陷入了局部最优，这是由于在搜索前期，EDPS+PSO运用欧氏距离规划核心圆域来控制种群规模，增加种群多样性，避免了种群较快收敛到局部最优；而SaDCPS+PSO采用增删算子策略，使得算法作用于多峰函数F₅时，有跳出局部最优的能力。

4.4   与GA, DE结合的算法对比分析

4.4.1   与传统GA, DE的对比

表3是EDPS+GA, EDPS+DE与GA, DE的实验对比数据，图5是EDPS+GA, EDPS+DE与GA, DE的对比收敛曲线图，考虑篇幅问题，只展示部分收敛曲线。横轴是适应度计算次数，纵轴是平均适应度值。从表的数据可以得出，EDPS+DE在11个测试函数上的寻优结果均优于DE，尤其是函数F₁, F₄, F₅, F₇, F₉, F₁₀, F₁₁，其收敛精度有显著的提高；对于遗传算法，只在单峰函数F₂上表现出劣势，这是由于此函数很难收敛到最小值。

表  3  适应度值的平均值与标准差

测试函数		GA	EDPS+GA	DE	EDPS+DE
F1	Mean Std	6.1788×10–4 4.3273×10–4	1.6779×10–23 9.0360×10–23	3.6639 1.3679	3.8710×10–108 1.6719×10–107
F2	Mean Std	27.2667 0.7982	37.3328 24.9148	3.9463×103 3.7519×103	57.1605 34.2014
F3	Mean Std	0.6668 9.7515×10–5	0.6667 3.0891×10–6	839.0467 813.5188	0.7655 0.4595
F4	Mean Std	0.0081 0.0020	0.0013 2.8946×10–04	28.8509 18.4569	9.6287×10–4 4.9931×10–4
F5	Mean Std	0.0059 0.0021	2.2649×10–13 3.2758×10–13	7.6543 1.0717	1.5099×10–14 3.8918×10–15
F6	Mean Std	2.5529×10–5 1.4647×10–5	1.2247×10–06 1.5500×10–06	2.5036 1.3115	0.0322 0.0509
F7	Mean Std	1.1032×10–04 8.6325×10–05	1.5921×10–26 8.5642×10–26	159.1248 69.8944	3.1682×10–106 9.8938×10–106
F8	Mean Std	0.0106 0.0112	0.0087 0.0162	13.4697 5.7995	0.0041 0.0054
F9	Mean Std	7.4007×10–4 4.0655×10–4	0 0	140.2000 19.1678	0 0
F10	Mean Std	0.0020 5.5404×10–4	7.9361×10–15 4.0250×10–14	14.9866 3.2050	1.7483×10–52 3.7124×10–52
F11	Mean Std	5.9413×10–4 4.0894×10–4	2.5991×10–6 1.6006×10–6	1.3808×103 526.4687	0.1605 0.1092

下载: 导出CSV 

| 显示表格

图  5  收敛曲线

下载: 全尺寸图片 幻灯片

由图5可以看出，运用欧氏距离动态控制种群规模的算法比未使用的更具备较强的全局搜索能力。根据收敛曲线，在函数F₁, F₁₀中，结合本文策略的算法在迭代过程中几乎一直保持下降的趋势，而传统算法则较早地陷入了局部最优，说明本文的方法具备较强的全局搜索能力，这是由于早期减少核心圆域内的较优个体，增加外围较差个体数，提高了个体的多样性，增强了算法的全局搜索能力。对于函数F₄, F₈，在迭代前期保证种群规模的前提下增删个体，使得算法大都较早地收敛到最优值附近，说明前期增加个体多样性对种群寻优有积极的引导作用，体现了增删个体操作的有效性。

4.4.2   与其他改进GA, DE的算法对比分析

为综合对比算法优势，将其与GA, DE结合的控制种群规模算法做对比分析。GAVaPS^[37], APAGA^[38], PL-GA^[39], GPS-GA^[40], dynNP-DE^[41], SAMDE^[42]这些算法基于不同的依据进行种群控制。将EDPS+GA, EDPS+DE与这些算法对比，进一步比较不同种群规模控制策略算法的性能，参数设置参考文献[41]，算法在每个函数上运行10次，对10次的最佳寻优结果进行平均。从表4结果可以看出，EDPS+GA在F₁, F₈, F₉函数上的性能优于其他算法；从函数角度来看，对于函数F₁, F₉，只有EDPS+GA和EDPS+DE能找到理想解。总的来说，EDPS+GA性能最好，因为它在大多数测试功能上具备较好的解，其次是SAMDE和EDPS+DE。

表  4  适应度值的平均结果对比

测试函数	EDPS+GA	GAVaPS	APAGA	PL-GA	GPS-GA	EDPS+DE	dynNP-DE	SAMDE
F1	8.09×10–310	5.02×10–5	5.01×10–5	5.02×10–5	5.04×10–5	0	5.02×10–5	5.02×10–5
F8	0.0197	4.94×10–2	5.14×10–2	5.74×10–2	4.91×10–2	0.0209	5.08×10–2	3.87×10–2
F9	0	–1.02×101	–1.02	–1.03×	–1.02	0	–1.03	–1.03
F11	1.67×10–8	0.11×10	0.11	0	0	0.3508	0	0.00

下载: 导出CSV 

| 显示表格

4.5   CEC13测试函数实验结果分析

为进一步验证本文策略的有效性，选用CEC13函数集作为测试函数^[43]，考虑篇幅问题，只选取部分函数，其中为F₁, F₂, F₅单峰函数，F₆, F₁₀, F₁₁, F₁₄, F₁₆, F₁₇, F₁₉为基础多模函数，F₂₀, F₂₁, F₂₃～F₂₅为组合函数。将EDPS+PSO, EDPS+GA, EDPS+DE与原始算法比较，取30次均值与全局最小值的误差作为最终的结果，实验结果见表5。

表  5  适应度值的运行平均结果

函数	PSO	EDPS+PSO	GA	EDPS+GA	DE	EDPS+DE
F1	1.84×103	5.46×10–13	6.38×10–3	2.74×10-2	5.69×103	6.96×102
F2	9.82×106	1.12×105	6.24×106	6.66×106	1.00×107	6.84×106
F5	9.39×102	1.83×10–4	1.91×10–2	6.03×10-2	1.50×102	5.00×101
F6	1.54×102	1.08×101	7.57×101	6.19×101	2.79×103	1.16×102
F10	3.99×102	1.08×101	1.46	1.61	5.08×102	1.45×102
F11	1.41×102	5.02×101	1.82×10–1	4.87×102	1.67×102	1.24×101
F14	2.83×103	1.38×103	1.25×101	4.16×10–1	6.51×103	7.62×102
F16	1.32	9.32×10–1	1.27	1.74	2.53	1.82
F17	1.38×102	3.47×101	4.24×101	3.06×101	2.45×102	3.18×101
F19	4.91×102	2.95	1.25	8.88×10–1	2.23×102	4.72
F20	3.86×102	3.35×102	5.14×102	3.24×10+02	9.91×102	6.08×102
F21	3.64×103	1.72×103	1.29×102	1.04×10+02	6.74×103	7.10×102
F23	2.87×102	2.80×102	2.94×102	3.16×102	2.41×102	2.33×102
F24	2.98×102	2.95×102	3.50×102	3.43×10+02	2.65×102	2.63×102
F25	3.33×102	2.05×102	2.02×102	2.25×102	2.002×102	2.001×102

下载: 导出CSV 

| 显示表格

与原始算法进行对比，EDPS+PSO在10个函数上寻得较高的精度解，其中包含全部单峰函数，基础多模函数F₆, F₁₀, F₁₁, F₁₄, F₁₆, F₁₇, F₁₉，表明EDPS+PSO处理单峰函数问题的能力非常强，运用动态控制策略后，改善了PSO易陷入局部最优的缺点，在多模和组合函数上也有较大的优势；EDPS+DE在全部函数上寻得精度最高的解，说明EDPS+DE在3类测试函数上的优化性能都有一定的竞争力；而EDPS+GA仅在多模函数F₆, F₁₄, F₁₇, F₁₉和组合函数F₂₀, F₂₁, F₂₄这7个函数上寻得的解的精度较高，这是由于GA本身不易于陷入局部最优的特点，对单峰函数而言，若算法在前期就寻得全局最优区域，动态控制策略的运用会造成评估次数的浪费，导致算法性能下降，相对来说，其处理组合函数问题的能力较强，说明本文提出的策略适用于解决此类函数优化问题。

5.   结论

平衡搜索本质上就是早期扩大搜索范围，后期精确搜索，本文通过动态控制种群规模从而达到平衡算法搜索能力的效果。迭代前期控制种群规模不变，删除核心圆域内较优个体，在核心圆域外等添加等量个体，提高个体多样性，达到扩大搜索范围的目的；后期进行局部精细搜索，因此对核心圆域外的个体进行删除操作，加速收敛，同时采用反向变异策略，避免算法陷入局部最优。但是，算法的不足之处在于反向变异策略的逐维性大大增加了算法计算高维函数的时间成本，在后续研究中，可以针对高维函数的反向变异进一步改善，降低时间复杂度。