期刊首页 优先出版 当期阅读 过刊浏览 作者中心 关于期刊 English

《中国工程科学》 >> 2009年 第11卷 第9期

基于Backbone的空间收缩与划分算法

山东省标准化研究院,济南 250014

资助项目 :国家“八六三”计划资助项目(2006AA04A129) 收稿日期: 2008-03-13 发布日期: 2009-09-14 16:25:02.000

下一篇 上一篇

摘要

搜索空间的规模和复杂程度是决定问题求解难度的重要因素,而解空间的信息往往可以引导搜索找到最优解。在已知JSP空间结构的基础上,提出一种空间收缩与划分算法。算法利用搜索算法获得的较优解,结合组合优化问题解的backbone的概念,将搜索空间收缩并划分为一个或多个优解域,在优解域内再进行小规模问题的优化。该算法不必在求解前或求解过程中进行大量的统计分析工作,可以利用求解信息对解空间的地形进行估计,提高求解速度和解的质量。实验结果也证明了算法的有效性。

参考文献

[ 1 ] Slaney J, Walsh T.Backbones in optimization and approximation [ A] .In Proceedings of the 17th International Joint Conference on Artificial Intelligence ( IJCAI -2001 ) [ C] , 2001 : 254 -259

[ 2 ] Martin O C, Monasson R, Zecchina R.Statistical mechanics methods and phase transitions in combinatorial problems [ J ] . Theoretical Computer Science, 2001 , 265 ( 1 -2 ) : 3 -6 链接1

[ 3 ] Matthew J S, Stephen F S.How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines[ R] . Pittsburgh: School of Computer Science, Carnegie Mellon Univer- sity, CMU -CS -05 -162 , 2005

[ 4 ] Zeng Sanyou , Kang Lishan , Ding Lixin.A new method of evolu- tionary algorithm for mixed-integer nonlinear optimization problem [ J ] .Wuhan Univ ( Nat Sci Ed) , 2000 , 46 ( 5B) : 554 -558

[ 5 ] 谢胜利,黄强,董金祥.求解JSP的遗传算法中不可行调度的方案[J].计算机集成制造系统-CIMS,2002,8(11):902-906 链接1

相关研究