基于隨機(jī)游走的多目標(biāo)A*算法的改進(jìn)

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

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

0 引言

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

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

1 相關(guān)知識(shí)

1.1 多目標(biāo)A*算法

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

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

?y′,y∈Rqyy′ ? ?

其中，q是多目標(biāo)問題中目標(biāo)的個(gè)數(shù)。

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

?y′,y∈RqyLy′ ? ??

定義3 給定一個(gè)向量v=(v1,v2,…,vn)，它的截?cái)嘞蛄縯(v)為刪除頭元素的向量t(v)=(v2,v3,…,vn)。

定義4 給定一組向量X，關(guān)于它的截?cái)嘞蛄繛門(X)=nd({t(x)|x∈X})，T(X)里僅包括非支配向量。

1)初始化。起始節(jié)點(diǎn)s的標(biāo)簽Gop(s)={(0)}、Gcl(s)=?，OPEN={(s,0,hs)}，COSTS=?，兩個(gè)截?cái)嘞蛄考蟃(Gcl(s))=?和T(COSTS)=?。

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

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

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

5)擴(kuò)展路徑。如果節(jié)點(diǎn)n不是目標(biāo)節(jié)點(diǎn)，則對(duì)節(jié)點(diǎn)n的所有子節(jié)點(diǎn)m進(jìn)行如下操作。

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

②如果不Pareto過濾fm：

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

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

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

③返回步驟3)。

1.2 隨機(jī)游走策略

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

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

2.2 算法描述

圖算法流程

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

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

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)平臺(tái)及環(huán)境

隨機(jī)網(wǎng)格是評(píng)測(cè)多目標(biāo)搜索算法的標(biāo)準(zhǔn)測(cè)試平臺(tái)[20]。本文使用的隨機(jī)網(wǎng)格允許解的長度控制算法性能的評(píng)估，具體是一張具有10 000個(gè)節(jié)點(diǎn)和39 800條弧的二維正方形網(wǎng)格圖，并且其每個(gè)節(jié)點(diǎn)具有4個(gè)鄰居節(jié)點(diǎn)。實(shí)驗(yàn)環(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。

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

3.2 實(shí)驗(yàn)結(jié)果與對(duì)比分析

圖2 多目標(biāo)搜索算法的平均運(yùn)行時(shí)間

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

表1 兩種算法的擴(kuò)展標(biāo)簽平均數(shù)

4 結(jié)語

本文的研究和嘗試僅僅是在多目標(biāo)搜索問題的經(jīng)典測(cè)試平臺(tái)(隨機(jī)網(wǎng)格)上進(jìn)行的，后續(xù)工作還需要在真實(shí)的空鐵聯(lián)運(yùn)網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，以發(fā)現(xiàn)算法的適應(yīng)性和局限性。另外，因?yàn)樗惴ū举|(zhì)上是啟發(fā)式搜索算法，啟發(fā)函數(shù)對(duì)搜索起決定作用，算法應(yīng)用于空鐵聯(lián)運(yùn)時(shí)需要具體研究啟發(fā)函數(shù)的設(shè)計(jì)和實(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] 呂強(qiáng).面向高性能和強(qiáng)表達(dá)力的自動(dòng)規(guī)劃[D].合肥：中國科學(xué)技術(shù)大學(xué)，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.