圖節(jié)點(diǎn)著色問題中的禁忌搜索算法

1、【作者簡(jiǎn)介】龍非池(1987- ) 男，通信與信息工程學(xué)院通信工程專業(yè)2005級(jí)本科生，曾獲2006電子科技大學(xué)高等數(shù)學(xué)競(jìng)賽特等獎(jiǎng)、2007電子科技大學(xué)數(shù)學(xué)建模競(jìng)賽一等獎(jiǎng)圖節(jié)點(diǎn)著色問題中的禁忌搜索算法龍非池(電子科技大學(xué)通信與信息工程學(xué)院 成都 610054)【摘要】 本文針對(duì)圖節(jié)點(diǎn)著色問題，提出了基于禁忌搜索的優(yōu)化算法設(shè)計(jì)方案，能夠跳出局部極小點(diǎn)，實(shí)現(xiàn)全局最優(yōu)化。并提出禁忌搜索算法能較好的用于一般算法較難實(shí)現(xiàn)的著色問題的推廣問題List著色。通過實(shí)驗(yàn)仿真，驗(yàn)證了算法的高效性和可靠性?！娟P(guān)鍵詞】 節(jié)點(diǎn)著色 List著色 全局優(yōu)化 禁忌搜索Algorithm of Graph Coloring

2、Based on Tabu SearchLONG Fei-chi (College of Communication and Information Engineering, Chengdu, 610054)Abstract This paper brings forward an algorithm based on taboo search to meet graph coloring problem. This algorithm can enlarge the search space and implement the global optimization. It is prove

3、d that the algorithm of taboo search can be effectively implemented in the problem of list coloring. The results of simulation show the high efficiency and reliability of the algorithm.Key words Graph coloring list coloring overall optimization tabu search1引言圖節(jié)點(diǎn)著色問題是組合最優(yōu)化中典型的非確定多項(xiàng)式(NP)完全問題，也是圖論中研究得最

4、久的一類問題3。目前解決該問題的算法很多6，如回溯算法、分支界定法、Welsh-Powell算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法以及模擬退火算法等。綜合比較各種算法，前兩種算法是精確算法，但時(shí)間復(fù)雜性太大；后三種屬于近似算法，雖然時(shí)間復(fù)雜性可接受，能夠得到較好的近似解，但算法本身過于復(fù)雜，算法效率難以保證。本文采用禁忌搜索算法，它同時(shí)擁有高效性和魯棒性4。禁忌搜索是一種全局逐步尋優(yōu)的人工智能算法，它常能有效的應(yīng)用于一些典型NP問題，如TSP5。但禁忌搜索存在一些參數(shù)較難設(shè)置，這也是應(yīng)用于通信系統(tǒng)時(shí)研究的熱點(diǎn)。本文提出針對(duì)著色問題的禁忌搜索的具體設(shè)計(jì)方案，較好的設(shè)置了參數(shù)，并優(yōu)化了數(shù)據(jù)結(jié)構(gòu)，通過實(shí)驗(yàn)比較得到

5、了較好的效果。最后提出通過領(lǐng)域簡(jiǎn)單的變化，禁忌搜索能較好的用于一般算法難以實(shí)現(xiàn)的List著色問題。2圖節(jié)點(diǎn)著色問題圖的著色問題可分為邊著色、頂點(diǎn)著色、List著色和全著色，其中最主要的一種是節(jié)點(diǎn)著色。節(jié)點(diǎn)著色問題可描述如下：給定一個(gè)無向圖G=(V,E)，其中V是節(jié)點(diǎn)集V=1,2,n，E是邊集，其中(i,j)表示有連接(i,j)的一條邊。若，且Vi內(nèi)部的任何兩個(gè)節(jié)點(diǎn)沒有E中的邊直接相連，則稱(V1,V2,Vn)為V的一個(gè)劃分。圖的節(jié)點(diǎn)著色問題可以描述為：求一個(gè)最小的k，使得(V1,V2,Vn)為V的一個(gè)劃分。以6節(jié)點(diǎn)的無向圖G=(V,E)為例，如圖1所示，其中的一種著色方案為：V1=C,E,F,

6、V2=A, V3=B,D圖1 6節(jié)點(diǎn)圖的著色通常的解決著色問題的算法采用蠻力法、貪婪法、深度優(yōu)先或廣度優(yōu)先等思想可以得到最優(yōu)解，但時(shí)間復(fù)雜性太大，如回溯法，其計(jì)算時(shí)間復(fù)雜性為指數(shù)階的；有的在多項(xiàng)式時(shí)間內(nèi)能得到可行解，但不是最優(yōu)解，如Welsh-Powell算法和貪婪算法。Welsh-Powell算法只能保證最多使用(為圖中頂點(diǎn)的最大度)種顏色給一個(gè)圖正常著色，而由Brooks定理，對(duì)于既不是完全圖又不是奇圈的簡(jiǎn)單連通圖，所需的顏色數(shù)。故通常的算法在解決圖節(jié)點(diǎn)著色問題這樣的NP完全問題時(shí)，存在很大的瓶頸，難以得到滿意的結(jié)果。而對(duì)于像遺傳算法和神經(jīng)網(wǎng)絡(luò)這樣復(fù)雜的啟發(fā)式算法，通常算法本身復(fù)雜性較大，

7、并且算法效率難以分析，最終得到的是近似解，其是否最優(yōu)解也不能保證。3禁忌搜索算法的設(shè)計(jì)禁忌搜索是對(duì)局部領(lǐng)域搜索的擴(kuò)展。傳統(tǒng)局部鄰域搜索是基于貪婪思想在當(dāng)前解的鄰域中進(jìn)行搜索，搜索性能完全依賴于鄰域結(jié)構(gòu)和初始解的選取，搜索結(jié)果容易陷入局部極小而無法保證全局最優(yōu)4。而禁忌搜索從一個(gè)初始可行解s開始，通過變換得解的鄰域函數(shù)V(s)，按照某種選擇策略從中選取一個(gè)解s*，從s移動(dòng)到s*，把s*作為一個(gè)新解，重新疊代搜索，直到滿足退出機(jī)制。為避免循環(huán)和陷入局部最優(yōu)，禁忌搜索使用禁忌表記錄已經(jīng)到達(dá)的局部最優(yōu)點(diǎn)，也即最近進(jìn)行的移動(dòng)狀態(tài)。在下一步的搜索中利用規(guī)定的禁忌規(guī)則，在一定搜索次數(shù)內(nèi)不允許選擇這些已被禁的

8、搜索點(diǎn)，從而可以跳出局部最優(yōu)的限制3。3.1解的數(shù)據(jù)結(jié)構(gòu)為了數(shù)據(jù)結(jié)構(gòu)的簡(jiǎn)化，我們?cè)O(shè)頂點(diǎn)集合為有序，1,2,n各代表一個(gè)頂點(diǎn)，如例子中的頂點(diǎn)ABCDEF分別編號(hào)為1,2,n。對(duì)于顏色集C，用C=1,2,m來表示。這樣便可用一個(gè)行向量來作為解的數(shù)據(jù)結(jié)構(gòu)，其中下標(biāo)1,2,n依次代表各個(gè)頂點(diǎn)，向量中下標(biāo)對(duì)應(yīng)的分量對(duì)應(yīng)所著色，著色相同的即在同一劃分集Vi。如例子的解可表示為：s=2 3 1 3 1 1，共3種顏色。3.2領(lǐng)域的選擇首先確定解的變化形式。一般而言，變化形式分為解的簡(jiǎn)單變化、向量分量的變化和目標(biāo)值的變化3。鑒于解的數(shù)據(jù)結(jié)構(gòu)，采用分量變化形式，即對(duì)于頂點(diǎn)i，其顏色值從si變?yōu)閖，其中j屬于顏色

9、集C。對(duì)于領(lǐng)域，每一個(gè)解s的領(lǐng)居由那些滿足上面的變化且只有一個(gè)分量變化的解組成，每一個(gè)分量可以選擇m個(gè)顏色中的一個(gè)，那么對(duì)每一個(gè)解，共有n×(m-1)個(gè)鄰居。例如，對(duì)于例子中的解s=2 3 1 3 1 1，它的一些領(lǐng)居為s1=1 3 1 3 1 1,s2=3 3 1 3 1 1,s3=2 1 1 3 1 1,s4=2 2 1 3 1 1等。解的領(lǐng)域即為所有這些鄰居組成的集合。3.3目標(biāo)函數(shù)的選擇和候選集的構(gòu)造對(duì)于圖節(jié)點(diǎn)著色問題，目標(biāo)函數(shù)的構(gòu)造是一個(gè)難點(diǎn)。由圖論的知識(shí)，對(duì)一個(gè)正常點(diǎn)著色，各個(gè)頂點(diǎn)與其相鄰的頂點(diǎn)所著顏色不同，即各個(gè)頂點(diǎn)同與之有邊相連的頂點(diǎn)不在同一個(gè)劃分集Vi中，則：E(V

10、1)+ E(V2)+ E(Vn)=0，其中E(Vi)表示頂點(diǎn)集Vi中包含的邊數(shù)。那么選取目標(biāo)函數(shù)為：f(s)=E(V1)+ E(V2)+E(Vn)，對(duì)于那些非正常點(diǎn)著色的不可行解，f(s)>0。在進(jìn)行禁忌搜索時(shí)，每次從領(lǐng)域中以目標(biāo)函數(shù)值最小為依據(jù)來選取解。在禁忌搜索完畢時(shí)，給出目標(biāo)函數(shù)值最小的解，若為0則得到一個(gè)正常點(diǎn)著色方案，若不為0，我們亦可以得到一個(gè)較好的方案，這也是用禁忌搜索來解決著色問題的優(yōu)點(diǎn)之一。實(shí)際編程中還要設(shè)置候選集，以便從中選取下一個(gè)最優(yōu)解。鑒于解的形式和目標(biāo)函數(shù)，可用 (n×(m-1)×(n+1)的矩陣來表示，其每行表示解的一個(gè)鄰居和其對(duì)應(yīng)的目標(biāo)函

11、數(shù)值。3.4禁忌表和特赦規(guī)則的構(gòu)造禁忌表的構(gòu)造和特赦規(guī)則的選取通常是禁忌搜索算法的難點(diǎn)，這也是禁忌搜索算法運(yùn)用于通信系統(tǒng)中時(shí)的一個(gè)瓶頸。首先，禁忌對(duì)象的選擇通常也有三種形式：解的簡(jiǎn)單變化、分量對(duì)換的變化和目標(biāo)值的變化。由于簡(jiǎn)單變化的禁忌對(duì)象太少，計(jì)算時(shí)間過多，而目標(biāo)值變化的對(duì)象過多，難以得到全局最優(yōu)，故選擇分量對(duì)換。那么禁忌表設(shè)為L(zhǎng)×3的矩陣，其第一列儲(chǔ)存分量所在下標(biāo)i，對(duì)應(yīng)圖中的某點(diǎn)，第二列儲(chǔ)存此點(diǎn)的顏色，即si，第三列儲(chǔ)存用來交換的顏色j。對(duì)于禁忌表長(zhǎng)度，鑒于此參數(shù)較難設(shè)置，我們用經(jīng)驗(yàn)式L=sqrt(n×(m-1)，在實(shí)際運(yùn)用時(shí)可以通過實(shí)驗(yàn)來比較選取該值。對(duì)于特赦規(guī)則，

12、其設(shè)置的好壞直接影響進(jìn)行全局最優(yōu)化時(shí)的效果?？紤]當(dāng)前解s對(duì)應(yīng)的候選集中的最優(yōu)解s*，若它被禁而同時(shí)它對(duì)應(yīng)的目標(biāo)函數(shù)值滿足f(s)<f(s*)，那么我們有理由將它特赦，因?yàn)橹庇^上理解，我們會(huì)得到更好的解。3.5算法終止原則設(shè)置兩目標(biāo)值無改進(jìn)的最大允許迭代次數(shù)k_max和目標(biāo)值下界fl來保證算法的有窮性。3.6算法實(shí)現(xiàn)的框架3.6.1主函數(shù)的設(shè)計(jì) 設(shè)計(jì)好算法后，現(xiàn)在不難給出算法的設(shè)計(jì)框架。在具體編程時(shí)，把一些功能放到外部函數(shù)中實(shí)現(xiàn)，只在主函數(shù)中留出接口。下面是主函數(shù)的框架,使用的是MATLAB的偽代碼。初始化：a，m，n為a的維數(shù)；%圖的鄰接矩陣、顏色數(shù)、頂點(diǎn)個(gè)數(shù) k，best_k，k_ma

13、x，fl；%迭代步數(shù)、最優(yōu)解所在步、最大允許迭代數(shù)、下界L=n×m0.5取整，h=zeros(L,3)；%禁忌表的設(shè)置 s=ones(1,n)，s_best=s，s_now=s，best；%形式、最優(yōu)解、當(dāng)前解、最終解 V=zeros(1,n+1)，A=f(s_now)-1；%候選集、特赦值、f為目標(biāo)函數(shù)開始： 當(dāng)f(s_now)>fl且(k-best_k<k_max)時(shí)，計(jì)算 k=k+1；%迭代步數(shù)增加 生成s_now的候選集V，其中的元素s是非禁忌或者特赦f(s)<A 在V中選擇使目標(biāo)函數(shù)值最小的解s_best 若f(s_best)<A，則A=f(s_be

14、st)-1，否則，A=f(s_now)-1；%更新特赦值 若h未滿，將對(duì)應(yīng)的交換加入下一行，否則，覆蓋第一行；%更新禁忌表 若f(s_best)<best，則best=s_best，best_k=k；%更新全局變量 s_now=s_best；繼續(xù)。結(jié)束3.6.2候選集生成函數(shù)的設(shè)計(jì)初始化：r=1；%候選集矩陣的行下標(biāo)循環(huán)： i=1:n，j=1:s_now(i) s_now(i+1):m temp=s_now，temp(i)=j；%臨時(shí)變量，儲(chǔ)存當(dāng)前解 change=i,s_now(i),j；%對(duì)換的變化方式 若禁忌表中沒有一行和change相同或者是特赦f(temp)<=A V(r

15、,1:n)=temp，V(r,n+1)=f(temp)；%前n行儲(chǔ)存解 最后一行儲(chǔ)存目標(biāo)值 r=r+1；end %增加迭代次數(shù)，繼續(xù)4圖節(jié)點(diǎn)著色問題的特例-List著色對(duì)一般著色，每個(gè)頂點(diǎn)都可從顏色集C中選取任一個(gè)顏色，而當(dāng)限制了每個(gè)頂點(diǎn)專屬的顏色集時(shí)，稱為L(zhǎng)ist著色1。圖2 圖的List著色如圖2所示，兩組化學(xué)物品，X=x1,x2,x3，Y=y1,y2，不同組的物品不能放在一起?，F(xiàn)將兩組物品放于1、2、3三個(gè)倉庫，且限制x1和y1只能放在1、2號(hào)倉庫、x2和y2只能放在2、3號(hào)倉庫，x3只能放在1、3號(hào)倉庫，則怎樣安排物品的存放？圖論中的定理指出，對(duì)任意存在List著色的圖，其所需顏色數(shù)在

16、區(qū)間 +1內(nèi)。對(duì)于List著色，針對(duì)此問題的算法在各個(gè)文獻(xiàn)中不多見。通過上面討論的禁忌搜索算法的設(shè)計(jì)，我們可以看出，只改變領(lǐng)域的構(gòu)造規(guī)則，便可以簡(jiǎn)單的實(shí)現(xiàn)List著色。具體實(shí)現(xiàn)是對(duì)每個(gè)頂點(diǎn)只選取那些變換，其變換后的顏色仍然存在于自己的顏色集中，而其他所有步驟同一般著色問題。對(duì)于上訴問題的解s=1 3 1 2 2(其解的下標(biāo)依次對(duì)應(yīng)于點(diǎn)x1、x2、x3、y1、y2所著顏色)，其領(lǐng)居選擇為s1=2 3 1 2 2,s2=1 2 1 2 2,s3=1 3 3 2 2,s4=1 3 1 1 2和s5=1 3 1 2 3。由此可見，對(duì)禁忌搜索算法擴(kuò)展，只變換領(lǐng)域的選擇就能夠較好的實(shí)現(xiàn)List著色，當(dāng)不存

17、在正常的List著色時(shí)，算法給出使目標(biāo)函數(shù)值最小的著色方案，這是一般的算法難以媲美的。5 算法的仿真實(shí)驗(yàn)由于禁忌搜索算法屬于啟發(fā)式算法，其性能分析一般較為復(fù)雜，我們采取大規(guī)模計(jì)算分析方法。用MATLAB隨機(jī)產(chǎn)生實(shí)例的語句為：a=rand(n)/2(先產(chǎn)生0 0.5范圍內(nèi)的n×n矩陣)；a=round(a+a)，則a最后表示隨機(jī)生成的一個(gè)無向圖的鄰接矩陣，圖中的邊集為均勻分布。我們?cè)O(shè)置n=50或n=100，即隨機(jī)產(chǎn)生有50或100個(gè)節(jié)點(diǎn)的無向圖。則用MATLAB語言，在1.8GHZCPU的配置下通過一系列仿真實(shí)驗(yàn)得到表1所示數(shù)據(jù)：表1 仿真實(shí)驗(yàn)數(shù)據(jù)頂點(diǎn)個(gè)數(shù)n50505050501001

18、00100100100所需色數(shù)12111213122019192021迭代步數(shù)43444444439391929493運(yùn)行時(shí)間(s)9.0310.189.459.229.71134135135142136由此可知，對(duì)于n=50、100，平均所需色數(shù)為12、20，且實(shí)驗(yàn)所得解的目標(biāo)函數(shù)值都為0，說明所得解為可行解。對(duì)于概率分析的結(jié)果，我們所得解同最優(yōu)解的偏差在2%以內(nèi)。再用其他算法采取同樣的隨機(jī)實(shí)驗(yàn)。用回溯法時(shí)，對(duì)于n=50或100實(shí)驗(yàn)在一個(gè)小時(shí)內(nèi)都不能得出結(jié)果。而采用Welsh-Powell算法時(shí)，當(dāng)n=1000時(shí)，平均色數(shù)為122，所需時(shí)間在10內(nèi)，但對(duì)于概率分析的結(jié)果，平均所需色數(shù)為85。6 結(jié)束語實(shí)驗(yàn)可看出，回溯法時(shí)間復(fù)雜性太差，Welsh-Powell算法雖然時(shí)間復(fù)雜性較好，但得出的結(jié)果并非最優(yōu)，當(dāng)n較大時(shí)尤為明顯。而我們?cè)O(shè)計(jì)的禁忌搜索算法解決節(jié)點(diǎn)著色問題具有較好的結(jié)果最優(yōu)和較小時(shí)間復(fù)雜性。參 考 文 獻(xiàn)1 張先迪,李正良.圖論及其應(yīng)用.北京,高等教育出版社,20052 王紅梅.算法設(shè)計(jì)與分析.北京,清華大學(xué)出版社,20063 邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法(第二版).北京,清華大學(xué)出版社,20054 張曉琴,黃玉清.基于禁忌搜索啟發(fā)式求解背包問題算法.成都,電子科大學(xué)報(bào),Vo1.34,No.3,Jun.20055 劉于江,喻澤峰.一