最大团问题研究报告
2009
摘要：
本文首先对最大团问题从一般性描述和数学描述两个方面进行了概述，其次对其研究发展进行了概括，之后对解决最大团问题的相关算法进行了逐一介绍，并对部分算法进行了比较分析，并对回溯法和分支限界法详细介绍，最后给出了最大团问题的应用领域。 关键字：最大团、蚁群、启发式、智能搜索
1 最大团问题概述
1.1 最大团问题一般描述
给定无向图G=(V，E)。如果U?V，且对任意u，v?U有(u，v)?E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。
如果U?V且对任意u，v?U有(u，v)?E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。
对于任一无向图G=(V，E)其补图G=(V1，E1)定义为：V1=V，且(u，v)?E1当且仅当(u，v)?E。
U是G的最大团当且仅当U是G的最大独立集。
1 2 3 4 5 图1 无向图G
1.2 最大团问题数学描述
MCP作为一个整数规划问题有许多等价的描述。整数规划问题的描述(二次0-1问题)： 设： 则：
t：(0,1)n?2v?x?{0,1}n,?S?2v,x?t?1(S)?{xi:i?1,2,...,n}xi???0,i?SnS其中, ? 1 , i ? ， n为图的顶点数。
min f(x)?-?xii?1s.t.xi?xj?1,?(i,j)?E,x?{0,1}n
如果 * 是（1）的最优解，那么集合C= t ( x * ) 是图G的最大团，且
x C??f(x)。由于 因此有：
*xixj?{0,1},故xi?xj?1,?(i,j)?E当且仅当xixj?0。nTxx?x?ij(AG?I)xf(x)???xi?2i?1MCP等价于下面的全局二次0-1问题
(i,j)?E,i?j
min f(x)?xTAxs.t.x?{0,1}nA?AG?I。其中：
如果 * 是（2）的最优解，那么集合 C ? t ( x * ) 是图G的一个最大团，且
x
C??f(x*)。2 最大团问题研究发展
1957年，Hararv和Ross首次提出求解最大团问题的确定性算法 ，随后，研究者们提出
各种各样的确定性算法来求解最大团问题。但随着研究的深入，遇到的问题复杂度越来越高(顶点增多和边密度变大)，确定性算法显得无能为力，不能有效解决这些NP完全问题，典型地体现是运行时间过长。
在20世纪80年代末开始采用启发式算法求解最大团问题，提出了各种各样的启发式算法，并且取得了令人满意的效果。在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、密度的增加而变得越来越小。唯一的缺点就是不一定能找到最优值，有时只能找到近优值。在1987年,神经网络被Ballard等人引进来解决最大团问题 。1989年，Aarts和Korst把模拟退火引进来求解最大团问题, Friden等人提出禁忌搜索用来求解该问题。在1990年由Pardal—OS等人提出一种基于连续的启发式算法来求解最大团问题。在1993年遗传算法被Carter和Park第一次引进来求解最大团问题 。
研究表明，单独使用一种启发式算法求解最大团问题，算法性能并不是很好，因此，需要算法之间互相取长补短，形成新的混合算法来求解最大团问题。当前求解该问题最好的启发式算法有反作用禁忌搜索算法(Reactive Tabu Search)、简单启发式算法(Simple Heuristic
Based Genetic Algorithm，HGA)和DLS—MC等。
3 相关算法综述
在解组合优化类问题时，通常有两种类型的算法:精确算法(exact algorithm)和近似算法(approximate algorithm)。精确算法在求解NP-Hard的问题时;通常需要指数时间才能找到最优解。目前求解最大团问题的精确算法，对于部分问题实例计算复杂度最好的结果约为
O(2)n3，对于像最大团问题的这种计算复杂度大的问题，精确算法的求解性能和结果都不
理想。对MCP问题的研究一直是学术界一个非常活跃的领域，学术界已经提出了不少算法，并且大多对1993年DIMACS的数据做了实验，但是仅从发表的试验结果，并不能一概而论说那一种算法最好，每个算法都有自己的长处。从试验结果来看，有几个算法可以说当前最好，如下：
Retrive Local Search(RLS),KLS，Dynamic Local Search(DLS)，Deep Adaptiv eGreedy Search(DAGS)，QUALEX-MS，Edge-AC+LS。群体算法中GLS、EDA/G以及ACO是当前最好的。此外，还有其它一些很有特色的算法，论文《A greedy randomized adaptive search procedure for maximum》提出了采用GRASP算法求解最大团问题；论文《DNA solution of the maximal clique problem》提出了采用DNA计算来求解最大团问题;论文《Variable neighborhood search for the maximum clique》提出了采用VNS算法求解最大团问题;论文《Finding maximum cliques with distributed ants》提出了采用分布式蚁群算法求解最大团问题。
3.1 RLS算法
Reactive Local Search (RLS)算法是Roberto Battiti于1999年提出的一个最大团问求解算法[2]，是在他们先前研究的RTS算法的基础上发展而来的算法.算法用搜索的历史信息，通过内部反馈来决定搜索进程。算法1给出了RLS的基本框架。算法中t是运行代数，T是禁忌时间周期，
tT是上一次T发生变化的时间，CurrentClique表示当前的集团，BestClique
到现在为止找到的最优解，最优解大小为Maxsize，找到最优解的时间是
tb。
为了避免没有意义的重复，T在开始时通常取值1。算法完成初相关参数的始化以后，先通过Memor梦Reaetion找到一个解CurrentClique.如果CurrentClique是一个新解，通过Hash方法把这个解保存起来，根据前面的搜索调整禁忌参数T。然后，搜索CurrentClique的邻域得到一个最好的邻居，赋给CurrentClique.如果找到的CurrentClique是一个最好解，把CurrentClique保存到BestClique，记录Maxsize和t。.如果最好解经过A代没有变化或者自从上一次重新启动已经超过A代，那么重新启动，通常取A=100*Maxsize。
在Best-Neighbor过程，有三种顶点操作:AddMove、DropMove和 NotFound.在Best一Neighbor执行时，首先选择一个可用的顶点通过AddMove都加入到Current-Chque。如果，没有可用顶点，那么就在CurrentClique中选择一个可以删掉的顶点个顶点删除。Memory-取action是RLS算法的一个重要过程，主要用在两个地方:根据过去的搜索历史，动态调整禁忌参数T;影响RJJS算法的重新启动。禁忌参数T在开始的时候都设置为1。但是，为了避免短期的重复，T应该设置的尽可能的大.另一方面，为了限制算法的随机性，T又应该设置的尽可能小.Memory Reaction采用了动态调整T的方法来解决这个矛盾.如果CurrentClique在缓存中，那么可以通过增加T来避免短期的重复。如果CurrentClique不在
缓存中，那么把CurrentClique和时间t加入缓存。如果T在过去的B代内都没有发生变化，那么就减小T。B根据Maxsize动态变化，B=10*Maxsize。禁忌参数的增加减小通过下面的方法实现:Increase(T)=min{max{T·1.1，T+l}，n-2};Deerease(T)=max{min{T·0.9，T-1}，1}.重新
启动的时间间隔A=10*B=100*Maxsize。 总的来说，RLS有几个特点:
算法只有一个核心参数T，类似丁hbu的禁忌表长度。 算法充分利用搜索历史信息来动态改变参数T。 算法提出Tplateau搜索的方法和restart机制。 算法的复杂度为0(max{n，。})，实现采用HASH技术，比较高效。
RLS在1993年DIMACS评测的37实例中，有36求得或超过最好解，基本上是其 它算法的对比对象，但是极个别问题实例没有得到最优解。 RLS算法 Initilation
1. t=0;T=1;
tT=0;
tR=0
2. CurrentClique=0;BestClique=0;MaxSize=0;
tb=0
3. Repreat
4. T=Memory-Reaction(CurrentClique,T)
5. CurrentClique=Best-Neighbor(CurrentClique) 6. t=t+1
7. if f(CurrentClique)>MaxSize then 8. BestClique=CurrentClique 9. MAxSize=| CurrentClique |;10. End if 11. If t-max{12.
tb=t
t,tbR}>A then
tR=t; Restart
13. End if
14. Until MaxSize is acceptable or maximum number of iterations reached
3.2 DLS算法
DLS(Dynamic Local Search)是一种随机搜索算法，搜索过程结合了构造局部扰动技术[27}。算法的行为也只有一个参数penlaty delay决定。算法有重要的过程:expand(G,C)，l-opt(G,C,C’)。每个顶点关联一个非0的penalty，每执行一次迭代，对进入C的顶点，把它的penalty加1。参数pd以iteration为计数器，调节penalty减1。相隔pd代数对所有非0的penalty减1。实际上，penalty就是顶个iteration中被选进C的计数器。
不管是在expand()还是在1-Pt，选择下一个满足条件的顶点都是基于penalty。是expand()的候选集，是指V（
iN(C)Iv?C）中所有与C中所有顶点都相连的合。执行expand (G，N(C)=0
IC)时，尽量不断地增长团，直到
NL(C)是1-oPt()的候选集，是指V中所有满足下面条件的顶点的集合与C中所有的
顶点相连，除了C中唯一的一个点v’。所以，v’就可以同从而形成一个等价的新的C。
1-opt()的说明:
C’是本次迭代开始时的C;
一旦交换后有终止条件
NL(C)中的任意一点进行互换，
N(C)存在，立即停止，转到到外面执行expand();否则，继续执行。
INL(C)检验是否还有可以交换的。
终止条件C?C'=0是希望得到一个与C完全不相同的新集团，避免实际没有多大价值的l-0pt()操作【28】。
在每次迭代后，又加进了一个扰动机制: ·当pd起作用时，一切restart。不过，取前面工作中最后一个被考虑的v，penalty的作用使得这时的restart，与程序开始运行时是不同的。
当pd不起作用时，向C中随机加入一点，挤掉与新加入的点矛盾的点。
3.3 DAGS算法
DAGS是Grosso在2004年提出来的一种启发，它是在基本的贪婪算法基础上发展而来，对基本的贪婪提出了两种改进方法，Greedy-swap和Greedy-weight，DAGS过先后执行两个算法的二个阶段策略，把两种方法融合起来。
对于任意给定的无向图G，定义
Cp(K)?{i?v:|K\\N(i)?p}.p?0,1
Cp(K)也就是与集团K中的元素仅郁个顶点不相连的顶点集合。易知
0C(K)就表示
0与K中元素都相连的顶点集合，
C(K)也是所有能和K组成新的集团的候选顶点集合。 C(K)?0，那么就从C(K)选择一个在子图C(K)000对于给定的初始集团K，如果中度最大的顶点，直到
0C(K)=0，参见一下算法：
K=KWhile
0
0C(K)?0 do