面向無人機路徑規(guī)劃的多目標(biāo)粒子群優(yōu)化算法

蘇子美，董紅斌

哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

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

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

1 無人機路徑規(guī)劃問題

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

1.1 VRPTW問題的形式化表示

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

1)頂點集C：頂點C包括無人機基地點和用戶點。其中當(dāng)i=0時，c0為圖的根，表示無人機基地。當(dāng)i∈[1,n],n為用戶數(shù)，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]的變量細節(jié)如表1所示。

表1 用戶細節(jié)變量

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

表2 無人機基地細節(jié)變量

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

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

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

圖1 RC101路徑規(guī)劃圖

1.2 解的形式

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

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

圖2 示例有向帶權(quán)圖

圖4 示例鄰接矩陣

圖3 示例鄰接圖

1.3 約束條件

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

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

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

(3)無人機總?cè)萘考s束：表示每架無人機的負載不得超過其承載能力。

式中qi為用戶ci的需求。

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

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

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

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

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

1.4 目標(biāo)函數(shù)

根據(jù)VRPTW的特點，設(shè)定了包含沖突的5個目標(biāo)函數(shù)。

1)調(diào)用無人機數(shù)f1與路線總距離f2。

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

2)路線總時間f3。

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

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

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

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

1.5 多目標(biāo)優(yōu)化

多目標(biāo)優(yōu)化問題可以用函數(shù)表示為

式中：RM為目標(biāo)空間；?為決策空間；目標(biāo)函數(shù)F可將決策空間映射到目標(biāo)空間。

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

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

2 兩階段MOCS-PSO/D算法

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

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

圖5 兩階段算法流程圖

2.1 粒子速度和位置的表達

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了更加清晰的進行表示，用定義算子的應(yīng)用實例進行說明。假設(shè)：

可以得到

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

2.3.2 位置更新

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

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

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

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

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

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)介紹

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

3.2 對比實驗設(shè)置

實驗都在運行30次取平均值后進行結(jié)果統(tǒng)計。

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

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

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

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

3.3 運行時間對比

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

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

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

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

3.4 算法性能對比

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

圖6 NNH+RANDOM算法結(jié)果

圖9 MOCS-PSO/D算法結(jié)果

圖7 GA算法結(jié)果

圖8 CS-PSO算法結(jié)果

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

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

4 結(jié)論

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

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