基于随机游走的多目标A*算法的改进

doi:10.11772/j.issn.1001-9081.2017071899

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 116-119.DOI: 10.11772/j.issn.1001-9081.2017071899

基于随机游走的多目标A^*算法的改进

刘浩翰, 郭晶晶, 李建伏, 贺怀清

中国民航大学计算机科学与技术学院, 天津 300300

收稿日期:2017-08-01 修回日期:2017-08-19 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 郭晶晶
作者简介:刘浩翰(1966-),男,黑龙江富锦人,副教授,硕士,主要研究方向:民航信息智能处理;郭晶晶(1988-),女,河北衡水人,硕士研究生,主要研究方向:民航信息智能处理;李建伏(1979-),女,河北沧州人,副教授,博士,主要研究方向:民航信息系统、人工智能;贺怀清(1969-),女,吉林白山人,教授,博士,CCF会员,主要研究方向:数据挖掘、图形图像与可视分析。
基金资助:
天津市应用基础与前沿技术研究计划重点项目（14JCZDJC32500）。

Improved multi-objective A^* algorithm based on random walk

LIU Haohan, GUO Jingjing, LI Jianfu, HE Huaiqing

College of Computer Science and Technology, Civil Aviation University of China, Tianjin 300300, China

Received:2017-08-01 Revised:2017-08-19 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the Tianjin Research Program of Application Foundation and Advanced Technology (14JCZDJC32500).

摘要/Abstract

摘要： 针对基于降维技术改进的多目标A^*（NAMOA_dr^*）算法中存在的高原搜索现象，结合蒙特卡罗随机游走策略提出了一种基于随机游走的多目标A^*（RWNAMOA_dr^*）算法，其基本思想是当NAMOA_dr^*算法陷入高原搜索时，利用随机游走策略及时找到一个出口（具有被上次扩展标签的启发值非支配的启发值的标签）逃离该高原搜索。针对NAMOA_dr^*算法何时陷入高原搜索的问题，提出了一种检测高原搜索的方法，即当连续扩展m次标签的启发值都被上一次扩展的标签的启发值支配时则认为NAMOA_dr^*算法陷入了高原搜索。使用多目标搜索算法的标准测试平台——随机网格进行了实验。实验结果表明RWNAMOA_dr^*算法比NAMOA_dr^*算法的运行时间平均减少了50.69%，占用的空间平均减少了约10%，能够为现实生活中加速多目标路径搜索提供理论支撑。

关键词: 最短路径, 启发式搜索, 多目标A^*算法, 高原搜索, 蒙特卡罗随机游走

Abstract: Since New Approach to Multi-Objective A^* combined with dimensionality reduction technique (NAMOA_dr^*) algorithm has the phenomenon of plateau exploration, a Random Walk assisted NAMOA_dr^* (RWNAMOA_dr^*) algorithm which invoked a random walk procedure was proposed to find an exit (labels with heuristic value not dominated by the last extended label's) when the NAMOA_dr^*was stuck on a plateau. To determine when NAMOA_dr^* algorithm was stuck on a plateau exploration, a method of detecting plateau exploration was proposed. When the heuristic value of the extended label was dominated by the last extended label's for continuous m times, NAMOA_dr^* algorithm was considered to fall into the plateau exploration. In the experiments, a randomly generated grid was used, which was a standard test platform for the evaluation of multi-objective search algorithms. The experimental results reveal that compared with NAMOA_dr^* algorithm, RWNAMOA_dr^* algorithm's running time is reduced by 50.69% averagely and its space consuming is reduced by about 10% averagely, which can provide theoretical support for accelerating multi-objective path searching in real life.

Key words: shortest path, heuristic search, multi-objective A^* algorithm, plateau exploration, Monte-Carlo random walk

中图分类号:

TP301
TP181

刘浩翰, 郭晶晶, 李建伏, 贺怀清. 基于随机游走的多目标A^*算法的改进[J]. 计算机应用, 2018, 38(1): 116-119.

LIU Haohan, GUO Jingjing, LI Jianfu, HE Huaiqing. Improved multi-objective A^* algorithm based on random walk[J]. Journal of Computer Applications, 2018, 38(1): 116-119.

参考文献

[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.
[2] PAIXÃO J, SANTOS J. Labelling methods for the general case of the multi-objective shortest path problem-a computational study[M]//Computational Intelligence and Decision Making:Trends and Applications. Berlin:Springer, 2013, 61:489-502.
[3] CLÍMACO J C N, PASCOAL M M B. Multicriteria path and tree problems:discussion on exact algorithms and applications[J]. International Transactions in Operational Research, 2012, 19(1/2):63-98.
[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, MVLLER 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, MVLLER 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.

基于随机游走的多目标A^*算法的改进

Improved multi-objective A^* algorithm based on random walk

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李钊, 董霄霄, 黄程程, 任崇广. 基于启发式搜索的浮点表达式设计空间探索方法[J]. 计算机应用, 2020, 40(9): 2665-2669.
[2]	高一鹭, 胡志华. 基于时空网络的自动化集装箱码头自动化导引车路径规划[J]. 计算机应用, 2020, 40(7): 2155-2163.
[3]	向雄, 田检. 基于软件定义网络的对等网传输调度优化[J]. 计算机应用, 2020, 40(3): 777-782.
[4]	杜明, 杨安平, 周军锋, 陈子阳, 杨云. 有向无环图上k步可达查询优化算法[J]. 计算机应用, 2020, 40(2): 426-433.
[5]	王维, 裴东, 冯璋. 改进A^*算法的移动机器人最短路径规划[J]. 计算机应用, 2018, 38(5): 1523-1526.
[6]	李祝红, 赵灿明, 周方, 张信明. 电力通信网络中高效的OSPF流量负载均衡协议[J]. 计算机应用, 2017, 37(7): 1873-1876.
[7]	温菊屏, 胡小生, 林冬梅, 曾亚光. 基于参考节点嵌入的图可达性查询[J]. 计算机应用, 2016, 36(7): 1998-2005.
[8]	邱吉刚, 李汶隆, 杨佳. 基于多点协作的团队出行路径优化算法[J]. 计算机应用, 2015, 35(7): 2093-2095.
[9]	熊壬浩, 刘羽. A^*算法的改进及并行化[J]. 计算机应用, 2015, 35(7): 1843-1848.
[10]	石磊, 苏锦海, 郭义喜. 量子密钥分发网络端端密钥协商最优路径选择算法[J]. 计算机应用, 2015, 35(12): 3336-3340.
[11]	景渊黄国策杨明戚云军陈尚华. 短波IP广域网建模与仿真[J]. 计算机应用, 2014, 34(2): 333-337.
[12]	王小龙赵礼峰. 基于加权节点的Steiner树启发式算法[J]. 计算机应用, 2014, 34(12): 3414-3416.
[13]	孔令晶曾华燊李耀. 等级OSPF网的安全保护方案[J]. 计算机应用, 2013, 33(08): 2212-2217.
[14]	郑伯川桑永胜. 求解最短路径问题的Lotka-Volterra回复式神经网络模型[J]. 计算机应用, 2012, 32(07): 1965-1968.
[15]	朱利娜梁伟赵瑞莲毕经平. 多协议标签交换流量工程隧道实时监测方法——MTRM[J]. 计算机应用, 2012, 32(07): 1812-1815.

基于随机游走的多目标A*算法的改进

Improved multi-objective A* algorithm based on random walk

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

基于随机游走的多目标A^*算法的改进

Improved multi-objective A^* algorithm based on random walk