汪宏海，張正球

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

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

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

汪宏海1,2，張正球3

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

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

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

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

1 引言

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

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

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

2 問題描述

2.1 最大團(tuán)問題描述

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

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

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

最大團(tuán)問題可以用一個(gè)0-1分配模型來描述[3,11]：

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

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

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

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

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

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

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

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

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

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

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

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

3.1 抗體編碼技術(shù)

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

3.2 親和度函數(shù)

3.3 自適應(yīng)克隆

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

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

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

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

3.4 變異算子

3.5 抗體修正

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

3.6 均勻設(shè)計(jì)

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

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

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

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

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

步驟2 計(jì)算所有個(gè)體的親和度,親和度函數(shù)為子團(tuán)中頂點(diǎn)數(shù)目,函數(shù)值越大，抗體越好。

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

步驟4 根據(jù)各個(gè)抗體的親和度值，進(jìn)行克隆擴(kuò)增操作。克隆采用自適應(yīng)克隆(2.3節(jié)所示)，即親和度高的抗體克隆數(shù)目較多。

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

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

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

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

4.2 算法實(shí)驗(yàn)結(jié)果

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

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

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

Table 1 Experiment results of MCP

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

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

5 結(jié)束語

最大團(tuán)問題是一類經(jīng)典的組合優(yōu)化問題，有著廣泛的工程應(yīng)用基礎(chǔ)?；谧畲髨F(tuán)問題的NP特性，本文采用免疫克隆優(yōu)化算法進(jìn)行求解。同時(shí)，為了減少實(shí)驗(yàn)設(shè)置次數(shù)，采用了均勻設(shè)計(jì)方法。通過標(biāo)準(zhǔn)實(shí)驗(yàn)進(jìn)行驗(yàn)證，結(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/.

附中文參考文獻(xiàn):

[1] 范月科,強(qiáng)小利,許進(jìn).圖的最大團(tuán)與最大獨(dú)立集粘貼DNA計(jì)算模型[J].計(jì)算機(jī)學(xué)報(bào)，2010，33(2)：855-864.

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

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

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

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

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

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

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

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

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

張正球(1978-),男，江西臨川人，碩士生，講師，研究方向?yàn)橛?jì)算智能、網(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基金項(xiàng)目：福建省教育廳JK類科技資助項(xiàng)目(JK2010010)；福建省自然科學(xué)基金資助項(xiàng)目(2011J01339)

TP18

A

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

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

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

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