基于回溯蟻群-粒子群混合算法的多點路徑規劃

劉麗玨，羅舒寧，高琰，陳美妃

（中南大學信息科學與工程學院，湖南 長沙 410083）

1 引言

隨著智慧旅游的興起，為了向游客提供更精準的導游服務，不少景區推出了官方App。單一基于道路網的導航方式已經難以滿足游客對精準化、個性化導航尋徑的需求。針對旅游景區個性化導航需求，不少論文提出了路徑規劃算法。文獻[1]通過改進A*算法，融合多維動態環境信息，提出了景點間動態路徑規劃的解決方案。文獻[2]以鼓浪嶼景區為例，改進Dijkstra算法，實現了對該景區旅游線路的規劃。文獻[3]考慮了景區路徑的復雜性，將景區路徑分為全景區圖和子景區圖，改進蟻群算法實現了景區路徑規劃。文獻[4]運用混合密度聚類方法識別景點熱度，改進傳統蟻群算法，提出了一種新型的熱門游覽景點路徑規劃方法。這些算法和模型僅僅解決了從起點到終點之間的最優路徑規劃問題。但在實際的旅游需求中，游客或旅游大巴進行路徑規劃時，更希望能得到一條從起點出發，經過某些必去的景點（必經點）的最短規劃路線，以便游客無遺漏且更省時間地進行游覽。

鑒于此問題，本文參考TSP（traveling salesman problem）問題解決方法，提出了一種回溯蟻群-粒子群混合算法（BAPM，backtracking ant colonyparticle swarm method），可用于解決景區中從某個旅游景點開始經過一些特定旅游點的多點路徑規劃問題，該問題的解決對旅游景區多點路徑規劃具有一定的參考價值。

本文將景區景點抽象為點，將景區路徑抽象為有向線段，將景區圖抽象為非完全有向圖，從而對該圖模型進行描述，并且利用該圖模型，實現本文提出的BAPM算法。

2 基本知識

2.1 最大最小蟻群系統

最大最小蟻群系統（MMAS，max-min ant system）[5]是目前眾多蟻群算法中效率較高的算法之一，它模擬了螞蟻在覓食過程中尋找路徑的場景，對當前路徑不斷地進行優化，從而找到最短覓食路線。該算法中，節點i到節點j路徑上的啟發因子記作ηij；在第t次迭代中，節點i到節點j路徑上的信息素記作τij（t）；ηij與τij（t）的占比將會成為第t次迭代中螞蟻k站在節點i選擇下一個節點j所走路徑的重要因素，記作（t），該因素值越大，選擇該值對應的節點的概率就越高。反復迭代該算法，最終可以得到一條近似最短路徑。在迭代過程中，信息素τij（t）根據螞蟻尋找到的最優權值變化進行更新。信息素τij（t）將會被限制在最大最小信息素范圍之間，使該方法不會在短時間內快速收斂陷入局部最優。

2.2 粒子群優化算法

粒子群優化（PSO，particle swarm optimization）算法[6]模擬鳥群或魚群的覓食方法，不斷地更新當前位置及下一時刻的方向及速度，使其不斷逼近目標。在PSO算法中，每個粒子通過不斷的自我學習與向迭代最優粒子學習來改進自身的速度及位置，從而達到一個最優結果。

MMAS算法相對于傳統的蟻群算法來說，極大程度地避免了局部最優情況的發生，并且增加了該模型找到最優值的概率，但是在節點數量非常多的情況下，MMAS仍然容易陷入局部最優，它的最大最小值的限制在避免算法快速陷入局部最優的同時，也降低了其尋找到最優路徑的可能性，即忽略了信息素中的優越因子。為了增強算法尋找最優路徑的能力，本文結合PSO算法和MMAS算法，對信息素τij（t）進行局部及全局更新，突出了對優越路段的標記，實現了對多點路徑規劃問題的有效處理。

3 回溯蟻群-粒子群混合算法

本文提出運用回溯蟻群-粒子群混合算法（BAPM）解決旅游景區中的多點路徑規劃問題。該算法結合了MMAS算法和PSO算法，增強了路徑尋優能力，避免了算法過早陷入局部最優，并改善了算法尋優能力弱的問題，在對比實驗部分，也達到了較為理想的測試結果。該算法如算法1所示。

算法1回溯蟻群-粒子群混合算法

1）使用Floyd-Warshall算法將圖G轉換成，更新權值，用city表示中節點個數

2）建立的權值矩陣，如果兩點之間沒有路徑，則=-1

3）設置迭代次數num和螞蟻數量m

4）初始化信息素τ、啟發因子η、信息素和啟發因子的相關重要性參數α與β、學習因子中的可調參數ω、衰減因子ρ、最小信息素可調參數pbest、迭代代數i=1、全局最優路徑 pathgb、局部最優路徑pathlb及螞蟻所處當前節點startpoint

5）whilei≤num

6）初始化path記錄每只螞蟻走過的路徑

7）forj=1:m

8）startpoint=s

9）設置 city×city的矩陣 tabu_arc，如果=-1，那么tabu_arc（i,j）=-1，設置鄰接表tabu_node用于存放螞蟻當前到達點的可行路段，設置不定長數組node記錄pathj中經過的所有不重復節點

11）if count（tabu_node（startpoint））＞0

12）計算 tabu_node（startpoint）中的所有路段的被選擇概率

14）更新變量,startpoint=b、ifb?node,node={n ode,b}

15）else

16）回溯到tabu_arc的上個狀態, 刪除pathj中的最后一條路段,更新startpoint、node,并在tabu_node中對當前不可行路段進行標記

17）end if

18）end while

20）用改進PSO算法局部更新信息素τ

21）end for

22）對全局最優路徑 pathgb進行更新

23）對信息素τ進行全局更新

24）i=i+1

25）end while

本文所提 BAPM 算法中關鍵的幾個部分為：原始圖G轉換成完全圖；尋找可行路徑，包括路徑的編碼、計算路徑的被選擇概率；信息素的局部更新和全局更新。下面分別對這幾個部分進行詳細說明。

3.1 圖模型轉換

從景區地圖中抽象獲得的圖G是一個非完全有向圖，它存在以下2種特殊情況：1）2個節點之間沒有一條直接連接的路徑，2）直接連接路徑的權值比間接路徑的權值大。因此在處理圖G之前，本文重新構建圖模型，以便更好地計算出多點最短路徑。

假設N為非完全連通圖G=（V,A）中所有節點的個數，其中有n（n≤N-1）個節點為必經節點，從節點s出發，尋找一條經過這n個必經節點一次且僅一次，再返回起始節點s的最短路徑。將起始點s看作固定點，s∈V，必經點集為M?V-{s} 。本文通過以下步驟實現問題的轉換。

步驟 1生成新的頂點集合顯然是V的子集。

步驟 2生成新的邊集合且i,j在G中存在路徑} ，顯然，由于G是一個連通圖，G中任意兩點間都有路徑，則）是一個完全圖。

步驟 3計算圖中每條邊的長度，令中的任意兩點i、j之間的距離為圖G中i、j之間最短路徑的長度，由于G是連通圖，圖中任意兩點間都有路徑，即該長度不會等于無窮大。在圖G中求i、j兩點之間的最短距離使用了Floyd-Warshall[7]算法。

很明顯，通過以上3個步驟建立了一個完全圖，其點集合只包含G中的起始點s和必經點集合M，邊的長度則對應邊的2個端點在G中的最短路徑長度，則原問題轉換為在完全圖中找尋一個最短Hamilton圈的TSP問題。

圖1 多點路徑規劃原問題

圖2 多點路徑規劃轉換后

圖1所示為非完全連通圖。需要從點1出發，前往點2、點3、點4、點5、點6進行游覽，之后回歸點1，起始點s=1，M={ 2 ,3,4,5,6}。將圖1中必經點提取出來構成圖2，運用Floyd算法計算集合M中每兩點之間最短路徑長度，將其作為圖2中的邊長。

斯坦納旅行商問題[8]（STSP，Steiner traveling salesman problem）與本文所述問題相似，都是解決經過必經點的路徑規劃問題，并且必經點可以重復使用。不同之處點在于STSP有固定的起始點和終點，而本文所述問題僅需要固定起始點。由于必經點可以重復使用，為了讓該問題在定義上更加準確，引入引理1[8]。

引理1在 STSP最佳解決方案中，任何一條有向邊僅能遍歷一次。

也就是說，在圖的最優路徑中，點集中的節點可以重復使用，但邊集中的有向邊不能重復使用。本文基于此規則實現了BAPM算法對最小權值路徑的搜索。

3.2 尋找可行路徑

3.2.1 路徑編碼

將景區地圖按照3.1節步驟1～步驟3進行轉換后，問題轉變為從轉換后的圖中給定的起始點s出發，需要找到一條經過所有必經點的可行路徑。

由3.1節可知，為轉換圖的有向邊集合。從節點i出發到達節點j的有向邊記作（i,j）。本文用圖中的邊構成的位串對路徑進行編碼，將螞蟻a尋找到的路徑patha表示為

將路徑patha中包含的所有不重復節點的集合記作node；使用禁忌表tabu_arc對有向邊集合進行管理，保證在patha中的有向邊不會重復出現；使用鄰接表tabu_node來記錄路徑patha當前到達節點的可選路段；startpoint記錄路徑當前到達的節點，當路徑patha經過（i,j）時，可以說當前路徑patha到達了節點j，此時startpoint=j。

3.2.2 可行路徑的尋找與路段的選擇

根據圖 2，初始化的權值矩陣和禁忌表tabu _ arc為

其中，存放路段的權值，tabu_arc表示路徑段的使用狀態，“0”表示該路徑可行，“-1”表示該路徑不可行。

尋找一條可行路徑的方法如下。螞蟻a從起始點startpoint=s開始尋找路徑，根據tabu_node（startpoint）得到下一時刻的所有可選路段，選擇其中一條路段（s,j），在tabu_arc中將已走過的路段標記為“-1”，同時，將路段（s,j）存入patha中，并且startpoint=j。為了減少算法的時間復雜度，tabu_node使用散列表進行存儲。當執行到某個沒有可行邊的節點，即可行路段tabu_node（startpoint）為空或者均已被標記時，證明該路徑不可行，則使用回溯方法，最終找到一條可行路徑。

上述尋找可行路徑的過程可簡化表示為圖3。

圖3 尋找可行路徑的迭代過程

在非完全有向圖中，運用回溯方法查詢路徑可以避免產生非可行性路徑，提高選擇路徑的效率。

Tabu_node表中，確定可選路段是該算法中的一個重要環節。在第k次迭代中，螞蟻a在尋找路徑時，會根據startpoint對應的tabu_node（startpoint）中每條路段的可行概率（k）,i∈,j∈，i≠j，選擇概率大的路段，并根據已選擇的路段到達下個節點d，startpoint=d。若tabu_node不存在可行路段，即 count（tabu_node（startpoint））=0，則刪除patha中startpoint所對應路段，將螞蟻到達的當前節點賦值給startpoint，釋放tabu_arc中該路段的標記，繼續尋找下一個可行路段，以此類推，直到所有必經點都包含在該螞蟻的所行路徑當中，即node=，此路徑patha則為一條可行路徑。這種尋路方式適應本文模型要求，使尋找路徑更加靈活并且保證了每條路徑的可行性，避免了非可行解的產生。

選擇路段的概率計算式如式（1）所示。

3.3 更新信息素

3.3.1 信息素的全局更新

根據上述尋路方法，可以得到所有螞蟻的可行路徑path，找出其中權值最小的路徑，記作 pathgb，并且記錄每只螞蟻的可行路徑，記作 pathlb。在迭代過程中，找出權值最小的路徑并且將其權值與pathgb的權值進行比較，將 pathgb替換成權值最小的路徑，本文將 pathgb稱作全局最優路徑，同理，將pathlb替換成每只螞蟻尋找到的權值最小的路徑，稱作局部最優路徑。

當所有螞蟻均尋找到一條可行路徑后，需要更新圖中每個路段對應的信息素。信息素τij（t）描述了螞蟻經過各個路段所留下的痕跡，本文將τij（t）值較大的路段稱為優越路段，信息素更新如式（2）所示。

其中，參數ρ（0≤ρ≤1）為衰減因子，用于沖淡信息素的濃度；為全局最優路徑 pathgb的信息素增量，計算式如式（3）所示。

為了避免信息素過快地陷入局部最優，設置最大信息素τmax和最小信息素τmin，如式（4）和式（5）所示，則信息素更新范圍為τmin≤τij（t）≤τmax。

其中，city表示點集的大小；pbest表示一個可調參數，本文取值為0.005。

3.3.2 信息素的局部更新

設置最大最小信息素后，隨著迭代次數的增多，優越路段得不到有效的突出，使算法容易陷入局部最優，造成最終得到的最短路徑與期望路徑存在較大差距。本文結合改進后的PSO算法，突出路徑中較優路段的信息素，以保證算法能產生更為接近最短路徑的結果。

基本的 PSO算法通常用于連續函數尋找最優解的問題，粒子從隨機的初始位置出發，不斷改變自身的速度和位置，每次迭代均飛向自身最優和全局最優位置的加權中心，以達到自我認知和信息共享的目的。本文建立了所討論問題和PSO算法之間的映射關系，將問題空間映射到粒子空間，將問題離散化。

將每只螞蟻a的可行路徑patha看作一個粒子，將當前的信息素τ看作粒子的當前位置，將信息素的增量看作PSO算法中的速度變化量。

本文定義了 2個變量——全局最優路徑片段pgb和局部最優路徑片段plb，用于計算粒子的運動速度。全局最優路徑片段為螞蟻當前找到的路徑與全局最優路徑中相同的路徑片段集合，局部最優路徑片段為螞蟻當前找到的路徑與其自身曾找到的最優路徑中相同的路徑片段集合。若螞蟻a找到當前路徑為patha，其計算式為

全局最優路徑為

局部最優路徑為

則全局最優路徑片段為

局部最優路徑片段為

在螞蟻a尋找到可行路徑patha后，得到pgb和plb，增加pgb、plb對應路段的信息素，信息素增長式如式（6）～式（9）所示。

在迭代過程中，不斷地更新 pathlb和 pathgb，從而更新plb和pgb對應的信息素，使信息素不斷地向有益于獲取最優路徑的方向增長，從而使算法能夠更加快速有效地得到圖中的最短路徑。

4 實驗結果與分析

本文的實驗主要分為4個部分。第一部分將本文所提BAPM算法與MMAS算法、遺傳算法（GA，genetic algorithm）進行比較，展示BAPM算法在精確度上的優越性，本文選擇了TSPLIB數據庫中的數據進行實驗。第二部分為仿真實驗，運用BAPM算法尋找包含多點的最短路徑，然后運用分支定界法[9-10]找出這個圖中的精確最短路徑，驗證 BAPM算法尋找最短路徑的正確性。第三部分為景區地圖實際規劃結果，展示了BAPM算法在一個實際的景區地圖數據上的實驗結果。第四部分對上述實驗進行總結。

4.1 TSPLIS數據庫實驗

為了驗證 BAPM 算法有效地改進了局部最優問題并且能找到更為接近的最短路徑，本文使用MMAS算法和GA算法作為對比算法，3種算法均在 MATLAB（R2014a）上進行實現，且迭代次數相同。BAPM算法的參數設置如表1所示。

表1 BAPM算法參數

分別運用BAPM算法、MMAS算法和GA算法對TSPLIS數據庫中提供的14組數據進行實驗，每種算法各運行10次，獲取每組數據在不同算法中運行得到的最大路徑長度、最小路徑長度以及10組數據值與精確解之間的平均偏差百分比，如表2所示。

表2 TSPLIB數據庫對比實驗

4.2 仿真實驗

為驗證BAPM算法的正確性，本文建立了一個仿真系統。該系統可隨機構建不同的圖。這些圖都可以看作景區地圖的抽象圖結構，圖中的頂點對應景區的景點，邊則表示景點之間的路徑。假設必經節點數量為 9，尋找圖中從某一起始點出發經過這些點的最短路徑，就對應為從景區的當前位置出發，規劃一條包含9個游覽景點的最短路徑問題。第一種情況，隨機構建一個包括100個隨機生成的節點的圖，任意兩節點之間均有路徑。在產生的路徑中隨機刪除4 000條路徑，將其轉換為一個稀疏圖，從而模擬景區路線網絡的布局，然后在圖中選擇10個必經點（包含起點），如圖4所示。第二種情況，隨機產生 10個點及其之間的路徑，構成一個有向非完全圖，隨機選擇一個起始點，尋找經過這10個點的最短路徑，如圖5所示。

圖4 第一種情況

圖 4（a）展示了通過 Floyd-Warshall算法變換后的路線圖，由選定的這 10個點構成的圖，圖4（b）是運用BAPM算法經過這10個點尋找的最短路徑。

圖 5（a）為由 Floyd-Warshall算法進行重組的有向圖，圖5（b）表示由BAPM算法產生的最短路徑。

圖5 第二種情況

以上2種情況下本文方法得到的結果與分支定界法找到的路徑相同。

4.3 橘洲景區游覽路線規劃

橘洲景區是長沙的著名旅游景區，本文算法被應用于橘洲景區智能導覽系統中。該系統中的橘洲地圖是借助GPS設備、GOOGLE衛星地圖等，通過實地打點，遍歷景區道路并測量記錄后自行建立的電子地圖，橘洲景區景點的位置信息如表3所示。

以表3中標注*的6個景點為實驗1必經景點，采用BAPM算法規劃出的最佳路徑為：枕江觀光車售票處—沁園春詩詞碑—毛澤東青年藝術雕像—望江亭—指點江山石碑—問天臺，全程645 m，為最短游覽路徑。

以表3中標注#的10個景點為實驗2必經景點，采用BAPM算法規劃出的最佳路徑為：地鐵站西站口—原長沙海關舊址—婚慶園—橘子洲古董鋼琴博物館—沁園春·長沙橘洲 1925 —橘子洲人行入口—美孚洋行舊址—財神古殿—游客服務中心西站點—橘子洲西大門，全程1 218 m，為最短游覽路徑。

表3 橘子洲景區景點信息

實驗1與實驗2均找到了包含必經景點的最短游覽路徑。

4.4 實驗總結

本文使用了3組實驗，驗證了提出的BAPM算法的有效性及優越性。在第一組實驗中，選用了TSPLIB數據庫中的TSP數據，將本文提出的BAPM算法與MMAS算法及GA算法進行了比較，結果顯示BAPM算法可以在數據量較大的條件下，找出更接近最小路徑的結果。在第二組實驗中，隨機生成點和路徑，模擬景區地圖和景點，該組實驗的必經點數設置較小（10個必經點），驗證了在點數較少的情況下，BAPM算法可以有效地找到準確的最短路徑。第三組實驗對實際的景區景點進行規劃，所有景點位置和景點間路徑長度均為實測數據，驗證了算法在景點路徑規劃中的有效性。

通過實驗驗證了BAPM算法的有效性。實驗結果表明，BAPM算法可以處理非完全圖問題和完全圖問題，并且在必經點個數較小的情況下，可以準確并且快速地尋找到最短路徑。

5 結束語

本文針對旅游景區場景下，旅游者對多景點游覽路徑的規劃需求，提出了一種基于回溯蟻群-粒子群混合算法的旅游景點路徑規劃模型，用于解決從起始點出發，經過若干必經點的景區景點路線規劃的問題。通過實驗，證明了BAPM算法可解決上述多點景點路徑規劃問題。由于BAPM算法實際上是一種多點路徑規劃算法，在復雜網絡分析與設計、機器人路徑規劃[11]、路由復雜網絡[12]等方面同樣具有一定的實用價值。