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

1、【作者簡介】龍非池(1987- ) 男，通信與信息工程學院通信工程專業(yè)2005級本科生，曾獲2006電子科技大學高等數(shù)學競賽特等獎、2007電子科技大學數(shù)學建模競賽一等獎圖節(jié)點著色問題中的禁忌搜索算法龍非池(電子科技大學通信與信息工程學院 成都 610054)【摘要】 本文針對圖節(jié)點著色問題，提出了基于禁忌搜索的優(yōu)化算法設(shè)計方案，能夠跳出局部極小點，實現(xiàn)全局最優(yōu)化。并提出禁忌搜索算法能較好的用于一般算法較難實現(xiàn)的著色問題的推廣問題List著色。通過實驗仿真，驗證了算法的高效性和可靠性。【關(guān)鍵詞】 節(jié)點著色 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é)點著色問題是組合最優(yōu)化中典型的非確定多項式(NP)完全問題，也是圖論中研究得最

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

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

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

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

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

9、集C。對于領(lǐng)域，每一個解s的領(lǐng)居由那些滿足上面的變化且只有一個分量變化的解組成，每一個分量可以選擇m個顏色中的一個，那么對每一個解，共有n×(m-1)個鄰居。例如，對于例子中的解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目標函數(shù)的選擇和候選集的構(gòu)造對于圖節(jié)點著色問題，目標函數(shù)的構(gòu)造是一個難點。由圖論的知識，對一個正常點著色，各個頂點與其相鄰的頂點所著顏色不同，即各個頂點同與之有邊相連的頂點不在同一個劃分集Vi中，則：E(V

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

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

12、其設(shè)置的好壞直接影響進行全局最優(yōu)化時的效果?？紤]當前解s對應(yīng)的候選集中的最優(yōu)解s*，若它被禁而同時它對應(yīng)的目標函數(shù)值滿足f(s)<f(s*)，那么我們有理由將它特赦，因為直觀上理解，我們會得到更好的解。3.5算法終止原則設(shè)置兩目標值無改進的最大允許迭代次數(shù)k_max和目標值下界fl來保證算法的有窮性。3.6算法實現(xiàn)的框架3.6.1主函數(shù)的設(shè)計 設(shè)計好算法后，現(xiàn)在不難給出算法的設(shè)計框架。在具體編程時，把一些功能放到外部函數(shù)中實現(xiàn)，只在主函數(shù)中留出接口。下面是主函數(shù)的框架,使用的是MATLAB的偽代碼。初始化：a，m，n為a的維數(shù)；%圖的鄰接矩陣、顏色數(shù)、頂點個數(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)解、當前解、最終解 V=zeros(1,n+1)，A=f(s_now)-1；%候選集、特赦值、f為目標函數(shù)開始： 當f(s_now)>fl且(k-best_k<k_max)時，計算 k=k+1；%迭代步數(shù)增加 生成s_now的候選集V，其中的元素s是非禁忌或者特赦f(s)<A 在V中選擇使目標函數(shù)值最小的解s_best 若f(s_best)<A，則A=f(s_be

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

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

16、區(qū)間 +1內(nèi)。對于List著色，針對此問題的算法在各個文獻中不多見。通過上面討論的禁忌搜索算法的設(shè)計，我們可以看出，只改變領(lǐng)域的構(gòu)造規(guī)則，便可以簡單的實現(xiàn)List著色。具體實現(xiàn)是對每個頂點只選取那些變換，其變換后的顏色仍然存在于自己的顏色集中，而其他所有步驟同一般著色問題。對于上訴問題的解s=1 3 1 2 2(其解的下標依次對應(yīng)于點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。由此可見，對禁忌搜索算法擴展，只變換領(lǐng)域的選擇就能夠較好的實現(xiàn)List著色，當不存

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

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