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

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

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

0 引言

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

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

1 相關知識

1.1 多目標A*算法

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

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

?y′,y∈Rqyy′ ? ?

其中，q是多目標問題中目標的個數(shù)。

定義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)初始化。起始節(jié)點s的標簽Gop(s)={(0)}、Gcl(s)=?，OPEN={(s,0,hs)}，COSTS=?，兩個截斷向量集合T(Gcl(s))=?和T(COSTS)=?。

2)判斷終止。如果OPEN為空，那么從當前節(jié)點回溯到起始節(jié)點，然后返回完整的路徑，并且從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)路徑(解)記錄。如果節(jié)點n是目標節(jié)點，則將gn放入集合COSTS中，并將t(gn)放入T(COSTS)并且更新T(COSTS)。轉向步驟3)。

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

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

②如果不Pareto過濾fm：

如果m是被擴展出的新節(jié)點，則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 隨機游走策略

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

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

2.2 算法描述

圖算法流程

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

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

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

3 實驗分析

3.1 實驗平臺及環(huán)境

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

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

3.2 實驗結果與對比分析

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

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

表1 兩種算法的擴展標簽平均數(shù)

4 結語

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

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] 呂強.面向高性能和強表達力的自動規(guī)劃[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.