張士磊，　張　朋，　熊志剛

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

0　引言

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

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

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

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

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

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

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

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

(1)

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

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

(2)

(3)

傳感器重要級(jí)用m×1階矩陣F2表示，其中，ci為傳感器si的重要級(jí)，其值大小表示該傳感器在我方傳感器網(wǎng)絡(luò)中擔(dān)負(fù)戰(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表示影響傳感器重要級(jí)的第k個(gè)因素所占權(quán)重；βi 1為傳感器屬性；βi 2為傳感器部署位置；βi 3為傳感器探測(cè)區(qū)域；βi 4為傳感器類型；βi 5為傳感器抗干擾能力。

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

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

(6)

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

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

(7)

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

(8)

約束條件有以下2個(gè)。

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

(9)

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

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

(10)

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

(11)

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

2.1　基本蝙蝠算法

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

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

2) 更新蝙蝠速度和位置。t時(shí)刻，對(duì)蝙蝠的速度和位置進(jìn)行更新，即

(12)

(13)

ha=hmin+(hmax-hmin)×R

(14)

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

xnew=xold+εAt。

(15)

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

(16)

(17)

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

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

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

2.2　改進(jìn)蝙蝠算法

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

2.2.1K-均值算法初始化

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

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

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

3) 再次計(jì)算N個(gè)聚類簇的聚類中心；

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

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

2.2.2自適應(yīng)步長(zhǎng)

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

(18)

(19)

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

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

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

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

(20)

更新，使種群按照兩個(gè)方向進(jìn)化，從而提高種群多樣性。若0

(21)

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

2.3　改進(jìn)蝙蝠算法步驟

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

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

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

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

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

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

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

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

3　仿真驗(yàn)證

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

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

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

3.1　蝙蝠算法改進(jìn)前后對(duì)比

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

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

目標(biāo)探測(cè)傳感器改進(jìn)前改進(jìn)后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可知，改進(jìn)蝙蝠算法和基本蝙蝠算法都能有效解決多傳感器-多目標(biāo)分配問題。

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

3.2　蝙蝠算法與其他智能算法對(duì)比

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

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

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

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

4　結(jié)論

針對(duì)多目標(biāo)多傳感器分配中的NP爆炸問題，本文引入蝙蝠算法進(jìn)行求解，并通過K-均值算法初始化、速度更新采用自適應(yīng)步長(zhǎng)、向反方向搜索及變異操作等3項(xiàng)措施對(duì)基本蝙蝠算法易陷入局部最優(yōu)、存在早熟現(xiàn)象等問題進(jìn)行了改進(jìn)，得到改進(jìn)的蝙蝠算法。仿真實(shí)驗(yàn)表明蝙蝠算法在改進(jìn)后，不僅其計(jì)算速度和尋優(yōu)能力相對(duì)于基本蝙蝠算法大大提高，而且其求解速度和求解質(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].電子信息對(duì)抗技術(shù)，2015,30(3)：30-34.

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

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

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

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

[9]羅文濤，許蘊(yùn)山，肖冰松，等.預(yù)警探測(cè)中的多傳感器多目標(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]易正俊，韓曉晶.增強(qiáng)尋優(yōu)能力的改進(jìn)人工蜂群算法[J].數(shù)據(jù)采集與處理，2013,18(6):761-769.

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