面向無人機路徑規劃的多目標粒子群優化算法

蘇子美，董紅斌

哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001

無人機路徑規劃的應用領域正變得越來越廣。在軍事領域方面無人機可以在戰場物資投放、作戰資源調度等方面使用[1?5]，無人機參與作戰可大量減少戰爭傷亡，大大提高作戰效率與成功率。在民用方面使用無人機進行快遞配送、救災物資投放和噴灑田地[6]也成為新的目標，因此在此方面所應用的技術具有巨大的市場潛力。

無人機在以上方面應用所產生的問題都可以歸結為無人機路徑規劃問題，這類問題是一個NP難問題(NP-hard problem)，目前使用進化算法可以在這類問題上得到很好的解決[7?8]。文獻[2]針對該問題提出了兩階段策略，使用貪心算法與遺傳算法作為一、二階段進行優化；文獻[5]使用了單目標進化算法應用于無人機追捕罪犯；文獻[9]使用極端擁擠的NSGA-II(EC-NSGA-II)作為第一階段，求得近似Pareto前沿的極端解作為多目標遺傳算法的初始粒子；文獻[10]將MOEA/D(基于分解的多目標優化)引入粒子群優化算法中以更好地平衡多個目標函數解；文獻[11]將基于集的粒子群優化算法(S-PSO)和綜合學習粒子群優化(CLPSO)引入無人機路徑規劃問題中，其中，使用多目標粒子群優化算法求得的解，其多樣性好且收斂速度快，因此在無人機路徑規劃上表現會更加有前景[12?13]。

1 無人機路徑規劃問題

假設無人機飛行在足夠高的上空可以忽略障礙且用戶位置不變的條件下，無人機路徑規劃的多種問題都可以歸結為帶時間窗的車輛路徑規劃(vehicle routing problems with time window，VRPTW)問題。在VRPTW問題中的每個實例下，存在一個無人機基地和若干待滿足需求的用戶，且在固定的位置。每架無人機從無人機基地出發，經過可滿足用戶后回到無人機基地。當一個路徑規劃方案可以使所有用戶按時得到滿足，且無人機可回到無人機基地，則說明路徑規劃方案可行。

1.1 VRPTW問題的形式化表示

VRPTW可以形式化表示為一個完整有向帶權圖G=(C,E)中的優化問題，如下所示。

1)頂點集C：頂點C包括無人機基地點和用戶點。其中當i=0時，c0為圖的根，表示無人機基地。當i∈[1,n],n為用戶數，ci表示用戶。

2) 邊集E：每條邊分別表示2個頂點之間的鏈接，并且有一個距離屬性。形式化的表示即在圖G中，邊集E={〈ci,cj〉|ci,cj∈C,i≠j}，每個邊〈ci,cj〉由從變量ci到變量cj之間的歐幾里得距離dij表示，其中dij=dji，且距離與時間需要做等價替換。

對于每個用戶ci∈C，i∈[1,n]的變量細節如表1所示。

表1 用戶細節變量

對于無人機基地c0的變量細節如表2所示。

表2 無人機基地細節變量

設無人機基地的無人機vr∈V，其中{r∈[1,|V|]|r∈N}。設計能服務所有用戶的路線需要二進制決策變量。

二進制決策變量bri由服務于用戶ci的無人機vr來表示。

以RC101為例，如圖1所示，集中的點代表無人機基地位置，其余點代表用戶位置，不同顏色代表不同的無人機出行路線，此圖1表明調用了8架無人機完成了此次任務。

圖1 RC101路徑規劃圖

1.2 解的形式

該問題中頂點集C={0,1,···,n}，0表示無人機基地，1～n代表用戶。每個解xi包含一組可行路徑。其中表示解i中的第j條路徑，由地的頂點序列組成，并且NVi表示在解xi中使用的從無人機基地到一組可服務用戶再回到無人機基無人機數量。

在使用該算法求解VRPTW時，會得到一組可行解，每個解xi包含一組可行路線,。其中表示解i中的第j條路線，并且N表示Vi在解i中使用的無人機數量。解可以由有向帶權圖、鄰接表、鄰接矩陣進行表示，如圖2—圖4所示。以有5個用戶為例，頂點集表示為C={0，1，2，···, 5},解的路線集表示為,其中

圖2 示例有向帶權圖

圖4 示例鄰接矩陣

圖3 示例鄰接圖

1.3 約束條件

在VRPTW問題中，有6個約束條件，其中：i為路段起點，j為路段終點，n為用戶加無人機基地總數，r為調用的第r架無人機，|V|代表調用無人機數。

1)邊與頂點的約束：恰好有一條路徑進入和離開與用戶相關聯的每個頂點，這樣后面的公式表示才是成立的。

2)每名用戶只能使用一架無人機，且所有路線從無人機基地開始。

(3)無人機總容量約束：表示每架無人機的負載不得超過其承載能力。

式中qi為用戶ci的需求。

4)無人機工作最長時間約束。

5)每個用戶完成時間的約束。

式中：dij為用戶ci和cj之間的旅行時間；sj為服務用戶cj的時間。

6)每個用戶的時間窗約束。

式中：tj為可以到用戶cj的時間；lj為無人機vr最晚可以開始服務用戶cj的時間。

1.4 目標函數

根據VRPTW的特點，設定了包含沖突的5個目標函數。

1)調用無人機數f1與路線總距離f2。

式(9)表示調用無人機數，式(10)表示路線總距離，在文獻[9]中證明無人機數量與路線總距離成正比，但路線總距離與無人機等待時間為一對沖突函數。

2)路線總時間f3。

式(11)表示路線總時間。總時間與車輛數量在文獻[9]中被證明為一對沖突函數。

3)無人機等用戶總時間f4與用戶等無人機總時間f5。

式中：|V|為使用的無人機架數；n為第r架無人機服務的用戶數。

式(12)表示無人機等用戶總時間，式(13)表示用戶等無人機總時間，這2個公式是本文提出的一對沖突函數。

1.5 多目標優化

多目標優化問題可以用函數表示為

式中：RM為目標空間；?為決策空間；目標函數F可將決策空間映射到目標空間。

與單目標優化問題不同，多目標優化中的不同目標之間一般需要存在沖突，因此用單目標優化算法往往效果不佳。

在多目標優化問題中，?2個解x，y∈?，當且僅當對于?i∈{1,2,···,M}，fi(x)≤fi(y)且?j∈{1,2,···,M}，fj(x)＜fj(y)，則x占優，x支配y，與y相比，x是Pareto最優解。使用多目標優化算法可以求得Pareto最優集，Pareto最優集是所有Pareto最優解的集合。

2 兩階段MOCS-PSO/D算法

本文提出的MOCS-PSO/D框架是基于MOEA/D的框架，將多個目標函數進行歸一化處理，并使用S-PSO來對VRPTW問題的解進行基于集合和概率的表示，同時結合CLPSO來對粒子進行更新。最后，根據實際的應用情況，對局部搜索策略進行調整，以減少調用的無人機架數。

兩階段算法流程如圖5所示。

圖5 兩階段算法流程圖

2.1 粒子速度和位置的表達

在VRPTW問題中，利用鄰接矩陣來表示每個粒子的位置，離散的位置表示方式可以適用于S-PSO的位置更新和速度更新公式中。每個粒子的位置由鄰接矩陣表示，粒子h在步驟k的位置可以由表示，粒子的位置可以擴展的表示成，每個維表示一個邊集，每個邊集有2個邊，每個邊由從無人機基地和用戶集中選取2個點組成，其中 δ為當前維度，δ相鄰的前后2個點ci,cj∈{1,2,···,δ?1,δ+1,···,m}，且ci≠cj。該邊集由式(15)表示。

根據每個粒子的位置可以畫出一個完整的有向哈密頓圓。其中每個有向哈密頓圓的集合代表要調度的每架無人機在滿足約束條件下的出行路線。

速度由邊與其出現概率表示，每個粒子的第m維的速度分量用表示。粒子h在步驟k時在m維空間上的速度定義為：,。δ維的邊概率集由式(16)表示。

集合Aδ中的邊都是與有向完全圖G中的狀態δ相鄰的狀態組成的狀態對。其中，邊〈ci,cj〉出現的概率用p(ci,cj)表示，p(ci,cj)∈[0,1]。在后續對邊〈ci,cj〉進行更新時，將根據此概率進行選擇。如果p(ci,cj)=0，則表示uhkδ忽略邊〈ci,cj〉。

2.2 第一階段(最近鄰隨機混合算法)

初始化階段將混合使用最近鄰算法和隨機算法兩種啟發式算法進行路徑初始化。

NNH是一種貪心的初始化種群候選解的方法，是在實際設計算法時常用的一種方法。將用戶集C和無人機基地集D的數據進行讀取，利用NNH建立可行解。具體方法如下。

1)初始化從無人機基地開始的路線，遞歸地將最近的可滿足用戶添加到路線中，直到不存在可滿足用戶，則回到無人機基地。已滿足的用戶移除用戶集。

2)如果用戶集C不為空，則轉到1)，否則終止算法。

隨機算法將每次選擇的用戶更改為隨機可滿足用戶即可。也可將2種算法混合使用。

2.3 第二階段(MOCS-PSO/D算法)

本文針對VRPTW問題的MOCS-PSO/D框架將階段一得到的結果作為初始值進行優化。

MOCS-PSO/D框架的執行詳細過程如下。

1)初始化：初始化種群大小Psize、目標函數個數N、每個目標函數上的采樣個數H，鄰居個數T，最大迭代次數gmax，學習率c1、c2，隨機數σ1、σ2，線性速度更新權重w，外部更新集EP。生成均勻權重向量，同時使用第一階段中的解作為初始化粒子。

2)求值和規范化：求得所有粒子以獲得目標向量。更新每個目標的上下限。相應地，規范化每個粒子的目標向量。

3)學習者和存檔更新：使用粒子的權重向量和其鄰域中所有新生成的解以MOEA/D方式更新每個粒子的學習者。使用所有新解基于Pareto優勢更新外部存檔EP。

4)粒子群更新：對每一個粒子，在CLPSO的速度更新公式中執行基于元素的運算來更新其速度，然后構造一個新的解來更新其位置。

5)局部搜索策略：再對每一個粒子進行局部搜索策略，不斷選擇用戶最少的路線，試圖將其中的用戶插入其他路線中，依舊可滿足約束條件。

6)額外粒子群更新：如果某粒子多次沒有進行更新，則對其進行額外粒子群更新策略，使用基于元素的算法運算來更新其速度，然后構造一個新的解來更新其位置。

7)終止：如果滿足停止條件，則停止并輸出外部儲存集EP;否則，轉到2)。

2.3.1 速度更新每次迭代k次時每個粒子的位置。CLPSO速度更

CLPSO算法是PSO算法的一個變種，其采用一種新的速度更新規則來防止解的過早收斂，在每次更新時只采用局部最優解進行更新，而不使用全局最優。用于更新VRPTW的S-PSO算法中新規則為

式中：w為隨迭代次數線性變化的慣性權重系數；c1為向鄰域學習的學習率；σ1為在[0,1]上的隨機數；在本算法中，為使用MOEA/D框架后的鄰域中隨機選擇的2個鄰居，最后將計算出的最大速度賦值給。

S-PSO是基于集合和概率定義的，因此將其用于VRPTW問題中需要對其中的運算符進行重新定義。

算子1：權重系數與速度算子相乘由式(18)定義，該公式使用公式(19)確定邊〈ci,cj〉更新后存在的概率p′(ci,cj)，其中p(ci,cj)為原來存在的概率。

算子2：位置與位置算子相減由式(20)定義。

算子3：c×σ×(位置與位置算子相減)算子由式(21)定義。該公式將使用給定的crisp集合Mδ轉化為具有概率的邊〈ci,cj〉集合，式(22)利用c×σ用來得到更新后的速度值。

算子4：速度與速度算子相加由式(23)定義，即邊〈ci,cj〉被選擇的概率將以最大值為準，以從多個粒子中保留下邊〈ci,cj〉被選擇的最大概率。

為了更加清晰的進行表示，用定義算子的應用實例進行說明。假設：

可以得到

此外針對綜合學習策略的缺陷，設置了額外粒子群更新策略，該策略將學習鄰域內的粒子及外部儲存集EP中解的信息。其中速度更新策略如式(24)所示

2.3.2 位置更新

當粒子位置的邊成立時，初始值將設置為[0,1]的隨機值，表示可以作為出行路段。位置更新的規則根據式(25)進行完成，這里的‘+’號將根據S-PSO的特點重新進行構造。將由和的crisp集合將在滿足約束條件的情況下，經過構造得到。

式中：rand為[0,1]的隨機數，當且僅當p(ci,cj)≥rand時，〈ci,cj〉/p(ci,cj)將保存在速度集中，說明當較大時，在經過轉換后被保存在crisp集合中的概率更大。在實際計算中，當同一邊〈ci,cj〉被多次選中后，即會增加進入crisp集合的概率。

2)為了構造無人機出行路徑，該方法將選擇一個從無人機基地的可到達點。再依次向后尋找可到達點，直到所有點都不滿足，則回到無人機基地。

其中，可到達點的選擇將根據以下3個crisp集合依次選擇：

如果S U、S X、S A中都沒有可到達點，則將調用新一架無人機出行，且將〈ci,0〉和〈0,cj〉添加到中。

3 實驗結果與分析

3.1 數據介紹

本文使用的數據是Solomon在1984中介紹的VRPTW的基準數據集，該數據集是基于幾個標準路徑測試問題數據集生成的；測試使用的RC1類包含隨機和集群地理位置用戶的混合；實驗數據的用戶規模為25。其中用戶數據集的屬性包括用戶編號、橫縱坐標、需求量、時間窗和服務時間，無人機數據集的屬性包括橫縱坐標、最大容量和最大工作時間。

3.2 對比實驗設置

實驗都在運行30次取平均值后進行結果統計。

為了對比的公平性，對以下對比算法進行了處理。

1)第一階段采取最近鄰隨機混合策略(NNH+RANDOM)：取實驗的隨機15個粒子與其他算法進行比較。

2)第二階段采取單目標遺傳算法(GA)和基于集的單目標CS-PSO(基于集的綜合學習粒子群優化算法)：取隨機15次實驗的粒子與其他算法進行比較，該算法使用的單目標適應度函數為

3)第二階段采取多目標算法MOCS-PSO/D：隨機取一次實驗的外部儲存集解與其他算法進行比較。

3.3 運行時間對比

本實驗將對4種算法的收斂速度進行對比。如表3所示。

表3 4種算法平均一次實驗的運行時間

該實驗數據表明，第一階段的Rand+NNH算法可以僅消耗少量時間即可以搜索到可行解，為第二階段的算法提供初始粒子。

GA與CS-PSO算法相比，運行消耗時間相對較長，因此選擇對CS-PSO算法進行改進。CS-PSO算法與MOCS-PSO/D算法相比時間消耗較少，但考慮到CS-PSO算法每次實驗只能得到1個最優解，而MOCS-PSO/D算法一次實驗則可以得到15個最優解，從獲得解效率來說，MOCS-PSO/D具有比較大的優勢，說明MOCS-PSO/D具有很好的收斂性。

3.4 算法性能對比

本實驗將從解的多樣性方面進行對比。以RC101數據樣本為實驗數據，圖6—圖9分別為NNH+RANDOM、GA、CS-PSO和MOCS-PSO/D的實驗圖，其中從左到右依次為其中一個粒子的路徑圖、3組目標f1?f2、f1?f3、f4?f5對比的散點圖，其中路程和時間已做標準化處理，單位為“1”。

圖6 NNH+RANDOM算法結果

圖9 MOCS-PSO/D算法結果

圖7 GA算法結果

圖8 CS-PSO算法結果

由4組實驗圖的(a)圖可以看出，4種算法都可以有效地找到可行路徑，且無人機群可以服務全部的25名用戶。由4組實驗圖的(b)圖可以看出，GA、CS-PSO和MOCS-PSO/D都可以顯著地降低調用無人機數量。同時，可以從MOCS-PSO/D算法中發現f1?f2為成正比的目標。最后，由4組實驗圖的(c)(d)圖可以看出，MOCS-PSO/D算法搜索到的解的多樣性更好，而GA、CS-PSO算法得到的解比較單一。同時，可以從MOCS-PSO/D算法中發現f1?f3、f4?f5為兩對沖突的目標。

綜上，MOCS-PSO/D算法具有很好的多樣性，且可以搜索到質量更高的Pareto最優解。

4 結論

在面向的無人機路徑規劃問題中，針對VRPTW問題使用提出的兩階段算法，第一階段為隨機貪心混合策略，第二階段使用的MOCSPSO/D算法在CS-PSO算法的基礎上增加了MOEA/D框架，改變了CLPSO和PSO的速度更新公式，使其解可以自適應的在5個目標函數上達到均衡，更加符合實際的應用場景，當某路徑規劃方案不能執行時，可立刻選擇其他備選方案。同時，與隨機貪心混合策略、GA和CS-PSO相比，在算法收斂速度、解的多樣性上都有很好的表現。

但是本文算法的解求得的調用無人機數量依舊較多，由于該目標為主要目標函數，未來將對該方面進行研究。