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

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

Improved multi-objective A* algorithm based on random walk

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.