張瑞鵬，馮彥翔，楊宜康

西安交通大學(xué) 自動化科學(xué)與工程學(xué)院，西安 710049

無人機系統(tǒng)具有隱身性能好、自主能力強、可重復(fù)回收利用的特點，在目標偵察、目標打擊、毀傷評估等軍用領(lǐng)域和環(huán)境監(jiān)測、災(zāi)害救援、區(qū)域物流等民用領(lǐng)域均發(fā)揮著重要的作用[1]。在實際應(yīng)用中為了解決單一無人機執(zhí)行復(fù)雜任務(wù)時的不足，更多的采用多無人機協(xié)同方案，把單一無人機作為獨立任務(wù)處理單元，在執(zhí)行任務(wù)時多個無人機利用設(shè)備或功能進行信息整合，實現(xiàn)高效統(tǒng)一的執(zhí)行步驟，并利用相關(guān)設(shè)備完成不同的任務(wù)[2]。因此多無人機協(xié)同控制成為了一項重要的研究內(nèi)容，而多無人機協(xié)同任務(wù)分配問題(Multi-UAV Task Allocation Problem, MTAP)，已成為無人集群協(xié)同自主導(dǎo)航領(lǐng)域需要解決的關(guān)鍵問題[3]。

多無人機任務(wù)分配是指在一定的決策時間內(nèi)，分配異構(gòu)無人機對給定的目標執(zhí)行多個任務(wù)，形成協(xié)調(diào)配合，使系統(tǒng)綜合成本最小化，以達到最優(yōu)效率[4]。在進行多無人機任務(wù)分配時，受多種約束條件的影響，如任務(wù)能力約束、任務(wù)時序約束、路徑安全性約束和規(guī)劃實時約束等。需要綜合協(xié)調(diào)任務(wù)優(yōu)先級、時間約束、可飛行軌跡等，因此多無人機任務(wù)分配問題本質(zhì)上是一個非確定性多項式(Non-deterministic Polynomial-hard, NP-hard)問題[5]。與此同時，待求解問題的規(guī)模(如：無人機數(shù)目、目標和任務(wù)的數(shù)量)也會影響求解過程的復(fù)雜性。目前，一些學(xué)者提出了多種計算可行的多無人機協(xié)同任務(wù)分配算法。文獻[6]通過豐富合同類型的改進合同網(wǎng)拍賣模型實現(xiàn)多無人機多任務(wù)拍賣，利用條件合同機制實現(xiàn)多無人機間的協(xié)調(diào)。文獻[7]提出了改進后的差分進化算法，進行尺度因子和交叉率動態(tài)調(diào)整。文獻[8]改進了和聲搜索算法，引入了一種調(diào)整音高的算子，將和聲搜索的解映射到聚類方法中。文獻[9]提出了基于分工機制的蟻群算法，利用基于任務(wù)能力評估的問題解構(gòu)造策略和基于任務(wù)代價的狀態(tài)轉(zhuǎn)移規(guī)則，改進蟻群算法。文獻[10]提出了一種混合蟻群優(yōu)化算法，將禁忌搜索算法與最大最小蟻群系統(tǒng)集合。文獻[11]基于不確定理論建立以信度函數(shù)為目標的最小風(fēng)險模型,任務(wù)分配時規(guī)避不確定變量標準差較大的目標點。文獻[12]將分布式合同網(wǎng)拍賣算法與模擬退火算法結(jié)合協(xié)調(diào)任務(wù)執(zhí)行次序。文獻[13]利用整數(shù)線性規(guī)劃模型，對遺傳算法進行改進，使用的編碼方案有效減低了算法的復(fù)雜度。此外，當(dāng)任務(wù)之間存在時序關(guān)系或者多個任務(wù)需要同時執(zhí)行時，有可能出現(xiàn)“死鎖”[14]。死鎖是由一系列需要順序執(zhí)行的任務(wù)形成“循環(huán)等待”的關(guān)系引起的，文獻[14]描述了死鎖定義和死鎖產(chǎn)生的必要條件。文獻[15]針對任務(wù)時序約束導(dǎo)致的死鎖問題，提出了一種基于圖論和矩陣轉(zhuǎn)置的死鎖檢測修復(fù)方法。文獻[16]在文獻[15]的基礎(chǔ)上，提出了一種基于自由邊翻轉(zhuǎn)的死鎖修復(fù)方法。任務(wù)執(zhí)行過程中，由于新目標發(fā)現(xiàn)等實時事件的發(fā)生，導(dǎo)致原任務(wù)分配方案失效，需要進行任務(wù)重分配。文獻[17]針對任務(wù)重分配場景，提出了一種匹配策略。文獻[18]使用匹配策略設(shè)計了重組和非重組兩種重調(diào)度方法。文獻[19]考慮了任務(wù)時序?qū)χ卣{(diào)度的影響。

同其他啟發(fā)式算法、智能優(yōu)化算法相比，粒子群算法具有計算簡單、魯棒性好、搜索能力強且收斂速度快的特點，在求解多飛行器協(xié)同任務(wù)分配問題時，具有較大優(yōu)勢[20-25]。文獻[20]基于啟發(fā)信息和沖突消解策略改進標準粒子群算法(Particle Swarm Optimization, PSO)，提高算法收斂性和全局搜索能力。文獻[21]利用混沌機制和變異算子增強量子粒子群算法的尋優(yōu)能力。文獻[22]在粒子矩陣編碼中引入任務(wù)時序約束和多機協(xié)同約束。但因自身結(jié)構(gòu)原因，粒子群算法不可避免的會出現(xiàn)粒子早熟和停滯傾向，容易陷入“局部收斂”，無法得到全局最優(yōu)解。目前解決這個問題有2種方法，一是改進粒子群算法參數(shù)，擴大局部搜索范圍，文獻[23]設(shè)計最優(yōu)粒子更新算法的控制參數(shù)。文獻[24]結(jié)合進化博弈理論動態(tài)調(diào)整粒子群算法3個主要控制參數(shù)，但是這樣的方法效果有限，沒有結(jié)合其它算法的混合算法性能好。另一種方法是利用其它智能優(yōu)化算法的局部搜索能力，幫助粒子群算法跳出局部收斂，文獻[25]將模擬退火算法與粒子群算法相結(jié)合組成混合算法，提高算法尋優(yōu)精度。但是這種方法每次迭代時都需要執(zhí)行跳出局部收斂策略，大幅度增加計算開銷。

多飛行器協(xié)同攻擊地面目標場景中的任務(wù)分配問題，屬于典型的MTAP問題。部分目標需要多架無人機同時打擊，可能會出現(xiàn)死鎖。任務(wù)具有軟時間窗約束，即允許任務(wù)開始執(zhí)行時間違背時間窗約束，但會產(chǎn)生相應(yīng)的偏差代價。基于MTAP問題的數(shù)學(xué)模型，提出一種綜合考慮任務(wù)收益和代價的混合粒子群任務(wù)分配算法。主要創(chuàng)新點包括：

1) 針對同時打擊任務(wù)引起的死鎖問題，提出一種基于多打擊任務(wù)有向圖的死鎖檢測和修正算法。

2) 根據(jù)變鄰域算法強大的解空間搜索能力，提出一種能夠有效跳出局部收斂的策略，并將這種策略嵌入到粒子群算法中。

3) 設(shè)計了一種局部搜索的概率啟動準則，綜合考慮了跳出局部收斂與計算開銷之間的平衡關(guān)系。

4) 設(shè)計不同規(guī)模的仿真實驗，結(jié)果表明同其它智能分配算法相比，混合粒子群任務(wù)分配算法的性能更好、適應(yīng)性更強。

1 MTAP模型

假設(shè)共有Nu架無人機U={U1,U2,…,UNu}和Nt個地面目標T={T1,T2, …,TNt}，無人機數(shù)量遠小于目標數(shù)。需要對每個目標Tj執(zhí)行一次攻擊任務(wù)Mj，因此有Nt個任務(wù)M={M1,M2,…,MNt}。每個打擊任務(wù)需要一架或多架無人機來執(zhí)行。令任務(wù)Mj需要Γ(j)≥1架無人機來執(zhí)行。故M分為單打擊任務(wù)集合Md={Mj∈M|Γ(j)=1}和多打擊任務(wù)集合Mk={Mj∈M|Γ(j)>1}。每個單打擊任務(wù)只需要一架無人機攻擊相應(yīng)目標；多打擊任務(wù)Mj∈Mk需要Γ(j)架無人機同時攻擊相應(yīng)的目標。無人機完成任務(wù)會獲得的綜合收益由摧毀目標的價值、目標打擊時間窗口、無人機飛行航程等因素決定。每架無人機武器載荷有限，只能完成有限個數(shù)的任務(wù)，即攻擊有限個數(shù)的目標。

(1)

(2)

?c∈{2,3,…,mi}

(3)

式中：vi為無人機Ui的飛行速度;TN(·)表示執(zhí)行對應(yīng)任務(wù)所需時間。

同時，無人機Ui執(zhí)行Δi中的單打擊任務(wù)時，無需等待，其到達時間等于任務(wù)執(zhí)行時間。但當(dāng)Ui執(zhí)行的任務(wù)Mci是多打擊任務(wù)時，則需要等待其它執(zhí)行Mci的無人機都到達同一目標點，共同執(zhí)行Mci。令Θ(Mj)={Us∈U|Mj∈Δs}表示需要執(zhí)行任務(wù)Mj的無人機集合，則

?c∈{2,…,mi}

(4)

(5)

式中：b1和b2分別是機會損失系數(shù)和延誤懲罰系數(shù)。

MTAP問題數(shù)學(xué)模型如下：

(6)

(7)

(8)

(9)

xij∈{0,1} ?Ui∈U,?Mj∈M

(10)

2 混合粒子群任務(wù)分配算法

提出一種用于多無人機協(xié)同攻擊地面目標的混合粒子群任務(wù)分配算法，設(shè)計粒子的編碼、解碼與修正過程。針對粒子群算法容易陷入局部收斂的缺點，提出一種基于變鄰域搜索的跳出局部收斂的策略，提高算法的性能和適應(yīng)性。

2.1 標準粒子群算法

在PSO[26]中，每個粒子對應(yīng)一個潛在解，多個粒子組成一個種群。在粒子種群進化過程中，粒子需要追蹤2個極值：個體極值pbest和群體極值gbest。前者是某個粒子搜索到的歷史最優(yōu)解，后者是整個種群當(dāng)前的最優(yōu)解。所有粒子根據(jù)適應(yīng)度函數(shù)更新自身的位置向量和速度向量，盡可能的向最優(yōu)解靠攏。

令粒子k時刻t的位置向量和速度向量分別是和。算法迭代演化過程中，每個粒子的速度和位置根據(jù)如下公式更新：

(11)

(12)

式中：r1和r2都是分布在[0, 1]之間的隨機數(shù)；c1=c2=2分別是個體加速常數(shù)與群體加速常數(shù)；pbestk,t是粒子k當(dāng)前時刻的個體極值，gbestt是當(dāng)前時刻粒子種群群體極值。ω稱為慣性因子，受文獻[27]啟發(fā)，ω由下式計算：

(13)

其中：ωmax和ωmin分別為慣性權(quán)重的最大和最小參考值；Iter和Imaxter分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)；Fold為過去10次迭代最優(yōu)粒子適應(yīng)度平均值，F(xiàn)(gbest)為當(dāng)前迭代最優(yōu)粒子適應(yīng)度。這樣設(shè)置的ω能在搜索過程中自適應(yīng)調(diào)整大小，特別當(dāng)算法陷入局部收斂時，ω將逐步變大，提高局部探索能力。

2.2 編碼、解碼與修正

PSO算法中粒子的位置和速度是連續(xù)性變量，對應(yīng)的解空間也是連續(xù)性的。而MTAP問題的任務(wù)分配解是離散的，因此需要先對粒子的位置和速度進行“離散化”編碼，進而解碼出MTAP的一個潛在解。

2.2.1 編 碼

已知Nt是任務(wù)數(shù)量，Nu是無人機數(shù)量，故粒子維數(shù)其中Γ(j)是執(zhí)行打擊任務(wù)Mj需要的無人機數(shù)量。采用實數(shù)編碼方式，令粒子k的位置Pk和速度Yk都是維實數(shù)向量，每個位置元素Pk[j]限制在1跟Nu+1之間但不等于Nu+1，即Pk[j]∈[1,Nu+1)。同時，為了保證粒子的位置盡可能在[1,Nu+ 1)之間，限定粒子的速度Yk的每個元素Yk[j]∈[-Nu,Nu]。

2.2.2 解碼與修正

令I(lǐng)n(n)為實數(shù)n的整數(shù)部分，De(n)表示n的小數(shù)部分，例如In(4.7)=4，De(4.7)=0.7?？捎昧Ｗ觡的位置元素Pk[j]表示一個任務(wù)分配解。例如對于In(Pk[j])=s，表示將任務(wù)Mj分配給了無人機Us。本文限定：對于具有相同整數(shù)部分的位置元素(將它們分給同一無人機)，其小數(shù)部分的大小順序?qū)?yīng)該無人機執(zhí)行這些任務(wù)的順序。因此從Pk可解碼出無人機Ui的一組任務(wù)序列Δi。

算例1將任務(wù)M1～M9分配給無人機U1～U3，即Nt=9且Nu=3，其中M2、M4和M6是多打擊任務(wù)，且Γ(2)=Γ(4)=Γ(6)=2，其余任務(wù)是單打擊任務(wù)。因此，=12，相應(yīng)PSO算法的解空間是12維。每個粒子的位置元素限定在[1, 4)之間，速度元素限定在[-3, 3]之間。表1給出一個粒子的位置、速度以及對應(yīng)位置元素的整數(shù)部分和小數(shù)部分。從中可以看出M1、M4、M6、M7和M8分配給無人機U1。同時，因為De(Pk[10])。同理可得Δ2=，Δ3= 。很顯然，對于Δ3，M2兩次分配給U3，不滿足約束式(8)。令而超過了無人機U1的任務(wù)上限，不滿足約束式(9)。

表1 一個粒子的速度、位置和對應(yīng)位置分量的整數(shù)部分和小數(shù)部分

算法1 約束修正1.for(1≤t≤Nu)2. while Δt中存在重復(fù)多打擊任務(wù)Mj∈Mk3. 隨機刪除Δt中一個Mj;4. 選擇r∈[1, Nu], s.t. r ≠ t且Δr中無Mj5. 將Mj隨機插入Δr中;6. end7.end8.令Φ=?,Π=?,s=1;9.for(s≤Nt)10. if (Δs>Qmaxs)11. Φ=Φ∪{s};12. elseif(Δs

在算法1中，第1～7行對分配同一無人機的中多打擊任務(wù)進行修正，以滿足約束式(8)；第8～16行計算Φ和Π，Φ表示分配任務(wù)數(shù)超過其上限的無人機序號集合，Π表示對應(yīng)任務(wù)序列還能插入任務(wù)的無人機序號集合；第17～28行是一個while循環(huán)，每次迭代中從Φ中選擇一個無人機序號i，隨機刪除任務(wù)序列Δi中的一個任務(wù)Me，并將Me隨機插入到任務(wù)集合Δj中，Δj中其余任務(wù)相應(yīng)移位，其中j為隨機從Π抽取得到無人機序號，與此同時更新集合Φ和Π。最終得到的新任務(wù)序列Δ′i(i∈{1, 2, …,Nu})，滿足約束式(9)。

經(jīng)算法1修正得到的任務(wù)分配解滿足約束式(8)和式(9)，但可能出現(xiàn)“死鎖”，即不同無人機執(zhí)行多打擊任務(wù)時，出現(xiàn)循環(huán)等待的現(xiàn)象，導(dǎo)致任務(wù)無法繼續(xù)執(zhí)行。比如，算例中任務(wù)分配解Δ經(jīng)算法1修正后變成Δ′={Δ′1,Δ′2,Δ′3}，其中Δ′1=，Δ′2=，Δ′3=，Δ′可用圖1描述，灰色圓形表示單打擊任務(wù)，白色圓形表示多打擊任務(wù)。很明顯，無人機U1需等待U2到達T6后，才能執(zhí)行多打擊任務(wù)M6；但U2需要先打擊目標T4(即執(zhí)行任務(wù)M4)，才能到達T6；而執(zhí)行任務(wù)M4又需要無人機U1先到達目標T4，這與U1的執(zhí)行任務(wù)序列相矛盾。即U1和U2陷入無限循環(huán)等待，出現(xiàn)了死鎖[14]。

圖1 任務(wù)分配解示意圖

本文中的死鎖只與多打擊任務(wù)有關(guān)，因此采用有向圖G=來表征死鎖，其中V={j|Mj∈Mk}表示多打擊任務(wù)節(jié)點，E中的弧線(i,j)表示存在一架無人機先執(zhí)行Mi再執(zhí)行Mj。根據(jù)文獻[15]，G中的強連通分量(即回路)表示死鎖。比如上述修正解Δ′的有向圖G如圖2(a)表示，其中頂點4和6組成回路，因此任務(wù)M4與M6組成了死鎖，這與上述分析結(jié)果相同。可用DFS算法(深度優(yōu)先搜索)檢測G的回路[28]。

根據(jù)文獻[16]，本文針對多打擊任務(wù)的死鎖問題，提出了一種基于多打擊任務(wù)有向圖的死鎖檢測和修復(fù)方法，如算法2所示。輸入為滿足約束式(8)和式(9)的任務(wù)分配解Δ′={Δ′k|k∈{1, 2, …,Nu}}，輸出為無死鎖可行解Δ″={Δ″k|k∈{1, 2, …,Nu}}。

圖2 多打擊任務(wù)有向圖

算法2 死鎖修正1.構(gòu)建Δ'對應(yīng)的有向圖G=;2.利用DFS算法檢測是否存回路,回路信息存入列表RΔ';3.while(RΔ'≠?)4. 對RΔ'中各弧線根據(jù)出現(xiàn)次數(shù)排序;5. 輪盤賭法選取換位弧線(i, j);6. fork∈{1, 2, …, Nu}7. if 根據(jù)Δk, Uk先執(zhí)行Mi再執(zhí)行Mj8. 交換Δk中Mi和Mj的位置;9. end10. end11. 更新Δ'對應(yīng)的有向圖G = ;12. DFS算法檢測回路,更新列表RΔ';13. end14. 輸出無死鎖可行解{Δ″kk∈{1, 2, …, Nu}}

在算法2中，第1～2行構(gòu)建有向圖，將DFS算法檢測到的回路信息保存在RΔ′中；第3～13行修正死鎖，根據(jù)RΔ′中出現(xiàn)的次數(shù)使用輪盤賭法選取弧線(i,j)，進行換位操作，交換一些任務(wù)序列Δ′k中多打擊任務(wù)Mi和Mj的位置。類似于文獻[16]中的分析，算法2在有限運算后輸出一個無死鎖的任務(wù)分配解。因為算法2僅調(diào)整任務(wù)序列Δ′k中一些多打擊任務(wù)的位置，不會在Δ′k中增加或者刪除任務(wù)，因此得到的無死鎖解仍然滿足式(8)和式(9)。

利用算法2對算例中的Δ′進行死鎖檢測和修復(fù)，可知RΔ′={(6, 4), (4, 6)}。選擇弧線(6, 4)，交換Δ′1中M6和M4的位置，得到新的有向圖G′，如圖2(b)所示。相應(yīng)的新的無死鎖解是Δ″1= ，Δ″2= ，Δ″3= 。

2.2.3 適應(yīng)度值計算

對于粒子k，首先將其位置向量解碼為1組任務(wù)分配解Δ，然后利用算法1和算法2確保Δ滿足約束條件且無死鎖。相應(yīng)的適應(yīng)度值F(k)由式(1)確定，即

(14)

式中，F(xiàn)(k)越小，從粒子k解碼出的任務(wù)分配解的質(zhì)量越好。

2.3 變鄰域搜索跳出局部收斂策略

為了提高PSO算法的性能，防止算法陷入局部收斂，本文提出一種基于變鄰域搜索(Variable Neighborhood Search, VNS)算法的局部搜索策略，使算法具備跳出局部收斂的能力。

2.3.1 鄰域結(jié)構(gòu)

VNS算法的基本思想是在搜索過程中改變鄰域結(jié)構(gòu)集，從而拓展搜索范圍，獲得最優(yōu)解[29]。

令Pk表示粒子k的位置向量，根據(jù)解碼和算法1可從Pk得到1組任務(wù)分配解，即Pk決定k對應(yīng)解的質(zhì)量。因此，本文采用以下3種鄰域結(jié)構(gòu)，修改位置向量Pk尋找更好的鄰域解：

2) 第2鄰域結(jié)構(gòu)(插入鄰域)：在Pk中隨機選擇2個位置i和j且i

算法3利用第1鄰域結(jié)構(gòu)(交換鄰域)搜尋局部最優(yōu)解。首先令i= rand(1,Nt)和j= rand(1,Nt)都為區(qū)間[1,Nt]的任一整數(shù)，并設(shè)當(dāng)前鄰域搜索次數(shù)N為0。Nmax表示最大搜尋次數(shù)。算法的主要組成部分是while循環(huán)(第2～14行)，在每次迭代中N

算法3 第1鄰域結(jié)構(gòu)1.Let i = rand(1, Nt), j = rand(1, Nt), N= 0//初始化2.while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. P'k=(Pk, i, j) ∥將Pk[i]和Pk[j]互換,得新的位置P'k8. P'k與粒子k的速度結(jié)合得新的粒子k';9. end10. if(F(k) > F(k'))11. 將粒子k替換為k'; ∥粒子k性能差,替換為k'12. end 13. N++14. end15. 輸出粒子k';

算法4 第2鄰域結(jié)構(gòu)1.Let i = rand(1, Nt), j = rand(1, Nt), N= 0;2.while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. if(j > i)8. P'k =(Pk, i, j) ∥將Pk[j]插入位置i處得新位置P'k9. else10. P'k=(Pk, j, i)11. end12. P'k與粒子k的速度形成新的粒子k';13. end14. if(F(k) > F(k'))15. 將粒子k替換為k'; ∥粒子k性能差,替換為k'16. end17. N++;18. end19. 輸出粒子k';

算法4利用第2鄰域結(jié)構(gòu)(插入鄰域)搜尋局部最優(yōu)解，其算法步驟與算法3相似，主要區(qū)別在于算法4需要判斷隨機選擇的位置序號i和j的大小，將較大位置序號的元素插入較小位置序號(見第6～12行)，形成新的位置向量P′k。

算法5使用第3鄰域結(jié)構(gòu)(逆轉(zhuǎn)鄰域)搜索局部最優(yōu)解，將隨機選擇的序號i和j之間的片段逆轉(zhuǎn)重排(第6～12行)，直至搜索到局部最優(yōu)解。

算法5 第3鄰域結(jié)構(gòu)1.令 i = rand(1, Nt), j = rand(1, Nt), N = 0;2. while(N < Nmax)3. while(i = j)4. i = rand(1, Nt), j = rand(1, Nt)5. end6. if(Pk[i]≠Pk[j])7. if(j > i)8. P'k=(Pk, i, j) ∥Pk中位置i、j之間元素逆轉(zhuǎn)重排9. else10. P'k = (Pk, j, i)11. end12. P'k與粒子k的速度形成新的粒子k';13. end14. if(F(k) > F(k'))15. 將粒子k替換為k'; ∥粒子k性能差,替換為k'16. end17. N++;18. end

2.3.2 局部搜索啟動概率準則

為了綜合平衡算法跳出局部收斂能力與整體計算開銷，以概率rk啟動對粒子k的變鄰域局部搜索，rk由下式計算

(15)

啟動概率rk由當(dāng)前粒子k的適應(yīng)度值F(k)和全局最優(yōu)值F(gbest)決定。當(dāng)F(k)≤F(gbest)時，由式(15)可知rk=1，此時算法很有可能已陷入了局部收斂，因此必須要啟動變鄰域搜索過程，跳出局部收斂；當(dāng)F(k)>F(gbest)時，粒子k的性能較差，距離全局最優(yōu)解較遠，此時是否會啟動局部搜索由概率rk=S決定；分析可知k性能越差，越不可能陷入到局部收斂中，相應(yīng)的啟動概率rk越小，同時將最小啟動概率設(shè)置為0.01。

通過此概率啟動準則，一方面對陷入局部最優(yōu)的粒子進行變鄰域搜索，跳出局部收斂；另一方面，對距離全局最優(yōu)解較遠的粒子，降低啟動局部搜索的概率，實現(xiàn)跳出局部最優(yōu)與計算開銷的合理平衡。

2.3.3 跳出局部收斂的變鄰域搜索算法

利用上述3種變鄰域結(jié)構(gòu)，提出一種VNS局部搜索算法，實現(xiàn)跳出PSO算法可能陷入的局部收斂。如算法6所示，輸入為粒子k的位置Pk，輸出為局部最優(yōu)解對應(yīng)的粒子k′。

在算法6中Nmax表示某一鄰域結(jié)構(gòu)內(nèi)最大搜索次數(shù)，本文采用了3級鄰域結(jié)構(gòu)，因此最高鄰域等級Klevel_max=3。令r= rand(0,1)為0～1之間的隨機數(shù)，啟動概率rk由式(11)確定。若r≥rk，則不啟動變鄰域搜索，直接輸出原粒子k。VNS搜索過程如第3～23行所示，當(dāng)鄰域搜索次數(shù)N≤Nmax時，進行第K變鄰域結(jié)構(gòu)局部搜索(第6～21行)。在此過程中，若新粒子k′優(yōu)于原粒子k，用k′替換k，跳出當(dāng)前循環(huán)過程，并初始化N和K(第15～21行)；若搜索Nmax次后仍未找到更優(yōu)粒子，則需要提升鄰域等級(第22行)；若當(dāng)前鄰域等級大于Klevel_max時仍未發(fā)現(xiàn)更優(yōu)粒子，直接輸出原粒子k。

算法6 VNS局部搜索算法1.Let Nmax= n,Klevel_max= 32.if (r = rand(0, 1) < rk)3. K = 1;4. while (K≤Klevel_max)5. N=1; ∥初始化當(dāng)前鄰域搜索次數(shù)6. while (N≤Nmax)7. switchK:8. case 1: ∥啟動第一鄰域搜索9. 執(zhí)行算法3,輸出粒子k'10. case 2: ∥啟動第二鄰域搜索11. 執(zhí)行算法4,輸出粒子k'12. case 3: ∥啟動第三鄰域搜索13. 執(zhí)行算法5,輸出粒子k'14. end15. if (F(k') < F(k)) ∥找到局部最優(yōu)解16. 將粒子k替換為k';17. K = 0; ∥復(fù)位鄰域等級18. break; ∥跳出當(dāng)前while循環(huán)19. end20. N = N + 1 ∥完成一次鄰域搜索21. end22. K = K + 1; ∥增加相應(yīng)鄰域等級23. end24. end25. 輸出粒子k;

2.4 混合粒子群任務(wù)分配算法設(shè)計

本文提出了一種結(jié)合標準PSO算法與VNS搜索跳出局部收斂策略的協(xié)同任務(wù)分配混合粒子群算法，算法流程圖如圖3所示。具體步驟如下所示：

步驟1初始化種群，設(shè)置最大迭代次數(shù)Tmax，經(jīng)過解碼和修正過程，計算當(dāng)前種群的全局極值和每個粒子的個體極值。

步驟2根據(jù)式(15)計算每個粒子k的局部搜索啟動概率rk，利用算法6進行VNS搜索，用生成的更優(yōu)粒子替代原粒子。

步驟3計算每個粒子k的適應(yīng)度值F(k)，更新k的個體極值與全局極值。

圖3 協(xié)同任務(wù)分配混合粒子群算法流程圖

步驟4根據(jù)式(11)和式(12)更新每個粒子的位置和速度。

步驟5判斷當(dāng)前迭代次數(shù)是否大于Tmax，若否，則返回步驟2。

步驟6輸出全局極值和相應(yīng)的任務(wù)分配解。

2.5 基于匹配策略的局部任務(wù)重分配方法

針對新目標發(fā)現(xiàn)等實時事件導(dǎo)致的初始分配計劃失效問題，結(jié)合2.4節(jié)中的協(xié)同任務(wù)分配混合粒子群算法，提出了一種基于匹配策略的局部任務(wù)重分配方法。匹配策略思想首先定義重分配范圍(以時間窗的形式)，然后重新調(diào)度在重分配范圍內(nèi)的任務(wù)，最后將得到的局部調(diào)度計劃集成到初始任務(wù)分配方案中，這樣能保證初始任務(wù)分配計劃的穩(wěn)定性，還減小了計算開銷，縮短了重分配用時[18]。

考慮發(fā)現(xiàn)新目標場景下的任務(wù)重分配。令Tn={T1n,T2n,…,TNn}表示ts時刻新發(fā)現(xiàn)的Nn個目標，對應(yīng)的打擊任務(wù)集合是Mn={M1n,M2n,…,MNn}。新任務(wù)Mjn需要Γ(jn)架無人機執(zhí)行，對應(yīng)的時間窗口[S(Mjn),C(Mjn)]。根據(jù)文獻[19]，定義重分配范圍[tstart,tend]，其中tstart=ts，tend=max{C(Mjn)|Mjn∈Mn}。需要將Mn中的新任務(wù)在時間窗[tstart,tend]內(nèi)分配給各個無人機，但這樣會影響初始計劃中[tstart,tend]內(nèi)的任務(wù)Mo(不包括tstart,tend點正在執(zhí)行的任務(wù))。因此，重分配的任務(wù)集合MR=Mo∪Mn。

圖4(a)表示一個任務(wù)分配方案的甘特圖，可知Δ1= ,Δ2= ,Δ3= , 假設(shè)在ts= 12發(fā)現(xiàn)新目標Ts，對應(yīng)任務(wù)Ms的時間窗是[15, 28]，故相應(yīng)的重分配范圍是[12, 28]。注意在tend時刻，M4正在執(zhí)行。按照初始計劃，此時段內(nèi)任務(wù)Mo= {M5,M6,M7}，因此需要重分配的任務(wù)集合是MR= {M5,M6,M7,Ms}。根據(jù)tstart之前的任務(wù)分配計劃，更新各個無人機的起始時間和地點，將MR中的任務(wù)分配給無人機，并將所得結(jié)果與原計劃tend后的方案結(jié)合起來，共同組成重分配結(jié)果。這樣的簡化調(diào)度問題減少了待分配任務(wù)數(shù)量，縮短重分配用時，保留部分原分配計劃。

圖4 任務(wù)分配甘特圖

現(xiàn)證明重分配任務(wù)方案Δ*是無死鎖的。假設(shè)對應(yīng)的多打擊任務(wù)有向圖G*具有回路。因為MR和∪i∈{1,2,…,Nu}Δvi對應(yīng)的多打擊任務(wù)有向圖都是無回路的(這由混合粒子群的死鎖修復(fù)算法決定)，則V′中肯定同時包含了MR和∪i∈{1,2,…,Nu}Δvi中的多打擊任務(wù)，且存在任務(wù)Mr∈MR∩V′以及Mv∈∪i∈{1,2,…,Nu}Δvi∩V′，使得弧線(Mv,Mr)∈E′，即有一架無人機先執(zhí)行Mv再執(zhí)行Mr。然而根據(jù)時間軸關(guān)系，這是不可能的。因此G*無回路，重構(gòu)結(jié)果Δ*無死鎖。

3 算法實例與分析

分別用遺傳算法(Genetic Algorithm, GA)[30]、模擬退火算法(Simulated Annealing, SA)[31]、粒子群算法(PSO)[26]、粒子群與模擬退火結(jié)合的混合算法(PSO+SA)[25]和本文提出的混合PSO算法求解多無人機協(xié)同任務(wù)分配問題，并對比分析實驗結(jié)果。驗證平臺為具有Intel Core i9-9900K處理器、32 GB內(nèi)存的PC機，所有算法在MATLAB R2021a平臺編譯運行。

實驗1考慮5架無人機協(xié)同攻擊20個地面目標的任務(wù)分配場景。無人機和攻擊目標的參數(shù)如表2和表3所示。為了簡化實驗場景，假設(shè)無人機起飛后均勻速飛行。每個目標具有不同打擊時間窗口和打擊用時。

設(shè)定上述5種算法的最大迭代次數(shù)均為800次，均衡考慮各受益和代價的影響，令目各項增益系數(shù)a1=a2=a3。同時設(shè)2種時間偏差的代價相同，即b1=b2=1。5種算法的任務(wù)分配結(jié)果如表4所示，括號中的數(shù)據(jù)為各無人機執(zhí)行相應(yīng)任務(wù)的無量綱時間，比如12(7.78)表示無人機于7.78時刻執(zhí)行任務(wù)12。從表4可看出，使用本文死鎖檢測和修復(fù)算法，多架無人機在同一時刻執(zhí)行同一多打擊任務(wù)，不會引發(fā)死鎖。與其他4種算法相比，提出的混合PSO適應(yīng)度值最小，性能最好。

表2 無人機參數(shù)

表3 任務(wù)目標參數(shù)

圖5為5種算法適應(yīng)度變化折線圖，可以看出GA算法具有較差的局部搜索能力和進化能力，所得結(jié)果與其他4種算法相比有明顯差距；SA算法在一開始優(yōu)化速度較快，但很快陷入了局部收斂；PSO算法在起始階段具有較快的優(yōu)化速度，但在中期陷入了局部收斂；PSO+SA算法雖具有一定的跳出局部收斂的能力，但收斂速度較慢，仍然會陷入局部收斂，所得適應(yīng)度值也非最佳；本文提出的混合粒子群算法采用了局部搜索啟動概率準則，不僅在起始階段具有并不低于PSO算法的優(yōu)化速度，還能不斷的跳出局部收斂，所得的結(jié)果也是最優(yōu)的。

表4 任務(wù)分配結(jié)果[25,30,31]

圖5 5種算法適應(yīng)度對比

實驗2為了驗證提出的概率啟動準則具有平衡跳出局部收斂與計算開銷的能力，本文對于實驗1的場景，設(shè)置3種情形：不執(zhí)行跳出局部收斂策略、每次迭代執(zhí)行跳出局部收斂、采用本文提出的概率啟動準則。共進行5次實驗，計算平均適應(yīng)度值和平均算法運行時間。

實驗結(jié)果如表5所示，從中可知：與不執(zhí)行跳出局部收斂策略的情形相比，本文的概率啟動準則跳出局部收斂策略使得解的性能提升324% (≈(182.82-43.08)/43.08)；與每次都執(zhí)行跳出局部收斂策略相比，概率啟動準則在節(jié)約84% (≈(4642-732)/4642)時間的前提下，解的性能僅下降4%(≈(43.08-41.43)/41.43)。因此，本文提出的概率啟動準則實現(xiàn)了計算開銷與跳出局部收斂的平衡。

表5 不同跳出最優(yōu)策略實驗統(tǒng)計結(jié)果

實驗3為了綜合驗證本文提出的混合PSO算法求解MTAP問題的能力，本文將上述5種算法用于不同規(guī)模的MTAP實驗，所得結(jié)果如圖6所示。其中，MTAP0305表示3架無人機協(xié)同打擊5個目標的任務(wù)場景。5種算法均進行5次實驗，并分別統(tǒng)計所得解目標值的3項指標：最小值、平均值和方差。從圖6可以看出，對于小規(guī)模問題(比如MTAP0305)，由于解空間較小，5種算法求解性能相似，均能得到最優(yōu)解；隨著問題規(guī)模的增大，不同算法的表現(xiàn)差異也顯著增大，但本文提出的混合PSO任務(wù)分配算法在不同規(guī)模的MTAP問題中都取得了最好的解，適應(yīng)性最好。

圖6 不同規(guī)模MTAP實驗對比

實驗4針對發(fā)現(xiàn)新目標導(dǎo)致初始任務(wù)分配方案失效問題，驗證本文提出的基于匹配策略的局部任務(wù)重分配算法的有效性。設(shè)初始任務(wù)分配方案Δ的甘特圖如圖7(a)所示，將10個任務(wù)M1～M10分配給了3架無人機，其中M2、M5和M8是多打擊任務(wù)。假設(shè)在ts=15時刻，發(fā)現(xiàn)新目標Tn={T11,T12}，新增加任務(wù)Mn={M11,M12}，它們的參數(shù)如表6所示，可知只有M12是多打擊任務(wù)。根據(jù)3.5節(jié)中的任務(wù)重分配方法，因max{C(Mjn)|Mjn∈Mn}=40，故重分配范圍為[15, 40]，相應(yīng)的重分配任務(wù)集MR={M1,M4,M5,M11,M12}。注意tend時刻任務(wù)M6未完成，因此M6不屬于MR。初始任務(wù)分配方案在tend之后序列Δv1= ，Δv2= ，Δv3= 。

圖7 任務(wù)重分配實驗甘特圖

表6 新任務(wù)參數(shù)

4 結(jié) 論

針對多無人機協(xié)同任務(wù)分配問題，建立了綜合考慮飛行航程、任務(wù)收益、任務(wù)完成時間窗口的混合粒子群任務(wù)分配算法。首先設(shè)計了滿足多打擊任務(wù)約束條件的粒子編碼與解碼過程，針對可能存在的死鎖問題，設(shè)計了一種基于多打擊任務(wù)有向圖的快速死鎖檢測修復(fù)算法，實現(xiàn)了粒子群算法解的離散化。然后對于標準粒子群算法容易陷入局部收斂的問題，設(shè)計了一種基于變鄰域搜索算法的跳出局部收斂策略，同時提出局部搜索概率啟動準則，實現(xiàn)了跳出局部收斂和計算開銷的平衡。最后，將所提出的跳出局部收斂策略與粒子群算法相結(jié)合，得到適用于MTAP問題的混合粒子群算法。對于新目標發(fā)現(xiàn)導(dǎo)致的初始計劃失效問題，本文也設(shè)計了一種基于匹配策略的局部任務(wù)重分配方法。

通過設(shè)計仿真實驗，與現(xiàn)有其他4種智能任務(wù)分配算法相比較，本文提出的混合粒子群算法在保證優(yōu)化速度的同時，還具有不斷跳出局部收斂的能力，因此會獲得較好的任務(wù)分配結(jié)果，性能表現(xiàn)顯著優(yōu)于其他算法。