具有小世界鄰域結(jié)構(gòu)的教與學(xué)優(yōu)化算法*

王培崇，馬　玥，耿明月，汪慎文

1.河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊 0500312.中國(guó)礦業(yè)大學(xué) 信息與機(jī)電學(xué)院，北京 1000833.重慶郵電大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400065

具有小世界鄰域結(jié)構(gòu)的教與學(xué)優(yōu)化算法*

王培崇1,2+，馬玥1，耿明月3，汪慎文1

1.河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊 050031
2.中國(guó)礦業(yè)大學(xué) 信息與機(jī)電學(xué)院，北京 100083
3.重慶郵電大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400065

教與學(xué)優(yōu)化（teaching-learning-based optimization，TLBO）算法是近年來(lái)提出的一種通過模擬“教”與“學(xué)”行為的群體智能算法。為了克服教與學(xué)優(yōu)化算法容易早熟，解精度較低，后期收斂速度慢等弱點(diǎn)，提出了一種改進(jìn)的教與學(xué)優(yōu)化算法，并命名為S-TLBO（small world neighborhood TLBO）。該算法采用小世界網(wǎng)絡(luò)作為其種群的空間結(jié)構(gòu)關(guān)系，種群中的個(gè)體被看作是網(wǎng)絡(luò)上的節(jié)點(diǎn)。在算法的“教”階段，學(xué)生基于概率向教師個(gè)體進(jìn)行學(xué)習(xí)，而在“學(xué)”階段，學(xué)生則在自己的鄰居節(jié)點(diǎn)中隨機(jī)選擇較為優(yōu)秀的個(gè)體進(jìn)行學(xué)習(xí)。為了提高加強(qiáng)算法的勘探新解和開采能力，引入教師個(gè)體執(zhí)行反向?qū)W習(xí)算法。在多個(gè)經(jīng)典的測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果表明，所提出的改進(jìn)算法具有較高的全局收斂性和解精度，適合于求解較高維度的多模態(tài)函數(shù)優(yōu)化問題。

教與學(xué)優(yōu)化（TLBO）；小世界網(wǎng)絡(luò)；鄰域結(jié)構(gòu)；反向?qū)W習(xí)（OBL）

1　引言

Rao提出的教與學(xué)優(yōu)化（teaching-learning-based optimization，TLBO）[1-4]算法是群體智能算法的典型代表之一，該算法的靈感來(lái)源于生活中自然班級(jí)的教和學(xué)行為。通過模擬教師的教學(xué)和學(xué)生相互之間的學(xué)習(xí)實(shí)現(xiàn)種群的進(jìn)化。教與學(xué)優(yōu)化算法具有參數(shù)少，求解速度較快，設(shè)計(jì)思想簡(jiǎn)單，容易實(shí)現(xiàn)等特點(diǎn)，受到了眾多研究者的關(guān)注。

為了提高算法的求解能力，克服該算法在后期收斂速度慢，容易陷入局部最優(yōu)的問題，文獻(xiàn)[4]引入了局部學(xué)習(xí)和自學(xué)習(xí)機(jī)制，使學(xué)生不僅可以向其鄰居進(jìn)行學(xué)習(xí)，而且還能夠進(jìn)行自學(xué)習(xí)。Rao等人[5]為了進(jìn)一步提高算法的求解能力，在TLBO中利用精英個(gè)體替換部分劣質(zhì)解，并刪掉了重復(fù)的學(xué)生個(gè)體，該算法被命名為精英教與學(xué)優(yōu)化（elitist TLBO，ETLBO）算法。實(shí)驗(yàn)表明該算法具有較快的收斂速度，但是魯棒性稍差。于坤杰等人[6]在ETLBO算法的基礎(chǔ)上進(jìn)一步提出了精英反饋機(jī)制教與學(xué)優(yōu)化算法，每次迭代之后劣質(zhì)個(gè)體向精英個(gè)體反饋其本身狀態(tài)變化情況，并根據(jù)變化情況進(jìn)行修正。仿真實(shí)驗(yàn)結(jié)果表明，該算法具有較高的精度和魯棒性。為了使算法的后期種群多樣性得以較好地維持，Rajasekhar等人[7]提出了相對(duì)精英教與學(xué)優(yōu)化（oppositedelitistTLBO，OETLBO）算法，學(xué)生個(gè)體不僅僅向教師個(gè)體進(jìn)行學(xué)習(xí)，還增加了學(xué)生個(gè)體向相對(duì)精英個(gè)體的學(xué)習(xí)，避免了學(xué)生個(gè)體過早聚集于教師個(gè)體周圍，從而使算法在后期能夠較好保持種群的多樣性，但是算法的精度較標(biāo)準(zhǔn)TLBO算法提高較少。文獻(xiàn)[8]提出了改進(jìn)的多教師自適應(yīng)教學(xué)TLBO算法，該算法中允許設(shè)置多個(gè)教師個(gè)體，教師的教學(xué)因子被修改為自適應(yīng)變化，隨著迭代次數(shù)的變化呈現(xiàn)線性變化。此外，該算法還為學(xué)生個(gè)體增加了自我學(xué)習(xí)機(jī)制，以加快算法的收斂。但是，該教學(xué)因子設(shè)置為簡(jiǎn)單的線性變化，缺少科學(xué)性。教與學(xué)優(yōu)化算法已經(jīng)被應(yīng)用于諸多領(lǐng)域，并取得了較好的效果，其中主要包括Realistic flow shop rescheduling[4]、數(shù)據(jù)聚類問題[9]、派送問題中的參數(shù)優(yōu)化[10]、PID控制器優(yōu)化[11]、二次指派問題[12]等。

相關(guān)研究發(fā)現(xiàn)，標(biāo)準(zhǔn)TLBO算法存在著諸如解精度較低，容易早熟，后期收斂速度慢等弱點(diǎn)[5]。為了克服算法的這些弱點(diǎn)，改善其求解能力，本文提出了一種引入小世界鄰域結(jié)構(gòu)的教與學(xué)優(yōu)化（small world neighborhood TLBO，S-TLBO）算法，個(gè)體的鄰居基于小世界網(wǎng)絡(luò)技術(shù)定義，學(xué)生基于概率機(jī)制向教師學(xué)習(xí)，并向自己的鄰居進(jìn)行學(xué)習(xí)。

2　標(biāo)準(zhǔn)教與學(xué)優(yōu)化算法

算法1 TLBO算法

不失一般性，以最小化minf(x1,x2,…,xn)問題為研究實(shí)例。

輸入：種群規(guī)模N，最大迭代次數(shù)n。

輸出：最佳個(gè)體Xbest(t)。

步驟1設(shè)置算法的相關(guān)參數(shù)。

步驟2初始迭代次數(shù)t=0，并在解空間內(nèi)隨機(jī)產(chǎn)生初始種群。

步驟3計(jì)算種群中所有個(gè)體的適應(yīng)度，從中選擇適應(yīng)度最優(yōu)的個(gè)體將其設(shè)為教師Xtea(t)。

步驟4教師對(duì)學(xué)生實(shí)施教學(xué)。

步驟5學(xué)生之間進(jìn)行互相學(xué)習(xí)。

步驟6算法滿足終止條件，輸出最佳個(gè)體Xbest(t)，終止算法；否則，轉(zhuǎn)步驟3。

說(shuō)明：學(xué)生個(gè)體通過步驟4、步驟5產(chǎn)生新的子狀態(tài)，并通過優(yōu)勝劣汰的方式對(duì)自身的狀態(tài)進(jìn)行更新。

算法的詳細(xì)資料請(qǐng)參考文獻(xiàn)[1-2]。

3　小世界鄰域教與學(xué)優(yōu)化算法

現(xiàn)實(shí)生活中，人與人之間通過各種連接構(gòu)成一個(gè)復(fù)雜的網(wǎng)絡(luò)，而鄰居往往對(duì)個(gè)體的學(xué)習(xí)進(jìn)化等有較大的影響。借鑒此思想，考慮小世界網(wǎng)絡(luò)介于隨機(jī)網(wǎng)絡(luò)與結(jié)構(gòu)化網(wǎng)絡(luò)中間，因此將TLBO種群設(shè)置為小世界網(wǎng)絡(luò)結(jié)構(gòu)鄰域。

3.1相關(guān)定義

因?yàn)榻膛c學(xué)優(yōu)化算法中種群內(nèi)個(gè)體之間的學(xué)習(xí)具有雙向性，所以本文采用無(wú)向圖定義小世界網(wǎng)絡(luò)。

定義1[13]設(shè)圖G=(V,E)表示一個(gè)小世界網(wǎng)絡(luò)，其中V={v1,v2,…,v3}為節(jié)點(diǎn)集，E={e1,e2,…,en}為邊集合。

定義2[13]設(shè)存在任意兩個(gè)節(jié)點(diǎn)vi,vj∈V，如果存在∈E，則稱vi、vj互為鄰居，記N(vi)={vj|vi的鄰居}為第i個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。

3.2小世界網(wǎng)絡(luò)構(gòu)造

在本算法中，個(gè)體之間通過相互間的小世界鄰域結(jié)構(gòu)進(jìn)行信息交互，因此在種群初始化過程中首先要構(gòu)建小世界網(wǎng)絡(luò)。借助相應(yīng)的建模方法獲得小世界網(wǎng)絡(luò)。

算法2小世界網(wǎng)絡(luò)生成算法

輸入：n個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)的重聯(lián)概率p和k=2，迭代次數(shù)t。

輸出：小世界網(wǎng)絡(luò)。

步驟1將n個(gè)節(jié)點(diǎn)中的每一個(gè)連接到直接鄰居，和鄰居的鄰居生成一個(gè)k-規(guī)則網(wǎng)絡(luò)，該網(wǎng)絡(luò)的鏈路數(shù)目是m=2n條。

步驟2對(duì)于每一個(gè)鏈路，u=1,2,…,m，基于概率p重聯(lián)鏈路u。

步驟3產(chǎn)生隨機(jī)數(shù)r，如果r

3.3教師“教”行為的改進(jìn)

TLBO算法中教師為種群的最佳個(gè)體，該個(gè)體通過其教行為，提高其他個(gè)體的狀態(tài)，以加速算法的收斂。但是在該步驟中，學(xué)生個(gè)體在被“教”之后，采用優(yōu)勝劣汰的機(jī)制更新自身的狀態(tài)，往往也容易使種群陷入局部最優(yōu)。因此修改為學(xué)生個(gè)體以一定的概率向教師進(jìn)行學(xué)習(xí)，概率計(jì)算公式為：

式中，f為種群的適應(yīng)度均值；p0∈(0,1)。從該公式中可以看出，狀態(tài)越是優(yōu)秀的個(gè)體向教師學(xué)習(xí)的概率越高，狀態(tài)越差的個(gè)體，向教師學(xué)習(xí)的概率越低，這樣可以使優(yōu)秀的學(xué)生個(gè)體協(xié)助教師的搜索，而且也能夠緩解種群多樣性下降的速度。學(xué)習(xí)公式為：

其中，α=round(1+rand(0,1))是教學(xué)因子，round函數(shù)為四舍五入，rand()產(chǎn)生指定范圍內(nèi)的隨機(jī)值。學(xué)生向教師學(xué)習(xí)之后，應(yīng)用所產(chǎn)生的子狀態(tài)直接更新學(xué)生狀態(tài)。

3.4小世界鄰域下學(xué)生的“學(xué)”行為

小世界理論認(rèn)為，網(wǎng)絡(luò)中的某個(gè)節(jié)點(diǎn)只需要通過6個(gè)節(jié)點(diǎn)即可與其他節(jié)點(diǎn)發(fā)生聯(lián)系?；诖死碚?，將學(xué)生的“學(xué)”行為修改如下：

設(shè)Xi(t)為當(dāng)前個(gè)體，其直接鄰居集合為N(Xi(t))，Xi(t)則向自己鄰居集合內(nèi)最優(yōu)的個(gè)體進(jìn)行學(xué)習(xí)。如果Xi(t)的鄰居僅有一個(gè)，且是當(dāng)前教師個(gè)體Xtea(t)，則從Xtea(t)的鄰居中隨機(jī)選擇兩個(gè)個(gè)體，并擇優(yōu)進(jìn)行學(xué)習(xí)，依次類推。通過式（3）產(chǎn)生新狀態(tài)，采用優(yōu)勝劣汰的方式更新Xi(t)：

其中，Xr1(t)為被選出學(xué)習(xí)的個(gè)體。

如果Xi′(t)無(wú)法使Xi(t)得到更新，則應(yīng)用Xi′(t)隨機(jī)更新Xi(t)鄰居中比Xi′(t)劣質(zhì)的某一個(gè)個(gè)體。

3.5教師的自我提高

Tizhoosh[14]提出了反向?qū)W習(xí)（opposition based learning，OBL）的概念，并給出了反向?qū)W習(xí)的算法描述。作者隨后的研究報(bào)告指出反向解較當(dāng)前解更為靠近最優(yōu)解，該幾率幾乎是50%?，F(xiàn)實(shí)生活中，教師通常會(huì)通過自學(xué)習(xí)機(jī)制，提升自身水平，而在標(biāo)準(zhǔn)TLBO算法中，教師個(gè)體則缺少自我學(xué)習(xí)和提高?？紤]到反向?qū)W習(xí)具有較好的勘探未知解的能力，故令教師個(gè)體執(zhí)行反向?qū)W習(xí)。

定義3[14]反向解：設(shè)在區(qū)間[a,b]上存在一個(gè)實(shí)數(shù)x，則x的反向數(shù)定義為x′=a+b-x。鑒于此，假設(shè)在R域上存在某N維點(diǎn)X=(x1,x2,…,xi,…,xN)，并且 xi∈[ai,bi]，則定義 X′=(x1′,x2′,…,xi′,…,xN′)為 X的反向點(diǎn)。其中，xi′=k×(ai+bi)-xi，k為[0,1]之間分布均勻的隨機(jī)數(shù)，稱作一般化系數(shù)。

定義4基于反向解的優(yōu)化：設(shè)待優(yōu)化問題為minf(x)，存在某個(gè)可行解 X及其反向解 X′，若f(X′)

算法3 OBL算法

輸入：Xi(t)，所在區(qū)間為[a,b]，迭代次數(shù)itermax。

輸出：Xi(t)。

步驟1迭代次數(shù)t=0。

步驟2依據(jù)定義1，在迭代次數(shù)內(nèi)經(jīng)過多次迭代生成反向解種群POP(t)。

步驟3在Xi(t)和POP(t)中選擇最優(yōu)的個(gè)體替換Xi(t)，輸出并結(jié)束算法。

按照如下方法使用動(dòng)態(tài)邊界。設(shè)個(gè)體Xij的搜索空間 j維的固定邊界為[aj,bj]，相應(yīng)的 j維的動(dòng)態(tài)邊界定義為min(aij),max(aij)。在一個(gè)N維空間中，Xbest= (x1,x2,…,xi,…,xN)，其反向解定義為xi′=k×(ai+bi)-xi,xi∈[min(aij),max(aij)],k∈[0,1]，為服從均勻分布的隨機(jī)數(shù)。

3.6算法實(shí)現(xiàn)

算法4小世界鄰域教與學(xué)優(yōu)化（S-TLBO）算法

輸入：種群POP(0)，迭代次數(shù)n。

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

步驟1初始化算法的參數(shù)，在解空間內(nèi)隨機(jī)產(chǎn)生初始種群POP(0)，迭代計(jì)數(shù)器t=0。

步驟2應(yīng)用算法2構(gòu)建小世界網(wǎng)絡(luò)。

步驟3選擇班級(jí)種群內(nèi)的最優(yōu)個(gè)體設(shè)為教師Xtea(t)。

步驟4計(jì)算班級(jí)的平均分Xmean(t)，平均適應(yīng)度f(wàn)，計(jì)算教師對(duì)學(xué)生個(gè)體執(zhí)行“教”的概率，并依據(jù)式（2）對(duì)學(xué)生執(zhí)行“教”行為。

步驟5個(gè)體Xi(t)依據(jù)3.4節(jié)執(zhí)行“學(xué)”行為。

步驟6如果教師的狀態(tài)長(zhǎng)時(shí)間得不到更新，則教師個(gè)體執(zhí)行OBL算法。

步驟7算法滿足結(jié)束條件，則輸出Xbest(t)，結(jié)束算法；否則轉(zhuǎn)步驟3。

在S-TLBO算法中，整體種群組成了一個(gè)小世界網(wǎng)絡(luò)，個(gè)體之間的“學(xué)”行為是向自己的鄰居（或鄰居的鄰居等）進(jìn)行學(xué)習(xí)，使這種學(xué)習(xí)具有了一定的目的性和偏好，加速了算法的收斂，同時(shí)也保證了一定程度上的隨機(jī)性。

4　仿真實(shí)驗(yàn)與分析

4.1非約束函數(shù)上的測(cè)試

為了驗(yàn)證算法的有效性，將S-TLBO算法應(yīng)用C語(yǔ)言編碼，并在VC6下編譯執(zhí)行，選擇AFSA（artificial fish swarm algorithm）[15]、TLBO算法以及兩個(gè)經(jīng)典的改進(jìn)TLBO算法（ITLBO[2]、ETLBO[5]）參與對(duì)比。AFSA算法的視野范圍visual=4，移動(dòng)步長(zhǎng)step= 1.2，擁擠度因子delta=0.3，嘗試次數(shù)try_number=5。所有算法的種群均設(shè)置為30，其他參數(shù)參考相關(guān)文獻(xiàn)進(jìn)行設(shè)置。用于測(cè)試的9個(gè)Benchmark函數(shù)列于表1，包括了多個(gè)單峰和多峰函數(shù)。實(shí)驗(yàn)中將待優(yōu)化函數(shù)設(shè)為50維和200維，f1~f6的迭代次數(shù)是1 000次，f7~f9的迭代次數(shù)為5 000次，分別測(cè)試算法在高維和低維度函數(shù)上的尋優(yōu)效果。將5個(gè)算法獨(dú)立運(yùn)行30次，分別取平均值M，收斂成功的次數(shù)N，解方差D，求解結(jié)果分別列于表2和表3。

Table 1　Testing functions表1 測(cè)試函數(shù)列表

首先分析當(dāng)函數(shù)是50維時(shí)的表現(xiàn)。f1是一個(gè)單峰函數(shù)，只有一個(gè)全局最優(yōu)值，比較容易優(yōu)化。由表2中的數(shù)據(jù)可以看出，AFSA算法的解精度和解方差均比較差，且收斂成功的次數(shù)為0，而本文提出的S-TLBO算法的表現(xiàn)則是5個(gè)算法中最優(yōu)的，其不僅解精度最高，解方差也最小，成功收斂的次數(shù)也是最高的。在 f2函數(shù)上，S-TLBO算法在解的均值上的表現(xiàn)仍然相對(duì)其他參與對(duì)比的算法優(yōu)秀，但是其解方差要低于ETLBO和ITLBO兩個(gè)算法，優(yōu)于AFSA算法。在 f3函數(shù)上，S-TLBO算法仍然保持了較高的精度和收斂成功率，并且解的方差也要優(yōu)于其他4個(gè)算法。f4函數(shù)是一個(gè)難以優(yōu)化的多峰函數(shù)，S-TLBO算法的表現(xiàn)較ETLBO稍差，但是仍然要優(yōu)于AFSA和TLBO兩個(gè)算法，與ITLBO算法基本相當(dāng)。在 f5函數(shù)的測(cè)試上，S-TLBO算法表現(xiàn)出了較高的解精度和解方差。f6仍然是一個(gè)多峰函數(shù)，主要用于測(cè)試算法逃脫局部最優(yōu)約束的能力，從表中所列數(shù)據(jù)可以看出，在此函數(shù)上，S-TLBO算法表現(xiàn)得較好，是全部5個(gè)算法中表現(xiàn)最優(yōu)的。f7、f8、f9均是多峰函數(shù)，3個(gè)函數(shù)在其解空間內(nèi)均存在多個(gè)局部極值，對(duì)算法逃脫局部極值約束的能力要求較高，尤其是 f9函數(shù)，在距離最優(yōu)解3.14距離處存在無(wú)窮個(gè)局部極值，且強(qiáng)烈震蕩。在 f7函數(shù)上，所有5個(gè)算法的成功率均為0，但是從解精度看，TLBO相關(guān)的4個(gè)算法的精度還是較AFSA算法高，最好的是ETLBO算法，其次是S-TLBO算法，在解精度的指標(biāo)上，S-TLBO算法是最好的。在 f8函數(shù)上，TLBO及其改進(jìn)算法表現(xiàn)得幾乎是一致的，解精度相當(dāng)接近，說(shuō)明TLBO算法本身的求解機(jī)制非常適合求解該函數(shù)，優(yōu)化后解的改進(jìn)效果不明顯，S-TLBO算法的表現(xiàn)也一般。在 f9函數(shù)上，S-TLBO算法的優(yōu)越性得以體現(xiàn)，其解精度和解方差明顯優(yōu)于其他4個(gè)算法，在迭代次數(shù)內(nèi)已經(jīng)非常接近最優(yōu)值，考慮到 f9具有強(qiáng)烈震蕩性，說(shuō)明S-TLBO算法能夠非常好地?cái)[脫該函數(shù)的局部最優(yōu)約束和震蕩的影響。

其次，分析函數(shù)維度增加到200時(shí)5個(gè)算法的表現(xiàn)。從表3所列數(shù)據(jù)可以看出，在維度增加到比較高的200時(shí)，幾乎所有算法的求解能力均有所下降，在f1、f3、f4函數(shù)上，S-TLBO算法并沒有表現(xiàn)最好，解精度較ITLBO或ETLBO算法略低，基本在一個(gè)數(shù)量級(jí)。在 f2、f5、f6函數(shù)上的解精度則是最好的。在f2、f3、f4、f5函數(shù)上的方差最好，在 f1函數(shù)上的方差劣于ITLBO，在 f6函數(shù)上的方差劣于ETLBO。在f7函數(shù)上，S-TLBO算法的解精度、解方差均是最優(yōu)的。因?yàn)?f8、f9函數(shù)的維度是固定的，測(cè)試數(shù)據(jù)基本沒有變化。

分別對(duì)比5個(gè)算法達(dá)到指定收斂精度時(shí)的迭代次數(shù)和時(shí)間。函數(shù)為50維時(shí) f1~f6的精度為0.01，f7~f9的精度為10，200維時(shí) f1~f9的精度為0.1，數(shù)據(jù)列于表4和表5。表中的“—”表示該算法在所設(shè)定迭代次數(shù)內(nèi)沒有達(dá)到指定的收斂精度，D=200時(shí)因?yàn)锳FSA難以在設(shè)定迭代次數(shù)（10 000）內(nèi)達(dá)到指定要求，所以不再對(duì)比AFSA。從表4所列數(shù)據(jù)可以看出，S-TLBO算法在9個(gè)函數(shù)上達(dá)到設(shè)定的精度，所需的迭代次數(shù)是最小的，但是時(shí)間卻不是最小的。這是因?yàn)镾-TLBO算法中增加了生成復(fù)雜網(wǎng)絡(luò)的操作，同時(shí)也調(diào)整了教師的教行為，所以較其他相關(guān)算法的運(yùn)行時(shí)間多一些。而AFSA、TLBO算法在3個(gè)多峰函數(shù)上沒有收斂到指定的精度。當(dāng)維度為200時(shí)，TLBO算法在 f4、f5、f9函數(shù)上沒有達(dá)到設(shè)定精度。其他3個(gè)算法的迭代次數(shù)與消耗時(shí)間均有所增加，但S-TLBO算法所需迭代次數(shù)仍然較少，在時(shí)間上雖然不是最少，但是與其他兩個(gè)算法基本相差無(wú)幾。

Table 2　Comparison of mean,convergence number and variance for unconstrained benchmark functions(Dim=50)表2　在非約束函數(shù)上算法的求解均值、成功收斂次數(shù)和方差（Dim=50）

Table 3　Comparison of mean,convergence number and variance results for unconstrained benchmark functions(Dim=200)表3　在非約束函數(shù)上算法的求解均值、成功收斂次數(shù)和方差（Dim=200）

為了更為形象地對(duì)比算法的收斂性能，繪制了全部參與對(duì)比實(shí)驗(yàn)的5個(gè)算法的收斂曲線圖。限于篇幅，僅列出其中的 f1~f6函數(shù)圖。收斂圖使用的數(shù)據(jù)是取算法30次實(shí)驗(yàn)中最好一次和最差一次的平均值，函數(shù)維度為50。6個(gè)收斂圖分別如圖1~圖6所示。從收斂曲線可以看出，S-TLBO算法的收斂曲線是很平滑的，而且下降速度非?？?，在所有的6個(gè)函數(shù)上明顯優(yōu)于AFSA和標(biāo)準(zhǔn)TLBO算法，對(duì)比ETLBO 和ITLBO算法也可以看出S-TLBO算法明顯具有一定的優(yōu)勢(shì)。

4.2約束函數(shù)的測(cè)試

為了對(duì)比得更加全面，繼續(xù)選擇文獻(xiàn)[6]中的5個(gè)約束函數(shù)進(jìn)行測(cè)試（本文分別對(duì)應(yīng) f10~f14）。參與測(cè)試算法的參數(shù)設(shè)置與3.1節(jié)相同，4個(gè)算法各自獨(dú)立運(yùn)行30次，取最優(yōu)值、平均值和解方差進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果列于表6。由表6中所列實(shí)驗(yàn)結(jié)果可以看出，S-TLBO算法在求解約束函數(shù)的實(shí)驗(yàn)中表現(xiàn)優(yōu)秀，f10、f12兩個(gè)函數(shù)找到了最優(yōu)解，在其他3個(gè)函數(shù)上找到的最優(yōu)解、平均值和解方差也均是4個(gè)算法中最優(yōu)的，比標(biāo)準(zhǔn)的TLBO算法有了非常大的提高。

Table 4　Interation number and cost time(Dim=50)表4　算法的平均迭代次數(shù)和時(shí)間（Dim=50）

Table 5　Interation number and cost time(Dim=200)表5　算法的平均迭代次數(shù)和時(shí)間（Dim=200）

Fig.1　Convergence curves of algorithms inf1圖1　f1函數(shù)上的收斂曲線

Fig.2　Convergence curves of algorithms inf2圖2　f2函數(shù)上的收斂曲線

Fig.3　Convergence curves of algorithms inf3圖3　f3函數(shù)上的收斂曲線

Fig.4　Convergence curves of algorithms inf4圖4　f4函數(shù)上的收斂曲線

Fig.5　Convergence curves of algorithms inf5圖5　f5函數(shù)上的收斂曲線

Fig.6　Convergence curves of algorithms inf6圖6　f6函數(shù)上的收斂曲線

Table 6　Results of constrained benchmark functions表6　在約束函數(shù)上的測(cè)試結(jié)果比較

綜合以上實(shí)驗(yàn)結(jié)果與分析可以看到，雖然S-TLBO算法在某些函數(shù)上的性能指標(biāo)不是最佳的，但是無(wú)論是對(duì)低維函數(shù)還是高維函數(shù)，S-TLBO算法整體的表現(xiàn)都是非常穩(wěn)定的，在約束函數(shù)的測(cè)試中，也明顯優(yōu)于其他算法。

5　結(jié)束語(yǔ)

本文提出了一種鄰域?yàn)樾∈澜缇W(wǎng)絡(luò)結(jié)構(gòu)的改進(jìn)教與學(xué)優(yōu)化算法?；赪S算法將種群進(jìn)行了小世界網(wǎng)絡(luò)構(gòu)建。在教學(xué)階段中，學(xué)生基于概率向教師學(xué)習(xí)，該概率由學(xué)生個(gè)體的適應(yīng)度和教師適應(yīng)度計(jì)算而得，學(xué)習(xí)后應(yīng)用臨時(shí)狀態(tài)直接更新原狀態(tài)。在互相學(xué)習(xí)過程中，學(xué)生在自己的直接鄰居節(jié)點(diǎn)或間接鄰居節(jié)點(diǎn)中隨機(jī)選擇個(gè)體進(jìn)行學(xué)習(xí)。為了提高最佳個(gè)體的勘探新解和開采能力，引入了教師個(gè)體的反向?qū)W習(xí)。在多個(gè)約束函數(shù)和非約束函數(shù)上的實(shí)驗(yàn)表明，本文算法的求解能力較標(biāo)準(zhǔn)TLBO算法有了較大幅度的提高，適合求解較高維度連續(xù)函數(shù)的優(yōu)化問題。鄰域結(jié)構(gòu)是影響群體智能算法效率的重要因素之一，將進(jìn)一步深入研究不同鄰域結(jié)構(gòu)下TLBO的求解能力。同時(shí)，研究其與經(jīng)典演化算法的相互結(jié)合模式，拓展其應(yīng)用領(lǐng)域，亦是重要的研究方向。

References:

[1]Chen Debao,Zou Feng,Li Zheng.An improved teachinglearning-based optimization algorithm for solving global optimization problem[J].Information Sciences,2015,297: 171-190.

[2]Kundu S,Biswas S,Das S,et al.A selective teaching-learning based niching technique with local diversification strategy [C]//LNCS 7677:Proceedings of the 3rd International Conference on Swarm,Evolutionary,and Memetic Computing, Bhubaneswar,India,Dec 20-22,2012.Berlin,Heidelberg: Springer,2012:160-168.

[3]Rao R V,Patel V.An improved teaching learning based optimization algorithm for solving unconstrained optimization problems[J].Scientia Iranica,2013,20(3):710-720.

[4]Li Junqing,Pan Quanke,Mao Kun.A discrete teachinglearning-based optimisation algorithm for realistic flowshop rescheduling problems[J].Engineering Applications ofArtificial Intelligence,2015,37:279-292.

[5]Rao R V,Patel V.An elitist teaching learning based optimization algorithm for solving complex constrained optimization problems[J].International Journal of Industrial Engineering Computations,2012,3(4):535-560.

[6]Yu Kunjie,Wang Xin,Wang Zhenlei.Elitist teaching-learningbased optimization algorithm based on feedback[J].Acta Automatica Sinica,2014,40(9):1976-1983.

[7]Rajasekhar A,Rani R,Ramya K,et al.Elitist teachinglearning opposition based algorithm for global optimization [C]//Proceedings of the 2012 IEEE International Conference on Systems,Man,and Cybernetics,Seoul,Oct 14-17, 2012.Piscataway,USA:IEEE,2012:1124-1129.

[8]Rao R V,Patel V.Multi objective optimization of two stage thermoelectric coolers using a modified teaching-learningbased optimization algorithm[J].Engineering Applications ofArtificial Intelligence,2013,26(1):430-445．

[9]Nayak J,Naik B,Kanungo D P,et al.A hybrid elicit teaching learning based optimization with fuzzy C-means algorithm for data clustering[J].Ain Shams Engineering Journal,2016 (5):148-156.

[10]Durai S,Subramanian S,Ganesan S.Improved parameters for economic dispatch problems by teaching learning optimization[J].Electrical Power and Energy Systems,2015, 67:11-24.

[11]Sahu B K,Pati T K,Nayak J R,et al.A novel hybrid LUSTLBO optimized fuzzy-PID controller for load frequency control of multi-source power system[J].Electrical Power and Energy Systems,2016,74:58-69.

[12]Dokeroglu T.Hybrid teaching-learning-based optimization algorithms for the quadratic assignment problem[J].Computers&Industrial Engineering,2015,85:86-101.

[13]Li Wenbin,Chen Yiying,He Yichao,et al.New different evolution with neighborhood structure based on complex network[J],Application Research of Computers,2016,32 (2):370-374.

[14]Tizhoosh H R.Opposition-based learning:a new scheme for machine intelligence[C]//Proceedings of the 2005 IEEE International Conference on Computational Intelligence for Modelling,Control and Automation,Vienna,Nov 28-30, 2005.Piscataway,USA:IEEE,2005:695-701.

[15]Wang Peichong.Swarm intelligence algorithms and their applications[M].Beijing:Publishing House of Electronics Industry,2015.

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

[6]于坤杰,王昕,王振雷.基于反饋的精英教學(xué)優(yōu)化算法[J].自動(dòng)化學(xué)報(bào),2014,40(9):1976-1983.

[13]李文斌,陳嶷瑛,賀毅朝,等.鄰域結(jié)構(gòu)為復(fù)雜網(wǎng)絡(luò)的差分演化算法[J].計(jì)算機(jī)應(yīng)用研究,2016,32(2):370-374.

[15]王培崇.群體智能算法及其應(yīng)用[M].北京:電子工業(yè)出版社,2015.

WANG Peichong was born in 1972.He received the Ph.D.degree from China University of Mining and Technology (Beijing)in 2010.Now he is an associate professor at College of Information Engineering,Hebei GEO University, and the member of CCF.His research interests include evolutionary computation,machine learning and pattern recognization,etc.He has published more than 30 papers in domestic and international journals and conferences.

王培崇（1972—），男，河北辛集人，2010年于中國(guó)礦業(yè)大學(xué)（北京）計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)獲得博士學(xué)位，現(xiàn)為河北地質(zhì)大學(xué)信息工程學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)檫M(jìn)化計(jì)算，機(jī)器學(xué)習(xí)，模式識(shí)別等。發(fā)表學(xué)術(shù)論文30余篇。

MAYue was born in 1993.She is an M.S.candidate at Hebei GEO University.Her research interests include artificial intelligence and machine learning,etc.

馬玥（1993—），女，山東濰坊人，河北地質(zhì)大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)槿斯ぶ悄埽瑱C(jī)器學(xué)習(xí)等。

GENG Mingyue was born in 1994.She is an M.S.candidate at Chongqing University of Posts and Telecommunications,and the student member of CCF.Her research interest is digital image processing.

WANG Shenwen was born in 1979.He received the Ph.D.degree from Wuhan University in 2014.Now he is an associate professor at College of Information Engineering,Hebei GEO University.His research interests include evolutionary computation and machine learning,etc.

汪慎文（1979—），男，湖北紅安人，2014年于武漢大學(xué)計(jì)算機(jī)學(xué)院獲得博士學(xué)位，現(xiàn)為河北地質(zhì)大學(xué)信息工程學(xué)院副教授，主要研究領(lǐng)域?yàn)檠莼?jì)算，機(jī)器學(xué)習(xí)等。

New Teaching-Learning-Based Optimization with Neighborhood Structure Based on Small World?

WANG Peichong1,2+,MAYue1,GENG Mingyue3,WANG Shenwen1
1.College of Information Engineering,Hebei GEO University,Shijiazhuang 050031,China
2.College of Mechanical Electronic and Information Engineering,China University of Mining and Technology,Beijing 100083,China
3.College of Computer,Chongqing University of Posts and Telecommunications,Chongqing 400065,China
+Corresponding author:E-mail:wpeichong@126.com

WANG Peichong,MA Yue,GENG Mingyue,et al.New teaching-learning-based optimization with neighborhood structure based on small world.Journal of Frontiers of Computer Science and Technology,2016,10(9)：1341-1350.

Teaching-learning-based optimization(TLBO)is a recently proposed swarm intelligent algorithm that simulates the process of teaching and learning.Concerning the problems that TLBO is easy to premature,low solution precision,slow convergence speed of weakness,this paper proposes an improved TLBO named S-TLBO(small world neighborhood TLBO).S-TLBO adopts small world network as its spatial structure,and individuals of S-TLBO is looked as the nodes of network.In teaching phase,student individuals learn from teacher individual based on probability,and they learn from their neighbor nodes which are better in learning phase.The best in dividual exe-cutes opposition based learning(OBL)algorithm to exploiting and exploring.Some experiments are conducted on many classical testing functions,the results show that the improved algorithm has superior global convergence and higher precision,especially fits for solving multimode and high dimension function optimization problems.

2016-04,Accepted 2016-06.

teaching-learning-based optimization(TLBO);small world network;neighborhood structure;opposition based learning(OBL)

*The National Natural Science Foundation of China under Grant No.61402481(國(guó)家自然科學(xué)基金);the Natural Science Foundation of Hebei Province under Grant No.F2015403046(河北省自然科學(xué)基金);the Key Research Plan of Hebei Province under Grant No. 15210710(河北省重點(diǎn)研發(fā)計(jì)劃).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-06-02,http://www.cnki.net/kcms/detail/11.5602.TP.20160602.1144.010.html

A

TP301.6