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