楊 洪, 張修軍, 邵澤輝

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院， 四川 成都 610106； 2.成都大學(xué) 模式識別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室， 四川 成都 610106)

一種求解最大團(tuán)問題的化學(xué)反應(yīng)算法

楊 洪1,2, 張修軍1,2, 邵澤輝1,2

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院， 四川 成都 610106； 2.成都大學(xué) 模式識別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室， 四川 成都 610106)

最大團(tuán)問題是在給定的一個圖中尋找一個頂點(diǎn)數(shù)最大的頂點(diǎn)子集S，使得S中任意2個頂點(diǎn)都相鄰,是一個著名的NP完全問題.提出一種帶有局部搜索策略的化學(xué)反應(yīng)算法求解最大團(tuán)問題.為了提高算法的性能，在化學(xué)反應(yīng)算法的分子碰撞階段引入分子親和度，使得碰撞后的分子傾向于得到對應(yīng)于最大團(tuán)較大的分子.將不相交的Golomb尺問題轉(zhuǎn)化為最大團(tuán)問題實(shí)例，通過求解最大團(tuán)問題，得到若干不相交的Golomb尺問題的新結(jié)果.

最大團(tuán)問題；局部搜索算法；化學(xué)反應(yīng)優(yōu)化；啟發(fā)式算法

0 引言

最大團(tuán)問題(Maximum Clique Problem,MCP)是指在給定的一幅圖中，尋找一個頂點(diǎn)數(shù)最大的頂點(diǎn)子集S，使得S中任意兩個頂點(diǎn)都能相鄰[1].目前，MCP廣泛應(yīng)用于移動網(wǎng)絡(luò)、計(jì)算機(jī)視覺、聚類分析、基因嵌合芯片技術(shù)、故障診斷與生物分析檢驗(yàn)等領(lǐng)域.眾所周知，最大團(tuán)問題是組合優(yōu)化問題中一個NP完全問題[2]，即對任意的ε>0，除非NP=ZPP，否則在n1-ε時間內(nèi)不存在多項(xiàng)式時間算法來計(jì)算圖的最大團(tuán)[3-4].近年來，研究者得到了更強(qiáng)的結(jié)果：對任意的ε>0，除非NP=P，否則最大團(tuán)問題無法在n1-ε時間內(nèi)求解[5].由于最大團(tuán)問題本身的困難性，MCP精確算法的有效性和應(yīng)用范圍僅局限于規(guī)模相對較小或者較稀疏的圖.此外，受物質(zhì)的化學(xué)反應(yīng)的啟發(fā)，研究者將化學(xué)反應(yīng)優(yōu)化(Chemical Reaction Optimization,CRO)作為一種啟發(fā)式算法來解決優(yōu)化問題[6].CRO是一個可變的基于種群的啟發(fā)式Multi-Agent算法，這里的Agent是一些具有許多特性的分子，這些特性包括分子結(jié)構(gòu)、勢能和動能等.分子結(jié)構(gòu)可用來表示問題的解，勢能可用來表示該解相應(yīng)的目標(biāo)函數(shù)值，動能則可用來作為從當(dāng)前解中選擇備選解的標(biāo)準(zhǔn).在基本的CRO算法中提到了α、β參數(shù)及分子分解、壁面碰撞、分子合成、分子間碰撞等函數(shù)[7-8].在此基礎(chǔ)上，本研究將CRO算法與傳統(tǒng)局部搜索算法有機(jī)結(jié)合，提出了一種帶有局部搜索策略的CRO算法.同時，為了提高算法的性能，在CRO算法的分子碰撞階段引入分子親和度，進(jìn)一步，將不相交的Golomb尺問題[9-10]轉(zhuǎn)化為最大團(tuán)問題的實(shí)例，得到了若干不相交的Golomb尺問題的新結(jié)果.

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

1.1 局部搜索

局部搜索，即從一個初始狀態(tài)(又稱作解)開始，然后按照某種啟發(fā)式策略從一個狀態(tài)移動到另一個狀態(tài)，如此重復(fù)下去，當(dāng)遇到滿意解時算法終止.更精確的描述是，在搜索空間S上定義一個目標(biāo)函數(shù)，其最小值和最優(yōu)解相對應(yīng).此外，當(dāng)算法到達(dá)局部極值時，為了跳出局部最優(yōu)解，可采用如下的策略：當(dāng)更新當(dāng)前解時，若新的狀態(tài)結(jié)果更好，那么無論該狀態(tài)轉(zhuǎn)換是否被禁止，都將該狀態(tài)作為下一狀態(tài)來接受.為了實(shí)現(xiàn)這一思想，需要用一個禁忌表來存儲被禁忌的移動操作[11-14].

在求解最大團(tuán)問題的局部搜索算法中，首先將一個初始團(tuán)C作為輸入，經(jīng)過一系列操作返回一個新團(tuán)C*作為輸出.搜索過程中將不斷執(zhí)行drop和add操作，這些操作都稱為一次移動，每一次移動都會存入禁忌列表中，然后更新C和禁忌表長度.實(shí)際上，如果每次只操作一個頂點(diǎn)，很容易陷入局部極小的情況，所以考慮每次操作多個頂點(diǎn)，即每次求解時執(zhí)行多次drop和add操作.具體步驟為：首先，給出算法中的變量名：tenure，禁忌表長度；minTenure，最小禁忌表長度；maxTenure，最大禁忌表長度；inc，禁忌表長度增量；dt，一次操作中的退出次數(shù)；maxIter，最大迭代次數(shù)；iter，當(dāng)前迭代次數(shù)；cycleCount，當(dāng)前循環(huán)迭代的次數(shù).同時，用一個表保存一組參數(shù)(freq，inc，cFreq，dt).詳細(xì)參見算法1.當(dāng)算法終止時，團(tuán)C*作為輸出返回，當(dāng)?shù)竭_(dá)局部極值時，將執(zhí)行dt次退出操作，見第9行，當(dāng)陷入局部最優(yōu)解時，可以用它作為跳出局部最優(yōu)解的策略.

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

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

(pFreq,pInc,pCFreq,pDt).

2:根據(jù)C更新M;iter←0;

3:whileiter

4:iter←iter+1;

5:ifM≠? then

6:從不在禁忌表中選擇頂點(diǎn)v且滿足v∈M，使得v加入后得到

的候選集頂點(diǎn)數(shù)最多;C←CU{v},更新M并將v加入禁忌表;

7:else

8:從C中選擇頂點(diǎn)v且滿足v∈M，使得v加入后得到的候選集

頂點(diǎn)數(shù)最多;C←C{v},更新M并將v加入禁忌表;

9:從C中以概率1/freq刪掉min{|C|-1，dt-1}個頂點(diǎn);更新M

并將v加入禁忌表;

10:end if

11:ifitermodfreq=0 then//以概率1/freq執(zhí)行下列操作

12:if 禁忌表長度達(dá)到最大或者最小 then

13:將當(dāng)前禁忌表長度設(shè)置為最大最小的平均值;

14:end if

15:if 檢測到C的狀態(tài)處于局部極值狀態(tài) then //通過記錄最近

是否有團(tuán)多次出現(xiàn)來判斷是否處于局部極值狀態(tài)

16:tenure←tenure+inc;

17:ifcycleCount=cFreqthen

18:從禁忌表中隨機(jī)選擇一個向量(pFreq,pInc,pCFreq,pDt)(freq,inc,cFreq,dt)←(pFreq,pInc,pCFreq,pDt)//更新當(dāng)前參數(shù)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 分子與操作.

本算法按照如下方式對一幅圖的團(tuán)S進(jìn)行編碼.設(shè)G=(V,E)是一個頂點(diǎn)集為V={v1,v2,…,vn}的圖，對每一個v∈V(G)，引入布爾變量xv使得xv=1當(dāng)且僅當(dāng)v∈S.用向量，w=(xv1,xv2，…，xvn)表示團(tuán)S的分子.勢能(PE)定義如下，

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

(1)

設(shè)E(S)表示S中的邊集，即E(S)={xy|x,y∈S，xy∈E(G)}.動能(KE)定義如下，

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

(2)

其中，α1，α2是指定的參數(shù).

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

(3)

其中，χ(G[N(S)])是G[N(S)]的色數(shù).因?yàn)閳D的頂點(diǎn)色問題也是NP完全問題，所以不采用精確算法來求G[N(S)]的色數(shù).由于貪婪算法著色可在多項(xiàng)式時間內(nèi)完成，所以采用圖G[N(S)]的貪婪色數(shù)作為結(jié)果來衡量分子親和度AFF(w).

1.2.2 團(tuán)搜索的不相交Golomb尺

通常，一個Golomb尺是一個整數(shù)序列a1

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

對任意I和J，要確定H(I,J)的值是一個有挑戰(zhàn)性的問題.固定I，求最優(yōu)(I，J，N)-DGR的計(jì)算復(fù)雜度會隨J的增大呈指數(shù)增長.為求上界，可構(gòu)造一個(I，J，N)-DGR且使得N盡可能小，由此給出算法2.

算法2 ByClique(I，J，T)

1:得到集合T中所有長度是J的Golomb尺；設(shè)這些Golomb 尺構(gòu)成的集合為W={W1,W2,…，Wn}；

2:通過W構(gòu)造一個圖G=(V,E)使得V=W，且(Wi,Wj)∈E當(dāng)且僅當(dāng)Wi∩Wj=?；

3:在G的補(bǔ)圖中應(yīng)用最大團(tuán)算法搜索是否存在團(tuán)數(shù)為I的團(tuán)；

4:if 存在一個團(tuán)數(shù)為I團(tuán) then

5:return TRUE；

6:else

7:return FALSE；

8:end if

但當(dāng)I和J很大時，所構(gòu)造的圖因太大而無法用計(jì)算機(jī)處理.對此，首先挑選部分(I，J，N)-DGR，然后用算法2處理剩下的數(shù)，再用CRO算法來求所構(gòu)造的圖中指定階數(shù)的團(tuán)，如算法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 計(jì)算結(jié)果

利用所提出的算法，本研究得到了若干不相交的Golomb尺的一些新的結(jié)果，如表2所示.表2中加粗的數(shù)值為精確值.其中，得到的若干(I,J,N)-DGR的新結(jié)果如圖1所示.

表2 H(I,J)的上界

3 結(jié) 語

本研究提出了一種帶有局部搜索策略的CRO算法求解最大團(tuán)問題.為了提高算法的性能，在CRO算法的分子碰撞階段引入分子親和度，使得碰撞后的分子傾向于得到對應(yīng)于最大團(tuán)較大的分子，并將不相交的Golomb尺問題轉(zhuǎn)化為最大團(tuán)問題的實(shí)例，得到了若干不相交的Golomb尺問題的新結(jié)果.

[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的新結(jié)果

[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.

國家自然科學(xué)基金(61309015)資助項(xiàng)目.

楊 洪(1972 — )， 男， 博士， 講師， 從事應(yīng)用數(shù)學(xué)與優(yōu)化算法研究.

TP18；TP301.6

A