基于均勻免疫優(yōu)化算法的最大團問題求解*

汪宏海，張正球

(1.西安電子科技大學(xué)計算機學(xué)院,陜西 西安 710071；2.贛州師范高等?？茖W(xué)校計算機系,江西 贛州 341000；

3.福建師范大學(xué)軟件學(xué)院,福建 福州 350027)

基于均勻免疫優(yōu)化算法的最大團問題求解*

汪宏海1,2，張正球3

(1.西安電子科技大學(xué)計算機學(xué)院,陜西 西安 710071；2.贛州師范高等?？茖W(xué)校計算機系,江西 贛州 341000；

3.福建師范大學(xué)軟件學(xué)院,福建 福州 350027)

最大團問題是一種典型的組合優(yōu)化問題，具有廣泛的應(yīng)用背景。針對最大團問題的NP特性，提出了一種基于免疫克隆優(yōu)化的智能求解算法。描述了最大團問題的數(shù)學(xué)模型，設(shè)計了求解最大團問題的抗體編碼、親和度函數(shù)、變異算子及抗體修正方法。在免疫克隆參數(shù)設(shè)置時，將其描述為多因素多水平的均勻設(shè)計，減少了設(shè)置參數(shù)的實驗次數(shù)。通過最大團問題的基準算例進行了實驗。結(jié)果表明，本算法求解效果較好，并且求解速度較快。

免疫優(yōu)化；最大團問題；抗體編碼；均勻設(shè)計

1 引言

最大團問題MCP(Maximum Clique Problem)是圖論中的一個經(jīng)典組合優(yōu)化問題，也稱為最大獨立集問題[1]。MCP在市場分析、方案選擇、計算機視覺、故障診斷等領(lǐng)域具有非常廣泛的應(yīng)用。因此，研究最大團問題具有較高的理論價值和現(xiàn)實意義。

最大團問題是一類典型的NP完全問題。目前，求解MCP問題的算法主要分為兩類：確定性算法和啟發(fā)式智能算法[2,3]。常見的確定性算法有分支限界算法和回溯算法等[4～7]，確定性算法要求在有效的時間內(nèi)給出最大團問題的最優(yōu)解，而非確定性的算法并不保證最終給出的是最優(yōu)解。由于最大團問題是 NP完全問題，當無向圖規(guī)模較大時，尋找最大團的時間復(fù)雜度較高[8～11]。已有的研究表明，非確定性算法中的智能優(yōu)化算法是求解NP完全問題的有效算法。

人工免疫系統(tǒng)是受生物免疫系統(tǒng)機制啟發(fā)的一種智能計算系統(tǒng)，克隆優(yōu)化算法是人工免疫系統(tǒng)的主要算法之一，已經(jīng)在優(yōu)化、智能控制、數(shù)據(jù)處理等多個領(lǐng)域得到廣泛應(yīng)用[12,13]。基于此，本文采用免疫克隆算法求解最大團問題，并在免疫參數(shù)設(shè)置時，描述為均勻設(shè)計問題(本文稱為均勻免疫優(yōu)化算法)。實驗結(jié)果表明，算法求解效果較好。

2 問題描述

2.1 最大團問題描述

最大團是圖論中的一個經(jīng)典問題，可描述為:從圖G中找到一個頂點最多的完全子圖(完全子圖即是指圖中的任意兩點都有邊相連)。

設(shè)無向圖G=(V,E),G的頂點集合V=(V1,V2,…,Vn), 其中，n=|V|為V所含的頂點個數(shù)，E=(Vi,Vj)為G的邊集合。設(shè)頂點子集合S?V,G(S)為由S導(dǎo)出的G的生成子圖。若G(S)的頂點兩兩相連，則稱G(S)為G的團。在G的所有團中, 包含頂點最多的團是G的最大團。最大團問題的目標就是尋找給定圖的最大團。

2.2 最大團問題的數(shù)學(xué)模型

最大團問題可以用一個0-1分配模型來描述[3,11]：

s.t.xi+xj≤1,?(Vi,Vj)∈E;

xi∈(0,1),i=0,1,2,…,n

3 算法關(guān)鍵實現(xiàn)技術(shù)

免疫優(yōu)化是人工免疫系統(tǒng)的主要算法之一，是一種得到廣泛應(yīng)用的智能優(yōu)化算法。使用免疫克隆算法求解問題時，抗體代表問題的解，算法通過相關(guān)的免疫克隆、變異算子對抗體進行演化，最終找到問題的最優(yōu)解。

免疫克隆算法基本過程簡述如下：

(1)將求解問題轉(zhuǎn)化為抗體編碼表示。

(2)抗體種群的初始化，即生成一定數(shù)量滿足問題的解。

(3)計算抗體種群中各個抗體的親和度。

(4)對親和度高的抗體進行克隆操作。

(5)對克隆生成的抗體進行相應(yīng)的變異操作。

(6)若當前解滿足要求，則算法結(jié)束，輸出最終結(jié)果；否則，轉(zhuǎn)步驟(3)繼續(xù)。

基于免疫的最大團問題實現(xiàn)中，幾個關(guān)鍵技術(shù)說明如下。

3.1 抗體編碼技術(shù)

最大團問題中，圖G用鄰接矩陣A表示，如果i、j之間有邊，則鄰接矩陣中的對應(yīng)元素為1，否則為0?？贵wx=[x1,x2,…,xi,…,xn]表示圖G中的一個可能的最大團，用0、l組成的行向量表示，其列數(shù)與A相等。x中的元素等于l，表示圖G的相應(yīng)點屬于這個可能的最大團。例如：x=[010101010]，表示圖頂點集V= {1,2,3,4,5,6,7,8,9}的一個子團S= {2,4,6,8}。

3.2 親和度函數(shù)

3.3 自適應(yīng)克隆

克隆操作是免疫優(yōu)化的主要操作之一，影響著算法的收斂速度和性能。這里采用一種按親和度的大小進行自適應(yīng)克隆的機制，保證具有較高親和度的優(yōu)秀抗體進化到下一代的機率加大。具體說明如下：

假設(shè)選出的s個抗體按親和度值升序排序為：M1(g),M2(g),…,Ms(g)，則對第i個抗體Mi(g)(1≤i≤s)的qi克隆產(chǎn)生的抗體數(shù)目為：

第g代克隆產(chǎn)生的抗體種群總個數(shù)為：

其中，Int(*)表示向上取整，nt(nt>s)表示克隆控制參數(shù)，f(*)代表親和度函數(shù)的計算。

3.4 變異算子

3.5 抗體修正

由于抗體變異后可能產(chǎn)生非法解,因此需要進行抗體修正操作，使其合法化?；谶B接矩陣，對抗體進行遍歷，找出對應(yīng)子圖的連接矩陣，刪除度最小的節(jié)點(即基因位1變0)，使其成為合法抗體。具體如下：逐一檢查x中的元素，如果xi等于1，逐一檢查xi之后等于1的元素是否與xi存在邊，如果不存在邊，該元素由l改為0。

3.6 均勻設(shè)計

均勻設(shè)計是一種解決多因素、多水平實驗問題的有效方法，以通過最少的實驗來獲得最多的信息，實驗次數(shù)比正交設(shè)計法明顯減少[14]。

一般地，如果有N個因素，且每個因素有Q個水平，則共有QN種組合。當N和Q比較大時，則取全部的組合進行實驗是不可能的。因此，需要選擇數(shù)量較少、具有代表性的因素水平組合做樣本。均勻設(shè)計方法正是這樣的一種策略，可以有效減少實驗的次數(shù)[14]。由于免疫優(yōu)化算法的參數(shù)設(shè)置需要通過實驗調(diào)整，為了減少實驗次數(shù)，本文采用均勻設(shè)計完成參數(shù)的取值，具體過程見實驗部分。

3.7 算法實現(xiàn)步驟

本文設(shè)計的免疫克隆優(yōu)化算法實現(xiàn)步驟如下：

步驟1 根據(jù)編碼方式初始化種群，設(shè)進化代數(shù)為g，令g=0。

步驟2 計算所有個體的親和度,親和度函數(shù)為子團中頂點數(shù)目,函數(shù)值越大，抗體越好。

步驟3 以進化代數(shù)g作為終止條件，判斷是否滿足結(jié)束條件。如果滿足結(jié)束條件,則終止程序，輸出最優(yōu)解；否則,轉(zhuǎn)步驟4。

步驟4 根據(jù)各個抗體的親和度值，進行克隆擴增操作?？寺〔捎米赃m應(yīng)克隆(2.3節(jié)所示)，即親和度高的抗體克隆數(shù)目較多。

步驟5 對克隆種群進行2.4節(jié)所示的變異操作。

步驟6 對抗體進行2.5節(jié)所示的修正操作。

步驟7g=g+1,轉(zhuǎn)步驟2。

4 仿真實驗與結(jié)果分析

4.1 免疫克隆算法的參數(shù)設(shè)置

免疫克隆算法的參數(shù)設(shè)置通常是依靠經(jīng)驗和實驗來確定的,因此實驗工作量大且難以得到最優(yōu)的參數(shù)組合[15]。本文將免疫算法的參數(shù)設(shè)定問題描述成均勻設(shè)計中多因素、多水平的實驗設(shè)計,從而能夠用較少的實驗設(shè)定參數(shù)的取值。均勻設(shè)計中的最大因素數(shù)即為免疫克隆算法的參數(shù)個數(shù)，水平數(shù)即為每個參數(shù)的取值范圍。本文中，克隆選擇算法的參數(shù)主要有變異概率pm、克隆比例系數(shù)k和種群規(guī)模M。

基本克隆選擇算法的三個參數(shù)(s=3),若每個參數(shù)取10個值(t=10)。使用均勻設(shè)計設(shè)置算法參數(shù)的步驟簡述如下:

(1)對s=3個參數(shù)分別確定取值范圍；

(2)對每個參數(shù)取t=10個水平,根據(jù)均勻設(shè)計的推薦表,得到Ut(ts)；

(3)根據(jù)均勻表編制實驗方案,找出對應(yīng)的參數(shù)組合,對每組進行多次實驗,統(tǒng)計其數(shù)據(jù),找出最優(yōu)的組合。

本文中，設(shè)置種群規(guī)模、變異概率、克隆系數(shù)的范圍分別為[30,80]、 [0.35,0.85]、[2,4], 經(jīng)過均勻設(shè)計實驗，最終參數(shù)取值如下：種群M=60，pm=0.3，克隆系數(shù)k=2，最大進化次數(shù)200次。

4.2 算法實驗結(jié)果

采用Matlab7.0對DIMACS[16]提供的標準算例進行實驗。為避免算法的隨機性，對每個算例在同一臺機器上進行連續(xù)100次計算，其中，sbest表示100次運行中求得的最好解；savg表示100次運行所得解的平均值；σ為標準差；tavg為100次運行中找到最好解的平均用時(秒)；gavg為收斂代數(shù)的平均值；s為100次運行中找到最好解的次數(shù)。結(jié)果如表1所示。實驗結(jié)果采用文獻[2]與文獻[5]作為對比算法，二者均是采用啟發(fā)式智能算法的經(jīng)典文獻，與本文算法有可比較性。

從表1可看出，本文算法對每個算例都能夠100%搜索到最好解，而文獻算法只有部分最好解，而且本文算法在很多衡量指標上，如解的平均值、標準差、找到解的時間、成功次數(shù)上均好于文獻算法。

具體而言，在數(shù)據(jù)規(guī)模較小時，各種算法找到的最優(yōu)解sbest相同，但當規(guī)模較大時，本算法具有一定的優(yōu)勢。此外，本文算法找的savg值優(yōu)于相關(guān)算法，100次運算中找到最好解的次數(shù)較多； 100次運行中找到最好解的平均用時相對較短；gavg收斂代數(shù)平均值較小。實驗結(jié)果說明本文算法取得了較好的求解效果。

Table 1 Experiment results of MCP

4.3 算法復(fù)雜度分析

最大團中頂點個數(shù)為n=|V|，免疫優(yōu)化算法中，抗體的種群規(guī)模為M，則基于免疫的最大團問題求解中，算法的最好時間復(fù)雜度為O(n*M)(當圖為低度圖時)；最壞情況下，算法的時間復(fù)雜度為O(M*n3)，是可以接受的。

5 結(jié)束語

最大團問題是一類經(jīng)典的組合優(yōu)化問題，有著廣泛的工程應(yīng)用基礎(chǔ)?；谧畲髨F問題的NP特性，本文采用免疫克隆優(yōu)化算法進行求解。同時，為了減少實驗設(shè)置次數(shù)，采用了均勻設(shè)計方法。通過標準實驗進行驗證，結(jié)果表明，算法求解效果較好，具有一定的優(yōu)勢。

[1] Fan Yue-ke,Qiang Xiao-li,Xu Jin. Sticker model for maximum clique problem and maximum independent set[J]. Chinese Journal of Computers,2010,33(2)：855-864.(in Chinese)

[2] Zhang Yan,Dang Qun,Huang Yong-xuan. A Memetic algorithm based on match-crossover for the maximum clique problem[J].Control and Decision,2010,25(9):213-219.(in Chinese)

[3] Zhou Yan-tao, Li Ken-li, Luo Xing.An algorithm for solving maximum clique problem based on self-assembly model of DNA[J].Journal of Hunan University(Naturnal Science), 2012,44(9):9-25.(in Chinese)

[4] Pan Quan,Guo Ming,Lin Peng.Largest group based on MapReduce algorithm [J]. Systems Engineering Theory and Practice, 2011,23(10):10-15.(in Chinese)

[5] Singh A,Gupta A K. A hybrid heuristic for the maximum clique problem [J].Journal of Heuristics,2006,12(6):5-22.

[6] Zhou Kang,Liu Shuo,Qin Lei, et al.Sticker model-based DNA algorithm of maximum clique problem[J].Journal of Huazhong University of Science and Technology(Nature Science), 2010,21(9):9-15.(in Chinese)

[7] Li Ken-li,Zhou Xu,Zou Shu-ting. Improved volume molecular solutions for the maximum clique problem on DNA-based supercomputing[J].Chinese Journal of Computers, 2008,41(12):12-15.(in Chinese)

[8] Pullan W,Hoos H H.Dynamic local search for the maximum clique problem[J]. Journal of Artificial Intelligence Research, 2006 (25):159-185.

[9] Lü Qiang,Bai Zhan-hua, Xia Xiao-yan.Leader-based parallel cross entropy algorithm for maximum clique problem[J].Journal of Software, 2008,34(11):11-15.(in Chinese)

[10] Katayama K,Hamamoto A, Narihisa H. An effective local search for the maximum clique problem[J].Information Processing Letters, 2005, 95(5):503-511.

[11] Pullan W.Approximating the maximum vertexedge weighted clique using local search[J]. Journal of Heuristics, 2008,14(2):117-134.

[12] Gong M G,Jiao L C,Zhang L N, et al. Immune secondary response and clonal selection inspired optimizers[J].Progress in Natural Science,2009,19(2):237-253.

[13] Gong Mao-guo,Jiao Li-cheng,Liu Fang,et al. Memetic computation based on regulation between neural and immune systems:The framework and a case study[J].Science China (Information Science),2010,45(11):2131-2138.

[14] Fang Kai-tai, Ma Chang-xing. Orthogonal and uniform design[M]. Beijing:Science Press, 2009.(in Chinese)

[15] Yu Hang,Jiao Li-cheng,Gong Mao-guo,et al.Clonal selection function optimization based on orthogonal experiment design[J].Journal of Software, 2010, 21(5):950-967.(in Chinese)

[16] DIMACS[EB/OL].[2012-12-13].ftp://dimacs.rutgers.edu/pub/challeng/.

附中文參考文獻:

[1] 范月科,強小利,許進.圖的最大團與最大獨立集粘貼DNA計算模型[J].計算機學(xué)報，2010，33(2)：855-864.

[2] 張雁, 黨群, 黃永宣.一種基于匹配交叉求解最大團問題的Memetic算法[J].控制與決策,2010,25(9):213-219.

[3] 周炎濤,李肯立,羅興.一種基于DNA自組裝模型求解最大團問題的算法[J].湖南大學(xué)學(xué)報(自然科學(xué)版),2012,44(9):9-25.

[4] 潘全,郭鳴,林鵬.基于MapReduce的最大團算法[J].系統(tǒng)工程理論與實踐,2011,23(10):10-15.

[6] 周康,劉朔,覃磊,等.基于粘貼模型的最大團問題算法[J].華中科技大學(xué)學(xué)報(自然科學(xué)版),2010,21(9):09-15.

[7] 李肯立,周旭,鄒舒婷.一種改進的最大團問題DNA計算機算法[J].計算機學(xué)報, 2008,41(12):12-15.

[9] 呂強,柏戰(zhàn)華,夏曉燕.一種求解最大團問題的并行交叉熵算法[J].軟件學(xué)報, 2008,34(11)：11-15.

[14] 方開泰,馬長興.正交與均勻試驗設(shè)計[M].北京:科學(xué)出版社,2009.

[15] 余航,焦李成,公茂果,等.基于正交試驗設(shè)計的克隆選擇函數(shù)優(yōu)化[J].軟件學(xué)報,2010, 21(5):950-967.

WANG Hong-hai,born in 1977,PhD,associate professor，his research interests include wireless network, and optimization algorithm.

張正球(1978-),男，江西臨川人，碩士生，講師，研究方向為計算智能、網(wǎng)絡(luò)安全和優(yōu)化算法。E-mail:zzqiu_2008@163.com

ZHANG Zheng-qiu,born in 1978,MS candidate,lecturer，his research interests include computational intelligence,network security, and optimization algorithm.

A uniform immune clone based intelligent optimization algorithm to solve the maximum clique problem

WANG Hong-hai1，2，ZHANG Zheng-qiu3

(1.School of Computer,Xidian University,Xi’an 710071;2.Department of Computers Science,Ganzhou Teachers Colleage,Ganzhou 341000;3.Faculty of Software,Fujian Normal University,Fuzhou 350027,China)

The maximum clique problem is a typical combinatorial optimization problem,which has wide application background.For the NP characteristic of the maximum clique problem, an immune clone based on intelligent optimization algorithm is proposed to solve it. The mathematical model of the maximum clique problem is described.For solving the maximum clique problem,antibody encoding, affinity function, mutation operator and antibody correction method are designed. To reduce the number of parameter setting for the experiment, it is converted into a uniform design problem of multi-factor and multi-level.The Benchmark experimental results show that the algorithm has better performance and rapid solving speed.

immune optimization;maximum clique problem;antibody encoding;uniform design

1007-130X(2015)03-0534-05

2013-11-01;

2014-02-24基金項目：福建省教育廳JK類科技資助項目(JK2010010)；福建省自然科學(xué)基金資助項目(2011J01339)

TP18

A

10.3969/j.issn.1007-130X.2015.03.021

汪宏海(1977-),男，江西樟樹人，博士，副教授，研究方向為無線網(wǎng)絡(luò)和優(yōu)化算法。E-mail:redsea54@163.com

通信地址：341000 江西省贛州市經(jīng)濟技術(shù)開發(fā)區(qū)高校園區(qū)35號

Address:No 35,Economic and Technological Development Zone,Ganzhou 341000,Jiangxi,P.R.China