王 毅 謝瑞煜 楊利斌 趙建軍

（海軍航空大學 煙臺 264001）

1 引言

多UAV聯(lián)合起來協(xié)同完成搜索、偵察、監(jiān)視、打擊等作戰(zhàn)任務，已經在軍事上有初步應用，顯示出十分良好的應用前景，受到越來越多研究者的關注。多UAV對海及對地協(xié)同偵察是很有代表性的問題。偵察問題中，由多UAV同時對給定區(qū)域的多個任務點進行偵察，由于偵察任務較多，需要事先進行任務分群和任務分配，任務分群不僅可以較清楚地反映戰(zhàn)場態(tài)勢，而且可以減少系統(tǒng)的計算量。使UAV之間相互協(xié)作，依據具體的指標要求提高整體的偵察效率［1］。

2 多UAV協(xié)同偵察任務分群

2.1 偵察任務分群建模

多UAV偵察任務分群問題的數學語言描述為，將任務集合T={T1,T2,…,TM}按一定原則劃分為一系列任務簇A={A1,A2,…,AS}，Ai中成員為{Ti1,Ti2,…,Timax} ，i=1,2,…,S ，【2】滿足：

將UAV集合V={V1,V2,…,VN}劃分為不同編隊F={F1,F2,…,Fk}，滿足：

定義“編隊-任務簇”分配矩陣：

2.2 任務分群性能優(yōu)化指標分析

2.2.1 任務群分布指標

2.2.2 任務數量均衡指標

定義任務數量均衡率：

2.2.3 巡航時間均衡指標

要達到比較均衡，應使每架飛機的巡航時間基本相同，根據分類算法得到的子圖分別運用禁忌搜索算法求得其最短偵察路徑ψi,i=1,2,…,S和最短偵察時間 t(ψi),i=1,2,…,S［4］。

定義任務執(zhí)行時間均衡率：

若η接近于1，則上面劃分的任務就可以接受。否則的話，根據t(ψi),i=1,2,…,S的大小用局部搜索算法調整，從而調整各分區(qū)內點的個數，直至任務達到均衡。

2.2.4 總體優(yōu)化函數建模

針對任務分群性能優(yōu)化指標［5～7］，得到任務分群的總優(yōu)化函數值計算方式：

2.3 K均值動態(tài)聚類任務分群算法

聚類分析就是按照一定的規(guī)律和要求對事物進行區(qū)分和分類的過程，在這一過程中沒有任何關于分類的先驗知識，沒有教師指導，僅靠事物間的相似性作為類屬劃分的準則。聚類屬于無監(jiān)督機器學習的范疇。K均值算法的一個特點是在每次迭代中都要考察每個樣本的分類是否正確。若不正確，就要調整，在全部樣本調整完后，再修改聚類中心，進入下一次迭代。如果在一次迭代算法中所有的樣本被正確分類，則不會有調整，聚類中心不會再有變化［8］。

K均值算法能夠使得聚類域中所有樣品到聚類中心距離的平方和最小，其原理為算法首先隨機從數據集中選取k個點作為初始聚類中心，然后計算各個樣本到這k個聚類中心的距離，把樣本歸到離它最近的那個聚類中心所在的類。計算新形成的每一個聚類的數據對象的平均值來得到新的聚類中心，直到新的聚類中心與上一次的中心沒有任何變化，則樣本調整結束［9］。數學模型描述如下：

假設任務集合T={T1,T2,…,TM}，按一定原則劃分為一系列任務簇A={A1,A2,…,AS}，且滿足：

K均值動態(tài)聚類法實現步驟如下：

Step1：選擇k個初始凝聚點，作為類中心的估計；

Step2：對每一個樣本，按照最短距離原則劃歸某個類中；

Step3：重新計算各類的重心；

Step4：跳轉到Step2直到各類重心穩(wěn)定。

2.4 K均值聚類算法優(yōu)化

基本的K均值算法目的是找到使目標函數值最小的K個劃分，算法思想簡單，易實現，而且收斂速度較快。如果各個簇之間區(qū)分明顯，且數據分布稠密，則該算法比較有效，但如果各個簇的形狀和大小差別不大，則可能出現較大的簇分割現象，此外，在K均值算法聚類時，最佳聚類結果通常對應于目標函數的極值點，由于目標函數可能存在很多的局部極小值點，這就會導致算法在局部極小值點收斂，因此初始聚類中心的隨機選取可能會使解陷入局部最優(yōu)解，難以獲得全局最優(yōu)解［10］。

基于模擬退火思想對K均值聚類算法進行優(yōu)化，模擬退火算法是一種啟發(fā)式隨機搜索算法，具有并行性和漸近收斂性。理論上證明它以概率1收斂于全局最優(yōu)，因此，用模擬退火算法對K均值聚類算法進行優(yōu)化，可以改進K均值聚類算法的局限性，提高算法性能?；谀M退火思想，將內能E模擬為目標函數值，將基本K均值聚類算法的聚類結果作為初始解，初始目標函數值作為初始溫度T0，對當前解重復“產生新解→計算目標函數差→接受或舍棄新解”的迭代過程，并逐步降低溫度，算法終止時當前解為近似最優(yōu)解，該算法開始時以較快的速度找到相對較優(yōu)的區(qū)域，然后進行更精確的搜索，最終找到全局最優(yōu)解［11～12］。

2.5 基于模擬退火思想的改進K均值聚類算法

算法實現步驟如下：

Step1：對樣本進行K均值聚類，將聚類劃分結果作為初始解A，根據當前聚類劃分的總類間離散度指標，計算目標函數值；

Step2：初始化溫度T0，令T0=JA。初始化退火速度a和最大退火次數；

Step3：對于某一溫度t，隨機擾動產生新的聚類劃分A'，即隨機改變一個聚類樣品的當前所屬類別，計算新的目標函數值JA'；

Step4：算新的目標函數值與當前目標函數值的差ΔJ=JA'

-JA，判斷ΔJ是否小于0；Step5：若ΔJ＜0，則接受新解，保存聚類劃分A'為最優(yōu)聚類劃分，JA'為最優(yōu)目標函數值，將新解作為當前解；

Step6：若 ΔJ≥0，根據Metropolis準則，以概率p=eΔJ/Kt接受新解，K為常數；

Step7：判斷是否達到最大退火次數，是則結束算法，輸出最優(yōu)聚類劃分，否則根據退火公式對溫程序設計流程圖如圖1所示。

圖1 基于模擬退火思想的改進K均值聚類算法流程

3 仿真分析

假設敵方100個任務點的GPS經緯度坐標如表1所示。

100個任務從左到右按列排序，由于給定的是地理坐標（經度和緯度），我們必須求兩點間的實際距離。設A,B兩點的地理坐標分別為(x1,y1)，(x2,y2)，過A,B兩點的大圓的劣弧長即為兩點的實際距離。以地心為坐標原點O，以赤道平面為XOY平面，以0°經線圈所在的平面為XOZ平面建立三維直角坐標系。如圖2所示。

表1 100個任務點的GPS經緯度坐標

圖2 GPS經緯度坐標轉三維直角坐標示意圖

則A,B兩點的直角坐標分別為

其中地球半徑R=6370km。

A,B兩點的實際距離：

我方有三個基地，經度和緯度分別為(10,60)，(30,60)，(50,60)。假設我方所有無人偵察機的速度都為1000 km/h。三個基地各派出一架飛機偵察敵方任務

首先用K均值聚類法通過聚類分析得到初始分群結果，再采用基于模擬退火思想的改進K均值聚類法得到優(yōu)化分群結果，如表2所示。

規(guī)劃出無威脅情況下算法改進前后的最短航路，為了顯示的直觀方便，選用經緯度坐標。

這樣劃分任務方案，使得巡航時間最短，目標群分布群內比較集中，群間比較分散，且各UAV任務分配比較均衡。

表2 算法改進前后最優(yōu)任務分群方案表

其中，1代表該任務分配給UAV1，在圖中以○表示；2代表該任務分配給UAV2，在圖中以△表示；3代表該任務分配給UAV3，在圖中以☆表示；（）內代表優(yōu)化后的分群方案。

圖3 算法改進前后任務分群與任務規(guī)劃方案

表3 任務分群與各無人機巡航時間表

4 結語

文中針對多UAV協(xié)同偵察任務分群問題，建立了偵察任務分群模型，提出了評價任務分群性能好壞的3個優(yōu)化指標，這些指標代表群內聚集，群間分散，以及任務數量均衡和巡航時間均衡等性能。采用基于模擬退火思想的改進K均值聚類算法進行任務分群和尋找最短路徑。仿真結果表明，基于模擬退火思想的改進K均值聚類算法能夠有效解決任務分群問題，符合部隊的實際情況。