999精品在线视频,手机成人午夜在线视频,久久不卡国产精品无码,中日无码在线观看,成人av手机在线观看,日韩精品亚洲一区中文字幕,亚洲av无码人妻,四虎国产在线观看 ?

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

2018-03-20 00:46:36劉浩翰郭晶晶李建伏賀懷清
計算機應用 2018年1期

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

(中國民航大學 計算機科學與技術學院,天津 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.

主站蜘蛛池模板: 欧美日本视频在线观看| 久久永久免费人妻精品| 青青草国产在线视频| 免费毛片视频| 女人天堂av免费| 国产一级毛片高清完整视频版| 91在线日韩在线播放| 国产在线精品香蕉麻豆| 无码不卡的中文字幕视频| 欧美成人精品一区二区| 亚洲天堂网视频| 在线精品亚洲一区二区古装| 91偷拍一区| 国产精品视频猛进猛出| 精品国产香蕉在线播出| 青青青视频91在线 | 国产菊爆视频在线观看| 免费中文字幕一级毛片| AV无码一区二区三区四区| 亚洲一区波多野结衣二区三区| 乱系列中文字幕在线视频| 99爱视频精品免视看| 男女男精品视频| 欧美日韩国产系列在线观看| 91在线高清视频| 91网站国产| 国产视频大全| 久久不卡国产精品无码| 毛片一区二区在线看| 日韩经典精品无码一区二区| 亚洲a级毛片| 欧美日韩v| 久久青青草原亚洲av无码| 日本欧美午夜| 国产人人干| 露脸国产精品自产在线播| 多人乱p欧美在线观看| 国产爽爽视频| 欧美性爱精品一区二区三区| 爱色欧美亚洲综合图区| 亚洲黄色片免费看| 永久免费无码成人网站| 日本国产一区在线观看| 91香蕉视频下载网站| 久久精品午夜视频| 性网站在线观看| 成人伊人色一区二区三区| 亚洲视频黄| 亚洲精品在线观看91| 亚洲av日韩av制服丝袜| 亚洲国产精品VA在线看黑人| 亚洲中文字幕97久久精品少妇| 亚洲欧洲日韩综合色天使| 色综合中文| 美女内射视频WWW网站午夜| 日韩在线观看网站| 国产精品黄色片| 四虎影视永久在线精品| 亚洲精品第五页| 欧美va亚洲va香蕉在线| 欧美激情视频一区| 香蕉视频在线观看www| 久久综合丝袜日本网| 国产成人久久综合777777麻豆| 无码中文字幕加勒比高清| 国产精品一区在线观看你懂的| 久久久久国色AV免费观看性色| 亚洲精品无码久久久久苍井空| 日韩A级毛片一区二区三区| 精品国产成人a在线观看| 亚洲中文字幕无码爆乳| 精品久久人人爽人人玩人人妻| 亚洲成人精品在线| 国产99视频精品免费观看9e| 一区二区午夜| 欧美成人国产| 亚洲中文字幕手机在线第一页| 色首页AV在线| 成年女人a毛片免费视频| 欧美三级视频网站| 亚洲国产综合自在线另类| 亚洲精品爱草草视频在线|