Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (1): 116-119.DOI: 10.11772/j.issn.1001-9081.2017071899

Previous Articles     Next Articles

Improved multi-objective A* algorithm based on random walk

LIU Haohan, GUO Jingjing, LI Jianfu, HE Huaiqing   

  1. 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).


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

  1. 中国民航大学 计算机科学与技术学院, 天津 300300
  • 通讯作者: 郭晶晶
  • 作者简介:刘浩翰(1966-),男,黑龙江富锦人,副教授,硕士,主要研究方向:民航信息智能处理;郭晶晶(1988-),女,河北衡水人,硕士研究生,主要研究方向:民航信息智能处理;李建伏(1979-),女,河北沧州人,副教授,博士,主要研究方向:民航信息系统、人工智能;贺怀清(1969-),女,吉林白山人,教授,博士,CCF会员,主要研究方向:数据挖掘、图形图像与可视分析。
  • 基金资助:

Abstract: Since New Approach to Multi-Objective A* combined with dimensionality reduction technique (NAMOAdr*) algorithm has the phenomenon of plateau exploration, a Random Walk assisted NAMOAdr* (RWNAMOAdr*) 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 NAMOAdr*was stuck on a plateau. To determine when NAMOAdr* 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, NAMOAdr* 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 NAMOAdr* algorithm, RWNAMOAdr* 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

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

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

CLC Number: