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

J4 ›› 2009, Vol. 47 ›› Issue (4): 752-758.

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

魏唯^1,2, 欧阳丹彤^1,2, 吕帅^1,2, 殷明浩³

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

收稿日期:2008-11-13 出版日期:2009-07-26 发布日期:2009-08-24
通讯作者: 欧阳丹彤 E-mail:ouyang@jlu.edu.cn

A Multiobjective Incremental Heuristic Search Algorithm

WEI Wei^1,2, OUYANG Dantong^1,2, LV Shuai^1,2, YIN Minghao³

1. College of Computer Science and Technology, Jilin University, Changchun 130012, China|2. Key Laboratory ofSymbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;3. School of Computer Science, Northeast Normal University, Changchun 130024, China

Received:2008-11-13 Online:2009-07-26 Published:2009-08-24
Contact: OUYANG Dantong E-mail:ouyang@jlu.edu.cn

摘要/Abstract

摘要：

提出一种多目标增量启发式搜索算法, 该算法结合启发式搜索与增量搜索的思想, 当多目标问题搜索图的状态格局发生改变时, 该算法并不是对变化后的问题进行完全重新求解, 而是部分利用了先前搜索保留的信息求解新问题的最优解集, 从而提高了问题求解的效率. 通过Gridworld标准测试问题上的实验测试, 验证了算法的效率.

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

Abstract:

A multiobjective incremental heuristic search algorithm which combines heuristic search with incremental search is put forward. When the state space of the multiobjective 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 multiobjective problems very efficiently when the state space changes continuously.

Key words: heuristic search, incremental search, multiobjective problems, set of optimal solutions

中图分类号:

TP18

魏唯, 欧阳丹彤, 吕帅, 殷明浩. 一种多目标增量启发式搜索算法[J]. J4, 2009, 47(4): 752-758.

WEI Wei, OU Yang-Dan-Tong, LV Shuai, YAN Meng-Gao. A Multiobjective Incremental Heuristic Search Algorithm[J]. J4, 2009, 47(4): 752-758.

[1]	王立君, 富倩. 一种凹形区域和简单宽边界区域间的拓扑关系表示模型[J]. J4, 2013, 51(03): 487-490.
[2]	王涛, 王瑞芹, 李占山, 陈超. 基于分割的超树分解方法[J]. J4, 2013, 51(02): 257-266.
[3]	王雁苓, 孙利, 郭新辰, 吕学实. 应用字典数据建模[J]. J4, 2013, 51(02): 273-278.
[4]	李健, 欧阳继红, 王国伟, 陈岗. 一个带单洞区域和一个简单区域间的拓扑关系表示[J]. J4, 2012, 50(06): 1209-1213.
[5]	吴晓洲, 万里明, 韩霄松, 梁艳春, 吴春国. 基于隐马尔可夫模型的转录因子文本挖掘算法[J]. J4, 2012, 50(02): 320-322.
[6]	孙凤芳, 朱晓冬, 刘元宁, 张晓旭, 张巍, 李为韬, 李鑫. 一种Personality_OCC情感建模的新方法[J]. J4, 2012, 50(01): 106-110.
[7]	王海洋, 王江, 李红利, 陈颖源, 王延权. 基于Terminal滑模的HindmarshRose神经元放电同步控制[J]. J4, 2011, 49(06): 1087-1094.
[8]	钟毅, 刘桂霞, 郑明, 沈威, 赖丽娜, 周春光. 基于AP算法支持向量机的设计与应用[J]. J4, 2011, 49(05): 906-910.
[9]	葛金辉. 有时间窗的车辆路径问题及改进[J]. J4, 2011, 49(01): 105-111.
[10]	杜会盈, 李占山, 李宏博, 沈海娇. 图分割在Singleton弧相容算法中的应用[J]. J4, 2010, 48(06): 981-986.
[11]	王俊勇, 张长海, 刘元宁, 朱晓冬, 何飞. 基于ROI归一化的ICA/PCA虹膜识别方法[J]. J4, 2010, 48(05): 793-798.
[12]	池淑珍, 周春光, 张长胜, 杨草原. 一种受限于给定最大延误上界的单目标启发式算法[J]. J4, 2010, 48(05): 805-810.
[13]	王红梅, 李宏博, 李占山. 无环配置问题研究[J]. J4, 2010, 48(03): 444-448.
[14]	李永丽, 刘衍珩, 肖见涛, 李向涛, 关伟洲. 基于支持向量机的增量学习算法[J]. J4, 2010, 48(03): 464-467.
[15]	李妮娅, 刘大有, 张健. 面向制造业的产品配置器与PDM集成设计方法[J]. J4, 2010, 48(1): 73-78.