一種求解最大團問題的化學反應算法

楊 洪, 張修軍, 邵澤輝

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

一種求解最大團問題的化學反應算法

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

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

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

最大團問題；局部搜索算法；化學反應優(yōu)化；啟發(fā)式算法

0 引言

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

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

1.1 局部搜索

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

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

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

7:else

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

頂點數(shù)最多;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執(zhí)行下列操作

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

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

14:end if

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

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

16:tenure←tenure+inc;

17:ifcycleCount=cFreqthen

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

本算法按照如下方式對一幅圖的團S進行編碼.設(shè)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)

設(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ù).因為圖的頂點色問題也是NP完全問題，所以不采用精確算法來求G[N(S)]的色數(shù).由于貪婪算法著色可在多項式時間內(nèi)完成，所以采用圖G[N(S)]的貪婪色數(shù)作為結(jié)果來衡量分子親和度AFF(w).

1.2.2 團搜索的不相交Golomb尺

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

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

對任意I和J，要確定H(I,J)的值是一個有挑戰(zhàn)性的問題.固定I，求最優(yōu)(I，J，N)-DGR的計算復雜度會隨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當且僅當Wi∩Wj=?；

3:在G的補圖中應用最大團算法搜索是否存在團數(shù)為I的團；

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

5:return TRUE；

6:else

7:return FALSE；

8:end if

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

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

表2 H(I,J)的上界

3 結(jié) 語

本研究提出了一種帶有局部搜索策略的CRO算法求解最大團問題.為了提高算法的性能，在CRO算法的分子碰撞階段引入分子親和度，使得碰撞后的分子傾向于得到對應于最大團較大的分子，并將不相交的Golomb尺問題轉(zhuǎn)化為最大團問題的實例，得到了若干不相交的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.

國家自然科學基金(61309015)資助項目.

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

TP18；TP301.6

A