（江南大學(xué) 信息工程學(xué)院， 江蘇 無錫 214122）

摘 要：提出一種基于禁忌搜索和蟻群算法的求解最小弱頂點(diǎn)覆蓋問題的混合優(yōu)化算法，用于解決網(wǎng)絡(luò)流量有效測量點(diǎn)的選擇問題。仿真結(jié)果表明，比較現(xiàn)有算法，本算法能夠找到更小的弱頂點(diǎn)覆蓋集，且具有更好的可擴(kuò)展性和實(shí)用性。

關(guān)鍵詞：蟻群優(yōu)化算法；禁忌搜索算法；最小弱頂點(diǎn)覆蓋

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2009)04-1480-04

Hybrid optimization algorithm forefficient monitor-nodes selection in network traffic

GE Hong-wei，PENG Zhen-yu，YUE Hai-bing

(School of Information， Jiangnan University， Wuxi Jiangsu 214122， China)

Abstract:This paper proposed a new hybrid optimization algorithm for solving minimum weak vertex cover set problem.The experimental results show that the proposed hybrid optimization algorithm is more expansibility and practicability，and can find smaller weak vertex cover set than other algorithms．

Key words:ant colony optimization；tabu search；minimum weak vertex cover set

隨著Internet重要性的日益提高和網(wǎng)絡(luò)結(jié)構(gòu)的日益復(fù)雜，網(wǎng)絡(luò)管理越來越成為人們關(guān)注的焦點(diǎn)?，F(xiàn)代的網(wǎng)絡(luò)管理系統(tǒng)注重于服務(wù)級(jí)、應(yīng)用級(jí)的管理，如主動(dòng)式和被動(dòng)式的資源管理、流量工程、端到端的服務(wù)質(zhì)量保證等。所有這些網(wǎng)管業(yè)務(wù)均以了解網(wǎng)絡(luò)流量等網(wǎng)絡(luò)運(yùn)行參數(shù)為基礎(chǔ)。為此，有必要對(duì)網(wǎng)絡(luò)流量進(jìn)行測量和分析，以利于發(fā)現(xiàn)網(wǎng)絡(luò)瓶頸，優(yōu)化網(wǎng)絡(luò)配置，并進(jìn)一步發(fā)現(xiàn)網(wǎng)絡(luò)中可能存在的潛在危險(xiǎn)。

由于Internet是一個(gè)不斷變化的龐大網(wǎng)絡(luò)，網(wǎng)絡(luò)流量的測量要具有一定的實(shí)時(shí)性。目前，網(wǎng)絡(luò)流量的測量方法要求針對(duì)特定的感興趣的鏈路，人工合理地規(guī)劃網(wǎng)絡(luò)的觀測節(jié)點(diǎn)，并安裝特定的監(jiān)測軟件或硬件。但這種方法難以擴(kuò)展，不便于動(dòng)態(tài)適應(yīng)網(wǎng)絡(luò)的變化，且可能因?yàn)樵O(shè)置過多的觀測節(jié)點(diǎn)而增加網(wǎng)絡(luò)的額外負(fù)擔(dān)。

測量方法關(guān)鍵的步驟是既要準(zhǔn)確獲取網(wǎng)絡(luò)流量參數(shù)，又要盡量減少數(shù)據(jù)收集對(duì)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)傳輸造成的額外負(fù)荷。因此，觀測節(jié)點(diǎn)的選擇尤其重要。研究中一般將網(wǎng)絡(luò)流量有效測量點(diǎn)選擇問題轉(zhuǎn)換為求給定無向圖中的最小弱頂點(diǎn)覆蓋問題，由于這個(gè)問題已被證明是NP-hard問題，因此一般采用近似算法求解，如文獻(xiàn)［1］給出了一個(gè)求解弱頂點(diǎn)覆蓋問題的貪婪秩算法；文獻(xiàn)[2]又提出了一個(gè)弱化的貪心算法。但所有這些算法均需知道網(wǎng)絡(luò)拓?fù)涞娜中畔ⅲ蚨蓴U(kuò)展性較差，而且問題規(guī)模較大時(shí)，算法求解質(zhì)量不高，或根本求不出最優(yōu)解。于是本文提出了一種求解最小弱頂點(diǎn)覆蓋問題的混合優(yōu)化算法，即基于禁忌搜索的蟻群優(yōu)化算法TSBACO（tabu search based ACO），對(duì)網(wǎng)絡(luò)流量有效測量點(diǎn)的選擇問題進(jìn)行研究和實(shí)驗(yàn)，取得了良好的成效。

1 網(wǎng)絡(luò)流量測量模型描述

在網(wǎng)絡(luò)中某一節(jié)點(diǎn)設(shè)置測量器(如SNMP agent)，可以得到與這一節(jié)點(diǎn)相連的所有鏈路上的流量。因此，為了得到網(wǎng)絡(luò)中所有鏈路的網(wǎng)絡(luò)流量，一般可以通過在某些交換節(jié)點(diǎn)(路由器)配置測量器實(shí)現(xiàn)。要考慮的問題是：在網(wǎng)絡(luò)哪些節(jié)點(diǎn)上設(shè)置測量器，才能使得在可以得到每一條鏈路流量的條件下，所需測量器數(shù)目最小。這一問題自然可以歸納為圖論中的最小頂點(diǎn)覆蓋問題。

為了方便問題模型的描述，參照文獻(xiàn)[2]給出以下定義：

定義1 給定無向圖G=(V，E)。其中：V是頂點(diǎn)集；E是邊集；S是V的子集，若根據(jù)與S中頂點(diǎn)相關(guān)聯(lián)的各條邊的流量，可確定E中任意邊的流量，則稱S是圖G關(guān)于流量的測量集。

有效測量問題的目標(biāo)就是求給定圖G關(guān)于流量的最小測量集。雖然采用求解最小頂點(diǎn)覆蓋問題的算法可以求出一個(gè)測量集，但已證明，最小頂點(diǎn)覆蓋問題是一個(gè)NP-hard問題，尚無多項(xiàng)式時(shí)間的求解算法，且求出的測量集也未必是最小測量集。如果測量器是路由器或交換機(jī)等交換設(shè)備，那么圖還滿足以下兩條約束條件：

a)對(duì)圖G的頂點(diǎn)集V中的任意頂點(diǎn)v，其degree(v)≥2；

b)對(duì)圖G的頂點(diǎn)集V中的任意頂點(diǎn)v，滿足流守恒方程，即流進(jìn)=流出。

盡管以下原因?qū)?huì)導(dǎo)致流守恒方程的失真，如：交換設(shè)備是數(shù)據(jù)的源或匯，而不僅僅是數(shù)據(jù)轉(zhuǎn)發(fā)器；多播導(dǎo)致輸出端口的數(shù)據(jù)復(fù)制；交換設(shè)備本身的數(shù)據(jù)包延遲或丟失。但是若干研究表明，流守恒方程所具有的相對(duì)誤差小于0.05%。因此，由以上兩條約束條件，求圖G關(guān)于流量的最小測量集問題可以轉(zhuǎn)換為求定義2中圖的弱頂點(diǎn)覆蓋問題。

定義2 假定無向圖G=(V，E)滿足對(duì)任意v∈V有degree(v)≥2，稱SV是圖G的弱頂點(diǎn)覆蓋集，當(dāng)且僅當(dāng)執(zhí)行以下操作能使E中所有的邊都可被標(biāo)記：

a)標(biāo)記所有與S中頂點(diǎn)相關(guān)聯(lián)的邊；

b)若某個(gè)頂點(diǎn)v的degree(v)-1條相關(guān)聯(lián)的邊已被標(biāo)記，則標(biāo)記剩下的那條相關(guān)聯(lián)的邊；

c)重復(fù)第b)步，直到不能再標(biāo)記新的邊為止。

圖G的弱頂點(diǎn)覆蓋S就是在流守恒約束條件下的圖G關(guān)于流量的測量集。首先與集合S中頂點(diǎn)相關(guān)聯(lián)的邊的流量可以通過測量手段來獲??；其次，如果vS，且v的degree(v)-1條邊的流量已獲得，那么根據(jù)流守恒方程可以計(jì)算出另外一條邊的流量。反復(fù)應(yīng)用流守恒方程，可計(jì)算出圖G中所有邊的流量。網(wǎng)絡(luò)流量測量中的有效測量點(diǎn)選擇問題實(shí)際上就是求解無向圖G的最小弱頂點(diǎn)覆蓋問題。

2 最小頂點(diǎn)覆蓋問題

設(shè)簡單圖G=(V，E)是一無向圖。其中：V是圖中頂點(diǎn)集合；E是邊集合。下面給出頂點(diǎn)覆蓋的有關(guān)定義。如果圖G中的一個(gè)頂點(diǎn)和一條邊相互關(guān)聯(lián)，則稱其相互覆蓋；稱頂點(diǎn)集V的一個(gè)子集V′為頂點(diǎn)覆蓋，如果圖G的任意一條邊都至少有一個(gè)端點(diǎn)屬于V′；如果一個(gè)頂點(diǎn)覆蓋是圖G的其他任何頂點(diǎn)覆蓋的真子集，則稱該頂點(diǎn)覆蓋為圖G的極小頂點(diǎn)覆蓋；包含頂點(diǎn)數(shù)最少的頂點(diǎn)覆蓋就是圖G的最小頂點(diǎn)覆蓋，最小頂點(diǎn)覆蓋的頂點(diǎn)數(shù)稱為圖G的覆蓋數(shù)。例如，圖1中黑色頂點(diǎn)所組成的頂點(diǎn)集就是相應(yīng)圖的最小頂點(diǎn)覆蓋。

由上述定義可知，最小頂點(diǎn)覆蓋(minimum vertex covering，MVC)問題是指，給定一個(gè)無向圖G=(V，E)，求頂點(diǎn)集V的一個(gè)最小子集S，使得e=(u，v)∈E，且u∈S或v∈S，即E中的任一邊至少有一個(gè)頂點(diǎn)屬于S，即S中的頂點(diǎn)覆蓋了邊集E。

由于最小頂點(diǎn)覆蓋問題是NP-hard問題，到目前為止還不存在多項(xiàng)式時(shí)間算法來求解。雖然一些學(xué)者已經(jīng)證實(shí)對(duì)于特殊的圖，通過采用特殊的算法，可以在多項(xiàng)式時(shí)間內(nèi)求得圖的最小頂點(diǎn)覆蓋，如互補(bǔ)圖、圓弧圖、立方圖等。但本文不是對(duì)一些特殊的圖求其多項(xiàng)式時(shí)間算法，而是要對(duì)一般的圖進(jìn)行最小頂點(diǎn)覆蓋問題的求解。在已有的近似算法中，算法僅根據(jù)局部信息進(jìn)行決策，因此在許多情況下，這類算法并不能確定最小頂點(diǎn)覆蓋問題。而對(duì)于傳統(tǒng)的精確算法如分支限界法、割平面法，對(duì)偶啟發(fā)方法等，盡管這些方法能求得最小頂點(diǎn)覆蓋的最優(yōu)解，但其計(jì)算復(fù)雜度高、花費(fèi)時(shí)間長，并不能應(yīng)用到大規(guī)模問題中，所以必須使用啟發(fā)式算法來求解圖的最小頂點(diǎn)覆蓋問題，使得在較短時(shí)間內(nèi)求出問題的較優(yōu)解甚至最優(yōu)解。由上述最小頂點(diǎn)覆蓋問題的定義可知，該問題是一個(gè)組合優(yōu)化問題，也是一個(gè)子集類問題，所以非常適合采用蟻群優(yōu)化(ant colony optimization，ACO)算法來求解。

3 基于禁忌搜索的蟻群優(yōu)化算法

ACO算法作為一種新型元啟發(fā)式算法，最近被用來解決許多不同的組合優(yōu)化問題，但ACO算法在搜索過程中容易出現(xiàn)停滯現(xiàn)象或陷入局部最優(yōu)。而禁忌搜索是對(duì)局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，采用的是一種確定性的局部極小突跳策略。禁忌搜索算法通過引入一個(gè)靈活的禁忌表和相應(yīng)的禁忌準(zhǔn)則來避免重復(fù)迂回搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實(shí)現(xiàn)全局優(yōu)化。禁忌策略最重要的思想是標(biāo)記對(duì)應(yīng)已搜索到的局部最優(yōu)解的一些對(duì)象，并在進(jìn)一步的迭代搜索中盡量避開這些對(duì)象（而不是絕對(duì)禁止循環(huán)）從而保證對(duì)不同的有效搜索途徑的探索。但在搜索算法中，可能會(huì)出現(xiàn)候選解全部被禁忌，或者存在一個(gè)優(yōu)于到目前為止最好解的禁忌候選解，此時(shí)藐視準(zhǔn)則就將使某些狀態(tài)解禁，以實(shí)現(xiàn)更高效的優(yōu)化性能。藐視準(zhǔn)則的設(shè)置就是要算法避免遺失優(yōu)良狀態(tài)，激勵(lì)對(duì)優(yōu)良狀態(tài)的局部搜索，進(jìn)而實(shí)現(xiàn)全局優(yōu)化。對(duì)于非禁忌候選狀態(tài)，算法無視它與當(dāng)前狀態(tài)的優(yōu)劣關(guān)系，僅考慮它們中間的最佳狀態(tài)，如此便可實(shí)現(xiàn)對(duì)局部極小的跳躍。正由于禁忌技術(shù)具有靈活的記憶功能和藐視準(zhǔn)則，且在搜索過程中可以接受劣解，所以搜索時(shí)能夠跳出局部最優(yōu)解，轉(zhuǎn)向搜索空間的其他區(qū)域，從而增強(qiáng)獲得更好的全局最優(yōu)解的概率。

為防止ACO算法出現(xiàn)停滯現(xiàn)象或陷入局部最優(yōu)，本文將ACO算法與禁忌搜索算法結(jié)合起來，提出了一種基于禁忌搜索的蟻群優(yōu)化算法TSBACO。該算法可以在一定程度上有效解決擴(kuò)大搜索空間和加快收斂速度之間的矛盾，從而使得TSBACO算法既能避免重復(fù)迂回搜索，跳出局部最優(yōu)解，又能對(duì)不同搜索區(qū)域進(jìn)行更有效探索，不僅提高了全局優(yōu)化性能而且還提高了搜索效率。



4 基于TSBACO的最小弱頂點(diǎn)覆蓋問題求解

由于在網(wǎng)絡(luò)環(huán)境中，所有頂點(diǎn)的度deg(v)≥2，所以求解最小頂點(diǎn)覆蓋問題可以轉(zhuǎn)換為求解最小弱頂點(diǎn)覆蓋問題。

4.1 關(guān)聯(lián)矩陣

首先給出最小弱頂點(diǎn)覆蓋問題的關(guān)聯(lián)矩陣定義，無向圖G的關(guān)聯(lián)矩陣A=(aij)是指如下定義的n×m矩陣：

aij=1，如果頂點(diǎn)vi與邊ej相關(guān)聯(lián)

0，其他

圖2為某網(wǎng)絡(luò)拓?fù)鋱D。

對(duì)于圖2中的網(wǎng)絡(luò)拓?fù)鋱D，其關(guān)聯(lián)矩陣A為

e1e2e3 e4e5

v111000

v201110

v300011

v410101

由上面的網(wǎng)絡(luò)拓?fù)鋱D和其關(guān)聯(lián)矩陣可知，對(duì)于任何一個(gè)有n個(gè)頂點(diǎn)和m條邊的無向圖G=(V，E)，滿足對(duì)任意v∈V有degree(v)≥2，則整個(gè)圖G都可用一個(gè)n×m的二階矩陣來表示，矩陣由{0，1}組成。其中每一行表示一個(gè)頂點(diǎn)，每一列表示一條邊；圖中每個(gè)頂點(diǎn)對(duì)應(yīng)行中的各個(gè)值表示該頂點(diǎn)的鄰邊情況，1表示頂點(diǎn)和邊存在關(guān)聯(lián)關(guān)系，0則表示不存在關(guān)聯(lián)關(guān)系。

4.2 求解最小弱頂點(diǎn)覆蓋問題的近似算法

以下給出一個(gè)求解最小弱頂點(diǎn)覆蓋問題的近似算法，并把求解得出的弱頂點(diǎn)覆蓋集作為蟻群初次循環(huán)的初始解，算法的思想為：

a)選取一個(gè)含有邊數(shù)最多的頂點(diǎn)vi；

b)刪除關(guān)聯(lián)矩陣中頂點(diǎn)vi對(duì)應(yīng)的行及該行中值為1的元素所在列；然后在剩下的關(guān)聯(lián)矩陣中再次刪除所有行元素之和不超過1的其他行及這些行中值為1的元素所對(duì)應(yīng)的列，直到不能再刪除新的行和列為止；

c)重復(fù)以上步驟，直到所有的邊都被包含到。

以圖2為例，對(duì)上述近似算法思想進(jìn)行形象說明：

a)計(jì)算關(guān)聯(lián)矩陣A的每行元素之和mj=1aij，當(dāng)i=1，2，3，4時(shí)，每行元素之和分別為2，3，2，3；可知當(dāng)i=2或i=4時(shí)，對(duì)應(yīng)行的元素之和最大，即對(duì)應(yīng)頂點(diǎn)覆蓋的邊最多，所以在這里可以選取v2或v4，假定本文選取的是v2。

b)刪除關(guān)聯(lián)矩陣中v2對(duì)應(yīng)的行及該行中值為1的邊，即刪除的是邊e2，e3和e4，最后得到剩下的關(guān)聯(lián)矩陣為

e1e5

v110

v301

v411

c)在這個(gè)關(guān)聯(lián)矩陣中再依次刪除所有行元素之和不超過1的其他行，如v1和v3行，以及這兩行中值為1的元素所對(duì)應(yīng)的列，如e1和e5列，最后得到的剩余關(guān)聯(lián)矩陣A=0。于是得到該近似算法的最小弱頂點(diǎn)覆蓋集S={v2}，即只要測量一個(gè)節(jié)點(diǎn)即可得到各條鏈路的流量。

雖然在此圖例中S是最優(yōu)解，但是隨著問題規(guī)模的擴(kuò)大，通過此近似算法求解得出的最小弱頂點(diǎn)覆蓋集將是一個(gè)近似解，而不是一個(gè)較優(yōu)解更不可能是一個(gè)最優(yōu)解。所以為了求解最小弱頂點(diǎn)覆蓋問題的最優(yōu)解，必須在此近似解的基礎(chǔ)上，繼續(xù)使用TSBACO算法對(duì)其進(jìn)行全局尋優(yōu)。

4.3 隨機(jī)比例狀態(tài)轉(zhuǎn)移規(guī)則

ACO算法在求解大多數(shù)問題時(shí)，主要是通過蟻群對(duì)邊的集合進(jìn)行搜索，因此信息素和期望啟發(fā)信息都被設(shè)置在邊上。而最小弱頂點(diǎn)覆蓋問題的求解則是通過對(duì)頂點(diǎn)的集合進(jìn)行的搜索，所以在本文提出的TSBACO算法中，信息素釋放在頂點(diǎn)上，而不是在邊上，同時(shí)還使用了期望啟發(fā)信息來引導(dǎo)螞蟻的搜索。在螞蟻k構(gòu)造弱頂點(diǎn)覆蓋集的過程中，對(duì)頂點(diǎn)的選擇將按如下概率選擇式進(jìn)行：

pki=ταiηβi/j∈Ckταjη β j(1)

其中：τi表示頂點(diǎn)vi的信息素軌跡強(qiáng)度；ηi表示頂點(diǎn)vi的期望啟發(fā)信息；Ck表示螞蟻k的候選頂點(diǎn)集；α為信息啟發(fā)式因子；β為期望啟發(fā)式因子，這兩個(gè)參數(shù)都是常量，其值的選取需要人為經(jīng)驗(yàn)的指定。

頂點(diǎn)的期望啟發(fā)信息是靜態(tài)的，其值在算法運(yùn)行前已確定，即頂點(diǎn)的期望啟發(fā)信息值在蟻群的尋優(yōu)過程中保持不變。雖然這種靜態(tài)定義方式不需要反復(fù)計(jì)算頂點(diǎn)的度，并提高了算法運(yùn)算速度，但當(dāng)圖中各頂點(diǎn)的度相差過大或過小時(shí)，就會(huì)失去對(duì)蟻群搜索的指導(dǎo)意義。所以這里，對(duì)頂點(diǎn)的期望啟發(fā)信息采用了動(dòng)態(tài)定義的方式。由于頂點(diǎn)的期望啟發(fā)信息值是頂點(diǎn)的度，當(dāng)與該頂點(diǎn)相連的頂點(diǎn)被選擇加入弱頂點(diǎn)覆蓋集時(shí)，該頂點(diǎn)的度要減1。頂點(diǎn)vi的期望啟發(fā)信息ηi表達(dá)式如下：

ηi=|vi|(2)

當(dāng)頂點(diǎn)vi被螞蟻k選擇后，筆者將頂點(diǎn)vi加入螞蟻k的部分解集合S中，同時(shí)將頂點(diǎn)vi和與該頂點(diǎn)相連的所有邊都刪除；然后按照上述近似算法思想更新關(guān)聯(lián)矩陣，繼續(xù)刪除頂點(diǎn)和邊，直到?jīng)]有任何可以刪除的頂點(diǎn)和邊。重復(fù)以上步驟直到關(guān)聯(lián)矩陣A=0，即所有邊都已被部分解集合S中的頂點(diǎn)所覆蓋，那么這個(gè)集合S就是螞蟻k構(gòu)造的弱頂點(diǎn)覆蓋集。

4.4 信息素更新規(guī)則

信息素更新規(guī)則有多種形式，本文提出的求解最小弱頂點(diǎn)覆蓋問題的TSBACO算法采用的是MMAS[3]的信息素更新規(guī)則，其主要特點(diǎn)在于：

a)在每次蟻群循環(huán)后，只有循環(huán)最優(yōu)螞蟻可以進(jìn)行信息素釋放；

b)各頂點(diǎn)的信息素軌跡強(qiáng)度被限制在[τmin，τmax]范圍內(nèi)；

c)各頂點(diǎn)的信息素軌跡強(qiáng)度被初始化為τmax。

MMAS通過這種信息素軌跡強(qiáng)度范圍控制，可以防止個(gè)別頂點(diǎn)上的信息素軌跡強(qiáng)度過度增加或減少，從而可以有效避免算法出現(xiàn)早熟停滯現(xiàn)象。

下面針對(duì)求解最小弱頂點(diǎn)覆蓋問題，詳細(xì)給出TSBACO算法的信息素更新規(guī)則：

首先需要為網(wǎng)絡(luò)拓?fù)鋱D中的每個(gè)頂點(diǎn)vi設(shè)置一個(gè)信息素軌跡強(qiáng)度初始值τmax，而信息素軌跡強(qiáng)度的更新則是在蟻群完成一次循環(huán)之后。為了充分利用循環(huán)最優(yōu)解，每次循環(huán)后只有循環(huán)最優(yōu)螞蟻可以進(jìn)行信息素釋放。為了模擬信息素?fù)]發(fā)，圖中所有頂點(diǎn)的信息素軌跡強(qiáng)度都要乘以一個(gè)信息素?fù)]發(fā)系數(shù)ρ；然后，循環(huán)最優(yōu)螞蟻才會(huì)釋放信息素。所以頂點(diǎn)信息素的更新分為兩步進(jìn)行：

a)頂點(diǎn)信息素的揮發(fā)

τi(t+1)=(1-ρ)τi(t)(3)

b)頂點(diǎn)信息素的增加

假定WVCc是某次循環(huán)中蟻群找到的包含頂點(diǎn)數(shù)最少的弱頂點(diǎn)覆蓋，即循環(huán)最優(yōu)解；而WVCg則是從算法運(yùn)行以來蟻群找到的包含頂點(diǎn)數(shù)最少的弱頂點(diǎn)覆蓋，即全局最優(yōu)解。在蟻群完成每次循環(huán)后，循環(huán)最優(yōu)螞蟻把一定量的信息素釋放在WVCc中的各個(gè)頂點(diǎn)上。通過循環(huán)最優(yōu)螞蟻信息素的釋放，循環(huán)最優(yōu)解WVCc中的頂點(diǎn)將得到大量的信息素增強(qiáng)。頂點(diǎn)信息素增量表達(dá)式如下：

Δτi=Q/（1+‖WVCc|-|WVCg‖）(4)

其中：Q為信息素增量系數(shù)，其值由經(jīng)驗(yàn)所定；|WVCc|和|WVCg|分別表示W(wǎng)VCc和WVCg中的頂點(diǎn)個(gè)數(shù)。

4.5 禁忌表的使用

禁忌搜索策略中禁忌表的使用就是要使算法盡量避免重復(fù)迂回搜索，這樣不僅能加強(qiáng)搜索的多樣性而且能使算法跳出局部最優(yōu)解。在禁忌搜索框架下，多樣性的加強(qiáng)是通過一些移動(dòng)的暫時(shí)禁止獲得的。針對(duì)最小弱頂點(diǎn)覆蓋集問題，筆者將螞蟻完成一次最小弱頂點(diǎn)覆蓋集的構(gòu)造稱為一次移動(dòng)。只要一次移動(dòng)完成，那么在隨后的L次循環(huán)中，這次移動(dòng)將被禁止，即在以下連續(xù)的L次循環(huán)中，具有相同結(jié)構(gòu)的弱頂點(diǎn)覆蓋集將被視為禁忌對(duì)象。禁忌搜索策略的實(shí)現(xiàn)則是要通過禁忌表的使用，其禁忌對(duì)象的替換是采用先進(jìn)先出的方式。螞蟻每完成一次移動(dòng)，這次移動(dòng)就被放入禁忌表，并將剛放入禁忌表的移動(dòng)禁忌初始值記為L，這樣每經(jīng)過一次循環(huán)，禁忌表中每個(gè)移動(dòng)的禁忌值均減1，當(dāng)移動(dòng)的禁忌值變?yōu)?時(shí)，這個(gè)移動(dòng)就要從禁忌表中刪除并被解禁。禁忌表長度是一個(gè)很重要的參數(shù)，它決定禁忌對(duì)象的任期，其大小直接影響整個(gè)算法的搜索進(jìn)程和行為。所以在算法求解過程中，如果某些弱頂點(diǎn)覆蓋集的結(jié)構(gòu)重復(fù)頻繁出現(xiàn)，那么就應(yīng)該增加禁忌表的長度；如果禁忌表的長度已經(jīng)影響到了算法的性能，那么就減少禁忌表的長度。

4.6 藐視準(zhǔn)則

TSBACO中的藐視準(zhǔn)則定義如下：當(dāng)候選頂點(diǎn)集中沒有可選非禁忌點(diǎn)，或者存在某個(gè)特殊的禁忌點(diǎn)，它的選擇會(huì)比其他非禁忌點(diǎn)的選擇有更高效的優(yōu)化性能，那么這個(gè)頂點(diǎn)就會(huì)在本次移動(dòng)中被選擇，并放入所求最小弱頂點(diǎn)覆蓋集中。為了判斷頂點(diǎn)的禁忌狀態(tài)，在螞蟻構(gòu)造新弱頂點(diǎn)覆蓋集時(shí)加入了一個(gè)頂點(diǎn)禁忌狀態(tài)核對(duì)函數(shù)f(vi)。如果頂點(diǎn)vi的返回值是1，那么這個(gè)頂點(diǎn)就被禁止，否則就是可選的。

4.7 TSBACO算法的偽代碼

初始化信息素軌跡

repeat

for每只螞蟻k

螞蟻k隨機(jī)選擇一個(gè)起始頂點(diǎn)vi∈V，并把起始頂點(diǎn)加入最小弱頂點(diǎn)覆蓋集WVCk



repeat

構(gòu)造一個(gè)非禁忌候選頂點(diǎn)集Ck

按照式（1）的概率選擇函數(shù)pkj

從Ck中選擇下一個(gè)頂點(diǎn)vj∈Ck

把頂點(diǎn)vj加入最小弱頂點(diǎn)覆蓋集WVCk

until最小弱頂點(diǎn)覆蓋集WVCk被構(gòu)造完成

end for

保存循環(huán)最優(yōu)解WVCc

如果|WVCc|＜|WVCg|，那么|WVCg|=|WVCc|，即更新全局最優(yōu)解WVCg

把禁忌初始值為的WVCc加入禁忌表

修改禁忌表中各對(duì)象的任期

刪除禁忌值為0的禁忌對(duì)象

按照更新規(guī)則進(jìn)行信息素軌跡更新

until最優(yōu)解被找到或已完成最大循環(huán)次數(shù)

返回全局最優(yōu)解，即|WVCg|

4.8 算法正確性分析

定理1 若圖G=（V，E）是簡單連通無向圖，且滿足對(duì)任意v∈V有degree(v)≥2，則TSBACO算法所得的頂點(diǎn)集是圖G的一個(gè)弱頂點(diǎn)覆蓋集。

證明 TSBACO算法中每只螞蟻在每次循環(huán)中進(jìn)行的搜索實(shí)際相當(dāng)于如下：

a)令G′=G；

b)從圖G′中選擇狀態(tài)轉(zhuǎn)移概率最大的頂點(diǎn)，記錄該頂點(diǎn)，并且刪除該頂點(diǎn)和該頂點(diǎn)的所有鄰邊，記生成的圖為G″；

c）在圖G″中，對(duì)于所有度為1的頂點(diǎn)，刪除該頂點(diǎn)及該頂點(diǎn)的一條鄰邊，仍記生成的圖為G″；

d)重復(fù)c)，直到圖G″中所有頂點(diǎn)的度都大于1或者圖G″中沒有任何頂點(diǎn)；

e)令G′=G″，轉(zhuǎn)回b)，直到圖G′中沒有任何頂點(diǎn)。

由前面定義2可知，圖G也是其本身的弱頂點(diǎn)覆蓋集。

由上述的c)可知，當(dāng)一個(gè)頂點(diǎn)只剩一條鄰邊時(shí)，該條邊也將被刪除，這與定義2中的b)相符，當(dāng)且僅當(dāng)該頂點(diǎn)的所有鄰邊均被刪除后，該頂點(diǎn)才被刪除，即該頂點(diǎn)的所有鄰邊都已被記錄的所有頂點(diǎn)覆蓋。

因此所有已經(jīng)記錄了的頂點(diǎn)和圖G′中的剩余頂點(diǎn)構(gòu)成了圖G的一個(gè)弱頂點(diǎn)覆蓋集。由于每次蟻群循環(huán)結(jié)束時(shí)，圖G′中沒有任何頂點(diǎn)，因此每次循環(huán)結(jié)束時(shí)，每只螞蟻記錄的頂點(diǎn)集合便構(gòu)成了圖G的一個(gè)弱頂點(diǎn)覆蓋集。算法最終是從每次循環(huán)每只螞蟻產(chǎn)生的頂點(diǎn)記錄列表中選取頂點(diǎn)個(gè)數(shù)最少的頂點(diǎn)記錄集，因此該頂點(diǎn)記錄集也是圖G的一個(gè)弱頂點(diǎn)覆蓋集。

證明完畢。

5 仿真實(shí)驗(yàn)

為驗(yàn)證TSBACO算法在實(shí)際網(wǎng)絡(luò)流量有效測量點(diǎn)選擇中的優(yōu)越性能，本文參考文獻(xiàn)［1］進(jìn)行了仿真實(shí)驗(yàn)，并比較了幾種有效測量點(diǎn)選擇算法。實(shí)驗(yàn)中所用到的網(wǎng)絡(luò)拓?fù)鋱D是通過Waxman網(wǎng)絡(luò)模型生成的，Waxman網(wǎng)絡(luò)模型是網(wǎng)絡(luò)研究中一種比較流行的拓?fù)渖赡Ｐ?。在Waxman模型中，n個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布在笛卡爾空間，考慮節(jié)點(diǎn)間所有可能的連接，網(wǎng)絡(luò)鏈路以一定概率方式加入網(wǎng)絡(luò)拓?fù)鋱D中。節(jié)點(diǎn)i和j之間的邊按概率p(i， j)生成，其概率表達(dá)式如下：

p(i， j)=λe-d/(γL)(5)

其中：參數(shù)λ＞0，用于控制拓?fù)鋱D中邊的密度；γ≤1，用于控制拓?fù)鋱D中節(jié)點(diǎn)的平均度數(shù)；e為自然指數(shù)；d為節(jié)點(diǎn)i和j之間的距離；L為各個(gè)節(jié)點(diǎn)間的最長距離。

由此可見，通過設(shè)置Waxman模型的三個(gè)參數(shù)n、λ、γ，即可得到各種不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖。下面設(shè)置四組參數(shù)，生成四種不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，其參數(shù)設(shè)置如表1所示。

表1 Waxman模型參數(shù)設(shè)置

nλγ

15000.40.02

25000.40.04

35000.40.06

45000.40.08

基于以上參數(shù)設(shè)置生成的四種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，比較了六種算法，分別是：文獻(xiàn)［1］中提到的三種算法，即生成簡單頂點(diǎn)覆蓋的最大匹配啟發(fā)算法(VC)、生成弱頂點(diǎn)覆蓋的最大匹配啟發(fā)算法(WVC)、生成弱頂點(diǎn)覆蓋的貪婪秩算法(greedy rank，GR)；文獻(xiàn)[4]中提出的SMN算法；標(biāo)準(zhǔn)ACO算法以及本文提出的TSBACO算法。

TSBACO算法的參數(shù)設(shè)置如下：螞蟻數(shù)量a=30，信息素?fù)]發(fā)系數(shù)ρ=0.02，信息啟發(fā)因子α=2，期望啟發(fā)因子β=1，信息素上界τmax=10，信息素下界τmin=0.1，信息素增量系數(shù)Q=0.5，最大循環(huán)次數(shù)c=500，禁忌長度L=10。

六種網(wǎng)絡(luò)流量測量點(diǎn)選擇算法的比較如表2所示。

表2 六種網(wǎng)絡(luò)流量測量點(diǎn)選擇算法的比較

avg degreeNvcmatchNWVCmatchNWVCrank

NWVCsumNWVCacoNWVCtsbaco

4.4387255165129124121

8.6441372254221216213

12.6453408307296292287

16.9466431334327322318

表2中的第一列為網(wǎng)絡(luò)拓?fù)鋱D中節(jié)點(diǎn)的平均度數(shù)，它隨著γ參數(shù)值的增大而增大；Nvcmatch，NWVCmatch，NWVCrank，NWVCsun，NWVCaco和NWVCtsbaco表示由上述六種算法得到的測量點(diǎn)個(gè)數(shù)。由表中的實(shí)驗(yàn)結(jié)果可以看出，TSBACO算法在四種網(wǎng)絡(luò)拓?fù)鋱D中選取的節(jié)點(diǎn)個(gè)數(shù)比前五種算法都少，即TSBACO算法可以生成更小的弱頂點(diǎn)覆蓋集，而VC、WVC、GR、SMN這些近似算法往往求得的是次優(yōu)解而不是較優(yōu)解和最優(yōu)解。再看NWVCaco和NWVCtsbaco列，由于TSBACO算法中禁忌表的使用，使得算法既能避免重復(fù)迂回搜索，跳出局部最優(yōu)解，又能對(duì)不同搜索區(qū)域進(jìn)行更有效地探索；相比ACO算法易陷入局部最優(yōu)和早熟收斂的缺點(diǎn)，TSBACO算法能以更大的概率收斂到全局最優(yōu)解，求解出節(jié)點(diǎn)數(shù)更少的弱頂點(diǎn)覆蓋集。

6 結(jié)束語

本文提出了一種求解網(wǎng)絡(luò)流量有效測量點(diǎn)選擇問題的混合優(yōu)化算法——基于禁忌搜索的蟻群優(yōu)化算法TSBACO。該算法利用ACO算法的正反饋機(jī)制加快了收斂速度，利用TS算法的全局搜索能力避開了局部最優(yōu)。仿真實(shí)驗(yàn)結(jié)果表明，TSBACO算法是求解網(wǎng)絡(luò)流量測量中的一種有效的測量點(diǎn)選擇算法，該算法求解質(zhì)量較高，而且擁有較好的可擴(kuò)展性和實(shí)用性。在TSBACO算法中，禁忌表長度L是一個(gè)很重要的參數(shù)，其大小直接影響真?zhèn)€算法的性能，如何選擇L使之能更好的求解最小弱頂點(diǎn)覆蓋問題，則是今后的研究重點(diǎn)之一。

參考文獻(xiàn)：

［1］BREITBART Y，CHAN Che-yong，GAROFALAKIS M，et al.Efficiently monitoring bandwidth and latency in IP networks[C]//Proc of IEEE INFOCOM.Anchorage， Alaska:IEEE Press，2001：933-942.

[2]劉湘輝，殷建平，唐樂樂，等.網(wǎng)絡(luò)流量的有效測量方法分析[J]．軟件學(xué)報(bào)，2003，14(2)：300-304.

［3］STUTZLE T，HOOS H.Max-min ant system[J].Future Generation Computer Systems，2000，16(8)：889-914.

[4]蔣紅艷，林亞平，黃生葉.網(wǎng)絡(luò)流量有效監(jiān)測點(diǎn)的設(shè)置模型及求解算法研究[J].電子與信息學(xué)報(bào)， 2006，28(4)：753-756.

[5]BATTITI R，PROTASI M.Reactive local search for the maximum clique problem[J].Algorithmica，2001，29(4)：610-637．

[6]FENET S，SOLNON C.Searching for maximum cliques with ant colony optimization[J].Applications of Evolutionary Computing，2003，26(11)：236-245.

[7]HUA Zhen，F(xiàn)AN Hui，LI Jin-jiang，et al.Solving point covering problem by ant algorithm[C]//Proc ofInternational Conference on Machine Learning and Cybernetics.Shanghai:[s.n.]，2004：3501-3504.

[8]劉湘輝，殷建平，唐樂樂，等.基于弱頂點(diǎn)覆蓋的網(wǎng)絡(luò)鏈路使用帶寬監(jiān)測模型[J]．軟件學(xué)報(bào)，2004，15(4)：545-549.