GPP问题的骨架分析与启发式算法设计

Backbone Analysis and Heuristic Design for the Graph Partitioning Problem

图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论上证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.

The graph partitioning problem （GPP） is one of the typical NP-Hard problems with extensively wide applications. Efficient heuristics have been the hotline in this research area at all times. There exist defects of theoretic results and limited size in backbone analysis, a useful tool for heuristic design of the GPP. In this paper, by constructing the biased instance, it is proved that it is NP-Hard to obtain the GPP backbone, and the backbone size is increased through analyzing the relationship between the biased GPP instance and general GPP instances. Furthermore, the biased instance-IBS （BI-IBS） is proposed to improve the IBS which is one of the best heuris- tics for the GPP. In this new heuristic, after a biased GPP instance was built and reduced by intersection of local optimal solutions, the reduced instance was then solved. Experiments indicate that the BI-IBS had achieved better performance than existing heuristics in terms of solution quality. Not only this work solved existing problems in research of the GPP backbone, but the skill of biased instance construction threw a light on the theoretic analysis of backbone and heuristic design for other NP-Hard problems.