一种多目标增量启发式搜索算法  

A Multiobjective Incremental Heuristic Search Algorithm

作　　者：魏唯[1,2] 欧阳丹彤[1,2] 吕帅[1,2] 殷明浩[3] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学符号计算与知识工程教育部重点实验室,长春130012 [3]东北师范大学计算机学院,长春130024

出　　处：《吉林大学学报（理学版）》2009年第4期752-758,共7页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:60773097;60873044;60803102;60873148);教育部博士学科点基金(批准号:20050183065;20060183044);吉林省科技发展计划项目基金(批准号:20060532;20080107);吉林省青年科研基金(批准号:20080617)

摘　　要：提出一种多目标增量启发式搜索算法,该算法结合启发式搜索与增量搜索的思想,当多目标问题搜索图的状态格局发生改变时,该算法并不是对变化后的问题进行完全重新求解,而是部分利用了先前搜索保留的信息求解新问题的最优解集,从而提高了问题求解的效率.通过Gridworld标准测试问题上的实验测试,验证了算法的效率.A muhiobjective incremental heuristic search algorithm which combines heuristic search with incremental search is put forward. When the state space of the muhiobjective problem changes, the algorithm will not resolve the new problem from scratch, but reuse the parts of the information of the previous search to find the set of optimal solutions of the new problem and thus the efficiency of resolution is improved. The experiment results of the Gridworld benchmark problem show that the algorithm can solve a series of similar muhiobjective problems very efficiently when the state space changes continuously.

关 键 词：启发式搜索 增量搜索 多目标问题 最优解集 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]