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

張 麗， 丁曉東

（1.上海理工大學(xué)管理學(xué)院，上海 200093；2.上海工程技術(shù)大學(xué)航空運(yùn)輸學(xué)院，上海 201620）

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

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

（1.上海理工大學(xué)管理學(xué)院，上海 200093；2.上海工程技術(shù)大學(xué)航空運(yùn)輸學(xué)院，上海 201620）

針對(duì)經(jīng)典的圖著色問題，依據(jù)傳統(tǒng)圖著色算法中逆序圖著色的著色思想，結(jié)合蟻群算法的搜索機(jī)制，給出了逆序蟻群著色算法.根據(jù)著色進(jìn)度和未著色點(diǎn)的相鄰點(diǎn)度數(shù)隨機(jī)動(dòng)態(tài)逆序選擇新的著色點(diǎn)，使得算法具有較強(qiáng)的搜索全局最優(yōu)解的能力.利用計(jì)算機(jī)生產(chǎn)大量隨機(jī)圖作為測(cè)試實(shí)例，對(duì)比逆序著色算法和逆序蟻群算法，實(shí)驗(yàn)結(jié)果說明逆序蟻群著色算法提高了求解質(zhì)量，加快了收斂速度，證明了其優(yōu)良特性.同時(shí)算法效率的提高，也保證了該算法可適用于較大規(guī)模的著色問題求解.此外，還進(jìn)行了一系列對(duì)比試驗(yàn)，得出了關(guān)鍵參數(shù)的合理取值范圍.

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

圖著色問題（graph coloring problem，GCP）是現(xiàn)代圖論中重要課題之一，在存儲(chǔ)分配、電路布線、機(jī)場(chǎng)停機(jī)位分配等問題中也有廣泛的應(yīng)用.圖著色的內(nèi)容包括點(diǎn)著色、邊著色、組合地圖的面著色等，邊著色和面著色都可轉(zhuǎn)化為點(diǎn)著色問題.

圖著色問題是組合優(yōu)化中一個(gè)很活躍的課題，國(guó)內(nèi)外研究人員進(jìn)行過許多研究，并取得了一系列成果.在理論方面，對(duì)“四色猜想”和“五色定理”的證明相繼引出許多重要結(jié)果，另外還有有關(guān)色多項(xiàng)式和一些根據(jù)子圖特征分析著色數(shù)上界的結(jié)論［1-2］.

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

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

1 問題描述

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

對(duì)圖G點(diǎn)著色，是指將它的每個(gè)頂點(diǎn)涂上一種顏色，使得任何相鄰的頂點(diǎn)都涂上不同的顏色.若用k種顏色能夠?qū)的頂點(diǎn)進(jìn)行一種著色，就稱G是k-點(diǎn)可著色的.若G是k-點(diǎn)可著色的，但不是（k-1）-點(diǎn)可著色的，就簡(jiǎn)稱G是k-色圖，稱k 為G的色數(shù)［5］.

問題的數(shù)學(xué)模型可寫成

2 逆序蟻群算法

2.1 逆序著色算法

逆序著色算法是對(duì)經(jīng)典圖著色算法——Welch Powell著色法的改進(jìn)，Welch Powell著色法的原理是將圖G中的結(jié)點(diǎn)按度數(shù)遞減的次序進(jìn)行排列，用第一種顏色，對(duì)第一點(diǎn)著色，并按排列次序?qū)εc前面結(jié)點(diǎn)不相鄰的每一點(diǎn)著同樣的顏色.然后用第二種顏色對(duì)尚未著色的點(diǎn)重復(fù)前一步，直到所有的點(diǎn)都著上顏色為止.

逆序著色算法的步驟為：

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

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

步驟3 取v3∈V2，并且與M2中的頂點(diǎn)鄰接的度數(shù)為最大，令

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

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

2.2 逆序蟻群著色算法

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

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

其算法流程為：

步驟1 參數(shù)初始化.

螞蟻總數(shù)A賦值，軌跡信息素矩陣T為全1矩陣，當(dāng)前最優(yōu)著色數(shù)C*（G）初值為n，著色數(shù)C（G）←1，1號(hào)色著色點(diǎn)集C1（G）=φ，1號(hào)色不可著色點(diǎn)集（G）=φ；k←1，未著色點(diǎn)集Vc=φ.

步驟2 第a個(gè)螞蟻開始著色.

選擇第一個(gè)著色點(diǎn)vi，deg（v1）=max｛deg（vi）｜vi∈V｝（第一著色點(diǎn)亦可使用其它選擇方案，例如隨機(jī)選擇）.

步驟3 為vi著色.

步驟4 著色進(jìn)度判斷.

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

步驟6 記錄螞蟻a的著色結(jié)果.

3 計(jì)算實(shí)驗(yàn)與分析

3.1 算法效率比較

下面就用隨機(jī)圖Gn，pE來檢驗(yàn)?zāi)嫘蛳伻褐惴ǖ那蠼庑?

在測(cè)試中，取ρ=0.5，α=β=2，表1中列出了其它實(shí)驗(yàn)參數(shù).

從表2顯示的結(jié)果可以看出逆序蟻群算法在算法結(jié)果上整體優(yōu)于逆序著色算法，點(diǎn)數(shù)和關(guān)聯(lián)邊增加的時(shí)候尤其明顯.

表1 逆序蟻群著色算法的其它實(shí)驗(yàn)參數(shù)Tab.1 Experimental parameters of ant coloring algorithm

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

3.2 算法參數(shù)的選擇

3．2．1 參數(shù)α與β

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

表3 不同重要度參數(shù)組合下的算法試測(cè)結(jié)果Tab.3 Different combinations of parameters_____

由上述測(cè)試結(jié)果可以看出，當(dāng)α=1，β=2時(shí)，這種組合的平均求解質(zhì)量較高.

3．2．2 蒸發(fā)系數(shù)ρ

仍以隨機(jī)圖G100，0.5為例，螞蟻總數(shù)取50，依據(jù)上面一組實(shí)驗(yàn)結(jié)論α和β都取為1，在信息素蒸發(fā)系數(shù)變動(dòng)時(shí)，可得到不同螞蟻著色算法的著色結(jié)果，如圖1所示.

圖1 不同蒸發(fā)系數(shù)對(duì)算法的影響Fig.1 Effect of different evaporation coefficients

根據(jù)以上實(shí)驗(yàn)結(jié)果可以推斷出ρ在（0.5，0.7）之間時(shí)，逆序蟻群著色算法求解效果較好.

3．2．3 蟻群規(guī)模

在前面的實(shí)驗(yàn)過程中還可以觀察到，當(dāng)蟻群規(guī)模達(dá)到50時(shí)，即使關(guān)聯(lián)邊的產(chǎn)生概率不同，逆序蟻群算法也都基本達(dá)到了可能實(shí)現(xiàn)的最好結(jié)果.蟻群規(guī)模繼續(xù)增加時(shí)，收斂速度已經(jīng)變得緩慢，因而可以選擇50只螞蟻來執(zhí)行著色任務(wù).

4 結(jié)束語

圖著色問題是經(jīng)典的分配型組合優(yōu)化問題，且屬于NP難題.傳統(tǒng)的圖著色算法時(shí)間復(fù)雜度較高，而隨機(jī)螞蟻著色算法搜索機(jī)制又比較盲目.本文將傳統(tǒng)算法的選擇策略融合在其中，設(shè)計(jì)的逆序蟻群著色算法在實(shí)驗(yàn)中驗(yàn)證了其優(yōu)良的特性，即降低了逆序著色算法的時(shí)間復(fù)雜度，又提高了求解結(jié)果的質(zhì)量.

算法的時(shí)間復(fù)雜度為O（A*n2）.經(jīng)驗(yàn)結(jié)果是，當(dāng)n＞50時(shí)，A取50即可.值得注意的是，由于圖著色問題的本身的復(fù)雜性，算法的時(shí)間和空間復(fù)雜度仍高于基本的尋路蟻群算法.

在機(jī)場(chǎng)停機(jī)位分配、工件排序等著色問題的實(shí)際應(yīng)用領(lǐng)域，逆序蟻群著色算法需要有針對(duì)性的改進(jìn)才可以應(yīng)用［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］ 盧開澄，盧華明.圖論及其應(yīng)用［M］.北京：清華大學(xué)出版社，1995.

［4］ 肖位樞.圖論及其算法［M］.北京：航空工業(yè)出版社，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］ 李煜，馬良.用量子蟻群算法求解大規(guī)模旅行商問題［J］.上海理工大學(xué)學(xué)報(bào)，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］ 廖飛雄，馬良.圖著色問題的啟發(fā)式搜索螞蟻算法［J］.計(jì)算機(jī)工程，2007，33（16）：191-192.

［11］ 王欣盛，馬良.工件排序的改進(jìn)蟻群算法優(yōu)化［J］.上海理工大學(xué)學(xué)報(bào)，2011，33（4）：362-366.

［12］ 任上，秦江濤.基于著色Petri網(wǎng)實(shí)現(xiàn)A星算法的生產(chǎn)調(diào)度優(yōu)化研究［J］.上海理工大學(xué)學(xué)報(bào)，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文獻(xiàn)標(biāo)示碼：A

1007-6735（2014）05-0483-04

10.13255／j.cnki.jusst.2014.05.014

2013-09-11

上海市一流學(xué)科建設(shè)資助項(xiàng)目（S1201YLXK）；上海市教委科研創(chuàng)新資助項(xiàng)目（12YS129）

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

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