基于禁忌表算法的傳感器管理

張勇 ZHANG Yong

（包頭職業技術學院電氣工程系，包頭 014030）

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

0 引言

在真實戰場態勢環境中，復雜而多變的動態環境對傳感器的數量和傳感器與傳感器之間的協同都提出來很高的要求。因此，當有多個傳感器同時進行目標檢測、目標識別和目標跟蹤時，傳感器和目標之間的任務分配問題，都是亟待解決的問題。本文采用與禁忌表結合的粒子群算法，來分析無人機尋求目標進行最優配對的問題。

1 粒子群算法流程

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

圖1 粒子群算法流程圖

2 與禁忌表結合的粒子群算法

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

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

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

3 仿真結果

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

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

圖3 兩種算法的的最優值和收斂情況

表1 兩種算法的優化結果

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

[1]王欣.多傳感器數據融合問題的研究[D].吉林大學,2006.

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

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