基于優(yōu)化算法的多傳感器自動規(guī)劃技術

劉睿 趙坤

（中國電子科技集團公司第二十七研究所 河南省鄭州市 450047）

1 引言

無人探測平臺搭載探測傳感器，實現(xiàn)對敵目標的探測、定位，完成目標活動規(guī)律的分析，為指揮決策提供支撐。

隨著電子技術與數(shù)據(jù)信息處理技術的發(fā)展，無人探測平臺可同時裝載多種探測傳感器，同時接收不同頻段、不同類型的信號，實現(xiàn)寬頻段、多類型信號的探測，無人探測平臺的探測能力不斷提升。單純依靠人工制定任務規(guī)劃方法的效率越來越低，并且已經(jīng)不能滿足探測需求。主要原因有以下幾個方面：

（1）目標搭載的輻射源增加、信號復雜多樣，判斷目標能否被無人探測平臺捕獲的條件增多，針對目標捕獲情況的建模更加困難；

（2）隨著傳感器探測能力的提升，可以同時探測到的目標越來越多，但是由于傳感器數(shù)據(jù)處理能力的限制，不能同時處理所有探測到的目標，需要合理舍棄目標，提高效率；

（3）隨著目標的增多、傳感器探測能力的增加和傳感器處理能力的限制，在同一時刻傳感器分配的排列組合增加，導致各傳感器資源競爭使用的機率增加，大大增加了傳感器規(guī)劃的復雜度和時間。

多傳感器規(guī)劃所討論的問題不僅僅要求傳感器可以探測到價值最大的目標，同時要求傳感器可以探測到盡可能多的目標。傳感器資源有限，隨著目標數(shù)目的增加，會存在傳感器資源不足的問題，為此，優(yōu)先將有限的傳感器資源分配給哪個目標是傳感器資源配置要解決的核心問題。

多傳感器資源配置問題是一個有約束的優(yōu)化問題，而遺傳算法一般解決的是無約束的優(yōu)化問題。用遺傳算法解決約束優(yōu)化問題有兩種方式：一種是利用懲罰函數(shù)將有約束的優(yōu)化問題轉(zhuǎn)化成無約束的優(yōu)問題，這種方法缺點是增加了算法適應度函數(shù)的復雜度使算法的計算量增大；一種是在遺傳算法迭代優(yōu)化的過程中加上約束條件的計算，缺點是增加了算法算子的復雜度，在尋優(yōu)過程中效率降低。一般來說，為了減少算法的復雜度，保證算法的搜索效率，將有約束的優(yōu)化問題轉(zhuǎn)換為無約束的優(yōu)化問題是比較常用的方法。但是由于不同類型的天線受限于頻率范圍及后端處理設備處理能力，可探測的目標信號類型、頻段范圍以及可探測的目標數(shù)量上限不同，多傳感器資源配置問題的約束條件比較復雜，不能直接轉(zhuǎn)換成無約束的優(yōu)化問題，所以使用后一種方法解決該問題。

2 國內(nèi)外研究現(xiàn)狀

傳感器規(guī)劃算法主要思想是建立目標價值的模型，根據(jù)目標價值進行搜索尋優(yōu)，合理舍棄目標，實現(xiàn)對高價值目標的有效探測。一般所使用的智能優(yōu)化算法有遺傳算法、蟻群算法、粒子群算法等元啟發(fā)式方法[1]。文獻[2][3]使用了任務拆分聚合和的方法將任務需求轉(zhuǎn)化為規(guī)劃需求效率較高的任務元，但是該方法主要是解決數(shù)據(jù)中繼衛(wèi)星資源有限且任務需求不斷增長的問題，沒有用于解決無人探測平臺的多傳感器任務規(guī)劃問題。文獻[4]討論了多目標的任務規(guī)劃提取方法，在約束空間內(nèi)通過融合不同目標目標規(guī)劃求解任務執(zhí)行策略，文獻中解決多約束問題的方法是基于相應的任務約束構建空間機械臂操作任務的約束空間，并根據(jù)具體的限定值，構建相應的約束子空間，在滿足任務約束的前提下，選擇最小化目標函數(shù)的解。文獻[5]使用有效觀測次數(shù)作為衡量遺傳算法價值的度量，但沒有考慮到傳感器頻繁開關、切換及目標長時間占用一個傳感器所影響的規(guī)劃效率。文獻[6]使用遺傳算法和模擬退火算法來解決空間目標地基監(jiān)視調(diào)度問題這種大規(guī)模調(diào)度問題，但是求解算法復雜，在尋優(yōu)過程中使用模擬退火算法進行全局尋優(yōu)，使用遺傳算法進行局部尋優(yōu)，兩個算法之間的參數(shù)設置復雜且不易尋找算法之間使用的平衡。

本文提出的多傳感器資源配置技術主要根據(jù)目標被捕獲情況對目標進行拆分和捕獲信息的合并，計算目標價值，建立一種新的適應度函數(shù)，使用遺傳算法對資源配置問題進行迭代尋優(yōu)，利用有限的資源高效的搜索出最優(yōu)的傳感器資源配置方法。

3 多傳感器自動規(guī)劃技術

3.1 目標價值分析

本文選用遺傳算法解決多傳感的自動規(guī)劃問題。遺傳算法的搜索過程不是直接作用在探測目標上，而是作用在探測目標的價值建模上，所以要將目標抽象成評價函數(shù)，作為算法的適應度函數(shù)，提供算法尋找最優(yōu)解的依據(jù)。建立遺傳算法的優(yōu)化模型是算法搜索效率的重要因素。

目標的偵測價值由目標的威脅等級，目標可以被偵測的總次數(shù)及目標歷史被捕獲的次數(shù)決定。目標的威脅等級越高，越需要被不斷偵測，其偵測價值越高。目標被偵測到的次數(shù)是根據(jù)目標被捕獲的時間和單位時間內(nèi)目標被偵測的次數(shù)計算得出。目標的歷史捕獲次數(shù)越多，目標的定位識別結(jié)果越準確，當目標的歷史捕獲次數(shù)大于一定的閾值時，目標參數(shù)已基本探明，其活動規(guī)律已基本掌握，再次偵測該目標的意義已經(jīng)不大。假設，目標的威脅等級為Threat，在航線上目標可被探測到的距離為Lkm，無人探測平臺的飛行速度為Vkm/s，每秒對目標的偵測次數(shù)為k，目標最少需要被偵測K 次以上才能進行定位，當目標被偵測M 次時，目標已經(jīng)可以被精確識別定位，再次探測的價值不會增加，那么在不考慮歷史捕獲次數(shù)的目標價值p 的計算公式為：

假設，該歷史捕獲該目標次數(shù)為n，歷史捕獲次數(shù)的閾值為N，那么該目標的價值P 表示為：

在航線上目標可被探測到的距離根據(jù)無人探測搭載傳感器的探測能力范圍、目標的位置及航線確定的。

如圖1 所示，目標T1 在無人探測平臺飛到航路段AB 和航路段BC 上的紅色線段A’B’和B”C’可以被無人探測平臺探測到。當B’B + BB”的長度小于設定的閾值且是在A’B’和B”C’均被使用同一傳感器偵測到時，為了避免傳感器頻繁開關和切換影響到傳感器的偵測效率，對目標被捕獲的航路段進行合并，該目標被偵測的距離變成A’C’；當B’B”的長度大于設定的閾值時或目標在A’B’和B”C’被不同的傳感器偵測且目標T2 和目標T1可以被同一傳感器偵測到時，為避免目標T1 長時間占用同一傳感器，導致目標T2 不能被偵測，可以將目標T1 拆分成目標T1’和T1”，這樣目標T1 和T2 都可以被偵測到。

圖1：目標被捕獲距離示意圖

仿真使用的航線及目標的示意圖如圖2 所示。

圖2：航線與目標示意圖

如圖2 所示，藍色線段表示飛機的飛行航線，紅色的*表示目標的分布，目標T1、T2、T3 的信號類型一致，頻率相近，并且只能使用天線1，天線1 只能同時探測1 個信號，3 個目標的被探測范圍是紅色圓圈所包含的航線。目標T1 的坐標為（-950，1340），信號頻率為10MHz，目標的價值為0.04；目標T2 的坐標為（-1500，1600），信號頻率為10MHz，目標的價值為0.0221640473625973；目標T3 的坐標為（-2000，1100），信號頻率為10MHz，目標的價值為0.0191642030938842。未進行目標拆分時，目標排序后，目標T1 編號為9、T2 編號為10、T3 編號為11，3 個目標只能被探測一個；使用拆分目標方法時，目標T1 被拆分成編號為9、15、27 的目標，T2 被拆分成編號10 和13 的目標，T3 被拆分成編號為11 和12 的目標，其中編號為27、10、13、11、12 的目標均可被探測到，原目標T1、T2、T3 均可被探測到。目標的捕獲情況如表1 所示。

3.2 遺傳算法

遺傳算法是建立在自然選擇和群體遺傳學基礎上的一種非數(shù)值計算優(yōu)化方法。將優(yōu)化問題的解表示成個體，有多個個體組成一個種群。隨機產(chǎn)生一個初始種群，通過對初始種群使用交叉和變異算子不斷進化并使用適應度函數(shù)去評價個體的價值，使種群中的個體向最優(yōu)解的方向收斂，從而搜索到最優(yōu)解。

表1：目標拆分與未拆分被傳感器探測的情況

3.2.1 算法前期準備

多傳感器資源配置的解表示為目標分配的傳感器。假設目標拆分合并后的個數(shù)是N，傳感器的個數(shù)是M，那么遺傳算法的個體表示為1×N 的數(shù)組：

上述公式中，TK表示第K 個目標，ArK表示目標TK使用的傳感器，在初始個體中，該傳感器是從M 個傳感器中隨機選取的能夠偵測目標TK的傳感器，其中rK 是小于M 的符合傳感器約束條件的隨機數(shù)整數(shù)，當rK 是0 時，表示該目標沒有傳感器探測。

其中個體的適應度函數(shù)f(x)用可以被偵測的目標的價值和表示。

3.2.2 算法流程

當完成目標的拆分合并之后，使用遺傳算法進行尋優(yōu)。假設初始種群的大小為NIND，隨機產(chǎn)生NIND 個個體，最大迭代次數(shù)為MaxGen，交叉概率PC，變異概率PM及代溝GGAP。算法的流程圖3 如所示。

圖3：遺傳算法流程圖

在每一次迭代過程中，交叉操作和變異操作不能使用傳統(tǒng)的遺傳算法中的交叉和變異算子直接進行計算，需要考慮約束條件。

交叉操作使用輪盤賭的方式隨機選取GGAP×NIND 的個體，將偵測該目標所使用的傳感器進行替換，但是在替換時需要判斷約束條件，若目標不能被所替換的傳感器偵測，那么從可以偵測該目標的傳感器中隨機選取一個傳感器（包括不被傳感器偵測的情況）去偵測該目標。

變異操作同樣需要從可以偵測該目標的傳感器中選取傳感器，當沒有備選傳感器時，則將該目標設置成不被傳感器偵測。

4 仿真分析

試驗數(shù)據(jù)準備：仿真中設置傳感器個數(shù)為11，目標的個數(shù)為72，計算目標偵測信息，將目標拆分成86 個。為了確定算法的參數(shù)，增加算法的性能，此章節(jié)通過對算法參數(shù)改變的收斂圖和具體的數(shù)據(jù)，分析參數(shù)的變化對算法的影響。為了減小初始種群的質(zhì)量對結(jié)果影響，增加算法的普遍性和可信度，所有試驗結(jié)果均運行25 次取平均值,圖4 表示各個參數(shù)改變的收斂圖。

從圖4(a)可以看出，當GGAP=0.99 時，父代遺傳直接傳遞至子代的優(yōu)秀個體較少，優(yōu)秀基因在種群基因中所占比重較低，算法迭代200 次還無法收斂；當GGAP=0.5 時較多父代基因傳遞至子代，不利于基因的多樣性，收斂雖快，算法易陷入局部最優(yōu)，GGAP=0.7 時算法找到最優(yōu)解價。從圖4(b)中可以看出，當Pc=0.8時算法找到最優(yōu)解，當Pc=0.5 時，基因交互較少，導致算法收斂至局部最優(yōu)解；當Pc=1 時，所有個體都進行基因交換，種群基因穩(wěn)定性較差，收斂慢。從圖4(c)可以看出，當Pm=0.08 時算法找到最優(yōu)解，Pm=0.01 時，由于基因突變概率減小，種群基因依賴于初始種群，不利于產(chǎn)生新的基因，大概率陷入局部最優(yōu)解。從圖4(d)可以看出，當NIND=140 時種群的價值最大，NIND=60 時，算法的結(jié)果最差，種群不能大小，否則基因的多樣性會受到影響。因為種群的大小和目標有關，該實驗設置的目標有72 個，所以種群大小設置成140。一般來說，目標的個數(shù)越多，種群的規(guī)模也應該越大。

圖5 為引入新的目標計算方法得到的試驗結(jié)果。

圖5：拆分合并目標的收斂圖

從表2 中可以看出拆分合并目標增加了整個種群的價值，從表2 可知該方法沒有對算法的收斂速度有大的影響，所以目標的拆分與合并方法提高了傳感器的利用率。

5 結(jié)束語

本研究解決了無人探測平臺多傳感器自動規(guī)劃問題，為了減少傳感器的資源浪費并且是傳感器偵測到更多的目標，提出目標拆分與合并的方法，并使用遺傳算法對該問題進行搜索尋優(yōu)，通過仿真分析了該方法對解決多傳感器自動規(guī)劃問題的結(jié)果及效率，證明了該方法的可行性。

表2：目標拆分與合并算法運行結(jié)果表（Pc=0.9，Pm=0.1，GGAP=0.9，NIND=120）