關(guān)于最大團(tuán)問題的一種新算法

摘要：最大團(tuán)問題是圖論中重要的NP完全問題，目前求解最大團(tuán)問題的方法只適合某些特殊的圖，活則消耗時間長，求解效率低。該文提出了一種新的算法，蟻群算法來解決最大團(tuán)問題。蟻群優(yōu)化算法是一種基于自然啟發(fā)的算法，是一種解決組合優(yōu)化問題的有效方法。實驗結(jié)果顯示，算法的有效性。

關(guān)鍵詞：最大團(tuán)；組合優(yōu)化；蟻群算法

中圖分類號：TP18文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)22-708-03

A New Algorithm for the Maximum Clique Problem

ZHOU Xiao-xiao， BAI Yang

(City College，Wenzhou University， Wenzhou 325035， China)

Abstract:The maximum clique problem is an important NP complete problem in graph theory.Prebious algorithms are either applicable only to some particular graphs or in need of exponential time cost. In this paper， an new algorithm-Ant Conlony Optimization(ACO) is presented，which is applied for MCP .ACO algorithm is a nature-inspired algorithm.It is an efficient tool for solving combinatorial optimization problem. Experimental results prove the effectiveness of the improvements.

Key words: Maximum clique; combinatorial optimization; Ant Conlony Optimization

1 引言

最大團(tuán)問題(Maximum Clique Problem，MCP)是經(jīng)典的組合優(yōu)化問題之一，這不僅僅因為它最早被證明是 NP-完全問題之一，而且因為它在理論和實踐上有著重要的意義?？梢詫⒑芏嗖煌念I(lǐng)域的問題轉(zhuǎn)化為最大團(tuán)問題來解決。它在編碼理論、差錯診斷、計算機圖像、模式匹配、信號傳輸、人工智能、聚類分析、移動計算、故障診斷、信息恢復(fù)、生物信息學(xué)等許多領(lǐng)域都有著廣泛的應(yīng)用。最大團(tuán)問題在國外有著廣泛的研究，在國內(nèi)還剛剛起步。對最大團(tuán)問題的研究實際就是一個NP問題的研究，目前解決最大團(tuán)問題的方法主要集中在多項式時間的近似算法上。有很多解決最大團(tuán)問題的metaheuristic近似算法，比如模擬退火、禁忌搜索、人工智能等。此文主要介紹一種遺傳算法――蟻群算法，蟻群算法（ant colony algorithm， ACA）是受到自然界中真實的蟻群集體行為的啟發(fā)而提出的一種基于種群的模擬進(jìn)化算法，屬于隨機搜索算法。意大利學(xué)者Dorigo等人在20世紀(jì)90年代初首先提出該算法時，充分利用了蟻群搜索食物的過程與著名的旅行商問題之間的相似性，通過人工模擬螞蟻搜索食物的過程來求解TSP，取得了較為理想的效果。它是一種應(yīng)用與組合優(yōu)化問題的啟發(fā)式智能搜索算法。蟻群算法不僅能夠智能搜索、全局優(yōu)化、而且具有魯棒性、正反饋、分布式計算、易與其它算法相結(jié)合等特點。由于蟻群算法基本原理與最大團(tuán)的求解過程有相似之處，所以本文所研究的內(nèi)容在理論上是具有可行性的。并根據(jù)蟻群算法的自身缺陷進(jìn)行了改進(jìn)，提出了一種新的解決最大團(tuán)問題的算法，測試表明算法是可行性。

2 最大團(tuán)問題的基本定義

2.1最大團(tuán)問題基本定義

給定一個無向圖G = (V，E)，其中V ={1，2，...，n}是頂點的集合，E?哿V×V 是它的邊的集合。一個團(tuán)（Clique）是頂點集V 的一個子集，記為C，C?哿V ，要求C 中任意兩個頂點之間有邊相連。也就是說由團(tuán)C 中頂點及其邊組成的子圖是完全圖。最大團(tuán)問題就是要找到具有最多元素數(shù)的子集C 。而最大團(tuán)問題的目標(biāo)就是要找到給定圖的最大團(tuán)。

2.2 最大團(tuán)問題的數(shù)學(xué)描述

設(shè)t:(0，1)n→2v，t(x)={i∈v:xi=1}，?坌x∈(0，1)n，?坌S∈2V，

則x=t-1(S)={xi:i=1，2，…，n}，其中，n為圖的頂點數(shù)。

（1）

St xi+xj≤1，?坌(i，j)∈E，x∈(0，1)n

如果x*是式（1）的最優(yōu)解，那么集合C=t(x*)是圖G的一個最大團(tuán)，且|C|=-f(x*)。

由于xi，xj∈(0，1)，xi+xj≤1，?坌(i，j)∈E當(dāng)且僅當(dāng)xi xj=0。有。其中，A為圖G的補圖G的鄰接矩陣。

MCP等價于下面的全局二次0－1問題

Min f(x)=xTAx（2）

St x∈(0，1)n

其中，A=A-I，如果x*是式（2）的最優(yōu)解，那么集合C=t(x*)是圖G的一個最大團(tuán)，且|C|=-f(x*)。

3 基本蟻群算法

仿生學(xué)家經(jīng)過大量地觀察、研究發(fā)現(xiàn)，螞蟻在尋找食物時，由大量螞蟻組成的蟻群的集體行為表現(xiàn)出了一種信息正反饋現(xiàn)象：某條路徑上經(jīng)過的螞蟻數(shù)越多，其上留下的外激素的跡也就越多（當(dāng)然，隨時間的推移會逐漸蒸發(fā)掉一部分），后來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑上外激素的強度。螞蟻個體之間就是通過這種信息的交流搜索食物，并最終沿著最短路徑行進(jìn)。蟻群優(yōu)化算法就是模擬蟻群這一覓食行為的優(yōu)化算法。蟻群算法主要包括兩個基本階段：適應(yīng)階段和協(xié)作階段。在適應(yīng)階段，各候選解根據(jù)積累的信息不斷調(diào)整自身結(jié)構(gòu)，路徑上經(jīng)過的螞蟻越多，信息素數(shù)量越大，則該路徑越容易被選擇，時間越長，信息素數(shù)量越少；在協(xié)作階段，候選解之間通過信息交流，以期望產(chǎn)生性能更好的解。其協(xié)作方式的本質(zhì)是：1)信息素蹤跡越濃的路徑，被選中的概率越大，即路徑概率選擇機制；2)路徑越短，它上面的信息素蹤跡增長得越快，即信息素更新機制；3)螞蟻之間通過信息素進(jìn)行通信，即協(xié)同工作機制。

3.1 蟻群算法在優(yōu)化過程中的規(guī)則

1)螞蟻在眾多的路徑中轉(zhuǎn)移路線的選擇規(guī)則：螞蟻總是傾向于選擇含有較多信息素的路徑。這里信息素（Pheromone）類似于一種分布式的長期記憶，這種記憶不是局部地存在于單個的人工蟻，而是全局地分布在整個問題空間，這就導(dǎo)致了一種間接聯(lián)絡(luò)方式。

2)全局化信息素更新規(guī)則：在路徑上的信息素，有一部分會被蒸發(fā)散失，這樣沒有被選擇過的路徑信息素越來越少，變得越來越不受歡迎。每只螞蟻按路徑的長短（或找到食物的質(zhì)量）成比例地在屬于其經(jīng)過的路徑上留下一定數(shù)量的信息素。信息素更新的實質(zhì)就是人工螞蟻根據(jù)真實螞蟻在訪問過的邊上留下的信息素和蒸發(fā)的信息素來模擬真實信息素數(shù)量的變化，它使得越好的解答得到越多的增強。這就是為了更形象地模擬蟻群這種選擇路徑的過程時形成的自催化行為而成立的一種自催化強化學(xué)習(xí)機制。

3.2 蟻群算法的數(shù)學(xué)描述

假設(shè)X={Xi|Xi=(xi1，xi2，…，xim)，i=1，2，…，N}是進(jìn)行分析問題的數(shù)據(jù)集合。r為解的半徑，phij(t)為t時刻數(shù)據(jù)Xi到數(shù)據(jù)Xj的路徑上的信息素濃度，dij為樣本與最佳解的加權(quán)歐氏距離，p為加權(quán)因子，可根據(jù)各分量在最佳解的求解中的影響程度而定。

則

（3）

設(shè)phij(0)=0為初始信息量，則

（4）

根據(jù)樣本與最佳解之間的路徑上的信息素濃度，

Xi歸并到Xj的概率phij為：

（5）

其中，ηij(t)是啟發(fā)式引導(dǎo)函數(shù)，表征螞蟻Xi轉(zhuǎn)移至Xj的期望程度，利用啟發(fā)函數(shù)可反映像素之間的相似度，啟發(fā)函數(shù)越大，像素歸于相同解的概率就越大。α、β分別為像素求解過程中所積累的信息以及啟發(fā)式引導(dǎo)函數(shù)對路徑選擇的影響因子。S={Xs|dsj≤r，s=1，2，…，j，j+1，…，N}；為可行路徑集合。

若pij(t)≥p0，則Xi歸并到Xj領(lǐng)域。設(shè)

Cj={Xk|dkj≤r，k=1，2，…，J}，Cj表示所有歸并到Xj領(lǐng)域的數(shù)據(jù)集合。求出理想的最佳解：

（6）

其中：Xk∈Cj

隨著螞蟻的移動，各路徑上信息素的量發(fā)生變化，經(jīng)過一次循環(huán)，按全局調(diào)整規(guī)則調(diào)整各路徑上的信息素如下[5]：

Phij(t)=ρphij(t)+Δphij （7）

其中，ρ為信息素隨時間的衰減系數(shù)，一般取0.5～0.99左右，Δphij為本次循環(huán)中路徑信息素的增量。

（8）

Δph表示第k只螞蟻在本次循環(huán)中留在路徑中的信息素的量。

4 基于蟻群算法的最大團(tuán)問題研究

4.1 最大團(tuán)問題重新定義

為了將最大團(tuán)問題的模型與蟻群算法的求解過程相一致，將最大團(tuán)問題重新定義如下：

最大團(tuán)的模型P=(G，S，Ψ，f，s*)由以下部分組成：

輸入G：輸入的問題為一個圖G=(V，E)，其中V是頂點結(jié)合，E∈V×V是邊的集合。

解空間S:S定義于一組變量和變量的域之上。設(shè)X={X1，X2，…，Xn}是一組n個離散變量的集合，其中n=|V|，對于?坌Xi∈X，Di={0，1}(i=1，2，…，n)是變量Xi的域。對變量Xi的賦值用Xi=xi來表示。若xi=1，表示頂點i在當(dāng)前所考慮的頂點集合中，反之，若xi=0，表示頂點i不在當(dāng)前頂點集合中。一個可行解S是滿足約束條件的X的一個完全賦值：X中的任意一個變量都被賦值。解空間則是所有可行解構(gòu)成的集合，S={s={(X1，x1)， (X2，x2)，…， (Xn，xn)}|xi∈Di}，當(dāng)s滿足所有約束條件時。

變量的約束條件Ψ：根據(jù)最大團(tuán)問題本身的特性，Ψ定義為：如果Xi=1，Xj=1，?坌i，j=1，2，…，n，且i≠i，則無向圖G的邊集E中必然有一條連接頂點i和頂點j之間的邊。目標(biāo)函數(shù)f的定義：f是一個可行解集合到正整數(shù)集合的映射f:S→Z，對于一個給定的可行解s∈S，。全局最優(yōu)解s*: s*∈S是有著最大目標(biāo)函數(shù)值的可行解，即對于s*∈S，f(s*)≥f(s)，?坌s∈S。

重新定義的MCP模型的最佳解是一個滿足一定約束條件的頂點集合，所以本文為了將最大團(tuán)問題與蟻群解決的辦法相關(guān)聯(lián)，采取的是基于頂點的信息素模型。定義如下：Ф=(τ1，τ2，…，τn)，其中n=|V|，τi表示頂點i上積累的信息素的數(shù)量，其值越大意味著在構(gòu)造極大團(tuán)過程中該頂點被選擇的概率越大。

4.2 應(yīng)用蟻群算法解決最大團(tuán)問題的步驟

應(yīng)用蟻群算法解決最大團(tuán)問題的流程如下所示：

procedure 組合優(yōu)化問題的 ACO 算法

設(shè)置參數(shù)，初始化信息素分布；

while 不滿足結(jié)束條件 do

for 蟻群中的每個螞蟻

for 每個解構(gòu)造步（直到構(gòu)造出完整解）

螞蟻按信息素及啟發(fā)式信息的指引構(gòu)造一步問題的解；

進(jìn)行信息素局部更新（可選）；

end of for

end of for

以某些已獲得的解為起點進(jìn)行領(lǐng)域（局部）搜索（可選）；

根據(jù)某些已獲得解的質(zhì)量進(jìn)行全局更新信息素；

end of while

end of procedure

說明：1)這里 while 循環(huán)中的“結(jié)束條件”一般由“達(dá)到最大循環(huán)次數(shù)”和“找到最優(yōu)解了”兩個條件確定，兩個條件中任意一個滿足均可結(jié)束 while 循環(huán)。所謂“找到最優(yōu)解了”是指連續(xù)若干次找不到更好的解的，我們認(rèn)為“找到最優(yōu)解了”。2)“局部更新信息素”過程也稱在線逐步（online step by step）的更新方式，它在每只螞蟻構(gòu)造一個完整的可行解之后進(jìn)行，下一只螞蟻構(gòu)造解的過程就受更新后的信息素指引，與全局更新方式不同，全局更新是一種在線延遲（online delayed）的更新方式。

5 實驗結(jié)果

在實驗中，設(shè)置蟻群的種群大小為10，即相當(dāng)于蟻群的大小m。種群的代數(shù)設(shè)置為5000，相當(dāng)于蟻群優(yōu)化算法中的最大迭代次數(shù)。其它參數(shù)設(shè)置為，α=0.001，Δ=3，λ=0.7，β=0.9。應(yīng)用5個典型的MCP基準(zhǔn)實例來測試本算法，實驗在Window XP操作系統(tǒng)下，MATLAB7.0仿真結(jié)果顯示，盡管本算法只設(shè)定為10個螞蟻進(jìn)行搜索比起更多的螞蟻來搜索所得到的解的質(zhì)量并沒有降低，相比更多的螞蟻進(jìn)行搜索，算法減少了相當(dāng)多的運行時間。實驗結(jié)果見圖1。

6 結(jié)論

蟻群算法作為一種新的啟發(fā)式算法，它具有正反饋、分布式計算等特點，使其能夠成功地解決許多組合優(yōu)化問題。本文在詳細(xì)介紹蟻群算法原理的基礎(chǔ)上，對蟻群算法在組合優(yōu)化問題中的應(yīng)用進(jìn)行了研究，主要應(yīng)用蟻群算法求解最大團(tuán)這個個經(jīng)典的組合優(yōu)化問題。通過改進(jìn)方法，即將信息素留在頂點上，而非邊上，這樣僅節(jié)省了存儲空間，更重要的是提高了運行速度；增加了局部啟發(fā)信息，消除了迭代初期的盲目性；在同等運算規(guī)模下，提高了算法的求解速度和能力，也為以后更加深入研究蟻群算法奠定一定的基礎(chǔ)。

參考文獻(xiàn)：

[1] 彭沛夫.遺傳融合的自適應(yīng)蟻群算法研究[D]. 長沙:湖南大學(xué)，2005

[2] 李默.解決最大團(tuán)問題的蟻群優(yōu)化算法的研究與應(yīng)用[D]. 哈爾濱:哈爾濱工業(yè)大學(xué)，2006.

[3] 賈曉峰，郭廷花，續(xù)曉欣.關(guān)于最大團(tuán)問題的一種新算法[J].中北大學(xué)學(xué)報，2006，27(2):180-182.

[4] 仲盛，謝立.求解圖的最大團(tuán)的一種算法[J].軟件學(xué)報，1999，10(3):288-292.

[5] 高尚.蟻群算法理論、應(yīng)用及其與其他算法的混合[J].電子學(xué)報，2005(10).

[6] 溫玉娟.蟻群算法在圖象分割中的應(yīng)用[J].電子學(xué)報，2005(10).

[7] 林亞平.基于遺傳因子的自適應(yīng)蟻群算法的研究[J].電子學(xué)報，2006(16).

[8] 付宇.蟻群優(yōu)化算法的改進(jìn)及應(yīng)用[J].電子學(xué)報，2006(7).

[9] 高尚，蔣新姿，湯可宗，楊靜宇.蟻群算法與粒子群優(yōu)化的混合算法[J]. 電子學(xué)報， 2006，8

[10] 李利香.基于混沌蟻群算法的研究[J].儀器儀表學(xué)報，2006(9)

[11] 劉彥鵬.蟻群優(yōu)化算法的理論研究及其應(yīng)用[J].電子學(xué)報，2007(4).