基于改進人工蜂群算法的多傳感器聯盟

龐 策，黃樹彩，韋道知，苑智瑋，劉錦昌

(空軍工程大學防空反導學院，陜西 西安 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