圖著色問題的逆序蟻群算法研究

張 麗， 丁曉東

（1.上海理工大學管理學院，上海 200093；2.上海工程技術大學航空運輸學院，上海 201620）

圖著色問題的逆序蟻群算法研究

張 麗1，2， 丁曉東1，2

（1.上海理工大學管理學院，上海 200093；2.上海工程技術大學航空運輸學院，上海 201620）

針對經典的圖著色問題，依據傳統圖著色算法中逆序圖著色的著色思想，結合蟻群算法的搜索機制，給出了逆序蟻群著色算法.根據著色進度和未著色點的相鄰點度數隨機動態逆序選擇新的著色點，使得算法具有較強的搜索全局最優解的能力.利用計算機生產大量隨機圖作為測試實例，對比逆序著色算法和逆序蟻群算法，實驗結果說明逆序蟻群著色算法提高了求解質量，加快了收斂速度，證明了其優良特性.同時算法效率的提高，也保證了該算法可適用于較大規模的著色問題求解.此外，還進行了一系列對比試驗，得出了關鍵參數的合理取值范圍.

圖著色問題；逆序著色算法；逆序蟻群著色算法

圖著色問題（graph coloring problem，GCP）是現代圖論中重要課題之一，在存儲分配、電路布線、機場停機位分配等問題中也有廣泛的應用.圖著色的內容包括點著色、邊著色、組合地圖的面著色等，邊著色和面著色都可轉化為點著色問題.

圖著色問題是組合優化中一個很活躍的課題，國內外研究人員進行過許多研究，并取得了一系列成果.在理論方面，對“四色猜想”和“五色定理”的證明相繼引出許多重要結果，另外還有有關色多項式和一些根據子圖特征分析著色數上界的結論［1-2］.

后來，從實用角度出發，更多的研究集中在算法設計而不再是理論證明上.早期的算法研究主要是如基于布爾代數運算的著色算法和基于深度優先檢索的回溯算法等經典方法，但由于圖著色問題屬于NP難題，經典圖著色算法隨著圖的規模增大，計算量將以指數速度增加到不可接受的地步.之后一些近似算法相繼推出，如逆序標號算法和貪心算法等啟發式算法［3-4］.

自從蟻群算法在著名的旅行商問題和工件排序問題上取得成效以來，已陸續滲透到其它組合優化問題領域中，并在許多方面表現出相當好的性能.目前，蟻群算法在著色問題方面的應用較少.

1 問題描述

已知G=（V，E），其中，｜V｜=n；｜E｜=m；且G為無自環的無向圖.

對圖G點著色，是指將它的每個頂點涂上一種顏色，使得任何相鄰的頂點都涂上不同的顏色.若用k種顏色能夠對G的頂點進行一種著色，就稱G是k-點可著色的.若G是k-點可著色的，但不是（k-1）-點可著色的，就簡稱G是k-色圖，稱k 為G的色數［5］.

問題的數學模型可寫成

2 逆序蟻群算法

2.1 逆序著色算法

逆序著色算法是對經典圖著色算法——Welch Powell著色法的改進，Welch Powell著色法的原理是將圖G中的結點按度數遞減的次序進行排列，用第一種顏色，對第一點著色，并按排列次序對與前面結點不相鄰的每一點著同樣的顏色.然后用第二種顏色對尚未著色的點重復前一步，直到所有的點都著上顏色為止.

逆序著色算法的步驟為：

步驟1 取頂點v1，deg（v1）=max｛deg（vi）｜vi∈V｝，即選擇度數最大的頂點，令c（v1）=1，M1=｛v1｝，V1=V＼｛v1｝.

步驟2 取v2∈V1，并且與M1中的頂點鄰接的度數為最大，令c（v2）=2，M2=｛v1，v2｝，V2=V1＼｛v2｝.

步驟3 取v3∈V2，并且與M2中的頂點鄰接的度數為最大，令

步驟4 一般地，設Mk=｛v1，v2，…，vk，｜vj∈V，j=1，2，…，k｝，Vk=Vk-1＼｛vk｝；若Vk+1=φ，則轉步驟5；否則，若vk-1∈Vk，并且與Mk中的頂點鄰接的度數為最大且唯一，令c（vk）=j （j為可以使用的最小數顏色）.

步驟5 C（G）=max（c（vi），vi∈E）

2.2 逆序蟻群著色算法

圖著色問題不像TSP問題有現成的測試庫，一般而言，圖著色問題的算法測試常用隨機生成圖來檢驗相關算法的正確性和效率.一個隨機圖Gn，pE表示有n個頂點，點與點之間以概率pE存在關聯邊，并且這些邊是否存在是相互獨立的.這類隨機圖已經用各種算法做過大量測試，尤其是當pE=0.5時的情況更有很多測試結果，得到了有意義的結論.

基本蟻群算法主要用于尋路問題［6-10］，下面借鑒其思路對逆序著色法進行改進，螞蟻在尋路過程中增加了著色任務，著色點的選擇和顏色的選擇是算法設計關鍵.改進后的算法可用于規模較大的問題，特別是大型的隨機圖Gn，pE著色，可以繼承傳統圖著色算法的搜索機制，并同時獲得蟻群算法能夠跳出局部解的優良特性.

其算法流程為：

步驟1 參數初始化.

螞蟻總數A賦值，軌跡信息素矩陣T為全1矩陣，當前最優著色數C*（G）初值為n，著色數C（G）←1，1號色著色點集C1（G）=φ，1號色不可著色點集（G）=φ；k←1，未著色點集Vc=φ.

步驟2 第a個螞蟻開始著色.

選擇第一個著色點vi，deg（v1）=max｛deg（vi）｜vi∈V｝（第一著色點亦可使用其它選擇方案，例如隨機選擇）.

步驟3 為vi著色.

步驟4 著色進度判斷.

式中，ηij為vj點飽和度，表示vj與Vc中的點相鄰度數，與未著色點相鄰越多的點被選擇的幾率越大；τij=T（i，j）；α表示信息素軌跡的相對重要性；β表示路徑能見度的相對重要性；而ρ為信息素蒸發系數.選擇最大轉移概率對應的vj，轉步驟3.

步驟6 記錄螞蟻a的著色結果.

3 計算實驗與分析

3.1 算法效率比較

下面就用隨機圖Gn，pE來檢驗逆序蟻群著色算法的求解效率.

在測試中，取ρ=0.5，α=β=2，表1中列出了其它實驗參數.

從表2顯示的結果可以看出逆序蟻群算法在算法結果上整體優于逆序著色算法，點數和關聯邊增加的時候尤其明顯.

表1 逆序蟻群著色算法的其它實驗參數Tab.1 Experimental parameters of ant coloring algorithm

表2 兩種算法的求解結果比較Tab.2 Results comparision between the two coloring algorithms

3.2 算法參數的選擇

3．2．1 參數α與β

為探索參數信息素軌跡的相對重要性α和路徑能見度的相對重要性β的設置規律，選擇較優的參數組合，下面使用隨機圖G100，0.5作為算例測試.α 和β分別取1，2，3，4進行組合，蒸發系數取值仍然取0.5.除α和β同時取值為1的情況，由于硬件環境的局限，其它α和β的組合對每種算法都進行了4次實驗，實驗的平均結果見表3.

表3 不同重要度參數組合下的算法試測結果Tab.3 Different combinations of parameters_____

由上述測試結果可以看出，當α=1，β=2時，這種組合的平均求解質量較高.

3．2．2 蒸發系數ρ

仍以隨機圖G100，0.5為例，螞蟻總數取50，依據上面一組實驗結論α和β都取為1，在信息素蒸發系數變動時，可得到不同螞蟻著色算法的著色結果，如圖1所示.

圖1 不同蒸發系數對算法的影響Fig.1 Effect of different evaporation coefficients

根據以上實驗結果可以推斷出ρ在（0.5，0.7）之間時，逆序蟻群著色算法求解效果較好.

3．2．3 蟻群規模

在前面的實驗過程中還可以觀察到，當蟻群規模達到50時，即使關聯邊的產生概率不同，逆序蟻群算法也都基本達到了可能實現的最好結果.蟻群規模繼續增加時，收斂速度已經變得緩慢，因而可以選擇50只螞蟻來執行著色任務.

4 結束語

圖著色問題是經典的分配型組合優化問題，且屬于NP難題.傳統的圖著色算法時間復雜度較高，而隨機螞蟻著色算法搜索機制又比較盲目.本文將傳統算法的選擇策略融合在其中，設計的逆序蟻群著色算法在實驗中驗證了其優良的特性，即降低了逆序著色算法的時間復雜度，又提高了求解結果的質量.

算法的時間復雜度為O（A*n2）.經驗結果是，當n＞50時，A取50即可.值得注意的是，由于圖著色問題的本身的復雜性，算法的時間和空間復雜度仍高于基本的尋路蟻群算法.

在機場停機位分配、工件排序等著色問題的實際應用領域，逆序蟻群著色算法需要有針對性的改進才可以應用［11-12］.

［1］ Edwards K.The complexity of coloring problems on dense graphs［J］.Theoretical Computer Science，1986，43（2／3）：337-343.

［2］ Held S，Cook W，Sewell E C.Maximum-weight stable sets and safe lower bounds for graph coloring［J］. Mathematical Programming Computation，2012，4（4）：361-381.

［3］ 盧開澄，盧華明.圖論及其應用［M］.北京：清華大學出版社，1995.

［4］ 肖位樞.圖論及其算法［M］.北京：航空工業出版社，1993.

［5］ Porumbel D C.Heuristic algorithms and learning techniques：applications to the graph coloring problem ［J］.4OR，2012，10（4）：393-394.

［6］ Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of cooperating agents［J］. IEEE Transactions on Systems，Man and Cybernetics，1996，26（1）：29-41.

［7］ 李煜，馬良.用量子蟻群算法求解大規模旅行商問題［J］.上海理工大學學報，2012，34（4）：355-358.

［8］ Walter J.A graph-based ant system and its convergence［J］.Future Generation Computer Systems，2000，16（8）：873-888.

［9］ Bui T N，Nguyen T V H，Patel C M，et al.An ant-based algorithm for coloring graphs［J］.Discrete Applied Mathematics，2008，156（2）：190-200.

［10］ 廖飛雄，馬良.圖著色問題的啟發式搜索螞蟻算法［J］.計算機工程，2007，33（16）：191-192.

［11］ 王欣盛，馬良.工件排序的改進蟻群算法優化［J］.上海理工大學學報，2011，33（4）：362-366.

［12］ 任上，秦江濤.基于著色Petri網實現A星算法的生產調度優化研究［J］.上海理工大學學報，2013，35（5）：463-474.

（編輯：董 偉）

Reverse Order Ant Colony Algorithm for Graph Coloring Problem

ZHANGLi1，2， DINGXiao-dong1，2
（1.School of Management，University of Shanghai for Science and Technology，Shanghai 200093，China；2.Air Transport Department，Shanghai University of Engineering Science，Shanghai 201620，China）

Based on the traditional reverse ordering graph coloring algorithm and combining with searching mechanism of ant algorithm，a reverse order ant coloy coloring algorithm was proposed to resolve graph coloring problems.In the algorithm according to the color progress and the adjacent points degree，the dynamic reverse transferring color sequence can give the algorithm strong ability to search the global optimal solution.A large number of random graph coloring experiments show the advantages of the new algorithm.The algorithm can improve the quality of solution and make the convergence faster.An improvement of the efficiency of the algorithm also ensures that it can be applied to solve large-scale coloring problems.In addition，through series of computer test，reasonable value ranges of key parameters were validated.

graph coloring problem；reverse order coloring algorithm；reverse order ant colony coloring algorithm

TP 18文獻標示碼：A

1007-6735（2014）05-0483-04

10.13255／j.cnki.jusst.2014.05.014

2013-09-11

上海市一流學科建設資助項目（S1201YLXK）；上海市教委科研創新資助項目（12YS129）

張 麗（1980-），女，博士研究生.研究方向：智能優化.E-mail：zhanglisues＠163.com

丁曉東（1963-），男，教授.研究方向：不確定系統分析與優化.E-mail：xdding＠usst.edu.com