一种基于欧氏距离的种群规模动态控制方法

季伟东 倪婉璐

(哈尔滨师范大学计算机科学与信息工程学院 哈尔滨 150025)

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]用来判定个体的相似程度，距离越近就越相似，可利用的有效信息就越匮乏，更易使算法陷入局部最优，算法全局搜索能力减弱。

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

2.2 动态控制策略

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

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

图1 动态控制流程图

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

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

2.4 反向学习策略分析

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

2.5 算法实现策略

3 算法收敛性分析

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

min{f(x)|∀x ∈S,

定义1 (最小优化问题)令

图2 算法流程图

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

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]的参数设置，令惯性权重ω由0.9到0.4线性递减，学习因子c1=c2=2。遗传算法中涉及的参数是种群规模、交叉概率Pc、变异概率Pm，令Pc=0.70，Pm=0.05。差分进化算法中涉及的参数是种群规模、缩放因子F=0.5 ，交叉概率Cr=0.9。本文中涉及的参数有种群规模的下界 P Smin、种群规模的上界 P Smax、激活阈值K。PSO, GA, DE中的种群规模P Smax都设为100。

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

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

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

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

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

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

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

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

对圆域内外个体的增删个数的选择，首先对比3种情况对算法的影响：在原圆域内外个体数的基础上随机增删、随机增删(0, 1/2)的原圆域内外个体、增删个体数取前两种情况取值区间内的随机值。根据图3可以明显看出，随机增删个体数的取值范围小于半数的算法收敛效果更好，其次是对总数的随机取值，这是由于增删过半数的个体，在收敛前期，通过删除圆域内个体，增加圆域外个体，虽然提高了各种群多样性，但是影响算法的收敛速度；而在收敛后期，删除多数圆域外较差个体，又极大程度地破坏了种群多样性，影响算法收敛精度；而对总数的随机取值，虽然收敛精度有所提高，但是降低了算法的鲁棒性。实验在(0,1/2]随机取值的基础上，又进行了较准确的增删个体数的对比，分别为原圆域内外个体数的10%, 20%, 30%,40%和50%。通过观察对比单峰函数F1和多峰函数F5的收敛曲线，都清晰地表明，当增删的个体数为总体的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 适应度值的平均值与标准差

图4 收敛曲线

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

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，尤其是函数F1, F4, F5, F7, F9, F10, F11，其收敛精度有显著的提高；对于遗传算法，只在单峰函数F2上表现出劣势，这是由于此函数很难收敛到最小值。

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

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

图5 收敛曲线

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在F1, F8, F9函数上的性能优于其他算法；从函数角度来看，对于函数F1, F9，只有EDPS+GA和EDPS+DE能找到理想解。总的来说，EDPS+GA性能最好，因为它在大多数测试功能上具备较好的解，其次是SAMDE和EDPS+DE。

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

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

为进一步验证本文策略的有效性，选用CEC13函数集作为测试函数[43]，考虑篇幅问题，只选取部分函数，其中为F1, F2, F5单峰函数，F6, F10, F11,F14, F16, F17, F19为基础多模函数，F20, F21,F23～F25为组合函数。将EDPS+PSO, EDPS+GA, EDPS+DE与原始算法比较，取30次均值与全局最小值的误差作为最终的结果，实验结果见表5。

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

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

5 结论

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