结合引力测度和质心变异策略的混合粒子群优化算法

胡 凯，李均利，林秀丽，邓 浩

(四川师范大学 计算机科学学院，成都 610101)

1 引 言

粒子群优化(Particle Swarm Optimization，PSO)算法是由Eberhart和Kennedy[1，2]受鸟群等群聚类生物觅食行为启发而于1995年提出的一种群体智能算法.PSO算法因其算法原理简单、易于实现，并且没有过多参数的调节，对非线性、多峰值问题均有较强的全局搜索能力，广泛应用于科研和工业领域.智能算法科研工作者们对PSO算法的研究也日益加深，同其他智能优化算法一样，PSO算法在求解高维度复杂函数的时候也存在在算法前期易陷入局部极值和在算法后期收敛精度不够高等问题，因此攻克这些难题就成为智能算法研究者们研究的主要方向.罗强等[3]等提出一种最优粒子逐维变异的粒子群优化算法，将全局最优的粒子逐维进行重心反向学习变异，降低了维度间的互相干扰，使粒子更好的向更优的位置移动.周凌云等[4]提出一种邻域重心反向学习的粒子群优化算法，使用邻域重心作为参考点计算反向解，采用收缩因子拓展搜索范围，增强高质量解的搜索机率.王越等[5]提出一种带变异算子的自适应惯性权重二进制粒子群优化算法，采用非线性递增策略优化惯性权重，平衡算法的全局和局部搜索能力，然后改进速度更新公式，扩大粒子的搜索域.李志鹏等[6]提出应用小生境和反向学习策略的量子粒子群算法，在群体中划分小生境并设置共享区域，其内粒子适应度动态共享，有效防止早熟，并引入反向策略，增强开发能力.孙辉等[7]提出混合均值中心反向学习粒子群优化算法，对所有粒子和部分最优粒子构造均值中心并进行贪心选择，然后采用反向搜索，平衡算法的勘探与开发能力.易云飞等[8]提出一种基于粒子优势分析的异步混合粒子群优化算法，根据最优粒子和其祖先粒子进行优势分析，进而确定不同粒子的速度更新等级，然后分解速度分配到不同维度以达到异步的目的，以此加快算法的收敛速度.

综上，学者们在PSO算法的改进上做了很多尝试也取得了很多优异成果，但是改进的PSO算法在算法易陷入局部极值和收敛精度不够等方面任然存在一些问题，因此在提升算法的收敛性和易陷入局部极值等方向还有待学者们进一步研究，故本文提出一种结合引力测度和质心变异策略的混合粒子群优化算法(A hybrid particle swarm optimization algorithm combining gravity measure and centroid mutation strategy，GMCMPSO)，首先在初始化阶段对种群采用精英分组策略将总群分为精英子群和普通子群，使得总群的优秀信息便于提取；然后计算两个子群之间的引力测度值，以便于挑选两个子群粒子之间最好的信息搭配方式；最后两个子群根据引力测度值对普通粒子进行随机变异、质心变异和重置操作，以提升种群对优质区域的开发和精细的探索能力.

2 结合引力测度和质心变异策略的混合粒子群优化算法

2.1 经典PSO算法

在经典的PSO算法中，每个粒子有位置Xi和速度Vi两部分属性组成，粒子根据经典更新公式(1)更新速度，根据经典更新公式(2)更行速度，并保存粒子的个体历史最优位置Pbest和全局历史最优位置Gbest，具体更新公式如下：

Vi+1，d=wVi，d+c1r1(pbi，d-Xi，d)+c2r2(gbi，d-Xi，d)

(1)

Xi+1，d=Xi+1，d+Vi+1，d

(2)

公式(1)中Vi+1，d表示第i+1个粒子的第d维；w是惯性权重，是第i个粒子对当前速度的影响程度；c1、c2是学习因子，用于调节对个体经验和总群经验的学习率；r1、r2是(0，1)内的独立随机数；pbi，d、gbi，d、Xi，d分别表示第i个粒子个体历史最优值的第d维、全局最优最优值的第d维、第i个粒子位置的第d维.

w根据迭代次数做线性变化，更新公式如下：

(3)

其中t表示当前迭代次数，tmax表示最大迭代次数.

2.2 精英分组策略

精英一词指代在群体中优秀的个体，在进化算法中代表适应度值高的个体，精英对种群的进化起着推动性作用[9].慕彩红等[10]提出的M-精英协同进化算法(MECA)里利用M个精英来提高算法优化性能，为了更好的利用精英个体携带的信息，本文采用精英分组策略来划分子群.

记种群P={x1，x2，…，xn}，种群大小为n，在每一代种群进行初始化时，按个体适应度大小，将种群划分为两个子群，即适应度大的精英子群和适应度小的普通子群.其中精英子群记为PE={x1，x2，…，xm}，普通子群记为PC={xm+1，xm+2，…，xn}，F(xi)>F(xj)，1≤i≤j≤n.如图1为精英分组策略示意图，左侧为精英粒子按适应度值从大到小排列，右侧为普通粒子.

图1 精英分组策略示意图Fig.1 Elite grouping strategy diagram

2.3 引力测度策略

引力测度策略的思想源于1687年，Issac Newton(牛顿)提出的万有引力定律(Law of universal gravitation).万有引力定律指出：任意两个质点有通过连心线方向上的力相互吸引.该引力大小与它们质量的乘积成正比与它们距离的平方成反比，与两物体的化学组成和其间介质种类无关.万有引力F的计算公式如下：

(4)

其中，G为引力常数，G≈6.67×10-11N·m2/kg2，m1和m2分别表示两个物体的质量，r表示两个物体间的距离.两个物体之间的万有引力值与两物体质量的积成正比，与两个物体之间的距离成反比.当引力值较大时，算法希望是因为两个物体的质量引起的，而不是两个物体间的距离，因为距离过小可能导致算法陷入局部极值.楼洋等[11]做的基于种群排序和引力分组模型的进化算法研究中，提出了“引力测度(Gravitational Measurement，GM)”这一概念，指出引力测度用来计算两个不同种群中粒子间的测度值，用引力测度来描述个体间的相互关系，从而达到合理挑选粒子的目的.

图2 引力测度策略示意图Fig.2 Schematic diagram of gravity measure strategy

图2中，精英个体1与所有普通个体计算一次引力测度值，同样地，其余精英个体也分别于每个普通个体计算引力测度值GMi，j，1≤i≤m，m≤m+j≤n，n为个体总数.GMi，j计算公式如下：

(5)

其中，Fitness(x)为粒子适应度值，xi∈PE，xj∈PC，ri，j为两个种群粒子间的欧式距离，k为常数，保证分母不为零，k取较大值时可以忽略掉ri，j对引力测度值的影响，从而排除距离很小时导致引力测度值很大的情况.k理论上最佳值为：

(6)

一般地，种群中粒子的搜索域是一样的，所以k0代表的是两个粒子间距离最远的情况.经验可知，当k≥1时，ri，j对结果的影响已经可以忽略，且算法不易陷入局部极值.金林鹏等[12]提出的用于函数优化的最大引力优化算法中，作者取k=10-10，在低维优化问题中实验结果较好.

2.4 随机变异和质心变异策略

2.4.1 随机变异策略

随机的目的是让事物的变化变成不可人为控制，在本算法中随机变异是为了使得当前粒子能有效跳出当前区域，并且随机性的掉落在整个搜索域的任何地方.当前普通粒子与精英粒子的引力测度值最小的时候，算法判断该粒子所处区域远离高质量区域，则采用随机变异的方式改变当前粒子的位置.如图3为粒子随机变异示意图.

图3 粒子随机变异示意图Fig.3 Schematic diagram of random variation of particles

图3中，当前循环中普通粒子PCj与精英粒子PEi的引力测度值最小，事件1、事件2和事件n等概率发生其中一个.随机变异公式如下：

(7)

其中，r为(0，1)之间的独立随机数，VRmax、VRmin分别为粒子搜索范围的上下边界值.

2.4.2 质心变异策略

在粒子的搜索过程中，最重要的问题是如何探索出更加优质的区域.在优质区域的开发中，最重要的问题是如何精准高效的定位到区域中的最优位置.质心变异策略是一种位置变异策略，利用精英粒子携带的优秀信息吸引与之最合适的普通粒子向优质区域移动，此过程也收到其他精英粒子的影响.变异方式分为两种，具体如下：

方式1(替换)：随机选择2个精英粒子和当前精英粒子，用3个精英粒子和当前种群最优粒子的优秀信息重组一个新的优秀粒子.

图4 质心变异策略示意图(替换)Fig.4 Schematic diagram of centroid variation strategy(replace)

如图4所示，用精英粒子PEa、PEb、PEc和gbest全局最优粒子的优秀信息共同构成新粒子PC.变异公式如下：

(8)

PC=r×Ct+gbest

(9)

注：式中所有粒子都处在同一维度，r为(0，1)之间的独立随机数.

方式2(牵引)：选择与当前普通粒子引力测度最大和次大的两个粒子，在两个精英粒子、当前普通粒子和精英种群质心的共同牵引下移动当前普通粒子.

图5 质心变异策略示意图(牵引)Fig.5 Schematic diagram of centroid variation strategy(pull)

如图5所示，在精英粒子PEa、PEb和精英子群质心EC的吸引下，普通粒子PCd向PC位置移动.变异公式如下：

(10)

PC=r×Ct+mean(PE)

(11)

注：式中所有粒子都处在同一维度，r为(0，1)之间的独立随机数.

2.5 GMCMPSO算法步骤

2.5.1 算法伪代码

输入：最大迭代次数M，粒子个数n，维度D，学习因子c1、c2，惯性权重变化区间[Wmin，Wmax]

输出：最优解

具体步骤如下：

声明变量：j—选择精英的次数

Npe—精英总数

r—(0，1)之间的独立随机数

Step1.随机初始化粒子速度V和粒子位置X；

Step2.计算个体最优Pbest及其适应度值；

Step3.计算当代全局最优解，迭代次数I=1；

Step4.进入迭代(while I

Step5.按式(3)更新权重W，按式(1)更新速度V；

Step6.if(V超限)->对速度V做超限处理；

Step7.按式(2)更新粒子位置X;

Step8.对新一代粒子按其适应度升序排列;

Step9.将排序好的种群分为两个子群(精英子群，普通子群)；

Step10.按式(5)计算两个子群的引力测度；

Step11.进入循环(1：精英总数Npe)

按式(9)对，每个精英个体选择与其引力测度最小的普通个体进行质心变异；

Else(r>1-W(I)+0.4)按式(7)对，每个精英个体选择与其引力测度最小的普通个体进行随机变异；

Step12.对最后一个普通粒子进行随机重置；

Step13.按式(11)对剩余未变异普通粒子选择与其引力测度最大和次大的精英个体进行质心变异；

Step14.if(X超限)->对位置X做超限处理；

Step15.计算所有粒子的适应度，并选出当前最优解；

Step16.if(I

Step17.输出最优解.

2.5.2 算法时间复杂度分析

GMCMPSO算法的时间复杂度主要包含以下部分：

a：初始化粒子时间复杂度为O(ND)

b：更新粒子的速度和位置时间复杂度为O(ND)

c：对粒子进行精英分组时间复杂度为O(N)

d：计算粒子之间的引力测度时间复杂度为O(NN)

e：普通粒子的变异时间复杂度为O(N)

综上，GMCMPSO算法的时间复杂度为O(ND).

3 实验分析

3.1 测试函数

为了检验GMCMPSO算法对比另外4个算法的性能，本文在16个标准测试函数上对5个算法进行同等条件下的仿真实验.各个测试函数的名称、搜索域、最优值和属性见表1.

表1 测试函数Table 1 Test functions

3.2 实验设置

为保证实验结果的公平性和准确性，本文所有实验按照统一的软硬件设施和参数设置，各个算法在统一条件下独立运行30次，取结果的平均值和方差做为实验结果的主要依据.软硬件环境和参数设置如下：

软硬件环境：Linux操作系统；MATLAB.R2018运行环境；CPU：i9 9900X；RAM：16GB DDR4；SSD：M.2 512G

参数设置：主要参数设置见表2.

表2 实验主要参数设置Table 2 Main parameter settings of the experiment

3.3 对比实验及结果分析

3.3.1 对比算法

将本文提出的结合引力测度和质心变异策略的混合粒子群优化算法(A hybrid particle swarm optimization algorithm combining gravity measure and centroid mutation strategy，GMCMPSO)与粒子群优化算法[1，2](Particle swarm optimization，PSO)、萤火虫和粒子群的混合优化算法[13](A Hybrid Firefly and Particle Swarm Optimization Algorithm，HFPSO)、基于分层自主学习的改进粒子群优化算法[14](Improved particle swarm optimization algorithm based on hierarchical autonomous learning，HCPSO)、适应度依赖优化算法[15](Fitness Dependent Optimizer:Inspired by the Bee Swarming Reproductive Process，FDO)共4个不同策略的代表性优化算法在16个标准测试函数上进行了实验对比.

3.3.2 算法结果分析

表3中罗列出了5个算法在16个标准测试函数上独立

表3 5个算法的测试结果(D=30)Table 3 Test results of 5 algorithms(D=30)

运行30次后所出结果的平均值和标准差.从表中可以看出GMCMPSO算法在多峰函数F1、F2、F5、F12、F14上收敛精度和收敛的稳定性皆优于其他4个算法.GMCMPSO算法在多峰函数F7上收敛精度和稳定性略劣于HFPSO，优于其他3个算法.GMCMPSO算法在多峰函数F9上收敛精度与HCPSO等级别，但稳定性高于HCPSO，且两个性能均优于其他3个算法.GMCMPSO算法在多峰函数F10上收敛精度与PSO、HCPSO等级别，稳定性略低于HCPSO高于其他3个算法.GMCMPSO算法在单峰函数F3、F4上收敛精度和稳定性劣于FDO而优于其他3个算法.GMCMPSO算法在单峰函数F6上收敛精度优于PSO而与其他3个算法等级别，稳定优于PSO和HCPSO与其他两个算法等级别.GMCMPSO算法在单峰函数F8、F13、F16上收敛精度和稳定性略低于FDO而优于其他3个算法.GMCMPSO算法在单峰函数F11上收敛精度和稳定性皆优于其他4个算法.GMCMPSO算法在单峰函数F15上收敛精度略低于HFPSO而优于其他3个算法，稳定性与HFPSO等级别而优于其他3个算法.且在多峰函数F9和单峰函数F15上，GMCMPSO算法的稳定性非常好.

表4为GMCMPSO算法对其他4个算法的T检验值和检验结果.“+”、“-”、“=”分别表示GMCMPSO算法对比相应算法明显优于、明显劣于、差异不明显3种情况，分别用B、W、S表示.GMCMPSO算法对比PSO算法、HFPSO算法、HCPSO算法和FDO算法的B-W得分情况为13、8、4、8，都呈现出优势且没有出现明显劣于4个对比算法的函数，所以T检验结果表明GMCMPSO算法具有更好的综合优化能力.

表4 GMCMPSO算法对其他4种算法的T检验结果Table 4 T-test results of GMCMPSO algorithm on the other four algorithms

综上可知，GMCMPSO算法总体上在收敛精度和稳定性方面优于其他4个对比算法.

3.3.3 算法收敛性分析

图6、图7分别是5个算法在函数F1-F16上0-1000代的收敛曲线图.图中纵坐标做了对数变换，可以更直观的进行效果对比.由图可知，除函数F7之外，GMCMPSO算法在其他15个函数上前期的收敛速度都是优于其他4个对比算法的，随着变异粒子数的增加，GMCMPSO算法在中期更侧重于搜索区域开发，因此放慢了收敛速度，但是在算法后期粒子找到最优区域以后，算法较强的寻优能力使得算法快速收敛.在函数F3、F4、F8、F13和F16上，算法FDO最后的收敛精度略高于GMCMPSO算法，但是在算法前期和后期FDO算法的收敛速度都不如GMCMPSO算法，因此两个算法在函数F3、F4、F8、F13和F16上的综合性能呈持平状体，但是其他函数上GMCMPSO的收敛速度和收敛精度皆优于FDO算法.在函数F15上，GMCMPSO算法和HFPSO算法表现很优异，都在前期就能快速收敛到最优区域.在函数F10和F15上，GMCMPSO算法的表现相当优异.GMCMPSO算法在前期进行的精英分组和引力测度策略使得算法对粒子优秀信息的运用更加充分，加快了前期的收敛速度；而中期的变异策略使得粒子能更大范围的对搜索域进行开发，增加了算法的收敛精度；后期引力测度策略再次发挥重要作用使得粒子能快速在优质区域中找到函数的最优点.

图6 单峰函数收敛曲线图Fig.6 Convergence curve of unimodal function

图7 多峰函数收敛曲线图Fig.7 Convergence curve of multi-peak function

4 结 语

本文提出的结合引力测度和质心变异策略的混合粒子群优化算法主要是为了解决粒子群优化算法容易陷入局部极值和早熟的问题.算法结合了精英分组策略、引力测度策略、随机变异策略和质心变异策略.精英分组策略负责对种群的优秀信息进行整理，提升算法搜索效率；引力测度策略负责进行粒子间信息的匹配，挑选最适合的变异粒子组合，提升算法搜索效率；随机变异策略负责使陷入局部极值和在局部极值周围的粒子顺利跳出局部极值区域，提升算法的搜索能力；质心变异策略负责根据精英粒子携带的优秀信息来引导其他粒子向更加优质的区域靠近，提升算法的收敛精度.通过一系列实验的结果对比，本文提出的GMCMPSO算法在收敛精度、收敛速度、稳定性和鲁棒性上相较于其他几个对比算法都有明显的提升.

未来还计划在种群分组和粒子变异策略上再进一步研究，尝试不同的策略对算法性能的影响.