基于混合優化算法的網絡流量有效測量點選擇
2009-01-01 00:00:00葛洪偉彭震宇岳海兵
計算機應用研究 2009年4期
（江南大學 信息工程學院， 江蘇 無錫 214122）
摘 要：提出一種基于禁忌搜索和蟻群算法的求解最小弱頂點覆蓋問題的混合優化算法，用于解決網絡流量有效測量點的選擇問題。仿真結果表明，比較現有算法，本算法能夠找到更小的弱頂點覆蓋集，且具有更好的可擴展性和實用性。
關鍵詞：蟻群優化算法；禁忌搜索算法；最小弱頂點覆蓋
中圖分類號：TP301.6文獻標志碼：A
文章編號：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重要性的日益提高和網絡結構的日益復雜，網絡管理越來越成為人們關注的焦點。現代的網絡管理系統注重于服務級、應用級的管理，如主動式和被動式的資源管理、流量工程、端到端的服務質量保證等。所有這些網管業務均以了解網絡流量等網絡運行參數為基礎。為此，有必要對網絡流量進行測量和分析，以利于發現網絡瓶頸，優化網絡配置，并進一步發現網絡中可能存在的潛在危險。
由于Internet是一個不斷變化的龐大網絡，網絡流量的測量要具有一定的實時性。目前，網絡流量的測量方法要求針對特定的感興趣的鏈路，人工合理地規劃網絡的觀測節點，并安裝特定的監測軟件或硬件。但這種方法難以擴展，不便于動態適應網絡的變化，且可能因為設置過多的觀測節點而增加網絡的額外負擔。
測量方法關鍵的步驟是既要準確獲取網絡流量參數，又要盡量減少數據收集對實際網絡數據傳輸造成的額外負荷。因此，觀測節點的選擇尤其重要。研究中一般將網絡流量有效測量點選擇問題轉換為求給定無向圖中的最小弱頂點覆蓋問題，由于這個問題已被證明是NP-hard問題，因此一般采用近似算法求解，如文獻［1］給出了一個求解弱頂點覆蓋問題的貪婪秩算法；文獻[2]又提出了一個弱化的貪心算法。但所有這些算法均需知道網絡拓撲的全局信息，因而可擴展性較差，而且問題規模較大時，算法求解質量不高，或根本求不出最優解。于是本文提出了一種求解最小弱頂點覆蓋問題的混合優化算法，即基于禁忌搜索的蟻群優化算法TSBACO（tabu search based ACO），對網絡流量有效測量點的選擇問題進行研究和實驗，取得了良好的成效。
1 網絡流量測量模型描述
在網絡中某一節點設置測量器(如SNMP agent)，可以得到與這一節點相連的所有鏈路上的流量。因此，為了得到網絡中所有鏈路的網絡流量，一般可以通過在某些交換節點(路由器)配置測量器實現。要考慮的問題是：在網絡哪些節點上設置測量器，才能使得在可以得到每一條鏈路流量的條件下，所需測量器數目最小。這一問題自然可以歸納為圖論中的最小頂點覆蓋問題。
為了方便問題模型的描述，參照文獻[2]給出以下定義：
定義1 給定無向圖G=(V，E)。其中：V是頂點集；E是邊集；S是V的子集，若根據與S中頂點相關聯的各條邊的流量，可確定E中任意邊的流量，則稱S是圖G關于流量的測量集。
有效測量問題的目標就是求給定圖G關于流量的最小測量集。雖然采用求解最小頂點覆蓋問題的算法可以求出一個測量集，但已證明，最小頂點覆蓋問題是一個NP-hard問題，尚無多項式時間的求解算法，且求出的測量集也未必是最小測量集。如果測量器是路由器或交換機等交換設備，那么圖還滿足以下兩條約束條件：
a)對圖G的頂點集V中的任意頂點v，其degree(v)≥2；
b)對圖G的頂點集V中的任意頂點v，滿足流守恒方程，即流進=流出。
盡管以下原因將會導致流守恒方程的失真，如：交換設備是數據的源或匯，而不僅僅是數據轉發器；多播導致輸出端口的數據復制；交換設備本身的數據包延遲或丟失。但是若干研究表明，流守恒方程所具有的相對誤差小于0.05%。因此，由以上兩條約束條件，求圖G關于流量的最小測量集問題可以轉換為求定義2中圖的弱頂點覆蓋問題。
定義2 假定無向圖G=(V，E)滿足對任意v∈V有degree(v)≥2，稱SV是圖G的弱頂點覆蓋集，當且僅當執行以下操作能使E中所有的邊都可被標記：
a)標記所有與S中頂點相關聯的邊；
b)若某個頂點v的degree(v)-1條相關聯的邊已被標記，則標記剩下的那條相關聯的邊；
c)重復第b)步，直到不能再標記新的邊為止。
圖G的弱頂點覆蓋S就是在流守恒約束條件下的圖G關于流量的測量集。首先與集合S中頂點相關聯的邊的流量可以通過測量手段來獲取；其次，如果vS，且v的degree(v)-1條邊的流量已獲得，那么根據流守恒方程可以計算出另外一條邊的流量。反復應用流守恒方程，可計算出圖G中所有邊的流量。網絡流量測量中的有效測量點選擇問題實際上就是求解無向圖G的最小弱頂點覆蓋問題。
2 最小頂點覆蓋問題
設簡單圖G=(V，E)是一無向圖。其中：V是圖中頂點集合；E是邊集合。下面給出頂點覆蓋的有關定義。如果圖G中的一個頂點和一條邊相互關聯，則稱其相互覆蓋；稱頂點集V的一個子集V′為頂點覆蓋，如果圖G的任意一條邊都至少有一個端點屬于V′；如果一個頂點覆蓋是圖G的其他任何頂點覆蓋的真子集，則稱該頂點覆蓋為圖G的極小頂點覆蓋；包含頂點數最少的頂點覆蓋就是圖G的最小頂點覆蓋，最小頂點覆蓋的頂點數稱為圖G的覆蓋數。例如，圖1中黑色頂點所組成的頂點集就是相應圖的最小頂點覆蓋。
由上述定義可知，最小頂點覆蓋(minimum vertex covering，MVC)問題是指，給定一個無向圖G=(V，E)，求頂點集V的一個最小子集S，使得e=(u，v)∈E，且u∈S或v∈S，即E中的任一邊至少有一個頂點屬于S，即S中的頂點覆蓋了邊集E。
由于最小頂點覆蓋問題是NP-hard問題，到目前為止還不存在多項式時間算法來求解。雖然一些學者已經證實對于特殊的圖，通過采用特殊的算法，可以在多項式時間內求得圖的最小頂點覆蓋，如互補圖、圓弧圖、立方圖等。但本文不是對一些特殊的圖求其多項式時間算法，而是要對一般的圖進行最小頂點覆蓋問題的求解。在已有的近似算法中，算法僅根據局部信息進行決策，因此在許多情況下，這類算法并不能確定最小頂點覆蓋問題。而對于傳統的精確算法如分支限界法、割平面法，對偶啟發方法等，盡管這些方法能求得最小頂點覆蓋的最優解，但其計算復雜度高、花費時間長，并不能應用到大規模問題中，所以必須使用啟發式算法來求解圖的最小頂點覆蓋問題，使得在較短時間內求出問題的較優解甚至最優解。由上述最小頂點覆蓋問題的定義可知，該問題是一個組合優化問題，也是一個子集類問題，所以非常適合采用蟻群優化(ant colony optimization，ACO)算法來求解。
3 基于禁忌搜索的蟻群優化算法
ACO算法作為一種新型元啟發式算法，最近被用來解決許多不同的組合優化問題，但ACO算法在搜索過程中容易出現停滯現象或陷入局部最優。而禁忌搜索是對局部鄰域搜索的一種擴展，是一種全局逐步尋優算法，采用的是一種確定性的局部極小突跳策略。禁忌搜索算法通過引入一個靈活的禁忌表和相應的禁忌準則來避免重復迂回搜索，并通過藐視準則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。禁忌策略最重要的思想是標記對應已搜索到的局部最優解的一些對象，并在進一步的迭代搜索中盡量避開這些對象（而不是絕對禁止循環）從而保證對不同的有效搜索途徑的探索。但在搜索算法中，可能會出現候選解全部被禁忌，或者存在一個優于到目前為止最好解的禁忌候選解，此時藐視準則就將使某些狀態解禁，以實現更高效的優化性能。藐視準則的設置就是要算法避免遺失優良狀態，激勵對優良狀態的局部搜索，進而實現全局優化。對于非禁忌候選狀態，算法無視它與當前狀態的優劣關系，僅考慮它們中間的最佳狀態，如此便可實現對局部極小的跳躍。正由于禁忌技術具有靈活的記憶功能和藐視準則，且在搜索過程中可以接受劣解，所以搜索時能夠跳出局部最優解，轉向搜索空間的其他區域，從而增強獲得更好的全局最優解的概率。
為防止ACO算法出現停滯現象或陷入局部最優，本文將ACO算法與禁忌搜索算法結合起來，提出了一種基于禁忌搜索的蟻群優化算法TSBACO。該算法可以在一定程度上有效解決擴大搜索空間和加快收斂速度之間的矛盾，從而使得TSBACO算法既能避免重復迂回搜索，跳出局部最優解，又能對不同搜索區域進行更有效探索，不僅提高了全局優化性能而且還提高了搜索效率。
4 基于TSBACO的最小弱頂點覆蓋問題求解
由于在網絡環境中，所有頂點的度deg(v)≥2，所以求解最小頂點覆蓋問題可以轉換為求解最小弱頂點覆蓋問題。
4.1 關聯矩陣
首先給出最小弱頂點覆蓋問題的關聯矩陣定義，無向圖G的關聯矩陣A=(aij)是指如下定義的n×m矩陣：
aij=1，如果頂點vi與邊ej相關聯
0，其他
圖2為某網絡拓撲圖。
對于圖2中的網絡拓撲圖，其關聯矩陣A為
e1e2e3 e4e5
v111000
v201110
v300011
v410101
由上面的網絡拓撲圖和其關聯矩陣可知，對于任何一個有n個頂點和m條邊的無向圖G=(V，E)，滿足對任意v∈V有degree(v)≥2，則整個圖G都可用一個n×m的二階矩陣來表示，矩陣由{0，1}組成。其中每一行表示一個頂點，每一列表示一條邊；圖中每個頂點對應行中的各個值表示該頂點的鄰邊情況，1表示頂點和邊存在關聯關系，0則表示不存在關聯關系。
4.2 求解最小弱頂點覆蓋問題的近似算法
以下給出一個求解最小弱頂點覆蓋問題的近似算法，并把求解得出的弱頂點覆蓋集作為蟻群初次循環的初始解，算法的思想為：
a)選取一個含有邊數最多的頂點vi；
b)刪除關聯矩陣中頂點vi對應的行及該行中值為1的元素所在列；然后在剩下的關聯矩陣中再次刪除所有行元素之和不超過1的其他行及這些行中值為1的元素所對應的列，直到不能再刪除新的行和列為止；
c)重復以上步驟，直到所有的邊都被包含到。
以圖2為例，對上述近似算法思想進行形象說明：
a)計算關聯矩陣A的每行元素之和mj=1aij，當i=1，2，3，4時，每行元素之和分別為2，3，2，3；可知當i=2或i=4時，對應行的元素之和最大，即對應頂點覆蓋的邊最多，所以在這里可以選取v2或v4，假定本文選取的是v2。
b)刪除關聯矩陣中v2對應的行及該行中值為1的邊，即刪除的是邊e2，e3和e4，最后得到剩下的關聯矩陣為
e1e5
v110
v301
v411
c)在這個關聯矩陣中再依次刪除所有行元素之和不超過1的其他行，如v1和v3行，以及這兩行中值為1的元素所對應的列，如e1和e5列，最后得到的剩余關聯矩陣A=0。于是得到該近似算法的最小弱頂點覆蓋集S={v2}，即只要測量一個節點即可得到各條鏈路的流量。
雖然在此圖例中S是最優解，但是隨著問題規模的擴大，通過此近似算法求解得出的最小弱頂點覆蓋集將是一個近似解，而不是一個較優解更不可能是一個最優解。所以為了求解最小弱頂點覆蓋問題的最優解，必須在此近似解的基礎上，繼續使用TSBACO算法對其進行全局尋優。
4.3 隨機比例狀態轉移規則
ACO算法在求解大多數問題時，主要是通過蟻群對邊的集合進行搜索，因此信息素和期望啟發信息都被設置在邊上。而最小弱頂點覆蓋問題的求解則是通過對頂點的集合進行的搜索，所以在本文提出的TSBACO算法中，信息素釋放在頂點上，而不是在邊上，同時還使用了期望啟發信息來引導螞蟻的搜索。在螞蟻k構造弱頂點覆蓋集的過程中，對頂點的選擇將按如下概率選擇式進行：
pki=ταiηβi/j∈Ckταjη β j(1)
其中：τi表示頂點vi的信息素軌跡強度；ηi表示頂點vi的期望啟發信息；Ck表示螞蟻k的候選頂點集；α為信息啟發式因子；β為期望啟發式因子，這兩個參數都是常量，其值的選取需要人為經驗的指定。
頂點的期望啟發信息是靜態的，其值在算法運行前已確定，即頂點的期望啟發信息值在蟻群的尋優過程中保持不變。雖然這種靜態定義方式不需要反復計算頂點的度，并提高了算法運算速度，但當圖中各頂點的度相差過大或過小時，就會失去對蟻群搜索的指導意義。所以這里，對頂點的期望啟發信息采用了動態定義的方式。由于頂點的期望啟發信息值是頂點的度，當與該頂點相連的頂點被選擇加入弱頂點覆蓋集時，該頂點的度要減1。頂點vi的期望啟發信息ηi表達式如下：
ηi=|vi|(2)
當頂點vi被螞蟻k選擇后，筆者將頂點vi加入螞蟻k的部分解集合S中，同時將頂點vi和與該頂點相連的所有邊都刪除；然后按照上述近似算法思想更新關聯矩陣，繼續刪除頂點和邊，直到沒有任何可以刪除的頂點和邊。重復以上步驟直到關聯矩陣A=0，即所有邊都已被部分解集合S中的頂點所覆蓋，那么這個集合S就是螞蟻k構造的弱頂點覆蓋集。
4.4 信息素更新規則
信息素更新規則有多種形式，本文提出的求解最小弱頂點覆蓋問題的TSBACO算法采用的是MMAS[3]的信息素更新規則，其主要特點在于：
a)在每次蟻群循環后，只有循環最優螞蟻可以進行信息素釋放；
b)各頂點的信息素軌跡強度被限制在[τmin，τmax]范圍內；
c)各頂點的信息素軌跡強度被初始化為τmax。
MMAS通過這種信息素軌跡強度范圍控制，可以防止個別頂點上的信息素軌跡強度過度增加或減少，從而可以有效避免算法出現早熟停滯現象。
下面針對求解最小弱頂點覆蓋問題，詳細給出TSBACO算法的信息素更新規則：
首先需要為網絡拓撲圖中的每個頂點vi設置一個信息素軌跡強度初始值τmax，而信息素軌跡強度的更新則是在蟻群完成一次循環之后。為了充分利用循環最優解，每次循環后只有循環最優螞蟻可以進行信息素釋放。為了模擬信息素揮發，圖中所有頂點的信息素軌跡強度都要乘以一個信息素揮發系數ρ；然后，循環最優螞蟻才會釋放信息素。所以頂點信息素的更新分為兩步進行：
a)頂點信息素的揮發
τi(t+1)=(1-ρ)τi(t)(3)
b)頂點信息素的增加
假定WVCc是某次循環中蟻群找到的包含頂點數最少的弱頂點覆蓋，即循環最優解；而WVCg則是從算法運行以來蟻群找到的包含頂點數最少的弱頂點覆蓋，即全局最優解。在蟻群完成每次循環后，循環最優螞蟻把一定量的信息素釋放在WVCc中的各個頂點上。通過循環最優螞蟻信息素的釋放，循環最優解WVCc中的頂點將得到大量的信息素增強。頂點信息素增量表達式如下：
Δτi=Q/（1+‖WVCc|-|WVCg‖）(4)
其中：Q為信息素增量系數，其值由經驗所定；|WVCc|和|WVCg|分別表示WVCc和WVCg中的頂點個數。
4.5 禁忌表的使用
禁忌搜索策略中禁忌表的使用就是要使算法盡量避免重復迂回搜索，這樣不僅能加強搜索的多樣性而且能使算法跳出局部最優解。在禁忌搜索框架下，多樣性的加強是通過一些移動的暫時禁止獲得的。針對最小弱頂點覆蓋集問題，筆者將螞蟻完成一次最小弱頂點覆蓋集的構造稱為一次移動。只要一次移動完成，那么在隨后的L次循環中，這次移動將被禁止，即在以下連續的L次循環中，具有相同結構的弱頂點覆蓋集將被視為禁忌對象。禁忌搜索策略的實現則是要通過禁忌表的使用，其禁忌對象的替換是采用先進先出的方式。螞蟻每完成一次移動，這次移動就被放入禁忌表，并將剛放入禁忌表的移動禁忌初始值記為L，這樣每經過一次循環，禁忌表中每個移動的禁忌值均減1，當移動的禁忌值變為0時，這個移動就要從禁忌表中刪除并被解禁。禁忌表長度是一個很重要的參數，它決定禁忌對象的任期，其大小直接影響整個算法的搜索進程和行為。所以在算法求解過程中，如果某些弱頂點覆蓋集的結構重復頻繁出現，那么就應該增加禁忌表的長度；如果禁忌表的長度已經影響到了算法的性能，那么就減少禁忌表的長度。
4.6 藐視準則
TSBACO中的藐視準則定義如下：當候選頂點集中沒有可選非禁忌點，或者存在某個特殊的禁忌點，它的選擇會比其他非禁忌點的選擇有更高效的優化性能，那么這個頂點就會在本次移動中被選擇，并放入所求最小弱頂點覆蓋集中。為了判斷頂點的禁忌狀態，在螞蟻構造新弱頂點覆蓋集時加入了一個頂點禁忌狀態核對函數f(vi)。如果頂點vi的返回值是1，那么這個頂點就被禁止，否則就是可選的。
4.7 TSBACO算法的偽代碼
初始化信息素軌跡
repeat
for每只螞蟻k
螞蟻k隨機選擇一個起始頂點vi∈V，并把起始頂點加入最小弱頂點覆蓋集WVCk
repeat
構造一個非禁忌候選頂點集Ck
按照式（1）的概率選擇函數pkj
從Ck中選擇下一個頂點vj∈Ck
把頂點vj加入最小弱頂點覆蓋集WVCk
until最小弱頂點覆蓋集WVCk被構造完成
end for
保存循環最優解WVCc
如果|WVCc|＜|WVCg|，那么|WVCg|=|WVCc|，即更新全局最優解WVCg
把禁忌初始值為的WVCc加入禁忌表
修改禁忌表中各對象的任期
刪除禁忌值為0的禁忌對象
按照更新規則進行信息素軌跡更新
until最優解被找到或已完成最大循環次數
返回全局最優解，即|WVCg|
4.8 算法正確性分析
定理1 若圖G=（V，E）是簡單連通無向圖，且滿足對任意v∈V有degree(v)≥2，則TSBACO算法所得的頂點集是圖G的一個弱頂點覆蓋集。
證明 TSBACO算法中每只螞蟻在每次循環中進行的搜索實際相當于如下：
a)令G′=G；
b)從圖G′中選擇狀態轉移概率最大的頂點，記錄該頂點，并且刪除該頂點和該頂點的所有鄰邊，記生成的圖為G″；
c）在圖G″中，對于所有度為1的頂點，刪除該頂點及該頂點的一條鄰邊，仍記生成的圖為G″；
d)重復c)，直到圖G″中所有頂點的度都大于1或者圖G″中沒有任何頂點；
e)令G′=G″，轉回b)，直到圖G′中沒有任何頂點。
由前面定義2可知，圖G也是其本身的弱頂點覆蓋集。
由上述的c)可知，當一個頂點只剩一條鄰邊時，該條邊也將被刪除，這與定義2中的b)相符，當且僅當該頂點的所有鄰邊均被刪除后，該頂點才被刪除，即該頂點的所有鄰邊都已被記錄的所有頂點覆蓋。
因此所有已經記錄了的頂點和圖G′中的剩余頂點構成了圖G的一個弱頂點覆蓋集。由于每次蟻群循環結束時，圖G′中沒有任何頂點，因此每次循環結束時，每只螞蟻記錄的頂點集合便構成了圖G的一個弱頂點覆蓋集。算法最終是從每次循環每只螞蟻產生的頂點記錄列表中選取頂點個數最少的頂點記錄集，因此該頂點記錄集也是圖G的一個弱頂點覆蓋集。
證明完畢。
5 仿真實驗
為驗證TSBACO算法在實際網絡流量有效測量點選擇中的優越性能，本文參考文獻［1］進行了仿真實驗，并比較了幾種有效測量點選擇算法。實驗中所用到的網絡拓撲圖是通過Waxman網絡模型生成的，Waxman網絡模型是網絡研究中一種比較流行的拓撲生成模型。在Waxman模型中，n個網絡節點隨機分布在笛卡爾空間，考慮節點間所有可能的連接，網絡鏈路以一定概率方式加入網絡拓撲圖中。節點i和j之間的邊按概率p(i， j)生成，其概率表達式如下：
p(i， j)=λe-d/(γL)(5)
其中：參數λ＞0，用于控制拓撲圖中邊的密度；γ≤1，用于控制拓撲圖中節點的平均度數；e為自然指數；d為節點i和j之間的距離；L為各個節點間的最長距離。
由此可見，通過設置Waxman模型的三個參數n、λ、γ，即可得到各種不同的網絡拓撲結構圖。下面設置四組參數，生成四種不同的網絡拓撲結構圖，其參數設置如表1所示。
表1 Waxman模型參數設置
nλγ
15000.40.02
25000.40.04
35000.40.06
45000.40.08
基于以上參數設置生成的四種網絡拓撲結構圖，比較了六種算法，分別是：文獻［1］中提到的三種算法，即生成簡單頂點覆蓋的最大匹配啟發算法(VC)、生成弱頂點覆蓋的最大匹配啟發算法(WVC)、生成弱頂點覆蓋的貪婪秩算法(greedy rank，GR)；文獻[4]中提出的SMN算法；標準ACO算法以及本文提出的TSBACO算法。
TSBACO算法的參數設置如下：螞蟻數量a=30，信息素揮發系數ρ=0.02，信息啟發因子α=2，期望啟發因子β=1，信息素上界τmax=10，信息素下界τmin=0.1，信息素增量系數Q=0.5，最大循環次數c=500，禁忌長度L=10。
六種網絡流量測量點選擇算法的比較如表2所示。
表2 六種網絡流量測量點選擇算法的比較
avg degreeNvcmatchNWVCmatchNWVCrank
NWVCsumNWVCacoNWVCtsbaco
4.4387255165129124121
8.6441372254221216213
12.6453408307296292287
16.9466431334327322318
表2中的第一列為網絡拓撲圖中節點的平均度數，它隨著γ參數值的增大而增大；Nvcmatch，NWVCmatch，NWVCrank，NWVCsun，NWVCaco和NWVCtsbaco表示由上述六種算法得到的測量點個數。由表中的實驗結果可以看出，TSBACO算法在四種網絡拓撲圖中選取的節點個數比前五種算法都少，即TSBACO算法可以生成更小的弱頂點覆蓋集，而VC、WVC、GR、SMN這些近似算法往往求得的是次優解而不是較優解和最優解。再看NWVCaco和NWVCtsbaco列，由于TSBACO算法中禁忌表的使用，使得算法既能避免重復迂回搜索，跳出局部最優解，又能對不同搜索區域進行更有效地探索；相比ACO算法易陷入局部最優和早熟收斂的缺點，TSBACO算法能以更大的概率收斂到全局最優解，求解出節點數更少的弱頂點覆蓋集。
6 結束語
本文提出了一種求解網絡流量有效測量點選擇問題的混合優化算法——基于禁忌搜索的蟻群優化算法TSBACO。該算法利用ACO算法的正反饋機制加快了收斂速度，利用TS算法的全局搜索能力避開了局部最優。仿真實驗結果表明，TSBACO算法是求解網絡流量測量中的一種有效的測量點選擇算法，該算法求解質量較高，而且擁有較好的可擴展性和實用性。在TSBACO算法中，禁忌表長度L是一個很重要的參數，其大小直接影響真個算法的性能，如何選擇L使之能更好的求解最小弱頂點覆蓋問題，則是今后的研究重點之一。
參考文獻：
［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]劉湘輝，殷建平，唐樂樂，等.網絡流量的有效測量方法分析[J]．軟件學報，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]蔣紅艷，林亞平，黃生葉.網絡流量有效監測點的設置模型及求解算法研究[J].電子與信息學報， 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，FAN 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]劉湘輝，殷建平，唐樂樂，等.基于弱頂點覆蓋的網絡鏈路使用帶寬監測模型[J]．軟件學報，2004，15(4)：545-549.
