一種高效的基于教與學(xué)的社區(qū)發(fā)現(xiàn)算法

李佩茜,馮少榮

(廈門大學(xué)信息科學(xué)與技術(shù)學(xué)院,福建廈門361005)

現(xiàn)實(shí)世界有許多復(fù)雜網(wǎng)絡(luò)體系,例如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、萬維網(wǎng)等．在數(shù)學(xué)與計(jì)算機(jī)領(lǐng)域中,復(fù)雜網(wǎng)絡(luò)被定義為圖,包括一系列的節(jié)點(diǎn)與連接節(jié)點(diǎn)的邊,節(jié)點(diǎn)代表個(gè)體,邊代表個(gè)體與個(gè)體之間的聯(lián)系．一般而言,社區(qū)是指復(fù)雜網(wǎng)絡(luò)中聯(lián)系較為緊密的子網(wǎng)絡(luò)[1],社區(qū)發(fā)現(xiàn)就是為了找到復(fù)雜網(wǎng)絡(luò)的內(nèi)部特征,便于更加了解復(fù)雜網(wǎng)絡(luò)中的內(nèi)在信息．社區(qū)發(fā)現(xiàn)問題通過發(fā)現(xiàn)節(jié)點(diǎn)之間的相似度或其他相關(guān)屬性,對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行社區(qū)劃分．它可以被看作是一種最優(yōu)化問題[2]．

基于教與學(xué)的最優(yōu)化算法(TLBO)[3]是一種種群智能優(yōu)化算法,分為兩個(gè)階段:1) 學(xué)生向老師學(xué)習(xí)(稱為教學(xué)階段);2) 學(xué)生之間的相互學(xué)習(xí)(稱為學(xué)習(xí)階段)．通過這兩個(gè)階段的共同作用提高學(xué)生成績．TLBO具有簡單、易于理解、算法參數(shù)少、優(yōu)化精度高和收斂速度快等優(yōu)點(diǎn),廣泛運(yùn)用于各個(gè)領(lǐng)域中的最優(yōu)化問題[4-7]．Keesari等[8]用TLBO解決車間作業(yè)調(diào)度問題,Xia等[9]提出簡化的TLBO解決拆分序列問題,Baykasoglu等[10]分別分析了TLBO在流水車間(FSSP)與車間作業(yè)調(diào)度(JSSP)的表現(xiàn)．與此同時(shí),Dede[11]把TLBO運(yùn)用于離散化的桁架結(jié)構(gòu)最優(yōu)化問題,Li等[12]提出離散化TLBO解決流水車間調(diào)度問題．

從本質(zhì)上來看,復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題是一種聚簇最優(yōu)化問題．Chen等[13]提出了一種基于教與學(xué)的多目標(biāo)社區(qū)發(fā)現(xiàn)算法(MODTLBO/D)來解決社區(qū)發(fā)現(xiàn)問題．該算法中,每個(gè)個(gè)體從鄰居的平均值處進(jìn)行學(xué)習(xí),算法時(shí)間復(fù)雜度高,且在學(xué)習(xí)階段,個(gè)體僅僅從鄰居處進(jìn)行學(xué)習(xí),容易陷入局部最優(yōu)．因此,本文中提出一種在多種群進(jìn)化策略下的MODTLBO/D(E-MODTLBO/D)．采用多種群并進(jìn)的進(jìn)化策略,在不同種群中采用不同的進(jìn)化規(guī)則．在教學(xué)階段,采用自適應(yīng)學(xué)習(xí)因子;在學(xué)習(xí)階段,每個(gè)個(gè)體在各自的子種群內(nèi)可以采用隨機(jī)學(xué)習(xí)策略或者是改進(jìn)的量子行為學(xué)習(xí)策略．在每次迭代更新后,子種群間進(jìn)行信息交流,維持算法的多樣性與避免早熟收斂．把改進(jìn)后的算法帶入真實(shí)網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)發(fā)現(xiàn),本文中提出的E-MODTLBDO/D算法在時(shí)間復(fù)雜度與發(fā)現(xiàn)高質(zhì)量的社區(qū)結(jié)構(gòu)方面比MODTLBO/D等算法表現(xiàn)更好．

1 社區(qū)發(fā)現(xiàn)

1.1 相關(guān)工作

近年來發(fā)現(xiàn),很多現(xiàn)實(shí)世界的復(fù)雜系統(tǒng)可以由復(fù)雜網(wǎng)絡(luò)來表示,發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)問題就是社區(qū)發(fā)現(xiàn)問題,該問題已經(jīng)越來越受到人們的廣泛關(guān)注．許多來自不同領(lǐng)域的算法被提出來解決社區(qū)發(fā)現(xiàn)問題,這些算法大致可以分為以下3類:

1) 基于圖劃分的算法:在這類算法中,節(jié)點(diǎn)通過預(yù)定義的方法被劃分到不同社區(qū),使得社區(qū)之間的連接盡可能少．Ezhilarasi等[14]提出一種基于圖劃分的算法,該算法定義社區(qū)之間連接與內(nèi)在連接差異的評(píng)價(jià)函數(shù),旨在最小化評(píng)價(jià)函數(shù)．Pothen等[15]利用拉普拉斯矩陣的特征進(jìn)行社區(qū)劃分,實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)．但這兩種方法都需要預(yù)先定義劃分準(zhǔn)則,最小化劃分準(zhǔn)則將會(huì)導(dǎo)致劃分效果不佳．因此,又出現(xiàn)了一些其他準(zhǔn)則,例如平均劃分[16]、比率劃分[17]、標(biāo)準(zhǔn)化劃分[18]等．基于圖劃分的算法存在需預(yù)定義社區(qū)大小等規(guī)則的缺點(diǎn),這表明該種算法并不是理想的社區(qū)發(fā)現(xiàn)算法．

2) 基于分層的算法:這類算法的核心思想是運(yùn)用相似度度量不同節(jié)點(diǎn)對(duì)之間的相似程度來解決社區(qū)發(fā)現(xiàn)問題．分層算法包括凝聚分層算法和分裂分層算法．典型的凝聚分層算法是標(biāo)簽傳播算法(LPA)[19]．典型的分裂分層算法是由Girvan與Newman提出的GN算法[20]．這些方法自然生成了網(wǎng)絡(luò)的社區(qū)劃分,但是它們需要一個(gè)停止的規(guī)則．

3) 基于模塊度的算法:此類算法在社區(qū)發(fā)現(xiàn)問題中被廣泛運(yùn)用．模塊度Q是由Newman等[1]提出的用來評(píng)價(jià)社區(qū)劃分質(zhì)量的評(píng)價(jià)函數(shù)．Fast Newman(FN)算法[21]是一個(gè)經(jīng)典的模塊度算法,該算法從一些獨(dú)立的節(jié)點(diǎn)開始,用貪心策略將原始圖的連接信息反復(fù)加入到圖中,獲得最大可能的模塊度增長．Blondel等[22]提出一種快速多步貪心策略(BGLL)來實(shí)現(xiàn)模塊度最優(yōu),找到最優(yōu)社區(qū)劃分．除此之外,有一些單目標(biāo)進(jìn)化算法[23-27]被用來最優(yōu)化模塊度Q．由于單目標(biāo)算法存在分辨率限制等缺陷,還有許多多目標(biāo)進(jìn)化算法被提出,其中包括Shi等[28]提出的多目標(biāo)社區(qū)發(fā)現(xiàn)算法(MOCD)、Pizzuti等[29]提出的多目標(biāo)遺傳算法(MOGA-Net)、Gong等[30]提出的基于分解的多目標(biāo)遺傳算法(MOEA/D-Net)．與此同時(shí),Gong等[31]還提出一種基于分解的多目標(biāo)離散粒子群智能算法來解決社區(qū)發(fā)現(xiàn)問題．除此之外,還有一些多目標(biāo)進(jìn)化算法解決社區(qū)發(fā)現(xiàn)問題[32-36],它們都是同時(shí)最優(yōu)化兩個(gè)互相矛盾的目標(biāo)函數(shù)實(shí)現(xiàn)社區(qū)發(fā)現(xiàn)．

1.2 社區(qū)定義

一個(gè)復(fù)雜網(wǎng)絡(luò)可以抽象為一個(gè)圖G=(V，E),其中V為節(jié)點(diǎn)的集合,E為連接節(jié)點(diǎn)的邊的集合．在復(fù)雜網(wǎng)絡(luò)中的社區(qū)是指具有密切關(guān)系的節(jié)點(diǎn)的集合[37],也就是說在社區(qū)內(nèi)部節(jié)點(diǎn)連接緊密,而在社區(qū)之間節(jié)點(diǎn)連接稀疏．復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題是一個(gè)聚類問題,旨在把圖G劃分成若干子圖Gi(i=1,2,…,k),滿足∪1≤i≤kGi=G且∩1≤i≤kGi=φ．

1.3 評(píng)價(jià)指標(biāo)

為了找到更好的社區(qū)劃分與評(píng)價(jià)社區(qū)劃分的質(zhì)量,必須采用恰當(dāng)?shù)馁|(zhì)量評(píng)價(jià)指標(biāo)．本文中采用標(biāo)準(zhǔn)互換信息(normalized mutual information,NMI)與模塊度Q這兩個(gè)最常見的評(píng)價(jià)指標(biāo).近些年來,這兩個(gè)評(píng)價(jià)指標(biāo)被廣泛運(yùn)用于社區(qū)發(fā)現(xiàn)問題．

由Danon等[38]提出的NMI是用于評(píng)價(jià)所得社區(qū)劃分與真實(shí)網(wǎng)絡(luò)社區(qū)劃分相似度的評(píng)價(jià)指標(biāo),給出一個(gè)網(wǎng)絡(luò)的兩種劃分p1與p2,C為混淆矩陣,Cij代表p1中屬于社區(qū)i的節(jié)點(diǎn)也屬于p2中屬于社區(qū)j的節(jié)點(diǎn)的數(shù)目總和,NMI(p1,p2)為:

NMI(p1,p2)=

其中,Cp1(Cp2)表示p1(p2)中的社區(qū)數(shù)目,Ci(Cj)表示混淆矩陣C的第i行(第j列)的元素和,N指節(jié)點(diǎn)總數(shù)．如果p1=p2,則NMI(p1,p2)=1,如果p1與p2完全不同,則NMI(p1,p2)=0．NMI值越大代表p1與p2的相似度越高．

由Newman等[1]提出的模塊度Q是一個(gè)非常受歡迎的用來評(píng)價(jià)社區(qū)劃分質(zhì)量的評(píng)價(jià)函數(shù),假設(shè)K為復(fù)雜網(wǎng)絡(luò)中的社區(qū)劃分?jǐn)?shù)目,則模塊度Q值定義如下:

其中,m表示網(wǎng)絡(luò)中的邊總數(shù),lS與dS分別表示社區(qū)S中的邊總數(shù)與節(jié)點(diǎn)總數(shù)．當(dāng)Q值越接近1,表示網(wǎng)絡(luò)的社區(qū)劃分質(zhì)量越好．在實(shí)際例子中,Q值一般為0.3～0.7．

2 預(yù)備知識(shí)

在E-MODTLBO/D中,由于學(xué)習(xí)規(guī)則的改變，本文中需要重新定義Chen等[13]提到的一些變量．

定義1 設(shè)Y=(y1,y2,…，yN),X=(x1,x2,…，xN),則定義函數(shù)Y=S(X)如下:

其中,j=1,2,…,N,sigmoid函數(shù)[39]定義如下:

定義2 假設(shè)Y=(y1,y2,…,yN),X=(x1,x2,…,xN),Z=(z1,z2,…，zN),則定義函數(shù)Z=XθY如下:

其中,SBestj是代表個(gè)體所有鄰居中第j個(gè)節(jié)點(diǎn)的最多標(biāo)簽數(shù)．

3 改進(jìn)的E-MODTLBO/D

3.1 離散化個(gè)體表示

本算法采用整數(shù)值編碼規(guī)則[13],個(gè)體向量代表社區(qū)劃分結(jié)果．假設(shè)一個(gè)節(jié)點(diǎn)的社區(qū)值與另一個(gè)節(jié)點(diǎn)的社區(qū)值相同,代表著兩個(gè)節(jié)點(diǎn)屬于同一社區(qū),反之則屬于不同社區(qū)．假設(shè)網(wǎng)絡(luò)共有C個(gè)社區(qū),N個(gè)節(jié)點(diǎn),則第i個(gè)個(gè)體向量Xi定義如下:

Xi=(xi1,xi2,…,xiN),

其中，xij(1≤j≤N,1≤i≤p)代表第i個(gè)個(gè)體的第j個(gè)節(jié)點(diǎn)所屬的社區(qū)值,p為種群大?。魓ij=xik,則第i個(gè)個(gè)體的第j個(gè)節(jié)點(diǎn)與第k個(gè)節(jié)點(diǎn)屬于同一社區(qū)內(nèi)．除此之外,本算法采用Gong等[40]提出的一種啟發(fā)式算法獲得初始個(gè)體向量．

3.2 多種群進(jìn)化策略

本算法采用一種改進(jìn)的多種群進(jìn)化策略[47]．種群內(nèi)所有個(gè)體以相同概率被均等地分到各個(gè)子種群內(nèi),不同子種群內(nèi)部進(jìn)化規(guī)則不同,以維持算法的探索能力與提高算法多樣性．在每一輪迭代中,每個(gè)個(gè)體通過教學(xué)階段與學(xué)習(xí)階段在各個(gè)子種群內(nèi)進(jìn)行學(xué)習(xí)更新,子種群間進(jìn)行信息交流,把種群內(nèi)部表現(xiàn)最優(yōu)的個(gè)體傳給其他子種群,維持種群的多樣性,避免陷入局部最優(yōu)．多種群進(jìn)化策略不僅可以提高算法的多樣性,還可以降低時(shí)間復(fù)雜度．

3.3 自適應(yīng)教學(xué)因子

在Chen等[13]提出的MODTLBO/D中,教學(xué)因子(TTF)決定平均值的改變程度與平均值對(duì)生成新解的影響程度,其值隨機(jī)取為1或2,分別反映學(xué)員什么也沒學(xué)到,或者是學(xué)到老師的全部知識(shí)兩種情況．但在實(shí)際教學(xué)中,情況隨著學(xué)習(xí)時(shí)間的推移有所不同．在教學(xué)階段的前期,學(xué)員與教師之間的知識(shí)存在較大差距,這是由于此時(shí)學(xué)員對(duì)所學(xué)知識(shí)掌握很少,所以學(xué)員學(xué)習(xí)效率較高,學(xué)到的知識(shí)多而且快；而在教學(xué)階段的后期,經(jīng)過一段時(shí)間的學(xué)習(xí),學(xué)員掌握的知識(shí)越來越多,與教師之間的差距越來越小,學(xué)習(xí)效率會(huì)顯著下降,學(xué)到的知識(shí)少而且慢．

在優(yōu)化算法中,TTF值小,則代表算法探索能力強(qiáng),但搜索能力弱；反之則代表算法探索能力弱,但搜索能力強(qiáng)．考慮到此問題,本算法參考2015年Yue等[41]提出的自適應(yīng)教學(xué)因子,改進(jìn)本算法的教學(xué)因子,使得TF隨著迭代次數(shù)的增加而呈線性遞減,表達(dá)式如下:

其中,TTFmax與TTFmin分別表示TTF的最大值與最小值,tmax表示算法的迭代總次數(shù),t表示當(dāng)前迭代次數(shù)．從上式可以看出,在搜索前期,TTF值大;在搜索后期,TTF值?。@表明在算法搜索前期,學(xué)員學(xué)習(xí)效率高,學(xué)到的知識(shí)多且快,TTF值大有利于增強(qiáng)算法的全局探索能力,加快算法的收斂速度．隨著迭代不斷進(jìn)行,學(xué)習(xí)效率下降,學(xué)到的知識(shí)少且慢,此時(shí)TTF值小有利于增強(qiáng)算法的局部探索能力,使算法搜索逐步向最優(yōu)解靠攏,獲得更高精度的解．

3.4 E-MODTLBO/D教學(xué)階段

在實(shí)際教學(xué)中,教師給學(xué)生傳播知識(shí)提高全班的知識(shí)水平,幫助學(xué)生得到較好的分?jǐn)?shù),因此全班的平均成績也可提高,個(gè)體基于全班平均成績與教師進(jìn)行更新．本算法把每個(gè)個(gè)體分配到不同種群內(nèi),個(gè)體從種群內(nèi)最優(yōu)個(gè)體(STeacheri)與平均值SMeani學(xué)習(xí)更新．

STeacheri與SMeani定義如下:

STeacheri=BBest(Xi1,Xi2,…,Xik,…，XiK),

其中,Xi1,Xi2,…,Xik,…,XiK代表個(gè)體Xi所在種群的個(gè)體集合,且Xik=(xik1,xik2,…,xikD)．

在教學(xué)階段,教師的任務(wù)是提高全班的成績,通過對(duì)最優(yōu)個(gè)體的學(xué)習(xí)來提高整體水平,因此,對(duì)社區(qū)發(fā)現(xiàn)問題重新定義對(duì)第i個(gè)個(gè)體Xi的更新規(guī)則:

newXi=Xiθ Differencei,

Differencei=S(rand(0,1)×(STeacheri?

(TTF(t)×SMeani))),

其中,rand(0,1)是0與1之間的隨機(jī)數(shù),TTF(t)是前文3.3節(jié)提到的自適應(yīng)教學(xué)因子,(STeacheri)與SMeani分別是個(gè)體Xi所在種群的最優(yōu)個(gè)體與平均值,?是異或算子．

3.5 E-MODTLBO/D學(xué)習(xí)階段

在學(xué)習(xí)階段,學(xué)生隨機(jī)向種群內(nèi)的其他學(xué)生學(xué)習(xí)知識(shí),學(xué)生從其他學(xué)生那里學(xué)習(xí)他們還未掌握的新知識(shí)．在這一階段,個(gè)體通過以下規(guī)則更新:

newXi=Xiθ Differencei，

Differencei=S(Xi?Xj)，

其中,?是異或算子,Xj代表Xi所在種群內(nèi)部的任意個(gè)體,這種策略被稱為隨機(jī)學(xué)習(xí)策略．

為了提高算法的表現(xiàn)效果,本算法提出一種改進(jìn)的量子行為學(xué)習(xí)策略[42]．在學(xué)習(xí)階段,每個(gè)個(gè)體在各自的子種群內(nèi)可以采用隨機(jī)學(xué)習(xí)策略或者是改進(jìn)的量子行為學(xué)習(xí)策略．給出學(xué)習(xí)概率pl,決定個(gè)體在學(xué)習(xí)階段采用的學(xué)習(xí)策略．隨機(jī)產(chǎn)生一個(gè)介于0與1之間的隨機(jī)數(shù)r,當(dāng)r

假設(shè)產(chǎn)生的新個(gè)體newXi=(z1,z2,…,zN),改進(jìn)的量子行為學(xué)習(xí)策略規(guī)則如下:

zj=

其中,STeacher與GTeacher分別表示個(gè)體Xi所在種群內(nèi)的最優(yōu)個(gè)體與全局最優(yōu)個(gè)體,且TempX定義如下:

TempX=β×(X?SMeani)×(-log(u)),

其中，u為介于0與1之間的隨機(jī)值,SMeanj是個(gè)體Xj所在種群內(nèi)的平均值．在傳統(tǒng)的學(xué)習(xí)階段,個(gè)體只是在種群中隨機(jī)選擇個(gè)體進(jìn)行學(xué)習(xí),而本算法中,個(gè)體有兩種不同的學(xué)習(xí)策略．在一定概率下,個(gè)體采用傳統(tǒng)的隨機(jī)學(xué)習(xí)策略；但在一定概率下,個(gè)體通過向全局最優(yōu)個(gè)體與種群內(nèi)最優(yōu)個(gè)體學(xué)習(xí)知識(shí),使得個(gè)體可以在其他個(gè)體、全局最優(yōu)個(gè)體與種群內(nèi)最優(yōu)個(gè)體的共同幫助下學(xué)習(xí),使學(xué)習(xí)效率明顯提高,加快算法收斂速度．

3.6 變異規(guī)則

當(dāng)算法中存在完全相同的兩個(gè)解,則必須修改它們以避免陷入局部最優(yōu),維持種群多樣性．采用Gong等[40]提出的基于鄰居的變異算子,對(duì)每個(gè)個(gè)體隨機(jī)生成一個(gè)介于0與1之間的數(shù),如果小于變異概率pm,則執(zhí)行變異算子．這里需要指出每次教學(xué)階段或者學(xué)習(xí)階段完成后,都需進(jìn)行一次變異操作．

3.7 算法框架

3.7.1 基于分解的多目標(biāo)優(yōu)化算法(MOEA/D)

MOEA/D[43]是基于傳統(tǒng)的多目標(biāo)最優(yōu)化策略的算法,該算法把多目標(biāo)優(yōu)化問題分解為一系列單目標(biāo)子問題,同時(shí)最優(yōu)化這些子問題,每個(gè)子問題通過其鄰居子問題進(jìn)行優(yōu)化,而子問題的鄰居關(guān)系通過子問題之間的距離與聚合多目標(biāo)權(quán)重向量定義．不同于傳統(tǒng)的帕累托分級(jí)方法,該算法通過實(shí)現(xiàn)每個(gè)子問題的最優(yōu)化來獲得最優(yōu)解．

在MOEA/D中,有許多方法可以把多目標(biāo)最優(yōu)化算法分解為一系列子問題,其中一種是通過構(gòu)造聚合函數(shù)實(shí)現(xiàn)分解．至今為止,有許多方法可以構(gòu)造聚合函數(shù),其中最受歡迎的是權(quán)重求和法與切比雪夫法．本算法采用切比雪夫法,因?yàn)樗芯康膯栴}中兩個(gè)目標(biāo)函數(shù)是不連續(xù)的,所以不能簡單判斷鉑累托前沿(PF)是不是凹的．如果PF是凸的,權(quán)重求和法的效果就會(huì)不佳．切比雪夫法把問題分割為一些具有單目標(biāo)子問題[43],最優(yōu)化問題可以表示為

3.7.2 目標(biāo)函數(shù)

采用Gong等[30]提出的兩個(gè)目標(biāo)函數(shù)NRA與RC,目標(biāo)是最小化這兩個(gè)函數(shù)．定義一個(gè)無向圖G=(V，E),定義鄰接矩陣A,一種劃分方法S=(V1，V2，…，Vm),Vi是社區(qū)Gi的節(jié)點(diǎn)集合,i=1,2,…,m．定義L(V1,V2)=∑i∈V1,j∈V2Aij,L(V1,V2)=∑i∈V1,j?V2Aij．目標(biāo)函數(shù)如下:

一般而言,NRA可看作是社區(qū)內(nèi)部連接的密度,RC可看作是社區(qū)之間連接的密度．最小化NRA趨向于把網(wǎng)絡(luò)切割成很多的小型社區(qū),而最小化RC趨向于把網(wǎng)絡(luò)切割成大型社區(qū),這兩個(gè)目標(biāo)函數(shù)有著權(quán)衡對(duì)方對(duì)于社區(qū)數(shù)目增加或者減少的趨勢(shì)的潛力．通過權(quán)衡最小化這兩個(gè)目標(biāo)函數(shù),可以獲得高質(zhì)量的網(wǎng)絡(luò)劃分．

3.7.3E-MODTLBO/D偽代碼

本文中采用MOEA/D的主要框架,加入多種群進(jìn)化策略,在每個(gè)種群內(nèi)部,個(gè)體通過種群內(nèi)部信息進(jìn)行更新進(jìn)化．因此,NTeacheri與NMeani代表第i個(gè)個(gè)體所在種群內(nèi)部最優(yōu)值與平均值．E-MODTLBO/D的偽代碼如下:

算法：E-MODTLBO/D

輸入：初始化個(gè)體X，個(gè)體數(shù)目N，迭代次數(shù)genmax，變異概率pm，學(xué)習(xí)概率pl，種群數(shù)目Sp，種群內(nèi)個(gè)體數(shù)目SN，權(quán)重向量W，初始化最優(yōu)參考點(diǎn)z*；

輸出：最優(yōu)個(gè)體

Begin

fort=1：genmax

把個(gè)體X隨機(jī)分入不同種群內(nèi)，更新全局最優(yōu)個(gè)體與種群內(nèi)最優(yōu)個(gè)體；

for每個(gè)種群 do

通過教學(xué)階段與學(xué)習(xí)階段更新每個(gè)個(gè)體Xi，計(jì)算個(gè)體與全局最優(yōu)參考點(diǎn)的距離z*；

保留每個(gè)種群內(nèi)表現(xiàn)最優(yōu)的SN個(gè)個(gè)體；

更新全局最優(yōu)參考點(diǎn)z*；

end for

把種群內(nèi)最優(yōu)個(gè)體傳給其他種群，并保留前SN個(gè)個(gè)體在種群內(nèi)；

end for

End

4 實(shí)驗(yàn)結(jié)果

4.1 參數(shù)設(shè)置

所有實(shí)驗(yàn)都在2.3 GHz CPU,4 GB RAM的處理器上運(yùn)行,操作系統(tǒng)為Windows7,軟件版本為MATLAB 8.3．為了減少系統(tǒng)誤差,每個(gè)函數(shù)都被單獨(dú)運(yùn)行了20次．對(duì)于所有的方法,種群大小popsize設(shè)置為100,更新迭代次數(shù)ggenmax設(shè)置為100,變異概率pm=0.06,種群數(shù)目設(shè)置為20,種群內(nèi)個(gè)體數(shù)目為5．為了維持算法多樣性與收斂性的平衡,設(shè)置學(xué)習(xí)概率pl=0.5．

4.2 真實(shí)網(wǎng)絡(luò)

采用Zachary空手道俱樂部網(wǎng)絡(luò)、Bottlenose海豚網(wǎng)絡(luò)、美國大學(xué)足球隊(duì)網(wǎng)絡(luò)和Krebs美國政治書網(wǎng)絡(luò)這4個(gè)真實(shí)的復(fù)雜網(wǎng)絡(luò)對(duì)本算法進(jìn)行驗(yàn)證．

空手道俱樂部網(wǎng)絡(luò)由Zachary提出[44],通過觀察在一段時(shí)期內(nèi)空手道俱樂部34名成員的活動(dòng)所獲得．在研究期間,俱樂部管理者與俱樂部開發(fā)者之間存在分歧,這個(gè)分歧最終導(dǎo)致開發(fā)者離開并且成立新的俱樂部；與此同時(shí),開發(fā)者帶走原俱樂部近1/2成員,網(wǎng)絡(luò)自然分成了兩個(gè)大小相近的社區(qū)．

Bottlenose海豚網(wǎng)絡(luò)由62只海豚構(gòu)成[45],海豚們住在新西蘭的一個(gè)神奇峽灣中,它們的行為活動(dòng)被Lusseau等學(xué)者所觀察．學(xué)者們花了7年時(shí)間觀察它們的行為活動(dòng),定義如果有兩只海豚發(fā)生固定且頻繁的協(xié)作行為,則認(rèn)為這兩只海豚之間有聯(lián)系．這個(gè)網(wǎng)絡(luò)中的海豚自然的分成2組,共有159組聯(lián)系．

美國大學(xué)足球隊(duì)網(wǎng)絡(luò)來自于對(duì)美國大學(xué)足球隊(duì)的觀察[20],網(wǎng)絡(luò)代表在Fall 2000常規(guī)賽賽季中不同球隊(duì)之間的比賽場(chǎng)次,網(wǎng)絡(luò)中的節(jié)點(diǎn)代表足球隊(duì),而邊則代表兩個(gè)足球隊(duì)會(huì)進(jìn)行比賽．比賽隊(duì)伍會(huì)被分到幾個(gè)不同的聯(lián)盟中去,每隊(duì)平均進(jìn)行4場(chǎng)聯(lián)盟間比賽與7場(chǎng)聯(lián)盟內(nèi)比賽,該網(wǎng)絡(luò)包含115個(gè)節(jié)點(diǎn)與616條邊．

Krebs的政治書網(wǎng)絡(luò)中,節(jié)點(diǎn)代表105本購自亞馬遜的關(guān)于美國政治的書,邊代表經(jīng)常由同一個(gè)買家買的書之間具有關(guān)聯(lián)關(guān)系．不同的書按不同的政治取向被分類[46]．

4.3 實(shí)驗(yàn)結(jié)果分析

為了評(píng)價(jià)本算法在復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題中的表現(xiàn),把本算法與其他一些經(jīng)典的算法進(jìn)行比較．

首先,與兩個(gè)經(jīng)典的單目標(biāo)算法：FM算法[21](采用貪心策略實(shí)現(xiàn)模塊度Q最優(yōu))，BGLL算法進(jìn)行比較，結(jié)果如表1所示．

表1 4個(gè)真實(shí)網(wǎng)絡(luò)的模塊度Q值Tab.1 The modularity values obtained on four real-world networks

從表1可以看出：在Zachary空手道俱樂部網(wǎng)絡(luò)中,BGLL算法表現(xiàn)最優(yōu),可以獲得最大的模塊度Q值為0.421 08;而對(duì)于另外3個(gè)網(wǎng)絡(luò),E-MODTLBO/D算法表現(xiàn)最優(yōu),比其他兩個(gè)單目標(biāo)算法表現(xiàn)都要好．

其次,把E-MODTLBO/D與一些多目標(biāo)進(jìn)化算法進(jìn)行比較,分別為MOCD[28]、MOGA-Net[29]、MOEA/D-Net[30]、MODPSO[31]和MODTLBO/D[13],所得結(jié)果如表2所示.

表2 4個(gè)真實(shí)網(wǎng)絡(luò)的模塊度Q值與標(biāo)準(zhǔn)互換信息NMI

Tab.2 Results obtained on four real-world networks

算法QNMIZachary空手道俱樂部Battlenose海豚美國大學(xué)足球隊(duì)Krebs美國政治書Zachary空手道俱樂部Battlenose海豚美國大學(xué)足球隊(duì)Krebs美國政治書MOCD0.418760.521950.595860.525740.837181.000000.893320.59498MOGA-Net0.414940.514170.526480.517420.837181.000000.801160.59419MOEA/D-Net0.419790.521180.603980.526551.000001.000000.926790.59642MODPSO0.419790.526050.604550.526621.000001.000000.928850.61583MODTLBO/D0.419790.522010.604550.526721.000001.000000.926680.61727E-MODTLBO/D0.419790.526800.604570.526941.000001.000000.924200.67710

從表2可以看出：從模塊度Q值的角度比較,在Zachary空手道俱樂部網(wǎng)絡(luò)中,E-MODTLBO/D與MOEA/D-Net、MODPSO、MODTLBO/D表現(xiàn)同樣好；但在另外3個(gè)網(wǎng)路中,E-MODTLBO/D比其他算法表現(xiàn)更優(yōu).從NMI這個(gè)評(píng)價(jià)指標(biāo)來看,在Zachary空手道俱樂部網(wǎng)絡(luò)中,E-MODTLBO/D與MOEA/D-Net、MODPSO、MODTLBO/D表現(xiàn)同樣好；在Battlenose海豚網(wǎng)絡(luò)中,所有算法的NMI值都可以達(dá)到1;在美國大學(xué)足球隊(duì)網(wǎng)絡(luò)中，MODPSO表現(xiàn)最優(yōu),NMI值為0.928 85,本算法的NMI值為0.924 20．在Krebs美國政治書網(wǎng)絡(luò)中,本算法表現(xiàn)最優(yōu),可以獲得最大的NMI值，為0.677 10,遠(yuǎn)大于其他算法．

從與這些算法比較中更可以看出,本算法在解決社區(qū)發(fā)現(xiàn)問題時(shí)是很有潛力的.在NMI值上來看,它可以在Zachary空手道俱樂部網(wǎng)絡(luò)、Bottlenose海豚網(wǎng)絡(luò)與Krebs美國政治書網(wǎng)絡(luò)中都表現(xiàn)優(yōu)于其他算法；從Q值來看,它在4個(gè)網(wǎng)絡(luò)中的表現(xiàn)都優(yōu)于其他算法．

5 結(jié) 論

本文中提出了一種高效的在多種群進(jìn)化策略下的E-MODTLBO/D．不同于MODTLBO/D,本算法采用多種群進(jìn)化策略來降低時(shí)間復(fù)雜度并且增加算法的多樣性．種群內(nèi)所有個(gè)體以相同概率被均等地分到各個(gè)子種群內(nèi),不同子種群內(nèi)部進(jìn)化規(guī)則不同,以維持算法的探索能力．每個(gè)個(gè)體在教學(xué)階段與學(xué)習(xí)階段在各個(gè)種群內(nèi)進(jìn)行學(xué)習(xí)更新,每次迭代后,種群間進(jìn)行信息交流,把種群內(nèi)部表現(xiàn)最優(yōu)的個(gè)體傳給其他種群,以維持種群的多樣性,避免陷入局部最優(yōu)．在教學(xué)階段,每個(gè)個(gè)體從種群內(nèi)學(xué)習(xí),同時(shí)采用自適應(yīng)教學(xué)因子．在學(xué)習(xí)階段,每個(gè)個(gè)體在各自的子種群內(nèi)采用隨機(jī)學(xué)習(xí)策略或者是改進(jìn)的量子行為學(xué)習(xí)策略,以保證算法的收斂性與多樣性．在每代更新完成后,子種群之間的信息交流可以維持算法的多樣性與避免早熟收斂．

為了驗(yàn)證提出該算法的有效性,把該算法運(yùn)用于不同的真實(shí)網(wǎng)絡(luò)中,并與其他算法進(jìn)行比較．實(shí)驗(yàn)結(jié)果表明,該算法在時(shí)間復(fù)雜度與發(fā)現(xiàn)高質(zhì)量的社區(qū)結(jié)構(gòu)方面要優(yōu)于MODTLBO/D等一些經(jīng)典社區(qū)發(fā)現(xiàn)算法,在解決復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問題方面高效且有廣泛應(yīng)用前景．

為了讓該算法更加高效,未來的工作將致力于研究基于特殊問題的更新策略與如何維持多樣性與收斂性的方法．進(jìn)而將離散性基于教與學(xué)最優(yōu)化的方法運(yùn)用于限制性的、動(dòng)態(tài)的復(fù)雜網(wǎng)絡(luò)中，這有助于解決各種各樣的真實(shí)復(fù)雜網(wǎng)絡(luò)的最優(yōu)化問題．

[1] NEWMAN M E J,GIRVAN M M.Finding and evaluating community structure in networks[J].Phys Rev E,2004,69(2):99-106.

[2] NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Phys Rev E,2004,69(6):066133.

[3] RAO R V,SAVSANI V J,VAKHARIA D P.Teaching-learning-based optimization:an optimization method for continuous non-linear large scale problems[J].Information Sciences,2012,183(1):1-15.

[4] YU K,WANG X,WANG Z.Constrained optimization based on improved teaching-learning-based optimization algorithm[J].Information Sciences,2016,352/353:61-78.

[5] GHASEMI M,GHAVIDEL S,GITIZADEH M,et al.An improved teaching-learning-based optimization algorithm using Levy mutation strategy for non-smooth strategy for non-smooth power flow[J].International Journal of Electrical Power& Energy Systems,2015,65:375-384.

[6] BASU M.Teaching-learning-based optimization algorithm for multi-area economic dispatch[J].Energy,2014,68:21-28.

[7] PATEL V K,SAVSANI V J.A multi-objective improved teaching-learning-based optimization algorithm (MO-ITLBO) [J].Information Sciences,2014,357:182-200.

[8] KEESARI H S,RAO R V.Optimization of job shop scheduling problems using teaching-learning-based optimization algorithm[J].Opsearch,2013,51(4):545-561.

[9] XIA K,GAO L,LI W D,et al.Disassembly sequence planning using a simplified teaching-learning-based optimization algorithm[J].Advanced Engineering Informatics,2014,28:518-527.

[10] BAYKASOGLU A,HAMZADAYI A,KOSE S Y.Testing the performance of teaching-learning-based optimization (TLBO) algorithm on combinatorial problems:Flow shop and job shop scheduling cases[J].Information Sciences,2014,276(C):204-218.

[11] DEDE T.Application of teaching-learning-based-optimization algorithm for the discrete optimization of truss structures[J].Ksce Journal of Civil Engineering,2014,18(6):1759-1767.

[12] LI J,PAN Q,MAO K.A discrete teaching-learning-based optimization algorithm for realistic flow shop rescheduling problems[J].Engineering Applications of Artificial Intelligence,2015,37:279-292.

[13] CHEN D,ZOU F,LU R Q,et al.Multi-objective optimization of community detection using discrete teaching-learning-based optimization & with decomposition[J].Information Sciences,2016,369:402-418.

[14] EZHILARASI G A,SWARUP K S.Network decomposition using Kernighan-Lin strategy aided harmony search algorithm[J].Swarm & Evolutionary Computation,2012(7):1-6.

[15] POTHEN A,SIMON H,LIOU K P.Partitioning sparse matrices with eigenvectors of graphs[J].Siam Journal on Matrix Analysis & Applications,1990,11(3):430-452.

[16] FIEDLER M.A property of eigenvectors of non-negative symmetric matrices and its applications to graph theory[J].Czechoslovak Mathematical Journal,1975,25:619-637.

[17] WEI Y C,CHENG C K.Ration cut partitioning for hie-rarchical designs[J].IEEE Transactions on Computer-Aided Design,1991,10(7):911-921.

[18] HE L,ZHANG H.Iterative ensemble normalized cuts[J].Pattern Recognition,2015,52:274-286.

[19] ZHANG X,FEI S,SONG C,et al.Label propagation algorithm based on local cycles for community detection[J].International Journal of Modern Physics B,2015,29(5):1550029.

[20] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.

[21] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(2):066111.

[22] BLONDEL V D,GUILAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,10:P10008.

[23] CRUZ J D,BOTHOREL C,POULET F.Entropy based community detection in augmented social networks[C]∥International Conference on Computational aspects of Social Networks.Salamanca:IEEE,2011:163-168.

[24] HASSAN E A,HAFEZ A I,HASSANIEN A E,et al.Community detection algorithm based on artificial fish swarm optimization[J].Advances in Intelligent Systems & Computing,2014,323:509-521.

[25] KARIMI-MAID A M,FATHIAN M,AMIRI B.A hybrid artificial immune network for detecting communities in complex networks[J].Computing,2015,97(5):483-507.

[26] LI Y,LIU J,LIU C.A comparative analysis of evolutio-nary and memetic algorithms for community detection from signed social networks[J].Soft Computing,2014,18(2):329-348.

[27] LI Z,LIU J.A multi-agent genetic algorithm for community detection in complex networks[J].Physica A Statistical Mechanics & Its Applications,2016,449:336-347.

[28] SHI C,YAN Z,CAI Y,et al.Multi-objective community detection in complex networks[J].Applied Soft Computing,2012,12(2):850-859.

[29] PIZZUTI C.A multi-objective genetic algorithm to find communities in complex networks[J].IEEE Transactions on Evolutionary Computation,2012,6(3):418-430.

[30] GONG M G,MA L,ZHANG Q F,et al.Community detection in networks by using multi-objective evolutionary algorithm with decomposition[J].Physica A Statistical Mechanics & Its Application,2012,391:4050-4060.

[31] GONG M G,CAI Q,CHEN X,et al.Complex network clustering by multi-objective discrete particle swarm optimization based on decomposition[J].IEEE Transactions on Evolutionary Computation,2014,18(1):82-97.

[32] AMIRI B,HOSSAIN L,CRAWFORD J W,et al.Community detection in complex networks:multi-objective enhanced firefly algorithm[J].Knowledge-Based Systems,2013,46:1-11.

[33] CAI Q,GONG M G,MA L,et al.Greedy discrete particle swarm optimization for large-scale social network clustering[J].Information Sciences,2015,316(41):503-516.

[34] LIU C,LIU J,JIANG Z.A multi-objective evolutionary algorithm based on similarity for community detection from signed social networks[J].IEEE Transactions on Cybernetics,2014,44(12):2274-2287.

[35] ZHAO Y,LI S,JIN F.Overlapping community detection in complex networks using multi-objective evolutionary algorithm[J].Computational & Applied Mathematics,2015,36(1):1-20.

[36] ZHOU X,LIU Y,LI B,et al.Multi-objective biogeography based optimization algorithm with decomposition for community detection in dynamic networks[J].Physica A:Statistical Mechanics & Its Applications,2015,436:430-442.

[37] RADICCHI F,CASTELLANO,CECCONI F,et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658-2663.

[38] DANON L,DAZ-GUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics Theory & Experiment,2005,78:P09008.

[39] KENNEDY J,EBERHART R C.A discrete binary version of the particle swarm algorithm[J].Computational Cybernetics and Simulation,1997,5:4104-4108.

[40] GONG M G,CAI Q,LI Y,et al.An improved memetic algorithm for community detection in complex networks[C]∥2012 IEEE Congress on Evolutionary Computation.Brisbane:IEEE,2012:1-8.

[41] YUE Z,GAO Y.An improved teaching-learning-based optimization algorithm[J].Journal of Lanzhou University of Technology,2015,41(6):99-103.

[42] ZOU F,WANG L,HEI X,et al.Teaching-learning-based optimization with dynamic group strategy for global optimization[J].Information Sciences,2014,273:112-131.

[43] ZHANG Q F,LI H.MOEA/D:a multi-objective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Compution,2017,11(6):712-731.

[44] ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1997,33(4):452-473.

[45] LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.

[46] NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Science,2006,103 (23):8577-8582.

[47] ROSINC C,BELEW R,MORRIS G,et al.New methods for competitive co-evolution[J].Evolutionary Computation,1997,5(1):1-29.