杨 洪, 张修军, 邵泽辉

(1.成都大学 信息科学与工程学院， 四川 成都 610106； 2.成都大学 模式识别与智能信息处理四川省高校重点实验室， 四川 成都 610106)

一种求解最大团问题的化学反应算法

杨 洪1,2, 张修军1,2, 邵泽辉1,2

(1.成都大学 信息科学与工程学院， 四川 成都 610106； 2.成都大学 模式识别与智能信息处理四川省高校重点实验室， 四川 成都 610106)

最大团问题是在给定的一个图中寻找一个顶点数最大的顶点子集S，使得S中任意2个顶点都相邻,是一个著名的NP完全问题.提出一种带有局部搜索策略的化学反应算法求解最大团问题.为了提高算法的性能，在化学反应算法的分子碰撞阶段引入分子亲和度，使得碰撞后的分子倾向于得到对应于最大团较大的分子.将不相交的Golomb尺问题转化为最大团问题实例，通过求解最大团问题，得到若干不相交的Golomb尺问题的新结果.

最大团问题；局部搜索算法；化学反应优化；启发式算法

0 引言

最大团问题(Maximum Clique Problem,MCP)是指在给定的一幅图中，寻找一个顶点数最大的顶点子集S，使得S中任意两个顶点都能相邻[1].目前，MCP广泛应用于移动网络、计算机视觉、聚类分析、基因嵌合芯片技术、故障诊断与生物分析检验等领域.众所周知，最大团问题是组合优化问题中一个NP完全问题[2]，即对任意的ε>0，除非NP=ZPP，否则在n1-ε时间内不存在多项式时间算法来计算图的最大团[3-4].近年来，研究者得到了更强的结果：对任意的ε>0，除非NP=P，否则最大团问题无法在n1-ε时间内求解[5].由于最大团问题本身的困难性，MCP精确算法的有效性和应用范围仅局限于规模相对较小或者较稀疏的图.此外，受物质的化学反应的启发，研究者将化学反应优化(Chemical Reaction Optimization,CRO)作为一种启发式算法来解决优化问题[6].CRO是一个可变的基于种群的启发式Multi-Agent算法，这里的Agent是一些具有许多特性的分子，这些特性包括分子结构、势能和动能等.分子结构可用来表示问题的解，势能可用来表示该解相应的目标函数值，动能则可用来作为从当前解中选择备选解的标准.在基本的CRO算法中提到了α、β参数及分子分解、壁面碰撞、分子合成、分子间碰撞等函数[7-8].在此基础上，本研究将CRO算法与传统局部搜索算法有机结合，提出了一种带有局部搜索策略的CRO算法.同时，为了提高算法的性能，在CRO算法的分子碰撞阶段引入分子亲和度，进一步，将不相交的Golomb尺问题[9-10]转化为最大团问题的实例，得到了若干不相交的Golomb尺问题的新结果.

1 带局部搜索策略的CRO算法

1.1 局部搜索

局部搜索，即从一个初始状态(又称作解)开始，然后按照某种启发式策略从一个状态移动到另一个状态，如此重复下去，当遇到满意解时算法终止.更精确的描述是，在搜索空间S上定义一个目标函数，其最小值和最优解相对应.此外，当算法到达局部极值时，为了跳出局部最优解，可采用如下的策略：当更新当前解时，若新的状态结果更好，那么无论该状态转换是否被禁止，都将该状态作为下一状态来接受.为了实现这一思想，需要用一个禁忌表来存储被禁忌的移动操作[11-14].

在求解最大团问题的局部搜索算法中，首先将一个初始团C作为输入，经过一系列操作返回一个新团C*作为输出.搜索过程中将不断执行drop和add操作，这些操作都称为一次移动，每一次移动都会存入禁忌列表中，然后更新C和禁忌表长度.实际上，如果每次只操作一个顶点，很容易陷入局部极小的情况，所以考虑每次操作多个顶点，即每次求解时执行多次drop和add操作.具体步骤为：首先，给出算法中的变量名：tenure，禁忌表长度；minTenure，最小禁忌表长度；maxTenure，最大禁忌表长度；inc，禁忌表长度增量；dt，一次操作中的退出次数；maxIter，最大迭代次数；iter，当前迭代次数；cycleCount，当前循环迭代的次数.同时，用一个表保存一组参数(freq，inc，cFreq，dt).详细参见算法1.当算法终止时，团C*作为输出返回，当到达局部极值时，将执行dt次退出操作，见第9行，当陷入局部最优解时，可以用它作为跳出局部最优解的策略.

算法1 LocalSearchForMCP(input:C,output:C*)

1:initialize tenure,minTenure,maxTenure,maxIterations and a vector

(pFreq,pInc,pCFreq,pDt).

2:根据C更新M;iter←0;

3:whileiter

4:iter←iter+1;

5:ifM≠⟩ then

6:从不在禁忌表中选择顶点v且满足v∈M，使得v加入后得到

的候选集顶点数最多;C←CU{v},更新M并将v加入禁忌表;

7:else

8:从C中选择顶点v且满足v∈M，使得v加入后得到的候选集

顶点数最多;C←C{v},更新M并将v加入禁忌表;

9:从C中以概率1/freq删掉min{|C|-1，dt-1}个顶点;更新M

并将v加入禁忌表;

10:end if

11:ifitermodfreq=0 then//以概率1/freq执行下列操作

12:if 禁忌表长度达到最大或者最小 then

13:将当前禁忌表长度设置为最大最小的平均值;

14:end if

15:if 检测到C的状态处于局部极值状态 then //通过记录最近

是否有团多次出现来判断是否处于局部极值状态

16:tenure←tenure+inc;

17:ifcycleCount=cFreqthen

18:从禁忌表中随机选择一个向量(pFreq,pInc,pCFreq,pDt)(freq,inc,cFreq,dt)←(pFreq,pInc,pCFreq,pDt)//更新当前参数cycleCount←0;

19:else

20:cycleCount←cycleCount+1;

21:end if

22:else

23:tenure←tenure-1;

24:end if

25:end if

26:if |C|>|C*| then

27:C*←C;

28:end if

29:ifC*是满意解 then

30:returnC*

31:end if

32:end while

33:end.

1.2 带局部搜索策略的CRO算法

1.2.1 分子与操作.

本算法按照如下方式对一幅图的团S进行编码.设G=(V,E)是一个顶点集为V={v1,v2,…,vn}的图，对每一个v∈V(G)，引入布尔变量xv使得xv=1当且仅当v∈S.用向量，w=(xv1,xv2，…，xvn)表示团S的分子.势能(PE)定义如下，

PE(w)=|V(G)|-∑x∈V(G)xv

(1)

设E(S)表示S中的边集，即E(S)={xy|x,y∈S，xy∈E(G)}.动能(KE)定义如下，

KE(w)=α1|S|-α2|E(N(S))|

(2)

其中，α1，α2是指定的参数.

AFF(w)=χ(G[N(S)])

(3)

其中，χ(G[N(S)])是G[N(S)]的色数.因为图的顶点色问题也是NP完全问题，所以不采用精确算法来求G[N(S)]的色数.由于贪婪算法着色可在多项式时间内完成，所以采用图G[N(S)]的贪婪色数作为结果来衡量分子亲和度AFF(w).

1.2.2 团搜索的不相交Golomb尺

通常，一个Golomb尺是一个整数序列a1

表1 目前H(I,J)最好的上界

对任意I和J，要确定H(I,J)的值是一个有挑战性的问题.固定I，求最优(I，J，N)-DGR的计算复杂度会随J的增大呈指数增长.为求上界，可构造一个(I，J，N)-DGR且使得N尽可能小，由此给出算法2.

算法2 ByClique(I，J，T)

1:得到集合T中所有长度是J的Golomb尺；设这些Golomb 尺构成的集合为W={W1,W2,…，Wn}；

2:通过W构造一个图G=(V,E)使得V=W，且(Wi,Wj)∈E当且仅当Wi∩Wj=⟩；

3:在G的补图中应用最大团算法搜索是否存在团数为I的团；

4:if 存在一个团数为I团 then

5:return TRUE；

6:else

7:return FALSE；

8:end if

但当I和J很大时，所构造的图因太大而无法用计算机处理.对此，首先挑选部分(I，J，N)-DGR，然后用算法2处理剩下的数，再用CRO算法来求所构造的图中指定阶数的团，如算法3所示.

算法3 SearchByClique(TimesSB,k,I,J,N)

1:result←SearchCliqueByCRO(TimesSB，k,I,J,N)；

2:whileresult=FALSEdo

3:result←SearchCliqueByCRO(TimesSB，k,I,J,N)；

4:end while

6:returnByClique(I-k,J,T)

2 计算结果

利用所提出的算法，本研究得到了若干不相交的Golomb尺的一些新的结果，如表2所示.表2中加粗的数值为精确值.其中，得到的若干(I,J,N)-DGR的新结果如图1所示.

表2 H(I,J)的上界

3 结 语

本研究提出了一种带有局部搜索策略的CRO算法求解最大团问题.为了提高算法的性能，在CRO算法的分子碰撞阶段引入分子亲和度，使得碰撞后的分子倾向于得到对应于最大团较大的分子，并将不相交的Golomb尺问题转化为最大团问题的实例，得到了若干不相交的Golomb尺问题的新结果.

[1]Tomita E,Kameda T.Anefficientbranch-and-boundalgorithmforfindingamaximumcliquewithcomputationalexperiments[J].J Glob Opt,2009,37(2):95-111.

[2]Karp R M.Reducibilityamongcombinatorialproblems[C]//ProcofASymposiumontheComplexityofComputerComputations.New York，USA：Springer US,1972:85-103.

[3]Geng X,Xu J,Xiao J,et al.Asimplesimulatedannealingalgorithmforthemaximumcliqueproblem[J].Inf Sci,2007,177(22):5064-5071.

[5]Zuckerman D.Lineardegreeextractorsandtheinapproximabilityofmaxcliqueandchromaticnumber[C]//ProcofSTOC’06.Seattle,Washington,USA:ACM Press,2006.

[6]Lam A Y S,Li V O K.ChemicalReactionOptimization:atutorial[J].Memet Comp,2012,4(1):3-17.

[7]Xu J,Lam A Y S,Li V O K.Chemicalreactionoptimizationfortaskschedulingingridcomputing[J].IEEE Trans Par Distr Syst,2011,22(10):1624-1631.

[8]Katayama K,Hamamoto A,Narihisa H.Aneffectivelocalsearchforthemaximumcliqueproblem[J].Inf Proc Lett,2005,95(5):503-511.

[10]Shearer J B.SomenewdisjointGolombrulers[J].IEEE Trans Inf Theory,1998,44(7):3151-3153.

图1 (a)～(i)为(I，J，N)-DGR的新结果

[11]Gendreau M,Soriano P,Salvail L.Solvingthemaximumcliqueproblemusingatabusearchapproach[J].Ann Oper Res,1993,41(4):385-403.

[12]Glover F.Tabusearch-partI[J].INFORMS J Comp,1989,1(1):89-98.

[13]Glover F.Tabusearch-partII[J].ORSA J Comp,1990,2(1):4-32.

[14]Lam A Y S,Li V O K,Yu J J Q.Real-codedchemicalreactionoptimization[J].Evol Comp IEEE Trans,2012,16(3):339-353.

Chemical Reaction Algorithm to Solve Maximum Clique Problem

YANGHong1,2,ZHANGXiujun1,2,SHAOZehui1,2

(1.School of Information Science and Engineering, Chengdu University, Chengdu 610106, China； 2.Key Laboratory of Pattern Recognition and Intelligent Information Processing of Sichuan Province, Chengdu University, Chengdu 610106, China)

The maximum clique problem consists of finding the largest subset S of the vertices of a graph so that the vertices in S are pairwise adjacent.It is a well-known NP-complete problem.This paper proposes a chemical reaction algorithm with a local search strategy to solve the maximum clique problem.In order to improve the performance of the algorithm,the paper introduces a molecular affinity at the molecular collision stage to obtain comparatively bigger molecules compared with the maximum clique after collision.The paper changes the disjoint Golomb rules into real examples of maximum clique problem.By solving maximum clique problem,the researchers obtain many new results of disjoint Golomb rules.

maximum clique problem；local search algorithm；chemical reaction optimization；heuristic algorithm

1004-5422(2017)01-0043-04

2016-12-25.

国家自然科学基金(61309015)资助项目.

杨 洪(1972 — )， 男， 博士， 讲师， 从事应用数学与优化算法研究.

TP18；TP301.6

A