基于改进人工蜂群算法的多传感器联盟

庞 策，黄树彩，韦道知，苑智玮，刘锦昌

(空军工程大学防空反导学院，陕西 西安 710051)



基于改进人工蜂群算法的多传感器联盟

庞 策，黄树彩，韦道知，苑智玮，刘锦昌

(空军工程大学防空反导学院，陕西 西安 710051)

针对以往求解多传感器联盟算法中参数多、计算复杂、实时性不强、全局搜索能力不高等问题，提出了基于改进人工蜂群算法的多传感器联盟方案。该方案对传感器联盟目标函数进行了优化，令跟随蜂采用双向轮盘赌的方式选择引领蜂，以便跳出局部最优解，提高算法收敛速度。仿真实验结果表明，所提出的算法能够有效获得传感器的最优联盟方案并保持较好的稳定性，与改进前相比，其寻优能力得到增强，进一步研究发现，适当扩大采蜜蜂在蜜源周围的搜索范围、增加蜜蜂个数、缩小未更新计数器阈值，能够进一步提高算法收敛速度，得到收益度更好的最优联盟方案。

改进人工蜂群算法；多传感器联盟；最优联盟方案

0 引言

世界各国常采用地基、海基、空基和天基等多种传感器协同组网的方式组建预警探测系统，当敌方目标来袭时，多传感器交叉提示[1]，针对不同目标的组建探测联盟，以此降低虚警率，提高探测的可靠性。

多传感器针对多目标组建探测联盟属于分配过程中的NP问题，文献[2]将线性规划方法引入到传感器分配问题，取得了较为满意的效果；文献[3]提出了一种基于遗传算法的多传感器目标分配方法，具有较强的鲁棒性；文献[4]把遗传算法和粒子群算法结合起来，建立了遗传粒子群算法模型，具有较快的收敛速度；文献[5]提出了一种基于萤火虫算法的雷达目标分配方法，该方法具有收敛速度快，求解结果稳定等优点；文献[6]研究了蚁群算法在多传感器管理中的目标分配问题中的应用，在处理较大规模的数据时显示出较好的优越性；文献[7]提出了基于效能函数的传感器分配模型，通过仿真实验验证了其有效性；文献[8]把信息熵和分辨增益等概念引入到传感器管理当中对线性优化模型进行了改进，取得了较好的效果；文献[9]从协方差的角度研究传感器分配问题，该方法更具有针对性和灵活性。

可以发现，在现有算法中，存在设置参数过多、计算较复杂、实时性不强、全局搜索能力不高等缺点。针对此问题，提出了基于改进人工蜂群算法的多传感器联盟方案。

1 人工蜂群算法原理

1.1 基本人工蜂群算法原理

人工蜂群算法由印度学者Karaboga于2005年提出，是一种模拟蜜蜂采蜜行为的新型群体优化算法[10-11]。蜜源为可行解，收益度为待优化函数。参与采蜜行为的蜜蜂共有四种：采蜜蜂、引领蜂、跟随蜂、侦查蜂。

四种蜜蜂的关系如图1所示[12]。

图1 蜜蜂关系转化示意图Fig.1 The transformation of the bee

基本人工蜂群算法步骤为：

1)随机生成N个蜜源，每个蜜源对应1个采蜜蜂，在蜜源周围搜索。当采蜜蜂发现收益度更高的新蜜源时，用新蜜源代替旧蜜源；若在一个蜜源周围连续搜索top次(未更新计数器阈值)后，该蜜源仍未更新，则采蜜蜂放弃该蜜源，变为侦查蜂，寻找新蜜源，继续在新蜜源周围搜索；

2)N个蜜蜂回到蜂巢变为引领蜂，对跟随蜂进行招募，N个跟随蜂根据各蜜源收益度，采用轮盘赌的方式参与招募；

3)跟随蜂跟随引领蜂回到相应蜜源变为采蜜蜂，回到步骤1)对蜜源进行更新；

4)当迭代次数达到最大值Final时，停止计算，得到最佳蜜源。

1.2 改进人工蜂群算法原理

在基本人工蜂群算法中，跟随蜂采用轮盘赌的方式按照式(1)求得的蜜源概率值选择蜜源。

(1)

式中，Xk为第k个蜜源，G(X)为蜜源收益度，Q(Xk)为按照正向轮盘赌方式该蜜源被选择的概率。

由式(1)可知，概率值越大的蜜源得到的跟随蜂数目越多，但随着计算次数增加，种群多样性下降，算法的全局搜索能力降低。

针对上述问题，对基本人工蜂群算法进行改进。跟随蜂采用双向轮盘赌的策略选择蜜源，除N个跟随蜂按照正向轮盘赌方式选择蜜源外，另外有N个跟随蜂根据式(2)采用反向轮盘赌的方式选择蜜源。

(2)

式(2)中，Xk为第k个蜜源，G(X)为蜜源收益度，O(Xk)为按照反向轮盘赌方式该蜜源被选择的概率。

从式(2)可以看出，收益度越小的蜜源被跟随蜂选择的概率就越大，从而得到的跟随蜂数目越多。

采用双向轮盘赌的策略，使种群朝着两个方向进化，既保证在每一次迭代中选择收益度最好的蜜源，同时保留了收益度较低的蜜源，维持了种群多样性，提高了算法的全局搜索能力，同时，由于增加了蜜蜂总数，也能够提高算法收敛速度，缩短计算时间。

2 传感器联盟模型

作战态势想定：传感器网络有m个传感器，为{s1,s2,…,sm}；来袭目标共有n个，为{t1,t2,…,tn}。

2.1 目标优先级模型

目标优先级表示目标对我方的威胁程度。影响目标tj优先级别的因素主要有：属性αj1、类型αj2、速度αj3、角度αj4、高度αj5、距离αj6、态势αj7等[13]。常用加权函数来确定目标的优先级别：

ϖ1+ϖ2+ϖ3+ϖ4+ϖ5+ϖ6+ϖ7=1

(3)

cj=ϖ1αj1+ϖ2αj2+ϖ3αj3+

ϖ4αj4+ϖ5αj5+ϖ6αj6+ϖ7αj7

(4)

式中，ϖk表示影响目标优先级第k个因素所占权重，cj表示目标tj的优先级。

2.2 传感器重要级模型

传感器重要级表示传感器在传感器网络中的重要程度。影响传感器si重要级的因素主要有：传感器属性βi1、传感器部署位置βi2、传感器探测区域βi3、传感器类型βi4、传感器抗干扰能力βi5。常用加权函数来确定传感器的重要级：

η1+η2+η3+η4+η5=1

(5)

fi=βi1η1+βi2η2+βi3η3+βi4η4+βi5η5

(6)

式中，ηk表示影响传感器重要级的第k个因素所占权重，fi表示传感器si的重要级。

2.3 目标函数

传感器联盟方案X为m×n阶矩阵。

(7)

传感器对目标的探测能力P为m×n阶矩阵。传感器si对目标tj探测能力pij由式(8)计算得出。

pij=(numij×timeij)/(Num×Time)

(8)式中，numij表示si对tj探测到的特征个数，timeij表示si探测到tj的有效时间，Num表示所需探测tj的总特征个数，Time表示tj在传感器网络中飞行的总时间。

目标函数为：

1)传感器网络对目标的总探测能力最大：

(9)

2)对目标探测的传感器重要级之和最小：

(10)

其约束条件为：

1)传感器在探测能力范围内进行探测，即：

(11)

式中，Mi为传感器si可同时探测的目标数。

2)每个目标都至少被一个传感器探测，即：

(12)

2.4 收益度函数

应用改进人工蜂群算法求解多传感器联盟，联盟方案X为蜜源(可行解)，其收益度G(X)的计算方法如式(13)所示：

(13)

2.5 算法流程图

算法流程图如图2所示。

图2 算法流程图Fig.2 The flow chart of thearithmetic

3 仿真分析

传感器网络共有10个传感器，来袭目标有6个，传感器对目标的探测能力见表1。其中，传感器重要级和目标优先级均为归一化后的数据。

3.1 蜂群算法改进前后最优联盟方案对比

采用基本人工蜂群算法和改进人工蜂群算法计算最优传感器联盟方案，迭代路线对比如图3所示，得到的最优联盟方案如表2所示。

由图3可知，改进人工蜂群算法和基本人工蜂群算法都能有效解决传感器联盟问题。但两者相比，改进人工蜂群算法在迭代1 044次左右达到稳定，最优分配方案的收益度为0.213 8，基本人工蜂群算法在迭代1 527次后达到稳定，最优分配方案收益度为0.213 3，改进人工蜂群算法收敛速度有所提高，最优联盟方案的收益度更高，寻优能力有所增强。

表1 传感器对目标的探测能力

图3 迭代路线对比Fig.3 The contrast of iterative courses

目标监测传感器改进前改进后11,2,7,8,91,3,1023,8,102,5,1032,3,5,8,101,4,6,7,941,2,3,4,5,84,5,951,2,3,4,5,6,81,4,6,7,8,961,2,3,4,5,6,8,91,2,3,5,6,7,8,10

3.2 采蜜蜂在蜜源周围搜索范围大小对结果的影响

研究采蜜蜂在蜜源周围搜索范围大小对改进人工蜂群算法的影响，迭代路线对比如图4所示，得到的最优联盟方案如表3所示。

图4 迭代路线对比Fig.4 The contrast of iterative courses

目标监测传感器搜索范围较小搜索范围较大11,2,4,6,7,8,91,3,6,7,921,3,4,7,102,3,4,5,6,7,8,9,1031,2,4,5,6,7,8,94,6,7,8,9442,6,7,851,3,4,6,7,8,101,5,6,9,1061,3,4,5,81,2,3,4,6,7,8,9

由图4可知，采蜜蜂在蜜源周围搜索范围较大时与采蜜蜂在蜜源周围搜索范围较小时相比，算法收敛速度和最优联盟方案的收益度有所提高。由此可知，在改进人工蜂群算法中，适当提高采蜜蜂在蜜源周围的搜索范围，能加快算法收敛，得到收益度更高的最优联盟方案，提高改进人工蜂群算法的寻优能力。

3.3 蜜蜂个数对结果的影响

研究蜜蜂个数对改进人工蜂群算法的影响，迭代路线对比如图5所示，得到的最优联盟方案如表4所示。

图5 迭代路线对比Fig.5 The of contrast iterative courses

目标监测传感器蜜蜂总个数为60个蜜蜂总个数为90个11,2,3,4,6,7,9,104,5,6,8,1022,3,5,6,7,8,101,3,4,6,7,934,6,7,101,5,6,941,4,8,92,3,4,8,9,1051,4,51,5,761,3,4,6,7,8,92,4,5,6,8,10

由图5可知，采蜜蜂、跟随蜂个数分别为60个时与分别为30个时相比，算法收敛速度和最优联盟方案的收益度有所提高。在改进人工蜂群算法中，适当增加算法中的蜜蜂数目，能够加快算法收敛，得到收益度更高的最优联盟方案，从而提高改进人工蜂群算法的寻优能力。

3.4 未更新计数器阈值对结果的影响

研究未更新计数器阈值大小对改进人工蜂群算法的影响，迭代路线对比如图6所示，得到的最优联盟方案如表5所示。

图6 迭代路线对比Fig.6 The contrast of iterative courses

目标监测传感器未更新计数器阈值为20未更新计数器阈值为3011,2,3,4,6,102,3,5,6,7,8,1021,3,4,6,7,101,2,732,3,5,6,7,9,101,4,5,6,7,941,7,81,3,4,5,8,1054,6,7,81,3,5,762,3,5,101,3,4,5,7,10

由图6可知，未更新计数器阈值为20时与未更新计数器阈值为30时相比，算法收敛速度和最优联盟方案的收益度有所提高。由此可见，适当降低未更新计数器阈值，能够加快算法收敛，得到收益度更高的最优联盟方案，从而提高改进人工蜂群算法的寻优能力。

在各次实验中，得到的最优联盟方案并不相同，这说明算法在初始化过程中随机生成的N个蜜源{X1,…Xk,…,XN}对最终得到的最优联盟方案有一定影响，改进人工蜂群算法结果的好坏受设置参数的影响较大。

4 结论

本文提出了基于改进人工蜂群算法的多传感联盟方案。在该方案中，对传感器联盟目标函数进行了优化，令跟随蜂采用双向轮盘赌的方式选择引领蜂，以便跳出局部最优解，提高算法收敛速度。仿真分析表明，改进人工蜂群算法具有操作简单、全局寻优能力强和收敛速度快等优点，在解决多传感器联盟问题时展现出了良好的性能。但同时也能够发现采用该方案得到的最优方案受设置参数的影响较大，如何找到算法中的最优参数以得到收益度更高的联盟方案将是下一步的研究方向。

[1]樊浩.多传感器交叉提示技术及其在目标探测中的应用研究[D].西安：空军工程大学，2012.

[2]NASH J M. Optimal allocation of tracking resource [C]//Proc of the IEEE Conference on Decision and Control. USA:IEEE,2000:1177-1180.[3]朱卫宵，祝前旺，陈康.基于遗传算法的多传感器目标分配方法[J].电子信息对抗技术，2015，30(03)：30-34.

[4]杨啸天，冯金富，冯媛，等.基于遗传粒子群的多传感器目标分配算法[J].电光与控制，2011,18(03)：5-8.

[5]田德伟，何广军，尤晓亮，等.基于萤火虫算法的雷达目标分配方法[J].探测与控制学报，2015,37(02)：62-65.

[6]黄树彩，李为民，李威.多传感器管理的目标分配问题蚁群算法研究[J].空军工程大学学报，2005,6(02)：28-31.

[7]杨秀珍，鞠传文，何有.基于效能函数的传感器管理系统仿真[J].系统仿真学报，2003,15(02)：251-261.

[8]David A. Casta A. Approximate Dynamic Programming for Sensor Management [EB/OL].http//www.gocon,02,7,2002.

[9]刘世前，郭治.基于满意滤波的目标图像跟[J].兵工学报，2002,23(04):481-484.

[10]班祥东.蜂群算法理论研究综述[J].软件导刊，2012,11(10)：36-38.

[11]李翠，纪峰，吴仰玉，等.基于二次插值的人工蜂群算法[J].科学技术与工程，2013，13(20):5819-5824.

[12]易正俊，韩晓晶.增强寻优能力的改进人工蜂群算法[J].数据采集与处理，2013，18(06):761-769.

[13]罗文涛，许蕴山，肖冰松，等.预警探测中的多传感器多目标匹配[J].电光与控制，2014,21(11)：28-33.

Multi-sensors Coalitions Basing on Improved Bee Colony Optimization

PANG Ce，HUANG Shucai，WEI Daozhi，YUAN Zhiwei, LIU Jinchang

(Air and Missile Defense College, Air Force Engineering University, Xi’an 710051, China)

Aiming at the problems of over-parameterized and calculably complex with poor real time and weak global searching ability in previous algorithms used to build multi-sensor coalitions are , a coalition scheme basing on the improved bee colony optimization was proposed. In this algorithm, the objective function was optimized, and the following-bee chose the leading-bee in the way of bidirectional roulette, contributing to jumping out of the locally optimal solution and improving the convergence rate of the algorithm. The simulation and experimental results showed, by using the improved bee colony optimization, the most optimized scheme could be gotten easily and the algorithm could keep smooth. Comparing to the basic bee colony optimization, the improved one could make optimization ability enhanced. By properly expanding the searching scale of bee around the source, increasing the number of the bee and reducing the threshold of not updated counter, the convergence of the algorithm and the adaptability of the most optimized coalition scheme could be improved.

improved bee colony optimization；multi-sensor coalition；most optimized coalition scheme

2016-04-27

航空科学基金项目资助(20130196004)

庞策(1993—)，男，河北衡水人，硕士研究生，研究方向：多传感器交叉提示技术。E-mail:m18392447996@169.com。

TN911

A

1008-1194(2016)05-0107-05