黃鑫，董紅斌

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

科學技術(shù)的不斷發(fā)展在推進社會進步的同時，也使得無人機的應用場景變得更加廣泛[1]。無人機指的是由地面工作人員進行遠程遙控或者部署已經(jīng)設計好的程序進行自主控制的無人駕駛飛機[2]，它不僅擁有有人駕駛飛機所沒有的優(yōu)勢，還能夠避免許多主觀因素的制約。目前無人機已經(jīng)在現(xiàn)代化戰(zhàn)爭中占據(jù)了十分重要的位置，成為進行戰(zhàn)場偵察和物資投放的重要工具。

使用無人機進行戰(zhàn)場物資投放時最重要的就是對無人機進行合理的路徑規(guī)劃。一種優(yōu)秀的無人機路徑規(guī)劃方案能夠大大提高物資投放的及時性和安全性，還可以有效地節(jié)省資源。目前，為解決無人機路徑規(guī)劃問題，國內(nèi)外的學者們已經(jīng)提出了許多種不同的算法，主要可以分為傳統(tǒng)的路徑規(guī)劃算法和受自然啟發(fā)的演化算法2 大類，其中傳統(tǒng)的路徑規(guī)劃算法包括圖搜索算法[3-4]、細胞分解法[5]以及人工勢場法[6]等。但是傳統(tǒng)的路徑規(guī)劃算法在解決復雜場景下的無人機路徑規(guī)劃問題時往往存在著很大的局限性，甚至無法有效解決此類問題。

近年來，受到自然啟發(fā)的演化算法在無人機路徑規(guī)劃中越來越流行，因為演化算法能夠有效處理無人機的動態(tài)約束，并且能夠在復雜的場景中搜索到全局最優(yōu)的解決方案。當前已經(jīng)有許多種演化算法被開發(fā)出來并用于解決無人機的路徑規(guī)劃問題，例如布谷鳥算法(cuckoo search,CS)[7]、蟻群算法(ant colony search, ACO)[8]、遺傳算法(genetic algorithm, GA)[9]、差分進化算法(differential evolution algorithm, DEA)[10]以及粒子群算法(particle swarm optimization, PSO)[11]等，其中粒子群算法使用最為廣泛并引入了許多變體。

粒子群算法是一種基于群體的算法，群體中的每個粒子都可以根據(jù)自己的經(jīng)驗和群體的經(jīng)驗搜索解空間。同時，粒子群算法對初始條件和目標函數(shù)的變化不太敏感，并且能夠通過少量的參數(shù)(包括1 個慣性權(quán)重系數(shù)和2 個認知因子)來適應各種環(huán)境結(jié)構(gòu)[12]，因此相較于其他演化算法，粒子群優(yōu)化算法能夠在更短的時間內(nèi)找到穩(wěn)定收斂的全局最優(yōu)解。除了經(jīng)典的粒子群算法(PSO)[13]外，隨著無人機路徑規(guī)劃問題的不斷復雜化，以及待優(yōu)化目標的不斷增多，還引入了多種變體，例如混合遺傳算法的動態(tài)多群粒子群算法 (the heterogeneous improved dynamic multi-swarm PSO with a genetic algorithm, GA-HIDMS-PSO)[14]、概率序列粒子群優(yōu)化算法(particle swarm optimization with probability sequence, WI-PSO)[15]和自適應加權(quán)延遲速度粒子群算法(particle swarm optimization with adaptive weighted delay velocity, PSO-AWDV)[16]等。文獻[17]將改進的粒子群算法和改進的共生生物搜索相結(jié)合，有效地結(jié)合了算法的搜索和開發(fā)能力，成功為每架無人機生成可行有效的路徑。文獻[18]將基于集合的粒子群算法與綜合學習粒子群算法相結(jié)合來解決無人機的路徑規(guī)劃問題。

目前以上這些算法在解決無人機路徑規(guī)劃問題時，仍然存在搜索效率低以及容易陷入局部最優(yōu)、出現(xiàn)早熟現(xiàn)象等局限，因此本文針對使用無人機進行戰(zhàn)場物資投放的特點，分析其約束函數(shù)以及待優(yōu)化的目標函數(shù)，額外增加了等待時間和延遲時間2 個相互沖突的目標函數(shù)，將無人機的路徑規(guī)劃問題歸約為帶時間窗的車輛路徑規(guī)劃(vehicle routing problem with time windows, VRPTW)問題，構(gòu)建出更合理的無人機路徑規(guī)劃問題模型，并提出一種新的兩階段雙層多目標粒子群算法用于解決該問題。同時為了避免算法可能出現(xiàn)早熟的現(xiàn)象，對多次未更新其歷史最優(yōu)位置的粒子采取了額外的更新策略，并通過粒子內(nèi)部搜索以達到每個解決方案所調(diào)用無人機數(shù)目最少的目的。

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

無人機路徑規(guī)劃的目的是為無人機系統(tǒng)中的多架無人機在出發(fā)點與多個目的地點之間找到一條滿足任務需求的路線。由于無人機在空中能夠保持直線飛行，為了更加直觀地描述無人機的路徑規(guī)劃問題，本文做出以下假設：

1) 無人機飛行在足夠安全的高度以避免地形等因素產(chǎn)生的威脅；

2) 每架無人機都有其固定的飛行高度，航行過程中互不干擾以避免無人機之間相互碰撞產(chǎn)生的威脅。

根據(jù)以上假設，在無人機路徑規(guī)劃的問題模型中，存在若干個無人機基地，其中包括一個初始基地，其余為目標基地。初始基地中的每架無人機攜帶一定量的物資以后出發(fā)，完成對一個或多個目標基地的物資投放后重新返回初始基地?；诖耍摕o人機路徑規(guī)劃問題實際上可以歸約為帶時間窗的車輛路徑規(guī)劃(VRPTW)問題，方便建立更為理想的數(shù)學模型。當一個無人機路徑規(guī)劃方案能夠使所有目標基地都能夠在其規(guī)定時間范圍內(nèi)接收所需物資，且每架無人機最終都能夠順利返回初始基地，則表示該方案是可行的[19]。

1.1 無人機路徑規(guī)劃問題的形式化表示

在使用無人機執(zhí)行物資投放任務的過程中，無人機需要從某一個基地航行到另一個基地，也就是說無人機的每一段航行路徑都連接了2 個基地，如果將無人機的初始基地以及等待接收物資的目標基地看作空間中的一個個點，那么無人機路徑規(guī)劃問題實際上就可以形式化表示為在有向帶權(quán)圖G=(C,E)中的優(yōu)化問題，其中：

1) 頂點集C：頂點集C={c0,c1,…,cn}中包含了一個無人機出發(fā)的初始基地以及若干個等待物資的目標基地。當i=0 時，c0表示初始基地；當i∈[1,n]時，ci表示各個目標基地，n為目標基地的數(shù)量。

2) 邊集E：邊集E={|ci,cj∈C,i≠j}中的每條邊表示連接頂點集C中的2 個頂點ci的一條有向線段，該有向線段的權(quán)重dij表示2 個目標基地之間的歐氏距離，可以與無人機從ci航行到cj所需要的時間進行等價替換，并且dij=dji。

對于每架可派遣的無人機，其屬性如表1 所示。

表1 無人機的屬性

對于每個目標基地，其屬性如表2 所示。

表2 目標基地的屬性

假設初始基地中可調(diào)用的無人機的集合為V={v1,v2,…,vm}，其中m為可用無人機的總數(shù)量。使用一個二進制變量表示目標基地ci是否由無人機vr進行物資投放：

1.2 無人機路徑規(guī)劃問題解的形式

每個解Xi都可以使用一個鄰接表來表示，以含有5 個目標基地的問題模型為例，其頂點集可以表示為C={c0,c1,c2,c3,c4,c5}，假如該問題的一個解為其中那么表示解Xi的鄰接表如圖1 所示。

圖1 解的鄰接表

1.3 無人機路徑規(guī)劃問題的約束條件

為了保證每個目標基地都可以在規(guī)定時間內(nèi)獲取所需物資，同時保證每架執(zhí)行任務的無人機都能夠安全回到初始基地，在使用無人機進行物資投放時應該滿足以下約束條件：

1) 每個與目標基地對應的頂點有且僅有一條有向邊進入和離開。

2) 每個目標基地只接收一架無人機的物資投放并一次接收全部所需物資。

3) 每架無人機的物資攜帶量不得超過其最大負載量，且當無人機當前攜帶物資量不滿足剩下任何目標基地的需求量時，開始返航。

4) 無人機總航行時間不得超過其最大工作時間。

式中：dij為2 個目標基地ci和cj之間的歐幾里得距離，此處與時間做等價替換，表示無人機從ci到cj所花費的時間；為無人機vr在目標基地ci處的等待時間，即當無人機到達目標基地的時間早于該目標基地最早可以開始接受物資的時間，那么無人機需要在原地等待，無人機的等待時間計算為

式中ti為無人機抵達目標基地的時間。

5) 每個基地完成接收物資的時間不得超過其最晚可結(jié)束接收物資時間。

式中compj為目標基地cj最晚可結(jié)束接受物資的時間。

1.4 無人機路徑規(guī)劃問題的目標函數(shù)

根據(jù)使用無人機進物資投放的特點以及前面所提到的約束條件，提出了以下5 個包含沖突關系的目標函數(shù)：

1) 調(diào)用無人機的數(shù)量F1：在無人機路徑規(guī)劃問題中，調(diào)用無人機的數(shù)量應該盡可能少。

2) 路徑的總距離F2：在無人機路徑規(guī)劃問題中，所有調(diào)用無人機的路徑之和應盡可能小。

3) 無人機完成物資投放所花費時間F3：指從無人機開始執(zhí)行任務到最后一架無人機返回目標基地的時間，在無人機路徑規(guī)劃問題中，執(zhí)行任務的時間應該盡可能短。

4) 等待時間F4：當無人機到達目標基地的時間早于目標基地最早可以開始接收物資的時間，無人機就會進行等待，產(chǎn)生等待時間，在無人機路徑規(guī)劃問題中，總等待時間應該盡可能短。

5) 延遲時間F5：當無人機到達目標基地的時間晚于目標基地最早可以開始接收物資的時間，目標基地就會進行等待，產(chǎn)生延遲時間，在無人機路徑規(guī)劃問題中，總延遲時間應該盡可能短。

在文獻[20] 中證明了F1與F2正相關，但與F3是一對沖突函數(shù)；此外F2與F3以及F4和F5同樣都是沖突函數(shù)。

1.5 多目標優(yōu)化

無人機路徑規(guī)劃問題是一個復雜的多目標優(yōu)化問題，其中還包括了多個相互沖突的目標，因此需要使用多目標優(yōu)化算法來解決此類問題。在使用多目標優(yōu)化算法解決多目標優(yōu)化問題時，問題的任意2 個解x,y∈Ω，(Ω 為解空間) 當且僅當對于?i∈{1,2,···,R},Fi(x)≤Fi(y)，且對于?j∈{1, 2, ···,R},Fj(x)

2 兩階段的雙層多目標粒子群算法

2.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法(PSO) 種群中的每個粒子i都在N維搜索空間中擁有一個位置特征和一個速度特征并通過其自身歷史最佳位置所反映的自身經(jīng)驗以及群體最佳位置所反映的群體經(jīng)驗在解空間中搜索最優(yōu)解。對于種群大小為M的粒子群，其粒子的速度與位置的更新方式為

式中：k為當前迭代次數(shù)；xi∈[xmin,xmax] 和vi∈[vmin,vmax] 分別為粒子i的位置和速度；c1和c2分別為自我認知系數(shù)和社會認知系數(shù)，其值決定了粒子為向局部最佳位置和全局最佳位置移動的趨勢；r1和r2為[0,1]內(nèi)的2 個隨機數(shù)。

2.2 基于集合的粒子群優(yōu)化算法

粒子群優(yōu)化算法(PSO) 簡單有效，主要用于在連續(xù)空間中求解，但實際上許多優(yōu)化問題都是定義在離散空間中的。因此為了遵循使用粒子群優(yōu)化算法解決離散空間問題的思想，基于集合的粒子群優(yōu)化算法(set-based PSO, S-PSO)采用了一種基于集合的表示方案，并重新定義了離散空間中的“位置”和“速度”以及所有相關算子[18]。

S-PSO 算法的結(jié)構(gòu)與PSO 類似，其速度更新規(guī)則也遵循相同的思想，但是位置、速度和所有相關算術(shù)運算符在離散空間中重新定義如下：

1) 位置：位置是解決問題的可行方案。第i個粒子的位置表示為Xi(Xi?E)。該位置由n個維度組成，即其中同樣，pbesti?E、gbesti?E以及l(fā)besti?E分別表示第i個粒子的迄今最佳位置、全局最佳位置和局部最佳位置。在算法開始時，使用隨機生成的可行解初始化Xi。

2) 速度：在S-PSO 中，速度被定義為具有可能性的集合，對于粒子i，它的速度表示為一個定義在E上的可能性集合Vi={e/p(e)|e∈E}。即對于每個元素e∈E，都有一個可能性p(e)∈[0,1]，其中當p(e)=0 時，忽略集合中的元素e。在第j維上有表示一組定義在Ej上的可能性集合。

3) 系數(shù)×速度：給定一個系數(shù)c(c≥0) 和一個可能性集合V={e/p(e)|e∈E}，它們的乘積定義為

4) 位置-位置：在S-PSO 的表示方案中，位置由1 個crisp 集合表示，對于2 個給定的crisp 集合A和B，A-B的計算為

5) 系數(shù)×(位置-位置)：“位置-位置”的結(jié)果仍然是1 個crisp 集合，系數(shù)與crisp 集合之間的運算定義為

6) 速度+速度：2 個可能性集合之間的加法算子定義為

2.3 綜合學習粒子群優(yōu)化算法

在經(jīng)典的粒子群優(yōu)化算法(PSO) 中，所有的粒子都會根據(jù)個體經(jīng)驗預計全局經(jīng)驗進行更新，如果搜索空間比較復雜且存在大量局部最優(yōu)解，粒子很有可能被吸引到局部最優(yōu)解區(qū)域并陷入局部最優(yōu)。為了避免此類情況的發(fā)生，綜合學習粒子群優(yōu)化算法(comprehensive learning particle swarm optimization, CLPSO)采用綜合學習的策略[21]，每個粒子的速度都會根據(jù)種群中其他粒子的歷史最佳位置pbest 進行更新。該策略可以確保種群的多樣性，防止出現(xiàn)早熟。在CLPSO 中，第i個粒子的速度vi和位置xi的更新方式為

2.4 雙層多目標粒子群優(yōu)化算法

受到以上幾種算法的啟發(fā)，針對粒子群算法(PSO)以及其變種算法的優(yōu)缺點，本文提出一種新的雙層多目標粒子群優(yōu)化算法(double layer multiobjective comprehensive learning swarm optimization algorithm framework based on set decomposition,MODCS-PSO/D)用于求解無人機的路徑規(guī)劃問題。該算法使用集合和概率的方式來表示粒子的速度與位置，將連續(xù)空間中的問題轉(zhuǎn)化到離散空間中進行求解，并使用基于分解的多目標優(yōu)化框架(multi-objective evolutionary algorithm based on decomposition, MOEA/D)來歸一化處理待優(yōu)化問題的多個目標函數(shù)，另外，在使用MOEA/D 框架來處理該無人機路徑規(guī)劃問題的目標函數(shù)時，將總時間F3、等待時間F4以及延遲時間F5這3 個時間目標函數(shù)轉(zhuǎn)換成一個混合目標函數(shù)進行處理。

2.4.1 基于分解的多目標進化框架

MOEA/D 是一種有效的基于分解的多目標進化框架[22]。它將一個多目標優(yōu)化問題分解為多個標量優(yōu)化子問題，并同時對其進行優(yōu)化。每個子問題由一個權(quán)向量表示，并通過組合來自其多個相鄰子問題的信息進行優(yōu)化。

切比雪夫(Chebyshev) 方法是常用的分解方法，其中標量優(yōu)化問題被定義為

式中為參考點，即

2.4.2 雙層粒子群算法

為了解決粒子群算法因為多樣性差而導致搜索效率低、易早熟等現(xiàn)象，雙層粒子群算法使用下層工作粒子群用以提升種群的多樣性，并創(chuàng)建上層決策粒子群用以調(diào)整進化方向[23]。

在雙層多目標粒子群優(yōu)化算法中，下層工作種群采用綜合學習的策略進行種群更新，即下層工作種群中的粒子在進化時將不會根據(jù)全局最優(yōu)位置進行學習，而是隨機在種群中選擇2 個粒子，并根據(jù)其歷史最優(yōu)位置進行更新。

上層決策種群中的粒子則根據(jù)下層工作種群更新后得到新種群的全局最優(yōu)位置以及自己的歷史最優(yōu)位置進行更新，從而引導整個種群的進化方向。

另外，在雙層粒子群算法中，下層工作種群更新時，上層決策種群不發(fā)生改變；而上層決策種群更新后也會被復制一份作為新的下層工作種群進入下一次迭代，具體如圖2 所示。

圖2 雙層粒子群算法的結(jié)構(gòu)

2.4.3 粒子的位置與速度表示

粒子h在第k次迭代中的位置表示為其中每個維度都是一個邊集，每個邊集包括2 條邊，每條邊的起點和終點都包含在無人機初始基地和目標基地對應的頂點集C={c0,c2,…,cn}中。假設o為粒子h的某個維度，且與o相鄰的前后2 個點為ci，cj(ci≠cj)，則該維度對應的邊集表示為

根據(jù)每個粒子的位置可以得到一組經(jīng)過頂點集C中所有頂點的有向哈密頓回路，其中每個有向哈密頓圓都表示一架被派遣的無人機執(zhí)行任務的路徑。

粒子的速度則由邊以及邊出現(xiàn)的概率表示，粒子h在第k次迭代中的速度表示為其中第δ維的速度表示為

式中：集合Aδ中的邊都是頂點集C中頂點構(gòu)成的完全有向圖G中的與狀態(tài)δ相鄰的狀態(tài)組成的狀態(tài)對；邊出現(xiàn)的概率用p(ci,cj)∈[0,1] 表示，并參照此概率對邊進行更新選擇，且當p(ci,cj)=0 時忽略邊。

2.4.4 粒子的速度與位置更新方式

雙層多目標粒子群優(yōu)化算法(MODCS-PSO/D)的下層工作種群采用綜合學習的方式進行更新，其速度更新規(guī)則為

式中：k為當前迭代次數(shù)，kmax為最大迭代次數(shù)

式(3)是隨迭代次數(shù)從ωmax線性衰減到ωmin的慣性權(quán)重系數(shù)的計算公式。

式中：c1為當前粒子向其他粒子學習的認知因子；r1為取值在[0,1] 的隨機數(shù)；為 當前粒子基于MOEA/D 框架在其鄰域中隨機選擇的其他粒子的歷史最優(yōu)位置，這里選擇2 個粒子進行學習。

更新速度后，粒子i根據(jù)新的速度和它當前的位置，構(gòu)建一個新的位置。與連續(xù)的情況不同，離散空間中的位置必須滿足某些約束條件，以保證新位置的可行性。

當構(gòu)造時，粒子i首先從Cut中的元素學習，這是一個由中所有滿足條件的元素組成的集合，其構(gòu)造方式為

式中：rand 為取值在[0,1]中的隨機數(shù)，當且僅當pci,cj≥rand時，/p(ci,cj)才會保存在速度集中，當p(ci,cj)的值越大，則邊(ci,cj)經(jīng)過轉(zhuǎn)換后保存到Cut集合中的概率就越大。

如果Cut中沒有可用的元素，粒子i將重用其當前位置中的元素。如果中也沒有可用的元素，粒子i將使用其他滿足條件的可用元素來構(gòu)造。

如果仍然沒有可用元素，粒子i則調(diào)用一架新的無人機執(zhí)行任務。

雙層多目標粒子群優(yōu)化算法(MODCS-PSO/D)的上層決策種群根據(jù)下層工作種群得到的結(jié)果進行更新，粒子速度更新方式為

式中為第k代下層工作種群的全局最佳位置。

上層決策種群中粒子的位置更新方式與下層工作種群一致。

2.4.5 額外的更新策略

1) 為了獲得一組均勻分布且收斂良好的解，使用一個固定大小的外部存檔保存算法每次迭代得到的優(yōu)勢解。當外部檔案中的所有非支配解的個數(shù)沒有超過外部存檔的大小，則將新得到的優(yōu)勢解直接保存到外部檔案中，否則將獲得的優(yōu)勢解與外部檔案中的所有非支配解逐個判斷是否占優(yōu)。若占優(yōu)，則使用該優(yōu)勢解替換外部存檔中的被占優(yōu)解，否則不進行更改。

2) 為了避免算法陷入局部最優(yōu)，出現(xiàn)早熟現(xiàn)象，在每次迭代開始前，算法對于種群中多次沒有更新歷史最優(yōu)位置pbest的粒子，利用其鄰域粒子以及外部存檔中的粒子對其進行額外的速度與位置的更新。計算其各個目標函數(shù)值，通過比較該粒子與鄰域粒子的切比雪夫值更新歷史最優(yōu)位置pbest以及參考向量z*。

3) 每次上層決策種群更新完畢后，都對其中的每個粒子進行額外的搜索，選擇粒子中最短的路徑，判斷該路徑中的目標基地節(jié)點是否可以在滿足約束條件的前提下，分配給其他無人機服務，如果可以，則進行更新，然后重新計算各個目標函數(shù)值，通過比較切比雪夫值更新粒子的歷史最優(yōu)位置pbest，并更新外部存檔。

2.4.6 算法流程

圖3 為兩階段算法的流程。其中第1 階段使用隨機最近鄰混合算法(nearest neighbor random mixed algorithm, Random+NNH)得到無人機的初始路徑，并作為第2 階段雙層多目標粒子群優(yōu)化算法(MODCS-PSO/D)的初始粒子。

圖3 兩階段MODCS-PSO/D 流程

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

3.1 數(shù)據(jù)

Solomon 基準數(shù)據(jù)集包含了多個標準路徑測試問題數(shù)據(jù)，能夠很好地模擬該無人機路徑規(guī)劃的問題模型。實驗選取其中RC1 類包含隨機和集群位置的混合數(shù)據(jù)，包括1 個無人機初始基地、25 個目標基地。

3.2 實驗設置

為了證明本文提出算法的可行性和有效性，在上述數(shù)據(jù)集上另外選取了3 種比較經(jīng)典的兩階段算法以及隨機最近鄰算法(Random+NNH)與本文提出的MODCS-PSO/D 算法進行對比實驗。對比的兩階段算法包括單目標遺傳算法(GA)、單目標基于集合的綜合學習粒子群優(yōu)化算法(CS-PSO)、以及多目標基于分解的綜合學習粒子群優(yōu)化算法(MOCS-PSO/D)，實驗記錄并統(tǒng)計分析了以上5 種算法進行30 次實驗的運行時間、迭代次數(shù)以及解的質(zhì)量等數(shù)據(jù)。

為了實驗的公平性，對于以上5 種算法做如下處理：

1) 對于Random+NNH、GA 和CS-PSO 這3 種算法，隨機取其15 次實驗的結(jié)果進行比較；

2) 對于所有兩階段算法，其第1 階段均使用Random+NNH 算法得到其第2 階段的初始粒子；

3) 對于所有單目標算法，其單目標適應度函數(shù)值計算為

4) 對于所有多目標優(yōu)化函數(shù)，均隨機取其一次實驗得到的外部檔案中保存的15 個優(yōu)勢解進行比較。

3.3 實驗參數(shù)設置

本實驗的操作系統(tǒng)為windows10，硬件環(huán)境為AMD Ryzen7 5800H，16 GB 內(nèi)存，代碼運行環(huán)境為python 3.5。

實驗中各個算法的具體參數(shù)設置如表3 中所示。

表3 實驗參數(shù)設置

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

實驗中所使用的5 種算法的平均運行時間以及平均迭代次數(shù)如表4 中記錄。

表4 5 種算法的平均運行時間以及平均迭代次數(shù)

從表4 中的數(shù)據(jù)可以看出， Random+NNH 算法只需要很短的時間就可以搜索到可行的路徑規(guī)劃方案，而對于單目標的2 種優(yōu)化算法，運行時間以及迭代次數(shù)都保持在一個相對較低的水平上，但是考慮到單目標優(yōu)化算法1 次實驗只能得到1 個解，而多目標算法1 次可以得到1 個Pareto 最優(yōu)解集（其中包含了15 個解），因此單目標優(yōu)化算法的效率實際上要低于多目標優(yōu)化算法。而對于本文提出的 MODCS-PSO/D 算法，其無論是在平均運行時間還是平均迭代次數(shù)上都明顯低于MOCS-PSO/D 算法，接近2 種單目標優(yōu)化算法，這也證明了MODCS-PSO/D 算法的效率更高，性能更好。

另外為了證明本文提出算法的有效性，實驗記錄了5 種算法在30 次實驗中的在各個目標函數(shù)值上的表現(xiàn)，以及單目標適應度值和算法的穩(wěn)定性評價，其中，算法的穩(wěn)定性評價計算為

通過表5 中的數(shù)據(jù)可以看出，Random+NNH算法在各個指標上的表現(xiàn)都普遍不如其他幾種演化算法。2 種單目標優(yōu)化算法能夠在單個目標處取得較為優(yōu)秀的結(jié)果，但是綜合來看，單目標優(yōu)化算法在針對某個目標進行優(yōu)化時，卻是以犧牲其他目標為代價的，因此單目標優(yōu)化算法得到的解其多樣性都比較差。而對于多目標優(yōu)化算法MOCS-PSO/D 和MODCS-PSO/D 在各個目標上的平均值都比較高，也證明使用多目標優(yōu)化算法得到的解不僅多樣性更高，而且能夠很好地平衡多個相互沖突的目標函數(shù)。另外，使用多目標優(yōu)化算法得到的解在各個目標函數(shù)處也都能取得比使用單目標優(yōu)化算法得到的解更好的值，表明了多目標優(yōu)化算法能夠規(guī)劃出質(zhì)量更高的路徑方案。最后MODCS-PSO/D 算法在各個指標上的表現(xiàn)都要比MOCS-PSO/D 更加優(yōu)秀，也證明了本文提出算法的有效性與可行性。

表5 5 種算法的實驗結(jié)果

圖4(a)是使用兩階段MODCS-PSO/D 算法為無人機規(guī)劃出的路徑方案，可以看出該算法能夠為無人機規(guī)劃出合理的路徑方案，使得無人機完成物資投放的效率更高，綜合成本更小。圖4(b)、圖4(c)和圖4(d)分別是問題模型中3 對包含沖突關系的目標函數(shù)：F1(調(diào)用無人機數(shù)量)-F2(總航程)、F1(調(diào)用無人機數(shù)量)-F3(完成任務的時間)以及F4(總等待時間)-F5(總延遲時間) 的散點分布圖，可以看出該算法不僅能夠很好地平衡這些沖突目標，而且還可以得到更多樣的解。

圖4 兩階段MODCS-PSO/D 結(jié)果

4 結(jié)論

本文提出了一種新的兩階段雙層多目標粒子群優(yōu)化算法MODCS-PSO/D，用于解決由使用無人機進行物資投放而產(chǎn)生的無人機路徑規(guī)劃問題。首先根據(jù)使用無人機執(zhí)行物資投放任務的特點構(gòu)建無人機路徑規(guī)劃模型，提出約束條件和目標函數(shù)。接下來本文介紹了基于分階段多目標優(yōu)化框架MOEA/D 和經(jīng)典PSO 的原理以及其相關變種算法S-PSO 和CLPSO，并基于此提出一種新的改進策略，通過利用S-PSO 中的思想對粒子的速度和位置以及其更新方式進行改造，將連續(xù)空間中的路徑規(guī)劃問題轉(zhuǎn)化成離散空間中的問題，然后引入雙層粒子群概念，下層工作種群采用綜合學習的策略進行更新，上層決策種群根據(jù)粒子的個體極值以及下層工作種群進行更新，然后引入基于分解的多目標優(yōu)化框架MOEA/D 來平衡多個沖突的待優(yōu)化目標。為了避免出現(xiàn)陷入局部最優(yōu)以及早熟等現(xiàn)象，為多次未更新的粒子添加了額外的更新策略，并增加了局部搜索以追求能夠使得到的每個解調(diào)用的無人機數(shù)目更少。最后，與Random+NNH、兩階段GA、兩階段CS-PSO以及兩階段MOCS-PSO/D 算法在同一數(shù)據(jù)集中進行對比實驗，對實驗獲得的數(shù)據(jù)進行對比分析可以得出結(jié)論，本文提出的MODCS-PSO/D 能夠有效地解決無人機路徑規(guī)劃問題，并規(guī)劃出滿足約束條件以及能夠很好平衡各個目標的優(yōu)秀路徑。

但是該算法的性能仍然有待提高，目前只適用于解決在二維環(huán)境中的路徑規(guī)劃問題，未來將繼續(xù)研究MODCS-PSO/D 的無人機動態(tài)以及三維路徑規(guī)劃，以建立更好的問題模型，更準確地規(guī)劃路徑。