中文摘要：

骨架是描述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年度辽宁省自然科学学术成果奖一等奖。