多種群合作學習的多模態多目標路徑規劃算法

趙萌，路輝，王詩琪，楊思旖，王贊

(北京航空航天大學 電子信息工程學院，北京 100191)

多模態優化問題旨在找到多個全局或局部最優解，為決策者提供多樣的選擇，增加決策的魯棒性；多目標優化問題是指通過權衡多個目標的最優化，為決策者提供更好的選擇，提高決策的實用性，與單目標的全局最優點不同，多目標優化的最優解通常用Pareto 解集表示，集合中的解是相互非支配的。多模態多目標優化(multimodal multi-objective optimization, MMO)問題指具有多個全局或局部最優Pareto 解集的優化問題[1]，在實際應用中，每個解集包含多種備選方案。豐富的決策方案不僅可以保障決策的有效性，還可以減少突發事件導致的經濟損失。

在路徑規劃問題中，決策者希望可以同時獲得滿足目標需求的多條路徑，從而保障決策的穩定性。目前大多數研究針對最小化路徑長度的規劃需求，在滿足約束條件的前提下同時規劃出多條最短路徑[2-3]，這是一種單目標多模態的優化問題。然而，單一目標通常難以滿足人們的實際需求，考慮到路網環境的不確定性，人們希望可以同時獲得多條路徑長度、堵塞路段數量、交叉路口數量等目標值最優且相等的路徑。因此，在路徑規劃問題中，多模態優化與多目標優化具有緊耦合的關系。雖然已經有學者對多目標路徑規劃問題進行了深入研究[4-7]，但是由于問題建模復雜，求解難度大，關于多模態多目標路徑規劃問題(multimodal multiobjective optimization path planning, MMOPP)的研究成果卻寥寥無幾。盡管多式聯運問題的研究正處于白熱化階段，但是這些研究往往只考慮運輸成本和時間成本[8-9]，缺少在多模態優化需求條件下，針對復雜路網中超多目標優化問題的研究。

從應用需求的角度分析，MMOPP 問題的研究通常分為2 種。一種是針對復雜任務中的路徑規劃[10-12]，決策者需要同時考慮路徑長度短、有途經點等規劃需求。另外一種是考慮物流配送需求的車輛路徑規劃[13-14]，這種問題的研究通常不需要考慮路徑的多樣性，主要考慮配送車輛的裝載量約束與配送網點的時間約束。本文針對復雜路網中MMOPP 問題的研究需求，在多模態優化需求條件下，研究超多目標路徑規劃問題。相關研究成果可以為車輛或無人載體在復雜路網中的路徑規劃提供理論與技術支撐。

經典的路徑規劃算法，如A*算法、Dijkstra 算法等僅考慮路徑長度的優化，難以實現對MMOPP 問題的求解。因此，大多數學者引入具有自組織、自適應、自學習特性的群體智能算法實現多目標路徑規劃。文獻[15]將蟻群算法與Dijkstra 算法相結合，通過豐富路徑搜索方向，解決了路徑長度短、路徑平滑度高、機器人行進安全性高3 種路徑規劃需求。文獻[16]提出用強化學習算法優化蟻群算法的參數，提高了算法的全局搜索能力。除蟻群算法外，粒子群優化（particle swarm optimization, PSO）算法[17]、灰狼優化算法[18]、螢火蟲算法[19]、天牛群算法[20]等也可用于解決多目標路徑規劃問題。針對無人機三維作業場景的特殊性，文獻[21]通過在NSGA-II算法中引入增加、刪除算子，同時解決了路徑長度短與躲避威脅區域2 種路徑規劃需求。此外，無人機燃料損耗的最小化也通常是路徑規劃問題中需要考慮的優化目標之一[22]。

大多數算法只考慮到了路徑規劃中的多目標需求，盡管這類算法的搜索能力強，收斂性好，但是由于算法設計過程中沒有考慮多模態的規劃需求，決策空間內解的多樣性難以得到保持，決策的魯棒性受限。因此，為提升算法的搜索能力與尋優能力，提高解的多樣性，本文在MMOPP 問題的研究中側重解決路徑規劃問題中的多模態需求，在PSO 算法框架下，提出多種群合作學習（multi-swarm cooperative learning, MSCL）算法。利用多個種群的合作搜索，將多目標優化問題轉化為多個單目標問題進行求解，豐富決策空間內解的多樣性，同時，兼顧算法在目標空間不同維度上的搜索能力。此外，為了緩解編解碼匹配的不唯一性引起的搜索效率低的問題，提出利用解碼經驗表傳遞有效的解碼經驗，以提高算法的尋優能力。算法驗證階段使用的MMOPP 測試集包括對路徑長度、道路寬度、道路擁擠度、堵塞路段等待優化目標的數值量化，并且包括必經點問題的求解約束。因此，本文的仿真測試實驗與實際應用場景具有緊耦合的關系。仿真測試結果驗證了多種群合作學習算法可以并行解決多模態和多目標的路徑規劃需求，與其他算法的比較結果說明了本文所提算法具有更強的搜索能力與尋優能力，并且解的多樣性更好。

1 多種群合作學習算法

多種群合作學習算法是利用多個種群的無交叉搜索并行解決多模態和多目標的路徑規劃需求。如圖1 所示，其中 f1,f2,···,fn為不同的優化目標。算法實現的過程分為3 個階段：首先，依據地圖中關鍵路徑點的數量對路徑碼進行編碼；然后，將初始化后的種群劃分為多個子種群，明確每個子種群的優化目標；最后，依據子種群的優化目標對個體的路徑碼進行解碼，計算相應的適應度值，并保留精英解對應的路徑。整個過程持續循環，直到滿足最大迭代次數。

圖1 多種群合作學習算法框架Fig.1 Framework of the proposed algorithm

1.1 基于關鍵點的路徑編碼

為了降低可行解的搜索難度，利用地圖中的關鍵路徑點表征路徑信息。如圖2 所示，用1、2、3、4 分別表示路徑節點與其右、上、左、下的節點具有鄰接關系。假設任意路徑節點 rj處的可行進方向集合 Wj，如果 rj屬于關鍵路徑點集合P={p1,p2,···,pK}，則一定滿足以下條件之一：

圖2 關鍵路徑點的提取Fig.2 Extraction of key path points

條件1 card(Wj)＞2；

條件2 如果c ard(Wj)=2，則Wj≠{1,3}且 Wj≠{2,4}；

條件3 rj∈{S,T}。

其中 j=1,2,···,R，R為地圖所有路徑節點的數量，K為關鍵路徑點的數量，且 K ＜R。S和 T分別為路徑的起點和終點。

顯然，關鍵路徑點的提取不會影響可行路徑的搜索，而且可以通過減小解空間的維度提高可行解的搜索效率。因此，采用地圖中關鍵路徑點數量K定義粒子編碼的維度，即粒子個體是 K維的實數碼，記為路徑碼。

1.2 基于多目標分解的子種群劃分

在多種群合作學習算法中，種群的初始化采用隨機數生成器的方式，即vdi,1=rand(0,1)，xdi,1=rand(0,1)，其中，d=1,2,···,K。然而，如圖3 所示，當有3 個優化目標（最小化）時，由于目標空間內的最優解在同一區域，所以，種群中所有粒子的搜索方向是一致的，從任意目標空間的切面看，受全局最優解的牽引，粒子均朝向左下角（最小值）移動。然而，多模態路徑規劃的目標不是找到一個全局最優解，而是需要綜合多個目標，搜索到多個最優解。當優化目標較多時，種群中的粒子具有朝向同一目標區域的搜索趨勢，容易出現早熟現象，即單一種群有限的搜索能力會影響解的多樣性。因此，為了提高算法的搜索能力與尋優能力，本文提出基于多目標分解的子種群劃分策略。

圖3 有3 個優化目標時單一種群的粒子群尋優過程Fig.3 Optimization process of particles when there are three objectives to be optimized

根據Pareto 解集的定義，某個解在單一目標維度上最優，即有機會成為Pareto 最優解。因此，在多種群合作學習算法中，種群會依據優化目標的個數進行均勻劃分，每個子種群在迭代尋優的過程中只負責優化一個目標，如圖4 所示，所有粒子具有相同的優化目標，其在目標空間內的運動具有一致性。當有3 個優化目標（最小化）時，每個種群分別負責在目標1、目標2、目標3 的維度內搜索最優解，從而避免由于粒子在目標空間內的一致性移動導致陷入局優的問題。多種群分工協作的機制使得粒子可以在目標空間內分散地搜索，趨向不同的方向尋找最優解，進而實現多目標的分維尋優，提高解的多樣性。因此，在多模態多目標路徑規劃問題的求解中具有更強的搜索能力與尋優能力。

圖4 有3 個優化目標時基于子種群劃分策略的粒子群尋優過程Fig.4 Optimization process of particles when there are three objectives to be optimized

1.3 基于粒子群的迭代過程

在多種群合作學習算法中，種群中的每個個體根據標準粒子群優化算法更新迭代自身的速度與位置[23]。粒子群優化算法是Eberhart 和Kennedy[24]于1995 年提出的一種基于群體協作的隨機搜索算法。該算法的基本思想是模擬鳥群的覓食行為，通過粒子群在解空間內的搜索實現對優化問題的求解。如式(1)和式(2)所示，種群中粒子的狀態用速度和位置2 個向量描述：

圖5 粒子的尋優過程Fig.5 The optimization process of the particles.

1.4 基于解碼經驗表的路徑解碼

根據路徑規劃的需求，從路徑起點對應的維度開始解碼，然后依據每個關鍵路徑點處的可行進方向依次選擇下一個路徑點，直至當前的解碼維度對應于終點，或重復到達某一路徑節點，則停止對該粒子個體（路徑碼）的解碼。如果可連續解碼至終點，則得到一條可行路徑，計算路徑對應的各個目標值，經過非支配排序得到精英解。然而，地圖中每個關鍵路徑點都有多個可行進方向，路徑碼的解碼空間不能一一映射地回溯至編碼空間。針對這種編解碼匹配的不唯一性，提出采用解碼經驗表傳遞有效的解碼經驗，降低解碼的不確定性。如圖6所示，解碼經驗表 D是 T×M 的二維矩陣，其中，T為路徑碼的維度，M為關鍵路徑點的最大可行進方向數量，即 M=max(card(Wv))，其中 v=1,2,···,T。在本文使用的測試問題（test problem, TP）中，M=4。解碼經驗表中的初始數值為0，在粒子解碼過程中，表中數值的更新依據式(5)所示的Bellman 方程:

圖6 解碼經驗表Fig.6 Decoding experience table

3）f =min(q)

式中：q 為從起點到終點的路徑點總數；Q(pt+1)為經過 pt+1的所有可行路徑中最小路徑點總數，如果所有路徑都沒有通過 pt+1，則 Q(pt+1)=0 ；δ為調節獎勵值大小的常數。

此外，為了保障算法的尋優能力，路徑碼的解碼過程不僅參考解碼經驗表中的經驗值，也會依概率 ε隨機選擇下一個關鍵路徑點。

1.5 算法流程

多種群合作學習算法流程如圖7 所示。

圖7 一個多模態多目標路徑規劃問題的應用實例Fig.7 An application example of MMOPP problem

2 多種群合作學習算法應用實例

為了進一步說明多種群合作學習算法的作用機理，以圖8 所示面積大小為11×11 的柵格地圖為例，展示粒子在多模態多目標路徑規劃問題中的編碼與解碼過程。其中，路徑規劃的起點與終點分別為 p1和 p13，圖8 中紅色區域模擬路網中的擁擠堵塞路段，則優化問題可描述為

圖8 多種群合作學習算法流程Fig.8 Flowchart of multi-swarm cooperative learning algorithm

式中：x 為可行路徑；f1(x)、f2(x) 和 f3(x)分別為路徑的長度、經過的紅色區域數量和經過的交叉點數量。

2.1 路徑編碼

根據地圖中關鍵點數量提供的決策變量維度，粒子個體將在種群初始化階段完成編碼，如圖9 所示，種群中每個粒子個體都是一個14 維的實數碼。考慮到路徑規劃時有3 個待優化目標，因此，種群被劃分為3 個子種群，每個種群分別負責搜索最短路徑長度、最少紅色區域數量、最少交叉點數量對應的路徑。

圖9 種群（路徑碼）初始化結果Fig.9 Result of initialing particle swarm (path codes)

2.2 路徑解碼

在路徑解碼時，從起點開始基于解碼經驗表中的經驗信息進行解碼，圖10 為以種群1 為例的解碼過程。種群中每個個體的路徑碼解碼都是從起點 p1開 始，依概率 ε (0 ＜ε ＜1)選擇下一個路徑點，即有 ε的概率在鄰接點中隨機選擇下一個路徑點，有(1-ε)的概率依據解碼經驗選擇下一個路徑點，如果解碼經驗表中鄰接關鍵點的經驗值相同，則隨機選擇一個作為下一個路徑點，如果經驗值不同，則選擇經驗值最大的一個作為下一個路徑點。依照此策略持續解碼并更新解碼經驗表，直至下一個路徑點是終點，存儲可行路徑。當個體解碼完成時，更新個體的 pbesti,t；當種群中所有個體解碼完成時，更新種群的 gbestt。由于種群1 的優化目標是最小化路徑長度，因此，pbesti,t與 gbestt的更新僅依據目標值 f1(x)。最后，基于粒子群算法的速度更新公式更新個體位置。整個過程循環迭代直至最大迭代次數。

圖10 以種群1 為例的路徑解碼過程Fig.10 Path decoding process of the first sub-swarm that is responsible for optimizing path length

3 仿真測試與驗證分析

為了驗證多種群合作學習算法在MMOPP 問題上的有效性，本文采用Liang 等[25]構建的MMOPP測試問題集檢測算法的性能。此測試集將實際路網地圖中的道路特征建模成規則的柵格地圖，利用黑色柵格表示可行路段，根據優化目標種類的不同分為三類，共計12 個測試問題。如圖11 所示，第1 類測試問題模擬實際路網地圖中的擁擠路段，紅色柵格表示擁堵路段，其優化目標為最小化路徑長度、擁擠路段數量、交叉點數量，根據問題規模的不同，這類問題包含5 個測試問題。在第2 類測試問題中，如圖12 所示，其有多個表征不同類型道路信息的F 值（F1,F2,···），用不同的F 值模擬道路擁擠度或道路寬度等信息，優化目標為最小化路徑長度和各個F 值，根據優化目標數量的不同，這類問題包含5 個測試問題。圖13 為第3 類測試問題模擬了有必經點約束的路徑規劃需求，而且允許折返路徑存在，黃色柵格表示路徑規劃過程中的必經路段，與第2 類問題類似，每個柵格都有多種不同的F 值（F1,F2,···），其優化目標為最小化路徑長度和各個F 值，根據問題規模的不同，這類問題包含2 個測試問題。因此，本文基于本節12 個MMOPP測試問題，從求解時間、搜索能力、尋優能力三方面對算法的性能進行評估，并將實驗結果與PSO 算法、融合子種群劃分策略的粒子群算法（PSOK）、融合解碼經驗表的粒子群算法（PSOD）進行對比，進一步分析驗證子種群劃分、解碼經驗表策略的有效性。

圖11 第1 類MMOPP 測試問題實例Fig.11 An example of the first kind of MMOPP test problem

圖12 第2 類MMOPP 測試問題實例Fig.12 An example of the second kind of MMOPP test problem

圖13 第3 類MMOPP 測試問題實例Fig.13 An example of the third kind of MMOPP test problem

本文的所有實驗結果都是50 次實驗的平均值，針對同一個測試問題，不同算法的參數、種群大小、迭代次數完全相同。然而，考慮到迭代次數與問題規模大小相關，在本文的仿真測試實驗中，針對不同測試問題搜索最優路徑所需要的迭代次數是不同的，迭代次數的設置依據問題的規模大小與算法的穩定性表現。具體實驗參數設置如表1 所示。

表1 實驗參數Table 1 Experimental parameters

表2 為從不同算法搜索時間的對比結果，可以看出，由于在MSCL 算法中，每個種群內部自主選擇個體最優解與群體最優解，并且在粒子個體解碼過程中有效經驗的總結與利用需要耗費額外的時間，因此，算法的求解時間比其他算法長。盡管MSCL 算法的搜索時間較長，但是，不同算法的搜索時間依舊在同一量級。此外，為了分析比較算法的搜索能力與尋優能力，在表3 和表4 中分別記錄了不同算法完成最大迭代次數時搜索到滿足優化需求的路徑總數和最優路徑數量。這2 個指標可以反映算法的搜索能力與尋優能力。其中，最優路徑是50 次實驗的所有結果經過非支配排序后得到的。在每個測試問題中，性能最好的算法結果加粗表示。從表3 和表4 所示結果可以看出，當實驗條件完全相同時，在測試問題11 中，PSOD 算法和MSCL 算法性能相同。除測試問題6（TP6）外，本文提出的MSCL 算法可以搜索到更多滿足多目標規劃需求的路徑，并且最優路徑的數量明顯多于其他算法的規劃結果。這是由于MSCL 算法采用了子種群劃分策略，平衡了粒子在各個目標維度上的搜索能力，并且經驗解碼表使粒子在搜索過程中可以有效地利用精英解提供的解碼經驗。因此，多個種群的合作學習具有更強的尋優能力。此外，本文對比最優路徑在搜索到的總路徑中所占的比例，并在表5 中展示了實驗結果。從最優路徑占比的結果可以看出除測試問題6（TP6）外，MSCL 算法的路徑規劃結果中最優路徑占比最多。

表2 不同算法的求解時間Table 2 Solving time of different algorithms

表3 不同算法搜索到的路徑數量Table 3 Number of paths searched by different algorithms

表4 不同算法的搜索到的最優路徑數量對比Table 4 Number of optimal paths searched by different algorithms

測試問題11（TP11）只有2 個優化目標，并且在40×40 柵格大小的決策空間內最優路徑數量很少。因此，問題規模小，求解難度小，不同算法的性能差別較小。然而，對于測試問題6（TP6），PSOD 算法與MSCL 算法搜索到的路徑數量相等，但是PSOD搜索到的路徑中最優路徑更多，其最優路徑所占的比例比MSCL 算法多1.2%。為了分析此現象產生的原因，對不同測試問題的求解難度從優化目標數量、地圖變長、編碼維度、最優路徑數量4 個維度進行分析，通過非支配排序的方式，得到如表6 所示的問題難度等級，等級越低，問題求解越容易。由于測試問題11 和問題12 具有必經點約束，且規劃要求不同，為保證分析結果的公平性，未分析這2 個問題的求解難度。

表6 測試問題難度等級分析Table 6 Analysis of difficulty level of test problems

顯然，測試問題3（TP3）與測試問題6（TP6）的求解難度低，算法的性能對比結果不明顯，由于實驗結果是50 次實驗的平均值，少數實驗規劃路徑數量少1 條會導致路徑數量的指標相差10-2的數量級，最終導致最優路徑占比結果的細微差距。因此，為了進一步驗證子種群劃分與解碼經驗表的引入提升了MSCL 算法的尋優能力，基于問題難度等級的增加，不同算法在最優路徑數量與搜索時間指標上的對比結果如圖14 和圖15 所示，橫軸為測試問題，其難度等級依次遞增。

從圖14 和圖15 可以看出，對于簡單的MMOPP問題，不同算法的尋優能力區別不大。但是，相比較于PSO 算法，子種群劃分與解碼經驗表的引入可以有效地提升算法性能。更重要的是，隨著問題求解難度等級的依次遞增，MSCL 算法與其他算法在尋優能力方面的差距逐漸增大。并且，對于測試問題8～10 這類優化目標多、地圖尺寸大的復雜MMOPP問題，MSCL 算法的求解效率、搜索能力、尋優能力都極大地優于其他算法。這進一步說明了多種群合作學習算法能夠有效地解決多模態多目標路徑規劃問題，尤其是在超多目標的多模態路徑規劃問題中具有很好的應用前景。

圖14 不同算法搜索到的最優路徑數量Fig.14 Number of the optimal paths searched by different algorithms

圖15 不同算法規劃路徑所需時間Fig.15 Time used in path planning for different algorithms

4 結 論

1）針對路徑規劃研究中存在解空間大、編碼困難的問題，采用基于關鍵點的路徑編碼，該策略可以降低編碼維度，提高算法的搜索效率。

2）針對多模態多目標的路徑規劃需求，考慮在保障算法尋優能力的同時，平衡粒子群在目標空間內不同維度上的搜索能力，提出基于多目標分解的子種群劃分。

3）為解決路徑規劃問題中編解碼匹配的不唯一性，提出基于解碼經驗表的路徑解碼，通過傳遞有效的解碼經驗，降低解碼的不確定性，進一步提高算法的尋優能力。

4）基于MMOPP 測試集的實驗結果驗證了多種群合作學習算法能夠有效地解決MMOPP 問題，并且，在復雜的MMOPP 問題中，所提算法的尋優能力更強，最優解的多樣性更好，搜索效率受問題規模大小的影響較小。

本文提出的多種群合作學習算法說明了解碼經驗的有效傳遞可以提升算法的搜索能力，提高優化問題的求解效率。因此，在后續的研究工作中筆者將繼續優化與改進解碼經驗的傳遞策略，解決具有多模態多目標優化需求的實際問題。