基于改進蝙蝠算法的多傳感器多目標(biāo)分配

張士磊，　張　朋，　熊志剛

(1.河南工學(xué)院自動控制系,河南 新鄉(xiāng)　453003；　2.中原工學(xué)院電子信息學(xué)院,鄭州　451191; 3.空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安　710051)

0　引言

在防空作戰(zhàn)體系中，單個傳感器往往不能完成對目標(biāo)的檢測、識別和跟蹤任務(wù)，多數(shù)情況下需要多個傳感器同時針對一個目標(biāo)進行探測，然后對多個傳感器探測到的數(shù)據(jù)進行信息融合。傳感器管理包括多傳感器交叉提示和傳感器控制兩個方面，是信息融合的反饋環(huán)節(jié)，主要解決多個傳感器探測多個目標(biāo)時的資源調(diào)度問題。一方面由于每個傳感器的探測能力有限，多個目標(biāo)來襲時，每一個傳感器不能同時對每個目標(biāo)

進行探測，這就對傳感器合理分配提出了需求;再者，如果每一個傳感器同時對每個目標(biāo)都進行探測，容易造成信息冗余和資源浪費。另一方面，由于對每個目標(biāo)的探測任務(wù)(檢測、識別、跟蹤)不同，也必須解決傳感器針對不同傳感器不同任務(wù)的資源協(xié)調(diào)問題，在確保完成對目標(biāo)的探測任務(wù)的情況下達到傳感器系統(tǒng)最優(yōu)性能，同時使傳感器資源消耗最少。

多傳感器多目標(biāo)分配屬于組合爆炸NP問題，針對此問題，已經(jīng)有許多學(xué)者作了探討。在國外，JEFFREY N等將優(yōu)化思想引入到解決傳感器分配問題當(dāng)中，得到了傳感器分配方案，但該算法的求解速度較慢，求解質(zhì)量較低；NASH J M等利用線性規(guī)劃的方法對傳感器資源進行分配，得到了較為理想的可行解，但該算法的復(fù)雜度較高[1]；CASTANON D A等采用動態(tài)規(guī)劃的方法有效解決了傳感器分配問題[2]；KASTELLA K等提出了一種基于信息熵和分辨力增益的傳感器管理方法，得到了較為理想的多傳感器多目標(biāo)分配方案，但算法穩(wěn)定性較差[3]。

隨著智能算法的發(fā)展，學(xué)者們將群智能算法引入到解決多傳感器多目標(biāo)分配問題。在國內(nèi)，朱衛(wèi)宵等將遺傳算法用于解決多傳感器多目標(biāo)分配問題，有效地得到了分配方案，該算法全局搜索能力較強[4]；黃樹彩等提出了一種基于蟻群算法的多傳感器多目標(biāo)分配算法，該算法具有較快的收斂性和較高的精度，但易陷入局部最優(yōu)[5]；樊浩等引入并改進了粒子群算法用于傳感器交叉提示多目標(biāo)探測動態(tài)聯(lián)盟模型求解，并證明了該算法的有效性[6]；田德偉等提出了基于螢火蟲算法的雷達目標(biāo)分配方法，并證明該算法具有收斂速度快、求解結(jié)果穩(wěn)定的優(yōu)點[7]；楊嘯天等將遺傳算法和粒子群算法結(jié)合起來，建立了基于遺傳粒子群算法的多傳感器多目標(biāo)分配模型，有效實現(xiàn)了傳感器資源對目標(biāo)的分配，該算法性能較以往算法大大提高[8]。

通過研究可以看出，尋找一種簡單易行的有效求解算法，并提高算法的收斂速度和穩(wěn)定性，有效跳出局部最優(yōu)，一直是學(xué)者探討的重點。對此，本文引入并改進蝙蝠算法解決此類問題，并通過仿真實驗證明了本文算法的有效性和先進性。

1　傳感器-目標(biāo)配對模型

設(shè)傳感器網(wǎng)絡(luò)有m個傳感器{s1,s2,…,sm}，來襲目標(biāo)有n個{t1,t2,…,tn}，需將m個傳感器分配給n個目標(biāo)進行探測。

設(shè)分配方案用m×n階矩陣X表示，其中，xij為X的第i行第j列元素,表示傳感器si對目標(biāo)tj的監(jiān)測狀態(tài),即

(1)

傳感器對目標(biāo)的探測能力用m×n階矩陣P表示，其中，pij為P的第i行第j列元素,表示傳感器si對目標(biāo)tj的探測概率。

目標(biāo)優(yōu)先級用1×n階矩陣F1表示，其中，fi為目標(biāo)tj的優(yōu)先級，其值大小表示該目標(biāo)對我方防御系統(tǒng)的威脅程度，本文中有

(2)

(3)

傳感器重要級用m×1階矩陣F2表示，其中，ci為傳感器si的重要級，其值大小表示該傳感器在我方傳感器網(wǎng)絡(luò)中擔(dān)負戰(zhàn)備任務(wù)的重要程度，本文中有

ci=βi 1η1+βi 2η2+βi 3η3+βi 4η4+βi 5η5

(4)

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

(5)

式中：ηk表示影響傳感器重要級的第k個因素所占權(quán)重；βi 1為傳感器屬性；βi 2為傳感器部署位置；βi 3為傳感器探測區(qū)域；βi 4為傳感器類型；βi 5為傳感器抗干擾能力。

目標(biāo)函數(shù)如下所述。

1) 傳感器網(wǎng)絡(luò)對目標(biāo)的總探測概率最大，同時考慮目標(biāo)優(yōu)先級，有

(6)

式中，pj為傳感器網(wǎng)絡(luò)對目標(biāo)tj的探測概率。pj的計算方法為

pj=1-(1-x1j×p1j)(1-x2j×p2j)…(1-xmj×pmj)。

(7)

2) 傳感器網(wǎng)絡(luò)消耗的傳感器資源最少，有

(8)

約束條件有以下2個。

1) 傳感器實際探測的目標(biāo)個數(shù)小于其探測能力，有

(9)

式中，Mi為傳感器si可同時探測的最大目標(biāo)數(shù)。

2) 應(yīng)保證有傳感器對目標(biāo)tj進行探測，有

(10)

評價多傳感器-多目標(biāo)分配方案X的好壞，需要建立一定的評價指標(biāo)，即適應(yīng)度函數(shù)G(X)，其計算方法為

(11)

2　改進蝙蝠算法設(shè)計

2.1　基本蝙蝠算法

蝙蝠算法(Bat Algorithm，BA)由YANG X S于2010年提出[10]，其算法來源于自然環(huán)境中蝙蝠依靠超聲波搜索和捕食的行為，具有模型簡單、計算方便、參數(shù)設(shè)置較少等優(yōu)點，其基本蝙蝠算法的尋優(yōu)機制如下所述。

1) 算法初始化。t=0時刻，將每個蝙蝠看作一個可行解，給定種群蝙蝠個數(shù)、蝙蝠位置、速度、脈沖速度、脈沖頻率、脈沖響度，根據(jù)適應(yīng)度函數(shù)對每個蝙蝠作出評價，確定最優(yōu)蝙蝠位置。

2) 更新蝙蝠速度和位置。t時刻，對蝙蝠的速度和位置進行更新，即

(12)

(13)

ha=hmin+(hmax-hmin)×R

(14)

3) 生成隨機數(shù)R1。若R1>ra，通過隨機游走的方法使蝙蝠進行局部搜索，生成新解，其生成方法為

xnew=xold+εAt。

(15)

4) 生成隨機數(shù)R2。若R2

(16)

(17)

5) 尋找更新后最佳適應(yīng)度蝙蝠，并記錄。

6) 判斷是否達到最大迭代次數(shù)，或者達到搜索精度ε1，若達到，則結(jié)束迭代，將最優(yōu)蝙蝠位置及其所對應(yīng)的適應(yīng)度輸出；否則，返回步驟3)。

通過上述基本蝙蝠算法中蝙蝠的全局位置更新和局部位置更新方法可知，該算法一味向群體最優(yōu)蝙蝠位置收斂，隨著算法迭代次數(shù)的增加，在迭代后期，群體的個體差異性越來越小，種群多樣性越來越低，甚至最終趨于0，一方面會導(dǎo)致群體進化能力降低，另一方面容易造成早熟，從而陷入局部最優(yōu)。雖然式(16)與式(17)對算法早熟起到一定的抑制作用，但其效果并不明顯，對此，在基本蝙蝠算法的基礎(chǔ)上進行改進，提出改進蝙蝠算法。

2.2　改進蝙蝠算法

針對蝙蝠算法易發(fā)生早熟、陷入局部最優(yōu)等缺點，主要進行如下改進。

2.2.1K-均值算法初始化

初始化生成蝙蝠群體，該群體應(yīng)均勻分布在求解空間當(dāng)中，以此才能對全局進行更好搜索。而在基本蝙蝠算法中，初始化過程中蝙蝠群體是隨機生成的，可能存在蝙蝠局部“扎堆”的現(xiàn)象，使蝙蝠群體在一開始就失去全局搜索能力，引起局部最優(yōu)，對此，設(shè)初始化群體中蝙蝠數(shù)量為N，提出基于K-均值的種群初始化方法，其步驟為：

1) 隨機生成N只蝙蝠作為聚類中心，共有N個聚類簇；

2) 隨機生成N1只蝙蝠，將每只蝙蝠劃分到離其最近的聚類簇當(dāng)中；

3) 再次計算N個聚類簇的聚類中心；

4) 重復(fù)步驟2)和3)，直至前后兩次聚類中心的變化區(qū)域小于給定的閾值Δ；

5) 輸出最后的N個聚類中心作為初始化群體中的N只蝙蝠個體。

2.2.2自適應(yīng)步長

在蝙蝠運動過程中，其移動速度過慢，會降低算法收斂速度，而移動太快，則可能會“越過”最優(yōu)值[11]。在算法迭代開始時，蝙蝠移動速度應(yīng)較大，從而提高向最優(yōu)解收斂的速度，而算法迭代后期，蝙蝠移動速度應(yīng)較小，從而在最優(yōu)解周圍能夠充分搜索，避免“錯過”最優(yōu)解，因此，提出基于自適應(yīng)步長的蝙蝠速度更新方法，每次迭代過程中，更新蝙蝠速度，即

(18)

(19)

式中：smin為最小步長，取smin=0.01；Tmax為最大迭代次數(shù)；t為當(dāng)前迭代次數(shù)；K為系數(shù)，取K=10。

由式(18)、式(19)可以看出，算法初期步長較大，以此提高收斂速度；算法后期步長較小，以此精細搜索。

2.2.3向反方向搜索及變異操作

由于在迭代過程中，所有蝙蝠均向適應(yīng)度高的蝙蝠位置移動，種群多樣性大大降低，對此，每次迭代過程中，對所有蝙蝠按照適應(yīng)度從高到低的順序排序，挑選適應(yīng)度排名最后的N2只蝙蝠，產(chǎn)生值為0～1的隨機數(shù)R3。若R3>0.5，其位置按照

(20)

更新，使種群按照兩個方向進化，從而提高種群多樣性。若0

(21)

更新。式中：R為0～1的隨機數(shù)；xmin為蝙蝠最大位置；xmax為蝙蝠最小位置。

2.3　改進蝙蝠算法步驟

通過2.2節(jié)所述，改進蝙蝠算法步驟為：

1) 算法初始化，t=0時刻，將給定各參數(shù)，按照K-均值算法生成在求解空間內(nèi)均勻分布的N只蝙蝠；

2) 計算每只蝙蝠的適應(yīng)度，并排序；

3) 按照式(13)、式(14)、式(18)～(21)更新蝙蝠速度和位置；

4) 生成隨機數(shù)R1，若R1>ra，通過隨機游走的方法使蝙蝠進行局部搜索，生成新解，新解生成方法如式(15)所示；

5) 生成隨機數(shù)R2，若R2

6) 尋找更新后最佳適應(yīng)度蝙蝠，并記錄；

7) 判斷是否達到最大迭代次數(shù)，或者達到搜索精度ε1，若達到，則結(jié)束迭代，將最優(yōu)蝙蝠位置及其所對應(yīng)的適應(yīng)度輸出,否則，返回步驟2)。

3　仿真驗證

傳感器網(wǎng)絡(luò)中共有10個傳感器，來襲目標(biāo)共有6個，各傳感器對目標(biāo)的探測能力見表1，其中各傳感器重要級和目標(biāo)優(yōu)先級均采用歸一化表示。

表1　傳感器對目標(biāo)的探測能力

在仿真過程中，參數(shù)設(shè)置分別為：蝙蝠數(shù)量N=30，N2=6，最大迭代次數(shù)為Tmax=2000，蝙蝠最大頻率hmax=2.0，初始響度為區(qū)間[0,2]內(nèi)的隨機數(shù)，初始脈沖取[0,0.05]內(nèi)的隨機數(shù)，α=β=0.9，蝙蝠最大速度vmax=0.5(無量綱值)。

3.1　蝙蝠算法改進前后對比

分別采用基本蝙蝠算法、改進蝙蝠算法計算多傳感器-多目標(biāo)分配方案，經(jīng)過100次蒙特卡羅實驗，其迭代過程對比如圖1所示，最終分配結(jié)果如表2所示。

圖1　兩種算法迭代路線對比Fig.1　The contrast of iterative courses of two algorithms

目標(biāo)探測傳感器改進前改進后11，7，8，91，3，1023，8，102，5，1032，8，101，4，641，2，3，4，5，84，5，951，2，3，4，51，4，6，7，861，2，3，4，5，8，91，2，3，5，6，7，10

由圖1可知，改進蝙蝠算法和基本蝙蝠算法都能有效解決多傳感器-多目標(biāo)分配問題。

基本蝙蝠算法計算時間為3.8 s，改進蝙蝠算法計算時間為2.1 s，基本蝙蝠算法在改進后，計算速度明顯提高。基本蝙蝠算法在680次計算后趨于穩(wěn)定，方案適應(yīng)度不再提高，計算得到的最優(yōu)方案適應(yīng)度值為0.212 3，而改進蝙蝠算法在計算93～1617次之間，方案適應(yīng)度穩(wěn)定，而當(dāng)計算到1617次時，方案適應(yīng)度又有所提高，計算得到的最優(yōu)方案適應(yīng)度值為0.220 8，說明其能夠跳出局部最優(yōu)，基本蝙蝠算法在改進后，其尋優(yōu)能力有所增強。

3.2　蝙蝠算法與其他智能算法對比

分別采用本文改進蝙蝠算法與文獻[12]中的粒子群算法、文獻[13]中的蜂群算法、文獻[14]中的狼群算法求解多傳感器-多目標(biāo)分配方案，經(jīng)過100次蒙特卡羅實驗，其迭代過程對比如圖2所示。

圖2　4種算法迭代路線對比Fig.2　The contrast of iterative courses of four algorithms

本文改進蝙蝠算法計算時間為1.9 s，粒子群算法計算時間為4.1 s，蜂群算法為3.2 s，狼群算法為2.5 s，本文算法求解速度最快。

由圖2可知，本文所提出的改進蝙蝠算法，在求解多傳感器-多目標(biāo)分配方案過程中，無論求解速度，還是求解質(zhì)量，均優(yōu)于其他3種算法。

4　結(jié)論

針對多目標(biāo)多傳感器分配中的NP爆炸問題，本文引入蝙蝠算法進行求解，并通過K-均值算法初始化、速度更新采用自適應(yīng)步長、向反方向搜索及變異操作等3項措施對基本蝙蝠算法易陷入局部最優(yōu)、存在早熟現(xiàn)象等問題進行了改進，得到改進的蝙蝠算法。仿真實驗表明蝙蝠算法在改進后，不僅其計算速度和尋優(yōu)能力相對于基本蝙蝠算法大大提高，而且其求解速度和求解質(zhì)量也均優(yōu)于粒子群算法、蜂群算法、狼群算法等其他算法。因而，本文算法更適用于多傳感器多目標(biāo)分配問題求解，其求解質(zhì)量更高。

[1]NASH J M.Optimal allocation of tracking resources[C]//1977 IEEE Confererce on Decision and Control,1977:1177-1180.

[2]CASTANON D A.Approximate dynamic programming for sensor management[C]//Proceedings of the 36th IEEE Conference on Decision and Control,1997:1202-1207.

[3]KASTELLA K.Discrimination gain to optimize detection and classification[J].IEEE Transactions on Systems, Man,and Cybernetics,Part-A:System and Humans,1997, 27(1):112-116.

[4]朱衛(wèi)宵，祝前旺，陳康.一種基于遺傳算法的多傳感器多目標(biāo)分配方法[J].電子信息對抗技術(shù)，2015,30(3)：30-34.

[5]黃樹彩，李為民，李威.多傳感器管理的目標(biāo)分配問題蟻群算法研究[J].空軍工程大學(xué)學(xué)報:自然科學(xué)版,2005,6(2)：28-31.

[6]樊浩,黃樹彩，高美鳳，等.多傳感器交叉提示多目標(biāo)探測動態(tài)聯(lián)盟技術(shù)研究[J].宇航學(xué)報，2011,32(11)：2380-2386.

[7]田德偉，何廣軍，尤曉亮，等.基于螢火蟲算法的雷達目標(biāo)分配方法[J].探測與控制學(xué)報，2015,37(2)：62-65.

[8]楊嘯天，馮金富，馮媛，等.基于遺傳粒子群的多傳感器目標(biāo)分配算法[J].電光與控制，2011,18(3)：5-8.

[9]羅文濤，許蘊山，肖冰松，等.預(yù)警探測中的多傳感器多目標(biāo)匹配[J].電光與控制，2014,21(11)：28-33.

[10]YANG X S.A new metaheuristic bat-inspired algorithm[J].Computer Knowledge and Technology,2010,284:65-74.

[11]杜繼永，張鳳鳴，李建文，等.一種具有初始化功能的自適應(yīng)慣性權(quán)重粒子群算法[J].信息與控制,2012, 41(2):165-169.

[12]楊嘯天，馮金富，馮媛，等.基于遺傳粒子群的多傳感器目標(biāo)分配算法[J].電光與控制，2011,18(3)：5-8.

[13]易正俊，韓曉晶.增強尋優(yōu)能力的改進人工蜂群算法[J].數(shù)據(jù)采集與處理，2013,18(6):761-769.

[14]吳虎勝，張鳳鳴，吳廬山.一種新的群體智能算法—狼群算法[J].系統(tǒng)工程與電子技術(shù),2013,35(11):2430-2438.