基于多目标局部变异- 自适应量子粒子群优化算法的复杂地形多传感器优化部署

徐公国， 段修生,2， 单甘霖， 童俊

(1.陆军工程大学石家庄校区， 河北 石家庄 050003； 2.石家庄铁道大学 机械工程学院， 河北 石家庄 050043)

0 引言

为了发挥有限传感器的最大侦察效能，传感器资源管理的作用日益突出。通过将多部传感器合理布设在不同位置，结合信息融合技术，综合利用来自多部传感器的信息，可以获得比运用单部、孤立的传感器更加详细且精确的目标信息。因此，为扩大传感器的侦察范围、探测概率等，寻求合适的传感器部署方案以及相应的数据融合估计算法显得至关重要。

多传感器的优化部署属于军事运筹学中的经典NP-hard完全问题，其实质是一个非线性、多约束、多目标的最优化问题，复杂度高且求解难度大[1-3]。主要求解方法有专家系统、数学规划和启发式搜索等。由于启发式搜索方法在传感器规模较大情况下仍能保持较快的求解速度和精确度，成为近年来的研究热点。传感器优化部署考虑的目标因素多种多样，而国内外的研究还主要集中在单目标优化、权重相加和约束化处理上。例如：文献[4]以最大化区域覆盖率为目标，研究了无线传感器的联合覆盖问题；文献[5]以目标定位精度为单一目标，研究了雷达组网的空间分布模型。

但是，将多目标问题转化为单目标问题进行求解，一次优化过程往往只能得到1个最优解，并且权重系数的选择需要充分的先验知识，选择不当反而达不到预期效果。基于Pareto最优解集的多目标优化方法，不需要将多目标问题转化为单目标问题，可以同时获取多个优化解。决策者可以根据实际任务需求选择决策方案，相对于传统方法更具实用性，因此得到了广泛应用[6-11]。Sun等[6]利用多目标优化理论对网络防御问题进行了研究，基于Pareto和多目标强化学习策略来确定最优解集。梁兴等[8]基于Pareto最优解理论对梯级泵站的多目标优化调度问题进行求解，提出了一种多目标混合粒子群优化(MO-HPSO)算法，但该算法的优化性能还不够理想。彭星光等[10]利用混合多目标进化算法对无人机侦察路径规划问题进行了研究，对任务完成时间、编队耗时和编队规模等多目标优化问题进行求解，有效解决了多目标优化问题，但该方法优化时间过长，实时性较差。

本文针对上述问题，基于多目标局部变异-自适应量子粒子群优化(LM-AQPSO)算法对复杂地形环境下的多传感器协同优化部署问题进行研究。首先利用网格技术对复杂地形进行数学建模，给出传感器探测模型和优化目标。然后基于量子粒子群优化(QPSO)算法提出了多目标LM-AQPSO算法——MO-LM-AQPSO算法，并构建了多传感器多目标优化部署模型。最后通过仿真实验表明所提优化算法和部署模型的先进性、有效性。

1 问题描述

本文主要面向复杂地形环境，对地面战场侦察任务下的传感器部署问题进行研究，旨在获取多目标任务需求下的传感器部署解决方案。

1.1 地形模型

实际作战环境中，侦察区域内不仅有陆地，也可能有水系、山脉等地形因素，而在水系、山脉等地形上往往不易部署侦察传感器资源。现阶段的传感器部署研究中，大多忽略了地形因素的影响。

假设感兴趣的侦察区域(ROI)如图1所示，其中包括水系、山脉等地形要素。ROI可描述为O=[0，H]×[0，W]，其中H、W分别为ROI的长和宽(图1中设为50 km×50 km)。

此外，为减少运算复杂度，对ROI进行网格划分，划分后的最小单位称为网格单元(Cell)，Cell一般为正方形，其边长依据作战需求设定。Cell的中心点视为侦察目标点，对所有的Cell中心点进行覆盖侦察即视为对ROI进行了覆盖侦察。定义Cell=〈[x，y]，r，a〉为1个三元组数据，其中[x，y]为Cell中心点坐标；r为Cell边长(图1中为5 km)；a表示Cell的地形属性，a=0表示该处为陆地，a=1表示该处为水系，a=2表示该处为山脉、建筑等障碍物。根据Cell的地形属性可以将侦察区域分为如下3类：1)可达区(AR)，如图1中灰色部分，表示该地区可以部署传感器，同时需要侦察覆盖；2)不可达区(UR)，如图1中蓝色部分，表示该地区不可以部署传感器，但需要侦察覆盖；3)障碍区(OR)，如图1中黑色部分，表示该地区不可以部署传感器，同时不需要侦察覆盖。

1.2 传感器探测模型

本文中传感器均为全向探测传感器，为全面刻画传感器的探测特性，给出传感器的截断概率探测模型如(1)式所示：

(1)

式中：P(S,Cell)表示传感器S对Cell的探测概率；d(S,Cell)表示传感器S和Cell之间的欧氏距离；R为传感器的预设定探测半径；Ru为传感器探测时的不确定度，且有Ru

1.3 目标函数

针对不同的战场任务，会有不同的传感器部署目标，不同目标之间还可能存在相互矛盾的情况。当同时考虑多个目标时，传感器部署问题就转化为多目标优化(MOP)问题。

1)传感器使用数目：由于传感器资源和能量有限，在传感器使用过程中应尽量减少传感器的使用数量。

2)整体ROI覆盖率：描述传感器网络对整个ROI的覆盖情况。假设CiS表示第iS个传感器SiS的覆盖范围，1≤iS≤mS，mS为传感器个数；CO表示整个ROI的区域面积，则整体ROI的覆盖率为

(2)

3)重点区域重复覆盖度：对于重点区域，单个传感器覆盖可能无法达到侦察要求，需要多部传感器同时侦察。假设Ck表示重点侦察区域的面积，则重点区域的重复覆盖度为

(3)

4)探测概率：当对具体的目标进行探测时，仅仅覆盖可能无法满足任务要求，还需要达到一定的探测概率。

1.4 优化求解

为求解上述MOP问题，本文不再采用传统的权系数相加或目标约束化等单目标处理方法，而是基于Pareto最优解集求出一组可行解，以期为决策者提供更多的决策选择。以最小化目标为例，MOP问题可形式化表示为

minF(X)={f1(X)，…，fj(X)，…，fmf(X)}，

(4)

式中：F(X)为目标组合向量，X=(x1，x2，…，xn)为MOP问题的解，n为解变量的个数；fj(X)为单个具体的目标函数，1≤j≤mf，mf为目标函数的个数。Pareto优化理论的相关定义[12]如下：

定义1Pareto支配：假设X1和X2为决策空间的两个可行解，若X1和X2满足(5)式中的条件，则称X1可支配X2.

(5)

定义2Pareto非支配解：假设X是决策空间Ω内的1个可行解，且在Ω内没有解可支配解X，则称X为非支配解。

定义3Pareto最优解集：所有的非支配解组成的集合为最优解集。

2 多目标优化求解算法

在求解Pareto最优解集时，Pareto最优解应尽可能靠近理论Pareto前沿，同时还要保持解的多样性。改进的非支配排序遗传算法(NSGA-II)[13]为经典的求解算法，该算法基于遗传算法进行设计，具有良好的优化性能，但该算法的复杂度较高，收敛时间比较慢。为解决上述问题，下面基于改进的LM-AQPSO算法和Pareto优化理论，给出MO-LM-AQPSO算法。

2.1 改进QPSO算法

QPSO算法是Sun等[14]将量子理论和粒子群优化(PSO)算法相结合提出的新型群体智能优化算法。相对于传统的PSO算法，QPSO算法不再关注粒子的移动速度，只考虑粒子位置。在QPSO算法中，用概率密度函数的形式表示粒子出现的位置，其搜索范围更加广泛，全局寻优能力更强。在离散情况下，粒子位置的更新方程[14]为

(6)

β(k)=1-0.5(iter/iterm)，

(7)

(8)

式中：iter为当前迭代次数；iterm为最大迭代次数；φ为[0,1]区间上均匀分布的随机数。与传统PSO算法一样，QPSO算法中的粒子也有强烈的趋同性，粒子多样性会逐渐降低，极易陷入局部最优陷阱。为避免该问题的出现、提高QPSO算法的全局寻优能力，引入局部变异和参数自适应策略对QPSO算法进行改进。

1)局部变异策略。如图2所示，局部变异的核心思想是在每次迭代搜索完成后，对粒子最优解进行小幅度的变异操作，并与原最优解进行比较，当新粒子的解优于原最优解时替换原最优解。实验结果表明，该策略能够在付出很小计算代价条件下获得较好的优化效果，有效提高了QPSO算法的全局寻优能力。

2)参数自适应策略。由(6)式可见，QPSO算法中只有1个β(k)可调参数，使得QSPO算法易于工程实现，但也使β(k)参数的选择更加重要。一般情况下β(k)随着迭代次数的增加逐步减小。为提高β(k)选择的合理性，引入自适应调整机制，依据粒子群的分布特性来动态调整β(k)取值。为判断粒子群的分布特性，本文设计了粒子进化度和粒子聚集度两个评价指标，相应的计算公式分别如(9)式和(10)式所示：

(9)

(10)

式中：pbad(k)为粒子群最差值；T为观测时刻(一般取当前时刻)，t为观测时间段。当L1和L2小于一定阈值时，粒子群视为进化缓慢且多样性较低，粒子群可能已陷入局部最优解。此时可相应地调节β(k)取较大值，使粒子群做扩张运动，从而跳出局部最优陷阱。

2.2 基于LM-AQPSO算法的多目标优化

单目标优化只注重解的收敛性，而多目标优化不仅关注解的收敛性，还关注解的多样性。其目的是求得一组互不支配的最优解集，此时全局最优解的存在不再合理。现阶段的研究[7-9]多将智能优化算法直接用于多目标优化，而未考虑多目标优化问题的特殊性，有较大的局限性。因此，为适应多目标优化问题，对LM-AQPSO算法进行调整，其中局部变异的对象调整为Pareto最优解，粒子位置更新方程调整为

(11)

步骤1初始化，设置粒子群pPop中粒子的数目m1，并随机初始化pPop；设置最优解集pPareto中解的个数m2，并随机初始化pPareto；设置最大迭代次数iterm.

步骤2根据定义2，从粒子群pPop中求取非支配解集pPareto，new.

步骤3如图3所示，将原最优解集pPareto与非支配解集pPareto，new合并，利用分层排序法求出新的pPareto. 具体操作为：首先求出pPareto∪pPareto，new中的所有非支配解，放入集合C1中。然后从pPareto∪pPareto，new中剔除C1中的解，并继续求取剩余解中的非支配解，放入集合C2中。依次类推，直到处理完pPareto∪pPareto，new中的所有元素。

步骤4利用拥挤距离[12]对C=C1∪C2∪C3∪…中的所有元素从大到小进行排序，拥挤距离等于其前后两个解在所有目标函数之上的距离和，边缘节点的拥挤距离设置为无穷大。如图3所示，排序完成后，选取前m2个解作为新的最优解集pPareto.

步骤5对pPareto最优解进行局部变异，并按照(11)式，利用新的pPareto最优解集更新pPop，获得新的粒子群pPop，new；与步骤3和步骤4相同，将pPop和pPop，new合并，并利用分层排序的方法求出新的粒子群pPop.

步骤6判断是否达到最大迭代次数，若达到最大迭代次数，则结束搜索，输出最后的最优解集

pPareto；否则，转步骤2继续进行迭代搜索。

2.3 仿真实验验证

为验证MO-LM-AQPSO算法的先进性，利用标准多目标优化测试函数ZDT1、ZDT2和ZDT3，对提出的MO-LM-AQPSO算法进行测试，并与NSGA-II算法、多目标量子粒子群优化(MO-QPSO)算法、MO-HPSO算法[7]进行对比。测试函数的参数选择如表1所示， ZDT1、ZDT2、ZDT3均为多变量双目标函数，其中ZDT1为凸Pareto前沿，ZDT2为非凸Pareto前沿，ZDT3具有5段不连续的凸Pareto前沿。此外，为客观、全面地评价算法的性能，选择收敛性GD、分布性SP、优化时间T共3个评价指标，其中GD和SP的计算方法如(12)式和(13)式所示：

(12)

(13)

表1 测试函数

实验用计算机CPU为i5-4590@3.3 Hz，内存为4 GB，运行环境为MATLAB2014a. 实验过程中，粒子群数目为200，Pareto最优解集的规模为50，最大迭代次数为200次。NSGA-II算法中交叉概率为0.8，变异概率为0.005. MO-HPSO算法中惯性因子c1、c2均为1.5. 实验结果分别如图4～图6和表2所示。

由图4、图5和图6可以看出，MO-LM-AQPSO算法相对于其他3种算法，求出的Pareto最优解无论收敛性还是分布性都有所改进。相对于经典NSGA-Ⅱ算法，MO-LM-AQPSO算法的收敛性改进幅度较小，但解的分布性比较优越。同时，相对于MO-QPSO算法有很大改善，证明了两种改进策略的有效性。MO-QPSO算法与MO-HPSO算法的优化结果基本相同，但MO-QPSO算法求出的Pareto最优解分布性更好，说明MO-QPSO算法的全局寻优能力要优于MO-HPSO算法。MO-HPSO算法全局寻优能力不强，求出的Pareto最优解容易聚集在某些解周围，分布性比较差。

表2 4种算法下不同测试函数的评价指标值

表2进一步验证了MO-LM-AQPSO算法的优越性，评价指标GD和SP均越小越好，与实验结果保持一致。此外，从表2可以看出，MO-LM-AQPSO算法相对于经典NSGA-II算法，虽然性能提高幅度不是很大，但是由于MO-LM-AQPSO算法的控制参数少、计算复杂度低，节省了大量寻优时间，可大大减少决策时间。

3 多传感器多目标优化部署模型

下面在第1节、第2节的基础上，构建基于MO-LM-AQPSO算法的多传感器多目标优化部署模型。该模型将传感器部署问题转化为非线性、多约束多目标优化问题，以1.3节提出的目标函数为例，多传感器多目标部署问题可表示为以下数学模型：

(14)

式中：f1(X)、f2(X)、f3(X)为3个具体的目标函数。为了将所有目标函数统一为最小化目标函数，f2(X)和f3(X)设置为ROI覆盖率和重点区域重复覆盖度的相反数；此外，解X具体形式为多传感器的部署位置和目标函数值组成的向量，部署位置应在可部署区域AR之内。如图7所示，对于粒子编码，其设计原则应尽可能满足所有的约束条件，且应尽量减少X的维数，以缩小搜索空间、提高优化速度。

图7中，(x2iS-1,x2iS)表示传感器SiS的部署坐标。

4 场景仿真

为验证所提传感器部署模型和求解算法的有效性，在1.1节建立的区域数学模型基础上，添加重点侦察区域(如图8中的红色区域)进行仿真实验。传感器均为全向探测，预设探测半径为5 km，探测不确定度为1 km. 实验环境与2.3节一致，利用MO-LM-AQPSO和NGSA-II两种算法进行求解，Pareto最优解集的数目调整为30.

4.1 场景1

为直观反映部署结果之间博弈性和求解算法的有效性，选择ROI覆盖率和重点区域重复覆盖度两个目标进行实验，对应的目标函数1代表ROI覆盖率的相反数，目标函数2代表重点区域重复覆盖度的相反数。为获得更好的侦察效能，二者都应尽可能大，对应的目标函数尽可能小。部署过程中传感器资源设置为8个。实验结果如图9、表3 和图10所示。

方案编号目标函数1目标函数2方案编号目标函数1目标函数21-0.3700-0.625016-0.2600-1.87502-0.3600-1.002517-0.2600-1.89253-0.3505-1.060018-0.2500-1.93754-0.3500-1.100019-0.2400-2.00005-0.3400-1.250020-0.2300-2.00006-0.3200-1.437521-0.2300-2.11507-0.3105-1.562522-0.2105-2.12508-0.3050-1.562523-0.2100-2.18759-0.2905-1.625024-0.2000-2.187510-0.2900-1.625025-0.1900-2.275011-0.2800-1.750026-0.1900-2.362512-0.2800-1.765027-0.1800-2.372513-0.2705-1.820028-0.1700-2.420014-0.2650-1.850029-0.1500-2.497515-0.2600-1.870030-0.1100-2.5625

由图9可见，MO-LM-AQPSO算法能够有效解决实际问题中的多目标优化问题，且有着比NSGA-II算法更好的优化性能，进一步验证了所提算法的有效性。

表3为由MO-LM-AQPSO算法优化得到的Pareto前沿面所有解的目标函数值，即对应了30种传感器部署方案。其中：整个ROI覆盖率最高可达到37%，最小为11%；重点区域重复覆盖度最高可达到2.562 5，基本实现了重点区域内的每个Cell有两部传感器覆盖侦察，最小为0.625 0.

图10是从Pareto前沿面中选出的3种典型传感器部署方案。其中：方案1侧重对整体ROI侦察区域的覆盖；方案3侧重对重点侦察区域的重复覆盖；方案2则位于中间，兼顾两个目标函数。此外，通过对粒子编码的约束化处理，3种部署方案中传感器的部署位置也均满足地形约束条件，即均部署在区域AR以内，且对区域OR不侦察，对区域UR侦察。由此可见，本文所提出的多传感器部署模型能够有效处理复杂地形环境下的传感器部署问题，并能通过优化Pareto最优解集的方式同时获取多个部署方案，为决策者提供更多的选择空间。

4.2 场景2

为进一步分析传感器数目对场景1中目标函数的影响情况，以便在传感器数目发生变化时进行快速决策，在本场景中，传感器数目分别设置为6个、8个、10个、12个进行实验，实验结果如图11和图12所示。

由图11可见，当传感器数目不同时，所提算法均能获得较好的Pareto最优解，且Pareto前沿面呈递进态势。由图12可见，当传感器总探测面积小于ROI区域面积时，ROI覆盖率和重点区域重复覆盖度的最大值大致呈线性增加。通过分析可知，每增加2个传感器，ROI覆盖率和重点区域重复覆盖度分别约增加0.073 3和0.562 5. 因此，当传感器数目变化时，可以提前预测所需的传感器数目。例如，要使总体ROI覆盖率达到90%，需要的传感器数目约为17个。此外，通过预测可加快决策速度，即寻优时在预测最优值附近初始化粒子群，可以减少算法的收敛时间、提高寻优效率。

5 结论

本文在QPSO算法的基础上引入Pareto最优解理论，考虑多目标部署需求，对复杂地形下的多传感器多目标协同优化部署问题进行了研究。得到的主要结论如下：

1)相对于传统NSGA-II算法，MO-LM-AQPSO算法优化求得的Pareto最优解具有更好的收敛性和分布性，且优化时间更短。

2)所提模型能够巧妙避免多目标之间难以平衡的矛盾问题，有效解决了多目标部署需求，可为决策者同时提供多个备选方案，有着较大的实际应用价值。

3)对决策预测进行了分析，为环境变化时的Pareto优化求解提供了理论支持，可有效加快决策速度。