混合粒子群和差分进化的定位算法*

吴 斌，金洁丽

（1.浙江邮电职业技术学院，浙江 绍兴 312016；2.吉首大学信息科学与工程学院，湖南 吉首 416000）

0 引 言

智能优化算法模拟地球上生物的行为，是一类具有自我学习、自我组织的方法，适合大规模问题求解，众多学者将该类算法应用于求解定位问题[1]。

林凤德等人[2]针对经典DV-Hop 方法定位精度低且计算复杂度高等难题提出一种利用遗传与蚁群混合优化算法的DV-Hop 定位方法。该方法中除利用遗传方法搜找最优解外，还利用蚁群进一步搜找，增强了定位精度和迭代速度，测试表明该算法增加了计算效率，迭代速率和定位适应度值。面对Amprphous 算法存在较低的定位精度的缺点，胡伟等人[3]利用遗传-禁忌搜索算法求解该问题。首先修正最小跳数的估计值然后经过遗传算法优化，优化后的解在经过禁忌搜索策略进一步增强了算法的精度。靳春景等人[4]通过大量的实验仿真发现单一算法定位精度容易受环境等因素的影响较大，提出一种利用DVC-Hop 的算法，它修正了平均跳距，并引入PSO 优化方法加快寻优速度，因为PSO 方法较易陷入局部解空间却无法跳出等缺点，因此提出随机扰动策略解决PSO的早熟难题。姚汝贤等人[5]提出一种利用改进量子PSO 的RSSI 测距方法，为了加快PSO 优化算法的收敛速率，在算法中引入学习自动机，粒子在获得自学习能力以后可以自适应的选择相应的动作。实验论证显示该方法具有较高的定位质量，并且速度快。

上述算法虽然有效的求解节点定位问题，但是在实时性和定位精度上仍有待改善，因此本文提出融合粒子群和差分进化算法的HPSO-DE 算法，并和文献[6]的PSO、文献[7]的DFOA 等方法进行比较，证明本文算法在适应度函数值和收敛速度方面的优势。

1 节点定位问题建模及目标函数

设 锚P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)和 未 知 节 点P(x,y)的实际真实长度分别是r1,r2,…,rn，测距误差分别是ε1,ε2,…,εn，则满足|ri-di|<εi，其中i=1,2,…,n，那么未知节点P(x,y)约束条件：

解(x,y)，使得：

由此节点定位问题转换成求如式2 中测距误差最小值的优化问题，本文将改进智能优化算法应用于节点位置估计的优化问题，以降低误差对定位性能的干扰，提高定位的精度。

2 粒子群算法及差分进化算法

2.1 粒子群算法（PSO）

PSO 算法的核心思想是粒子的在解空间里面随意飞行，然后在每次迭代过程中通过和其他粒子进行信息交互，然后根据个人经验和其他粒子的影响决定下一次飞行的位置。受到其他优秀的个体的影响，粒子从最初无序的状态朝着熵减状态转变，直至最终搜索到食物位置。

假设一个种群规模为N 的粒子群在解空间里面搜索最优解，搜索维度为D。粒子i 在t 时刻的状态属性设置如下：

则在t+1 代更新过程里，个体的速度和位置更新公式分别为：

式中，u1,u2为介于（0,1）内随机服从uniform分布的数；c1,c2分别表示个体认知因子和社会认知因子（二者统称加速度因子），一般取c1=c2=2.0。

2.2 差分进化算法(DE)

（1）种群初始化

DE 算法的种群由NP 个D 维向量个体组成。记xi为一个D 维向量，则一个种群可以表示为Pop={x1.x2,…,xNP}。其中，NP 是种群的规模大小，该值在每次迭代过程中保持不变。种群的初始化应在符合边界约束的条件下尽可能均匀覆盖全部区域，假设个体第j 维的上下边界分别为和那么个体按下面的方式进行初始化：

式 中，i=1,2,…,NP；j=1,2,…,D。randj（0,1）是一个在（0,1）上服从uniform 分布的随机数。

（2）变异操作

种群经过初始化赋值后，利用差分变异操作产生变异矢量。常见的差分变异操作有DE/rnad/1、DE/best/1、DE/rand-to-best/1、DE/best/2、DE/rand/2、DE/current-to-best/1、DE/current-to-rand/1等。其中，经典的“DE/rand/1”变异策略如式（6）所示：

式中，r1,r2,r3 ∈[1,2,….NP]为两两不相同的整数，缩放因子F 是（0，1）区间内的常数，用于控制差分向量的大小。

（3）交叉操作

在进行变异操作之后，需要将目标向量xi,g与变异向量vi,g进行二项式交叉生成最终的试验向量ui,g=[ui1,g,ui2,g,uiD,g]，按照公式（7）执行交叉操作。

式中，jrand是从集合{1,2,…,D}内随机选择的一个整数，以保证变异向量vi,g至少有一维信息被保留下来。交叉概率CR 是区间（0,1）内的一个常数。

（4）选择操作

试验向量与对应的目标向量之间执行一对一的锦标赛选择。对试验向量ui,g与vi,g目标向量的目标函数值进行比较，如果试验向量具有更优的目标函数，则将目标向量替换成试验向量；否则，该目标向量保持不变。以目标函数最小化为例，选择操作可用公式（8）来表示：

式中，f(·)为优化问题的目标函数。

3 节点定位的HPSO-DE 算法

粒子群算法较易出现局部最小[8]，主要因为该算法优化过程中，种群的差异性丧失，趋向于同一性，但是粒子群收敛速度快，差分进化算法虽然全局探索能力强，但是其在进化的前提和中期一般都探索解空间，而未对较优解的局部空间进行细致的开发，导致寻优速度慢，因此本文提出混合粒子群和差分进化算法HPSO-DE 以平衡算法的局部寻优和全局探索的能力，其中自适应惯性权重更新策略和混合进化策略使得该算法不仅寻优能力强而且寻优速度快。

3.1 自适应惯性权重更新策略

粒子群算法中的w 衡量了前一时刻的速度对当前速度的影响[9]，用于平衡算法的局部搜索能力和全局搜索能力。传统的粒子群算法将w 设置为固定值，导致该算法无法在不同的优化阶段下相应的做出调整导致陷入局部最优。本文在计算w 时考虑到每次迭代过程中种群的分布情况，首先定义第i 个粒子距离其他N-1 个粒子的平均距离di为：

其中，N 和D 分别表示种群规模大小和编码维度。然后定义进化因子δ 如式（10）所示：

其中，dg表示为全局最优个体的平均距离，dmax、dmin分别表示种群中最大和最小的平均距离。最终w 的更新公式如式（11）所示：

其中w 随着δ 的增加而增加，变化范围是[0.4 0.9]，在早期的迭代过程中，δ 较大，此时w 也较大，有利于粒子快速找到最优解的大致位置区域，在迭代后期，w 较小，此时检测到种群趋于同一开始收敛，减小w 有利于进行精准的局部搜索。

3.2 混合优化策略

如前文所述，粒子群算法容易陷入局部最优，全局搜索能力差，但是差分进化算法的搜索能力却很强，因此可以将经过PSO 进化的种群再经过DE算法进化，同时为了减少算法的复杂度，我们设定了阈值，将种群划分为优等群和劣等群，只将劣等群中的个体经过差分进化，然后将进化后的种群和优秀群合并继续进行下一次迭代。即，首先设定阈值favg，计算公式如式（12）所示：

然后将每个粒子的适应度值与之比较，若小于该值，表示该个体较优秀，即归入优等群，反之，如果该粒子的适应度值大于该值意味着该个体当前解较差，因此要归入到劣等群中通过DE 算法进一步优化。

在经过DE 进化后，利用贪婪选择机制，确定当前种群中的最优解。

综上所述可得HPSO-DE 算法的步骤如下：

（1）初始化粒子群中的粒子的速度和位置，设置迭代次数I=1.

（2）利用式2 计算每个粒子的适应度值。

（3）利用式12 计算种群的阈值favg，将种群划分为优等群Su 和劣等群In。

（4）将In 中的个体依次利用式6、7 和8 进行变异和交叉和选择操作，进一步提高劣等群中个体的适应度值。

（5）将优等群和劣等群合并，并更新全局最优值和个体最优值

（6）若I 等于最大迭代次数则进行步骤7，否则转步骤2

（7）输出最优个体的位置作为对未知节点的位置估计。

4 仿真实验与分析

4.1 参数设置

在PSO 算法中，设置学习因子c1=c2=1.4945，在DFOA[7]算法中,设置搜索步长radiusX 为0.1，本文HPSO-DE 算法中，设置常数交叉概率cr=0.6。三种算法中设置种群规模大小为30，最大迭代次数设置为80。

4.2 实验仿真分析

本文参考文献[10]以平均定位误差（average location error，AVE）为评价标准。其公式如式（13）所示：

式中：M 为已知节点的总个数，(x,y)为预测位置，(xi,yi)为实际位置。

首先设置网络节点的通信半径为10 m，随机将30 个传感器置于30 m×30 m 的区域中，随机挑选10 个节点为锚节点，设置算法的最大迭代次数为200 次，每一个未知节点的坐标估计值都是20 次独立实验的平均。将HPSO-DE 算法与参考文献[7]中的DFOA 算法进行节点定位结果的对比，见表1。

表1 给出了在HPSO 算法和DFOA 算法下，挑选的10 个无法测量自身坐标的节点的预测值比较，由表可以看出（1）首先两种算法都可以应用于WSN 网络的定位场景中，同时，由10 个未知点的预测误差来看，HPSO-DE 的AVE 比DFOA 要低很多，证明了本文所提算法的优势。

PSO、DFOA 和HPSO-DE 等算法在已知自身精确位置信息的节点个数为10 个时的AVE 随测距误差关系图如图1 所示。图中的每条曲线均进行了20 次独立重复实验而得到。由图1 可知：（1）由图中的三条曲线的走向可以看出总体定位精度是HPSO-DE>DFOA>PSO（2）本文提出的HPSO-DE随着迭代次数自适应的变化惯性权重的值和混合进化策略使得该算法不仅定位能力强而且寻优速度快，在测距误差为30%时，HPSO-DE 的定位误差分别比DFOA 和PSO 降低2 m 和1 m。（3）由表可以看出当测距误差由25%增加到30%时，PSO算法和DFOA 算法的曲线的斜率显著增大，说明该两种算法的鲁棒性能差，但是所提HPSO-DE 算法却增加的很平缓，说明在较大测距误差情况下，HPSO-DE 也可以有较高的定位精度。

图1 平均定位误差与测距误差关系

如图2 给出了PSO、DFOA 和HPSO-DE 在测距误差为10%时的AVE 和已知自身精确位置信息的节点个数变化关系。由图可以看出，（1）由图中的三条曲线表示的平均定位误差与锚节点个数的关系图走向可以看出总体定位精度是HPSODE>DFOA>PSO，（2）虽然PSO 算法的误差在信标节点的数目增加的时候而下降，但是AVE 仍然高于DFOA 算法和HPSO-DE 算法，说明该算法很敏感，和对成本要求较高。（3）本文在仿真场景中设置相同数量的已知个体坐标精确位置的节点的情况下，HPSO-DE 具有最小的误差性能，例如当锚节点个数为4 个时，HPSO-DE、DFOA 和PSO 算法的定位误差分别是1.5 m、2.2 m 和3.35 m。

图2 平均定位误差与锚节点个数关系

PSO、DFOA 和HPSO-DE 在定位误差为10%，信标节点个数为10 个时，AVE 与种群规模的关系如图3 所示。由图可知，（1）随着种群规模的增大，有更多的个体在搜索空间里寻找更优解，因此三种算法的定位误差都在逐渐减小。（2）HPSO-DE、DFOA 和PSO 算法在达到最小的定位误差时需要的种群个体数量分别是20、20 和47。说明HPSODE 和DFOA 的寻优能力强，同时算法复杂度低，特别是HPSO-DE 算法，在个体数量为10 时平均定位误差就很小，而PSO 达到同等的平均定位误差，需要的种群个体数量为37。这是因为本文提出的HPSO-DE 算法的自适应惯性权重更新策略和混合进化策略使得该算法同时拥有PSO 的开采性能高和DE 的勘探能力强的特点，在保持较快收敛速度的同时具有更高的优化性能。

图3 平均定位误差与种群规模大小关系

4.3 实测分析

上述理论仿真表明所提算法具有良好的定位性能，为了实测算法定位效果，搭建了如图4 所示的实验平台，在一块6 m×6 m 的正方形操场上，按图5 设置8 个锚节点（T1～T8），然后测量未知节点（1～9）的位置信息。

图4 定位实验点实测

将实测数据与参考文献[11]中的改进PSO 算法测得的数据进行比较，得到结果对比如图6 所示。由图可以看出，本文所提HPSO-DE 算法约比改进PSO 算法的平均定位误差低0.1 m。

图5 定位实验点布置

图6 锚节点为8 时平均误差对比图

5 结 语

如何确定传感器节点的精确位置是WSN 网络技术需要解决的重要难题之一。针对由测量误差造成的精度不高的问题，本文首先改进PSO 的固定权重为自适应变化方式，增强了PSO 优化的整体勘探能力，然后改进差分进化算法的变异策略，增强DE 算法的局部寻优能力，然后将经过粒子群优化后的较差个体继续通过差分进化算法优化，得到混合粒子群与差分进化的HPSO-DE 算法，将该算法应用于本文建模的WSN 定位场景中，仿真实验和实测实验结果表明，HPSO-DE 算法不仅提高了定位精度而且减少了定位需要消耗的时间。