一种求解图论中最大独立集问题的启发式算法

冯 云

(河北省药品医疗器械检验研究院，河北 石家庄 050081)

0 引言

最大独立集问题(Maximum Independent Set Problem)是图论中经典的组合优化问题，在生物信息学[1]，无线网络通信[2]，信息传输调度[3]以及社交网络分析[4]等领域有着非常广泛的实际应用，数十年来吸引了国内外大量学者进行研究。Carraghan[5]，Babel[6]，Östergård[7]，Li[8]等人研究了求解的精确算法(Exact Algorithms)，其核心都是基于分支界定策略(Branch and Bound Strategy)。分支界定的基本思想是对解的上界进行估计，当上界小于当前已知解时就放弃该分支的继续搜索，称作“剪枝”。后来有学者对分支界定策略进行了优化，利用动态规划、染色等方法加速剪枝的过程，提高精确算法的速度。尽管如此，在给定图中求解最大独立集仍是NP-hard问题[9]，当图的规模增大，求解该问题的时间复杂度越来越高，精确求解是不可能的，即使是超级计算机也无能为力。因此许多学者研究了启发式算法，启发式算法虽不能保证一定能够得到最优解，但在对于规模较大的最大独立集问题上具有极高的性价比。目前应用比较广泛的启发式算法有贪婪算法(Greedy Algorithm)[10-11]，局部搜索(Local Search)[12-13]和禁忌搜索(Tabu Search)[14]。贪婪算法通过一定的规则按顺序逐次扩充解的集合，直至顺序搜索结束，获得一个可行解。局部搜索对可行解的局部邻域进行搜索，来提高已知解的质量。禁忌搜索是一种改进的局部搜索算法，通过设立“禁忌列表”来避免在搜索过程中出现死循环，并且有助于跳出循环并开发新的搜索区域。本文综合了贪婪算法与禁忌搜索各自的特点，提出了一种启发式的最大独立集问题解法，并使用DIMACS基准中的实例进行了验证，取得了令人满意的效果。……