启发式算法设计中的骨架分析与应用

项目名称： 启发式算法设计中的骨架分析与应用

项目编号： No.60805024

项目类型： 青年科学基金项目

立项/批准年度： 2009

项目学科： 轻工业、手工业

项目作者： 江贺

作者单位： 大连理工大学

项目金额： 19万元

中文摘要： 骨架是描述NP-难解问题特征的强有力手段。基于骨架的启发式算法具有简单灵活、易于实现、性能提升显著等优点。故此，骨架成为启发式算法研究的前沿热点。目前骨架研究还存在众多问题：缺少计算复杂性分析，难以逼近骨架、难以应对小规模骨架实例。针对上述问题，本课题围绕骨架研究进行探索：1）理论基础：骨架的多尺度计算复杂性分析，分析了典型NP-难解问题（包括QAP问题，p-Median问题等）的完整骨架和部分骨架的计算复杂性；2）应用基础：骨架的高效逼近，通过多种不同途径来近似全局最优解以获取高纯度近似骨架；3）骨架应用：小规模骨架实例的启发式算法设计，通过提高骨架规模以提升基于骨架的启发式算法性能。课题组在IEEE Trans. on Soft. Eng., Evol. Comput., Knowl. Based Syst., 中国科学等国内外顶级杂志和GECCO、PPSN等本领域著名会议先后录用、发表论文21篇，其中SCI检索论文5篇，EI检索论文16篇，ISTP检索论文2篇。获得2010年国际演化计算大会（GECCO）元启发式算法领域最佳论文提名和2009年度辽宁省自然科学学术成果奖一等奖。

中文关键词： 启发式算法；骨架分析；组合优化；搜索空间；地貌分析

英文摘要： The backbone is an efficient tool to characterize NP-hard problems. Heuristic Algorithms based on the backbone are usually simple, easy to realize, and achieve dramatic improvement in terms of performance. However, there still exist a lot of problems to be solved in research of the backbone. As for theoretic aspect, few results on computational complexity have been reported yet. In applications, it is hard to approximate the backbone and to tackle instances with small backbones. Aiming to tackle the above problems, this project investigates in the following ways: 1) theoretical foundation, including computational complexity with multiple scales, which focuses on the computational complexity to obtain either full or part of the backbone for typical NP-hard problems (e.g., QAP and p-Median); 2) application foundation, including effectively approximating the backbone in such a way that we approximate global optimal solutions through distinct ways; 3) applications, including heuristic algorithms for instances with small backbone, which improve the performance of heuristic algorithms by enlarging the backbone size. Under the support of this NSFC grant, 21 papers have been accepted or published on top journals and conferences, including IEEE Transactions on Software Engineering, Evolutionary Computation, Knowledge Based Systems, Science in China (English version), GECCO and PPSN. Out of these papers, 5 papers are SCI-indexed, 16 papers are EI-indexed, and 2 papers are ISTP-indexed. One paper of our NSFC grant is nominated for the Best Paper awards in the meta-heuristics track of GECCO 2010. Our research result also achieves the natural science academic prize of LiaoNing Province in 2009.

英文关键词： Heuristic Algorithms; Backbone Analysis; Combinatorial Optimization; Search Space; Fitness Landscape Analysis