最大团问题研究进展及算法测试标准摘要：定义了最大团问题，分析和研究了使用启发式算法求解最大团问题的进展，介绍了当前求解最大团问题的典型启发式算法，最后给出了测试这些启发式算法性能的测试基准图。关键词：最大团问题；启发式算法；组合优化中图分类号：TP301文献标志码：A文章编号：1001－3695(2007)07－0069－02最大团问题是图论中的一个经典组合优化问题，也是一类NP完全问题，对最大团问题的研究具有很大的理论价值。最大团问题也被称为最大独立集问题，在实践中有非常广泛的应用，被应用于市场分析、方案选择、信号传输、计算机视觉、故障诊断等不同领域。最大团问题在国外有相对广泛的研究，在国内的研究则刚刚起步。图分为有权图和无权图，本文主要讨论针对无权图的最大团问题。??1最大团问题定义??1．1最大团问题的基本定义??对于给定图??G=(V,E)。其中，V={1,…,n}是图G的顶点集，E??V×V是图G的边集。图G的团就是一个两两之间有边的顶点集合。如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图G的极大团。顶点最多的极大团，称之为图G的最大团。最大团问题的目标就是要找到给定图的最大团。??最大团问题也被称为最大独立集问题，独立集指的是两两顶点之间没有边的顶点集合。顶点最多的独立集就是最大独立集。如果C是图G的最大团，其实C也是G??的最大独立集。??1．2最大团问题的数学描述??最大团问题作为一个整数规划问题有许多等价的描述。整数规划问题的描述（二次0－1问题）[1]：??2最大团问题研究进展??1957年，Hararv和Ross首次提出求解最大团问题的确定性算法（ExactAlgorithm）[1]，随后研究者们提出各种各样的确定性算法来求解最大团问题。随着研究的深入，遇到的问题复杂度越来越高（顶点增多和边密度变大），确定性算法逐渐不能有效解决这些问题。??由于最大团问题是一类NP完全问题，确定性算法不能够有效解决这类问题，典型地体现在求解问题时运算时间过长，且不能够很好地克服这一问题。目前确定性算法主要用于求解顶点数相对较少、密度相对较低的图的最大团。??针对上面的情况，在20世纪80年代末开始采用启发式算法求解最大团问题，提出了各种各样的启发式算法，并且取得了令人满意的效果。在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、密度的增加而变得越来越小。唯一的缺点就是不一定能找到最优值，有时只能找到近优值。??启发式算法的出现给求解顶点多、密度高的图的最大团问题带来了希望，并且经过这十几年的发展，取得了长足进步。大部分确定性算法所不能解决的图，用启发式算法都能得到有效解决。人们对启发式算法关注程度越来越高。??当前求解最大团问题的启发式算法都基于以下几类：局部搜索启发式算法(LocalSearchHeuristics)、遗传算法、神经网络、模拟退火和禁忌搜索、基于连续的启发式算法等。在局部搜索启发式算法中，比较著名的算法是K－interchange启发式算法，该算法基于K－neighbor实现。遗传算法在1993年被Carter和Park第一次引进来求解最大团问题[2]。神经网络在1987年被Ballard等人引进来解决最大团问题[3]。***年，Aarts和Korst把模拟退火引进来求解最大团问题[4]。禁忌搜索在***年由Friden等人[5]被用来求解该问题。1990年由Pardalos等人[6]提出一种基于连续的启发式算法来求解最大团问题。??研究表明，单独使用一种启发式算法求解最大团问题，算法性能并不是很好，因此，需要算法之间互相取长补短，形成新的混合算法来求解最大团问题。当前求解该问题最好的启发式算法有反作用禁忌搜索算法（ReactiveTabuSearch）、简单启发式算法(SimpleHeuristicBasedGeneticAlgorithm,HGA)和DLS－MC等。??1998年，Marchiori[7]给出了一种基于遗传算法的简单启发式算法(HGA)。该算法由两部分组成，即简单遗传算法（SimpleGeneticAlgorithm,SGA）和简单的贪婪启发式局部搜索算法。Marchiori在基准图上对算法HGA的性能进行测试，证明了该算法在解的质量和计算速度上均优于基于遗传算法的其他算法。??Battiti和Protasi[8]提出的反作用禁忌搜索算法，通过...