结合增量与启发式搜索的多目标问题处理方法

An Approach Combining Incremental Search and Heuristic Search for Solving Multiobjective Problems

提出了一种结合增量与启发式搜索的多目标问题处理方法,设计并实现了一个基于路径扩展方法的多目标增量启发式搜索系统.当问题搜索图中边的权重发生改变或添加删除节点时,该系统通过对搜索现场进行实时的更新,部分利用先前搜索保留的信息,从更新后的状态开始求解新的问题,从而提高了重搜索的效率.对gridworld标准测试样例进行了大量的系统测试,实验结果表明:结合增量与启发式搜索的处理方法能够有效地解决状态格局不断变化的一系列相似的多目标最短路径问题.

Multiobjective problems are much more difficult to solve than single objective problems because of the multiple conflicting objectives.Heuristic search is an efficient approach for solving multiobjective shortest paths problems.However,many real problems change their state spaces with different situations.Incremental search which reuses information from previous searches can be used to find solutions in dynamic situations.In this paper,an approach combining incremental search and heuristic search for solving multiobjective problems is proposed,and a multiobjective incremental heuristic search system based on path expansion in the search process is designed and implemented.When the edge costs of a graph change or nodes are added or deleted in the state space,the system does not solve the new problem from scratch,but updates the scene of the search immediately,reuses parts of the information of the previous search and then starts a new search process from the scene after the update process,thus the efficiency of replanning is improved.The gridworld benchmark problem is used for testing and the experimental results show that the approach combining incremental search and heuristic search can solve a series of similar multiobjective shortest path problems very efficiently when the state space changes continuously.