最大團問題研究進展及算法測試標準

摘要：定義了最大團問題，分析和研究了使用啟發式算法求解最大團問題的進展，介紹了當前求解最大團問題的典型啟發式算法，最后給出了測試這些啟發式算法性能的測試基準圖。

關鍵詞：最大團問題； 啟發式算法； 組合優化

中圖分類號：TP301文獻標志碼：A

文章編號：1001－3695(2007)07－0069－02

最大團問題是圖論中的一個經典組合優化問題，也是一類NP完全問題，對最大團問題的研究具有很大的理論價值。最大團問題也被稱為最大獨立集問題，在實踐中有非常廣泛的應用，被應用于市場分析、方案選擇、信號傳輸、計算機視覺、故障診斷等不同領域。最大團問題在國外有相對廣泛的研究，在國內的研究則剛剛起步。圖分為有權圖和無權圖，本文主要討論針對無權圖的最大團問題。

1最大團問題定義

1．1最大團問題的基本定義

對于給定圖G=(V，E)。其中，V={1，…，n}是圖G的頂點集，EV×V是圖G的邊集。圖G的團就是一個兩兩之間有邊的頂點集合。如果一個團不被其他任一團所包含，即它不是其他任一團的真子集，則稱該團為圖G的極大團。頂點最多的極大團，稱之為圖G的最大團。最大團問題的目標就是要找到給定圖的最大團。

最大團問題也被稱為最大獨立集問題，獨立集指的是兩兩頂點之間沒有邊的頂點集合。頂點最多的獨立集就是最大獨立集。如果C是圖G的最大團，其實C也是G的最大獨立集。

1．2最大團問題的數學描述

最大團問題作為一個整數規劃問題有許多等價的描述。整數規劃問題的描述（二次0－1問題）[1]：

2最大團問題研究進展

1957年，Hararv和Ross首次提出求解最大團問題的確定性算法（Exact Algorithm）[1]，隨后研究者們提出各種各樣的確定性算法來求解最大團問題。隨著研究的深入，遇到的問題復雜度越來越高（頂點增多和邊密度變大），確定性算法逐漸不能有效解決這些問題。

由于最大團問題是一類NP完全問題，確定性算法不能夠有效解決這類問題，典型地體現在求解問題時運算時間過長，且不能夠很好地克服這一問題。目前確定性算法主要用于求解頂點數相對較少、密度相對較低的圖的最大團。

針對上面的情況，在20世紀80年代末開始采用啟發式算法求解最大團問題，提出了各種各樣的啟發式算法，并且取得了令人滿意的效果。在時間上，由于采用了啟發式信息，啟發式算法的運算時間與確定性算法的運算時間之間的比值會隨著圖的頂點、密度的增加而變得越來越小。唯一的缺點就是不一定能找到最優值，有時只能找到近優值。

啟發式算法的出現給求解頂點多、密度高的圖的最大團問題帶來了希望，并且經過這十幾年的發展，取得了長足進步。大部分確定性算法所不能解決的圖，用啟發式算法都能得到有效解決。人們對啟發式算法關注程度越來越高。

當前求解最大團問題的啟發式算法都基于以下幾類：局部搜索啟發式算法(Local Search Heuristics)、遺傳算法、神經網絡、模擬退火和禁忌搜索、基于連續的啟發式算法等。在局部搜索啟發式算法中，比較著名的算法是K－interchange啟發式算法，該算法基于K－neighbor實現。遺傳算法在1993年被Carter和Park第一次引進來求解最大團問題[2]。神經網絡在1987年被Ballard等人引進來解決最大團問題[3]。1989年，Aarts和Korst把模擬退火引進來求解最大團問題[4]。禁忌搜索在1989年由Friden等人[5]被用來求解該問題。1990年由Pardalos等人[6]提出一種基于連續的啟發式算法來求解最大團問題。

研究表明，單獨使用一種啟發式算法求解最大團問題，算法性能并不是很好，因此，需要算法之間互相取長補短，形成新的混合算法來求解最大團問題。當前求解該問題最好的啟發式算法有反作用禁忌搜索算法（Reactive Tabu Search）、簡單啟發式算法(Simple Heuristic Based Genetic Algorithm，HGA)和DLS－MC等。

1998年，Marchiori[7]給出了一種基于遺傳算法的簡單啟發式算法(HGA)。該算法由兩部分組成，即簡單遺傳算法（Simple Genetic Algorithm，SGA）和簡單的貪婪啟發式局部搜索算法。Marchiori 在基準圖上對算法HGA的性能進行測試，證明了該算法在解的質量和計算速度上均優于基于遺傳算法的其他算法。

Battiti和Protasi[8]提出的反作用禁忌搜索算法，通過引入局部搜索法（Reactive Local Search）擴展了禁忌搜索的框架。與一般的禁忌搜索算法相比，該算法的特點是，在執行過程中，根據所得到的解的情況形成一種內部反饋來控制和調整算法的控制參數。所以該算法的控制參數是動態變化的。比如，禁止表長度參數動態變化，使禁忌表長度動態變化。在DIMACS基準圖上進行測試，取得了非常好的效果。

Wayne Pullan等人[9]最近提出解最大團問題的方法DLS－MC。該算法基于迭代改善法和Plateau Search 算法。在該方法中引入了頂點懲罰函數（Vertex Penalties），該函數在算法的求解過程中能夠動態改變。在算法執行過程中，迭代改善法和Plateau Search 算法輪流執行以提高解的質量。在基準圖上對該算法進行了測試，性能非常好。

3啟發式算法測試標準——DIMACS基準圖

DIMACS組織是由美國政府成立的離散數學及理論計算機科學中心。該中心是當前離散數學和理論計算機科學的重要研究陣地之一。

DIMACS基準圖是DIMACS提供的圖，在1993年以前由于對最大團算法性能測試沒有統一的標準，算法之間無法進行有效比較。因此，DIMACS在1993年集中當時比較有代表性的圖形成基準圖，目的是提供統一的最大團算法測試標準圖[10]。DIMACS組織統計了當時各種啟發式算法在DIMACS基準圖測試所取得結果，并且由其中最好的解組成DIMACS Best，作為比較對象（表1）。DIMACS 基準圖可通過登錄ftp://dimacs.rutgers.edu/pub/challeng/或者http://dimacs.rutgers.edu/challenges/獲得。

表1DIMACS基準圖及DIMACS Best

4結束語

最大團問題是現實世界中的一類真實問題。

傳統的確定性算法不能有效地進行求解，因此使用了各種各樣的啟發式算法。目前國內通過啟發式算法求解最大團問題的研究還處于初期階段。

大量研究表明，使用啟發式算法求解最大團問題，將多種算法結合使用所呈現的性能要優于單純使用一種算法時的性能。目前，測試求解最大團問題的啟發式算法性能標準是由DIMACS組織所提供的DIMACS基準圖，其并不是最合理的算法性能比較的依據，需要提出更為合適的測試標準。

參考文獻：

[1]ADLEMAN L M. Molecular computation of solutions to combinatorial problems[J]. Science， 1994，226(11):1021－1024.

[2]CARTER B， PARK K. How good are genetic algorithms at finding large cliques: an experimental study， Technical Report Bu－CS－93－015[R]. Boston: Computer Science Dept.， Boston University， 1993.

[3]BALLARD D H， GARDNER P C， SRINIVAS M A. Graph problems and connectionist architectures， Technical Report TR 167[R]. New York: Dept Computer Science， University of Rochester， 1987.

[4]AARTS E， KORST J. Simulated annealing and boltzmann machines， a stochastic approach to combinational optimization and neural computing[M]. New York: Wiley， 1989.

[5]FRIDEN C， HERTZ A， DeWERRA D. Stabulus: a technique for finding stable sets in large graphs with tabu search[J]. Computing， 1989，42(1):35－44.

[6]PARDALOS P M， PHILLIPS A T. A global optimization approach for solving the maximum clique problem[J]. International Journal of Computer Mathematics， 1990，33:209－216.

[7]MARCHIORI E. A simple heuristic based genetic algorithm for the maximum clique problem: proc.of the ACM Symposium on Applied Computing[C].New York: ACM Press， 1998:366－373.

[8]BATTITI R， PROSTASI M. Reactive local search for the maximum clique problem[J]. Algorithmica， 2001，29(4):610－637.

[9]PULLAN W， HOOSH H. Dynamic local search for the maximum clique problem[J]. Journal of Artificial Intelligence Research， 2006，25:159－185.

[10]JOHNSON D， TRICK M. Cliques， coloring and satisfiability: second DIMACS implementation challenge[J].DIMACS Series in Discrete Mathematics and Theoretical Computer Science， 1996，26:533－558.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”