基于隨機游走的多目標A*算法的改進

劉浩翰，郭晶晶，李建伏，賀懷清

(中國民航大學 計算機科學與技術學院，天津 300300)(*通信作者電子郵箱peony_g@163.com)

0 引言

目前很多研究領域的問題都可以歸結為多目標最短路徑問題，例如，車道規劃、城市交通網絡、機器人監控、衛星定位、路由通信網絡等。

多目標最短路徑問題是根據多個目標在圖中找到起始節點到一個目的節點(一對一問題)或圖中的多個節點(一對多問題)的所有帕累托(Pareto)最優解的集合。學者們提出了幾種解決該問題的方法，包括枚舉方法(標簽設置[1]和標簽校正[2])、排序算法[3]和兩階段算法[4]。在大規模圖中，尋找任意給定的起始節點和目的節點間的最短路徑(一對一的問題，例如路線圖中的導航查詢)，標簽設置算法通常是最佳的選擇。通常情況下，多目標標簽設置算法是在單目標算法，如Dijkstra算法和A*算法[5]基礎上改進的。在一對一問題中A*算法作為Dijkstra算法的變體，通過使用啟發函數來提高搜索效率。如果啟發函數值滿足下界條件，則A*算法是一種精確的算法，即它總是返回一個最優解。極端情況下，如果啟發函數值等于0，A*算法等同于Dijkstra算法。

1 相關知識

1.1 多目標A*算法

多目標A*算法描述如下：G=(N,A,c)用于表示描述搜索空間的有向圖。其中：N表示節點，A表示兩節點之間的有向弧，c表示標志有向弧的多目標代價向量，每一維代表一個目標。在G上任意指定起始節點s∈N，目的節點t∈N，尋找兩節點間的非支配路徑P=(n1,n2,…,nk)，代價向量c(P)可以通過路徑的子部分的代價向量求和得到。多目標A*算法用到的部分重要定義如下。

定義1 支配()或帕累托最優偏序的定義如下：

?y′,y∈Rqyy′ ? ?

其中，q是多目標問題中目標的個數。

定義2 詞典順序(L)的定義如下：

?y′,y∈RqyLy′ ? ??

定義3 給定一個向量v=(v1,v2,…,vn)，它的截斷向量t(v)為刪除頭元素的向量t(v)=(v2,v3,…,vn)。

定義4 給定一組向量X，關于它的截斷向量為T(X)=nd({t(x)|x∈X})，T(X)里僅包括非支配向量。

1)初始化。起始節點s的標簽Gop(s)={(0)}、Gcl(s)=?，OPEN={(s,0,hs)}，COSTS=?，兩個截斷向量集合T(Gcl(s))=?和T(COSTS)=?。

2)判斷終止。如果OPEN為空，那么從當前節點回溯到起始節點，然后返回完整的路徑，并且從COSTS中得到路徑代價。

3)路徑選擇。如果OPEN不為空，從OPEN中選擇一個標簽(n,gn,fn)，其中的fn必須為f中非支配的，即?(n′,gn′,fn′)∈OPEN，不存在fn′fn，并從OPEN中刪除標簽(n,gn,fn)，將gn從Gop(n)移入Gcl(n)，將t(gn)加入T(Gop(n))并更新T(Gcl(n))。如果Pareto過濾fn，則重復步驟3)。

4)路徑(解)記錄。如果節點n是目標節點，則將gn放入集合COSTS中，并將t(gn)放入T(COSTS)并且更新T(COSTS)。轉向步驟3)。

5)擴展路徑。如果節點n不是目標節點，則對節點n的所有子節點m進行如下操作。

①計算到節點m的路徑的代價和其下限，gm=gn+c(n,m)和fm=gm+hm。

②如果不Pareto過濾fm：

如果m是被擴展出的新節點，則Gop(m)={(gm)}并且將(m,gm,fm)放入OPEN表中，并添加從n到m的指針；

如果g(m)等于Gop(m)∪Gop(m)中某向量，則添加從n到m的指針；

如果不進行Pareto修剪：從Gop(m)中刪除所有被gm支配的gm′(gmgm′)，并在OPEN中刪除相應的標簽(m′,gm′,fm′)，將標簽(m,gm,fm)放入OPEN表中，gm放入Gop(m)中并添加從n到m的指針。

③返回步驟3)。

1.2 隨機游走策略

蒙特卡羅隨機游走搜索使用隨機游走策略跳躍搜索當前狀態的一個鄰接狀態，重復循環直到搜索到目標狀態。如果在經過m次這樣的跳躍搜索后，所有狀態的最小啟發函數值仍然沒有減小，或者遇到終端狀態，蒙特卡羅隨機游走會回到初始狀態重新開始搜索。

隨機游走搜索每次從一個狀態開始搜索其鄰接狀態空間，試圖找到一個具有更小啟發式函數值的狀態。在最多n次的循環中，每次搜索一條路徑，計算每條路徑末尾狀態的啟發式函數值，如果其值小于已搜索路徑的最小值，則更新節點和節點的啟發式函數值；最后返回具有最小啟發式函數值的狀態。

2.2 算法描述

圖算法流程

1)在擴展從OPEN表中選出的非支配標簽之前，檢測該標簽是否屬于高原搜索，若屬于則退回至前m步的標簽(s,gs,fs)。

2)從標簽(s,gs,fs)開始，隨機搜索t次，即算法不管是否找到一個更好的標簽都將在有限的時間內返回一個標簽。

3)每次隨機搜索標簽(s,gs,fs)的鄰近長度為l的路徑，并在n條路徑中選擇一條最好的路徑(末尾標簽的啟發值h不被當前標簽的啟發值支配)，返回其末尾的標簽；否則，該標簽作為下一次游走的起始標簽。在搜索過程中，當找到一個出口立刻返回，無需將n條路徑全部搜索完后再結束。

3 實驗分析

3.1 實驗平臺及環境

隨機網格是評測多目標搜索算法的標準測試平臺[20]。本文使用的隨機網格允許解的長度控制算法性能的評估，具體是一張具有10 000個節點和39 800條弧的二維正方形網格圖，并且其每個節點具有4個鄰居節點。實驗環境配置為：硬件環境為Intel Core i7- 6700 CPU@3.40 GHz,4 GB；操作系統為Windows 7 旗艦64位；編程軟件為Lisp Works Professional 6.01；其他軟件為Matlab 8.3。

實驗將起始節點設置在網格的中心位置(50，50)。目的節點放置在中心節點至右下角節點的對角線上，使用解的長度d(20到100)表示目的節點的坐標(50+d/2，50+d/2)。網格中每條弧的代價向量c(i,j)=(c1,c2,c3)是使用均勻分布在1至10范圍內產生的3個數。

3.2 實驗結果與對比分析

圖2 多目標搜索算法的平均運行時間

鑒于此，可將其應用到空鐵聯運路徑搜索問題中。空鐵聯運是指航空運輸與鐵路運輸之間協作的一種聯合運輸方式，參與者包括民航機場、航空公司、鐵路系統等。該算法可搜索出滿足旅客出行多種需求的路線，例如，距離最短、花費最少或者時間最短等，對進一步提高提供給旅客的服務質量，實現民航業客源的增長具有重要的意義。

表1 兩種算法的擴展標簽平均數

4 結語

本文的研究和嘗試僅僅是在多目標搜索問題的經典測試平臺(隨機網格)上進行的，后續工作還需要在真實的空鐵聯運網絡中進行實驗，以發現算法的適應性和局限性。另外，因為算法本質上是啟發式搜索算法，啟發函數對搜索起決定作用，算法應用于空鐵聯運時需要具體研究啟發函數的設計和實現。

References)

[1] MANDOW L, PéREZ de la CRUZ J. Path recovery in frontier search for multi-objective shortest path problems [J]. Journal of Intelligent Manufacturing, 2008, 21(1): 89-99.

[4] MOTE J, MURTHY I, OLSON D L. A parametric approach to solving bicriterion shortest path problems [J]. European Journal of Operational Research, 1991, 53(1): 81-92.

[5] HART P, NILSSON N, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[6] HANSEN P. Bicriterion path problems [C]// Proceedings of the Third Conference on Multiple Criteria Decision Making Theory and Application. Berlin: Springer, 1980: 109-127.

[7] STEWART B S, WHITE C C. Multi-objective A*[J]. Journal of the ACM, 1991, 38(4): 775-814.

[8] MANDOW L, PéREZ de la CRUZ J L. Multi-objective A*search with consistent heuristics [J]. Journal of the ACM, 2010, 57(5): Article No. 27.

[9] PULIDO F J, MANDOW L, PéREZ de la CRUZ J L. Dimensionality reduction in multi-objective shortest path search [J]. Computers & Operations Research, 2015, 64: 60-70.

[10] HAMPSON S, KIBLER D. Plateaus and plateau search in boolean satisfiability problems: when to give up searching and start again [C]// Proceedings of the 2nd DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) Implementation Challenge, Cliques, Coloring and Satisfiability. Providence, RI: American Mathematical Society, 1993: 437-456.

[11] FRANK J D, CHEESEMAN P, STUTZ J. When gravity fails: local search topology [J]. Journal of Artificial Intelligence Research, 1997, 7(1): 249-281.

[12] HOFFMANN J. Local search topology in planning benchmarks: an empirical analysis [C]// IJCAI’01: Proceedings of the 17th International Joint Conference on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2001: 453-458.

[13] HOFFMANN J. Local search topology in planning benchmarks: a theoretical analysis [C]// Proceedings of the 2002 International Conference on AI Planning and Scheduling. Menlo Park, CA: AAAI Press, 2002: 92-100.

[14] BENTON J, TALAMADUPULA K, EYERICH P, et al. G-value plateaus: challenge for planning [C]// Proceedings of the Twentieth International Conference on Automated Planning and Scheduling. Menlo Park, CA: AAAI Press, 2010: 259-262.

[15] GOVER F, LAGUNA M. Tabu Search*[M]. Norwell, MA: Kluwer Academic Publishers, 2013: 3261-3362.

[16] KAUTZ H, SELMAN B. Pushing the envelope: planning, propositional logic, and stochastic search [C]// AAAI’96: Proceedings of the Thirteenth National Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 1996: 1194-1201.

[17] NAKHOST H, MüLLER M. Monte-Carlo exploration for deterministic planning [C]// Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 2009: 1766-1771.

[18] NAKHOST H, HOFFMANN J, MüLLER M. Resource-constrained planning: a Monte Carlo random walk approach [C]// Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling. Menlo Park, CA: AAAI Press, 2012: 181-189.

[19] 呂強.面向高性能和強表達力的自動規劃[D].合肥：中國科學技術大學，2012:29-45.(LYU Q. Towards enhanced efficiency and expressiveness of automated planning [D]. Hefei: University of Science and Technology of China, 2012: 29-45.)

[20] MACHUCA E, MANDOW L, PéREZ de la CRUZ J L, et al. A comparison of heuristic best-first algorithms for bicriterion shortest path problems [J]. European Journal of Operational Research, 2012, 217(1): 44-53.

This work is partially supported by the Tianjin Research Program of Application Foundation and Advanced Technology (14JCZDJC32500).

LIUHaohan, born in 1966, M. S., associate professor. His research interests include intelligent processing of civil aviation information.

GUOJingjing, born in 1988, M. S. candidate. Her research interests include intelligent processing of civil aviation information.

LIJianfu, born in 1979, Ph. D., associate professor. Her research interests include civil aviation information system, artificial intelligence.

HEHuaiqing, born in 1969, Ph. D., professor. Her research interests include data mining, graphic, image and visual analysis.