張勇 ZHANG Yong

（包頭職業(yè)技術(shù)學(xué)院電氣工程系，包頭 014030）

（Department of Electrical Engineering，Baotou Vocational&Technical College，Baotou 014030，China）

0 引言

在真實戰(zhàn)場態(tài)勢環(huán)境中，復(fù)雜而多變的動態(tài)環(huán)境對傳感器的數(shù)量和傳感器與傳感器之間的協(xié)同都提出來很高的要求。因此，當(dāng)有多個傳感器同時進(jìn)行目標(biāo)檢測、目標(biāo)識別和目標(biāo)跟蹤時，傳感器和目標(biāo)之間的任務(wù)分配問題，都是亟待解決的問題。本文采用與禁忌表結(jié)合的粒子群算法，來分析無人機(jī)尋求目標(biāo)進(jìn)行最優(yōu)配對的問題。

1 粒子群算法流程

在任務(wù)分配的求解問題中，變量的取值是離散的，所以是非連續(xù)的優(yōu)化問題。在利用粒子群算法進(jìn)行優(yōu)化時，必須進(jìn)行變量的離散化：一方面需要將粒子的位置離散化，另一方面也要將更新速度離散化。因此粒子在選擇新位置的時候，并不是在全定義域內(nèi)進(jìn)行選擇。粒子移動的位置就表示為該粒子對于任務(wù)分配的結(jié)果，目標(biāo)的數(shù)目也是微粒的維數(shù)，粒子的更新速度為無人機(jī)和目標(biāo)之間的任務(wù)配對的變化情況。根據(jù)約束條件要求，任意目標(biāo)只能有一個無人機(jī)對其發(fā)生作用，任一無人機(jī)至多也只能對一個目標(biāo)執(zhí)行任務(wù)，因此在粒子群算法的尋優(yōu)過程中，微粒各維的最終位置應(yīng)該是互異的，在本文中采用多次迭代的方法，直到各維變量的位置都不同的時候，才繼續(xù)往下執(zhí)行，具體的算法流程如圖1所示。①運(yùn)行開始，進(jìn)行相關(guān)參數(shù)的初始化設(shè)置（比如設(shè)置最大迭代次數(shù)等）；②隨機(jī)對微粒進(jìn)行初始化設(shè)置，即：無人機(jī)和目標(biāo)的任務(wù)配對，并計算目標(biāo)評價函數(shù)；1）依次對每一個目標(biāo)分配一個無人機(jī)來執(zhí)行作戰(zhàn)任務(wù)，如果無人機(jī)和目標(biāo)的任務(wù)分配出現(xiàn)了同一個無人機(jī)對兩個不同的目標(biāo)執(zhí)行任務(wù)時候，在重新分配，直到此類情況不再出現(xiàn)（不重復(fù)原則）。2）當(dāng)每個微粒滿足任務(wù)分配，進(jìn)行微粒初始值評價；③對微粒進(jìn)行新速度的計算，并加以限幅；④對微粒進(jìn)行新位置的計算，并加以限幅；⑤如果微粒處于新位置時，出現(xiàn)微粒對于無人機(jī)和目標(biāo)的任務(wù)分配出現(xiàn)步驟②中1）的情況時，重新執(zhí)行步驟③和步驟④，直到滿足要求；⑥按目標(biāo)評價函數(shù)，重新評價各微粒的適應(yīng)值；⑦對每個微粒，找出微粒個體或群體的最優(yōu)值；⑧更新所有微粒，并將最優(yōu)解保存為該微粒的全局歷史最優(yōu)任務(wù)分配；⑨若滿足終止條件，搜索停止，輸出搜索，否則，返回③繼續(xù)搜索；⑩gbest就是搜索到的最優(yōu)值。利用粒子群算法來對傳感器和目標(biāo)進(jìn)行分配從本質(zhì)上說，就是使得變量中的每一維參數(shù)都不同，在這種情況下來獲得最大的效用。根據(jù)速度更新公式，在粒子每維變量速度的更新公式中，速度的變化量取決于隨機(jī)數(shù)的取值，當(dāng)出現(xiàn)該維變量與其他維變量取值相同時，最直觀的想法就是持續(xù)更新隨機(jī)數(shù)，來改變速度變量，從而實現(xiàn)變量取值的目的。因此，有必要對粒子群算法進(jìn)行改進(jìn)，從而來得到適合于求解傳感器與目標(biāo)分配效用函數(shù)的解決算法。

圖1 粒子群算法流程圖

2 與禁忌表結(jié)合的粒子群算法

除了上述的更改粒子更新速度的方法以外，我們還采取了控制粒子選擇域的方法來實現(xiàn)傳感器與目標(biāo)的配對。這里，采用了禁忌表的方法。

禁忌表算法是一種全局性鄰域搜索算法，禁忌搜索的思想最早由Fred Glover（美國工程院院士，科羅拉多大學(xué)教授）提出，它是對局部領(lǐng)域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法。禁忌表的主要目的是阻止搜索過程中出現(xiàn)循環(huán)和避免陷入局部最優(yōu)，它通常記錄前若干次的移動，禁止這些移動在近期內(nèi)返回。結(jié)合禁忌表對粒子群算法進(jìn)行改進(jìn)：每個微粒的變量都一次來進(jìn)行速度和位置的更新。值域中被選擇過的取值被推入禁忌表，之后的變量在取值時，只能在未被推入禁忌表中的值域中進(jìn)行選擇，因此隨著變量的依次取值，值域在不斷變小。這樣可以避免出現(xiàn)變量取值相同的情況。與禁忌表的粒子群算法流程圖如圖2所示。它解決了當(dāng)微粒變量的取值最優(yōu)解時，由于變量取值的改變程度有限，進(jìn)入死鎖狀態(tài)，而不能得到最優(yōu)解。

圖2 與禁忌表結(jié)合的粒子群算法流程圖

3 仿真結(jié)果

為了驗證無人機(jī)傳感器與目標(biāo)間的配對問題，與禁忌表結(jié)合的粒子群算法是可行的。故假設(shè)出6個目標(biāo)，分別是 （200，12）、（250，12）、（300，12）、（350，12）、（400，12）、（450，12），把目標(biāo)3作為無人機(jī)沒辦法識別的目標(biāo)，把目標(biāo)4作為已經(jīng)被無人機(jī)擊毀的目標(biāo)，其余目標(biāo)作為無人機(jī)攻擊的真目標(biāo)。現(xiàn)將無人機(jī)的飛行方向改為從與x軸正向呈負(fù)65度開始，以一度的差值依次遞減。經(jīng)過多次計算得到的結(jié)果為：第25號無人機(jī)對第一個目標(biāo)執(zhí)行攻擊任務(wù)，即25號無人機(jī)上的力學(xué)傳感器對第一個目標(biāo)進(jìn)行力學(xué)參數(shù)測量：第32號無人機(jī)對第二個目標(biāo)執(zhí)行攻擊任務(wù)，即第32號無人機(jī)上的力學(xué)傳感器對第二目標(biāo)執(zhí)行力學(xué)參數(shù)測量；第35號無人機(jī)對第三個目標(biāo)執(zhí)行再識別任務(wù)，即第35號無人機(jī)上的目標(biāo)識別傳感器對第三個目標(biāo)執(zhí)行識別任務(wù)；第38號無人機(jī)對第四個目標(biāo)執(zhí)行毀傷評估的任務(wù)，即第38號無人機(jī)上的威脅評估傳感器對第四個目標(biāo)進(jìn)行威脅判斷；第40號目標(biāo)對第五個目標(biāo)執(zhí)行攻擊任務(wù)，即第40號無人機(jī)上的力學(xué)傳感器對第五個目標(biāo)進(jìn)行力學(xué)測量；最終的效益函數(shù)適應(yīng)值為1.187。

一共做了30次試驗，每次試驗要完成100次迭代。如圖3所示，圖中BPSO為基本粒子群算法，TPSO為與禁忌表結(jié)合的粒子群算法。圖中為兩種算法尋求最優(yōu)值和收斂情況的仿真結(jié)果。很好的將與禁忌表結(jié)合的粒子群算法和基本的粒子群算法，進(jìn)行無人機(jī)傳感器進(jìn)行目標(biāo)識別中收斂情況進(jìn)行比較。

圖3 兩種算法的的最優(yōu)值和收斂情況

表1 兩種算法的優(yōu)化結(jié)果

從表1中得出如下結(jié)論，采用BPSO算法，通常進(jìn)行30次試驗，其收斂的成功率只達(dá)到46.7%，并且無法尋找到最優(yōu)值。采用TPSO算法，同樣進(jìn)行了30次試驗，其收斂成功率達(dá)到100%。但是在試驗的平均耗時角度分析，BPSO算法耗時較少。TPSO算法耗時略有些長。總之，采用與禁忌表結(jié)合的粒子群算法，對于無人機(jī)傳感器管理問題，可以得到很好的解決。其收斂的成功率為100%，雖然在尋求最優(yōu)配對時，耗時略長，但從搜索成功率的角度看，與禁忌表結(jié)合的粒子群算法是可以采用的。

[1]王欣.多傳感器數(shù)據(jù)融合問題的研究[D].吉林大學(xué),2006.

[2]李琪.傳感器管理及研究進(jìn)展[J].科技信息(學(xué)術(shù)研究),2008(28).

[3]張玉芳,薛青松,熊忠陽.基于禁忌搜索的動態(tài)粒子群算法[J].計算機(jī)工程與應(yīng)用,2008(24).