具有動(dòng)態(tài)自適應(yīng)學(xué)習(xí)機(jī)制的教與學(xué)優(yōu)化算法

李麗榮，李木子，李崔燦，王培崇

1.河北地質(zhì)大學(xué) 藝術(shù)設(shè)計(jì)學(xué)院，石家莊050031

2.河北地質(zhì)大學(xué) 信息工程學(xué)院，石家莊050031

3.河北地質(zhì)大學(xué) 人工智能與機(jī)器學(xué)習(xí)研究所，石家莊050031

1 引言

群智能[1-3]算法是通過(guò)模擬生活中的自然現(xiàn)象或某些動(dòng)、植物群體間競(jìng)爭(zhēng)、協(xié)作進(jìn)化等行為，實(shí)現(xiàn)對(duì)優(yōu)化問(wèn)題的求解。Rao 和何雨潔等人[4-5]提出的教與學(xué)優(yōu)化（Teaching and Learning Based Optimization，TLBO）就是具有代表性的群智能算法之一，且已被應(yīng)用于多個(gè)工業(yè)或?qū)W術(shù)領(lǐng)域。如：Data Clustering[6]，生物醫(yī)學(xué)中的TDC時(shí)間數(shù)字轉(zhuǎn)換器的優(yōu)化[7]，工業(yè)機(jī)器人裝配序列規(guī)劃優(yōu)化[8]，拆卸服務(wù)生產(chǎn)線(xiàn)中的服務(wù)平衡優(yōu)化問(wèn)題[9]，集合聯(lián)盟背包問(wèn)題[10]等。

在TLBO 算法中，標(biāo)記最優(yōu)個(gè)體為“教師”，其他個(gè)體為“學(xué)生”，通過(guò)模擬一個(gè)班級(jí)中的“教”和“學(xué)”兩種行為，實(shí)現(xiàn)對(duì)問(wèn)題的求解。算法原理簡(jiǎn)單、參數(shù)較少、易理解，且收斂速度較快。但是，相關(guān)的研究表明，當(dāng)待優(yōu)化問(wèn)題的維度較高時(shí)，該算法也容易出現(xiàn)收斂速度變慢、陷入局部最優(yōu)等弱點(diǎn)[10]。為了克服算法的這些弱點(diǎn)，改善其性能，文獻(xiàn)[11]提出了一種改進(jìn)算法（ICTLBO），該算法將種群劃分成多個(gè)子種群?！敖獭边^(guò)程中，個(gè)體通過(guò)所在子種群的平均位置和教師個(gè)體間的差異信息，被引導(dǎo)著向全局最優(yōu)所在區(qū)域收斂。同時(shí)子種群間實(shí)施信息交換，以逃離局部最優(yōu)的約束。在“學(xué)”階段引入了全新的學(xué)習(xí)機(jī)制，提高種群的多樣性，并設(shè)計(jì)了針對(duì)三種不同約束情況的處理策略。文獻(xiàn)[12]在TLBO中引入多教師，并將“教”過(guò)程中的TF參數(shù)修改為自適應(yīng)變化，同時(shí)又引入了討論學(xué)習(xí)和自我激勵(lì)學(xué)習(xí)機(jī)制。一系列的實(shí)驗(yàn)表明，算法改進(jìn)后效果明顯。文獻(xiàn)[13]在TLBO 中引入局部學(xué)習(xí)機(jī)制和自適應(yīng)學(xué)習(xí)機(jī)制，以提高算法的搜索能力。在“學(xué)”階段，當(dāng)前個(gè)體不僅向種群內(nèi)的最優(yōu)個(gè)體學(xué)習(xí)，而且也向隨機(jī)產(chǎn)生的個(gè)體學(xué)習(xí)。在自我學(xué)習(xí)階段，當(dāng)前個(gè)體要么依賴(lài)自身的梯度信息更新自身狀態(tài)，要么依據(jù)種群的平均位置和個(gè)體的差異度，隨機(jī)勘探新位置。迭代多次后，所有的個(gè)體重新排列。于坤杰等[14]針對(duì)TLBO算法中種群間缺少信息交流和反饋的問(wèn)題，提出了一種精英反饋學(xué)習(xí)機(jī)制，利用精英個(gè)體的強(qiáng)反饋能力引導(dǎo)種群內(nèi)狀態(tài)較差的個(gè)體快速收斂。王滔高等[15]提出了一種基于種群結(jié)構(gòu)分層的改進(jìn)機(jī)制。將學(xué)生種群依班級(jí)的平均成績(jī)劃分為多個(gè)等級(jí)層次，種群的進(jìn)化狀態(tài)自底向上更新，有效緩解了算法易陷入局部最優(yōu)的問(wèn)題。張琳琳等[16]提出了一種基于四邊形網(wǎng)狀元胞自動(dòng)機(jī)模型來(lái)處理種群的鄰域和種群更新規(guī)則。何杰光等[17]提出將個(gè)體分為全局和局部?jī)煞N維度。種群內(nèi)的個(gè)體采用全局維度和局部維度混合更新，并設(shè)置兩種權(quán)重動(dòng)態(tài)調(diào)整更新的維度數(shù)量。后期引入自我學(xué)習(xí)機(jī)制，強(qiáng)化搜索最優(yōu)個(gè)體周邊和邊界信息。文獻(xiàn)[18]提出了一種應(yīng)用經(jīng)驗(yàn)信息和變異操作的改進(jìn)TLBO 算法。參考DE算法的變異操作，在“教”和“學(xué)”兩個(gè)階段引入不同的變異操作。文獻(xiàn)[19]在精英教與學(xué)優(yōu)化算法基礎(chǔ)上提出了一種具有多教師和自我激勵(lì)學(xué)習(xí)的改進(jìn)TLBO。文獻(xiàn)[20]在TLBO中引入基于個(gè)體差異的自主多機(jī)制學(xué)習(xí)，同時(shí)令當(dāng)前個(gè)體執(zhí)行融合高斯搜索的反思機(jī)制，協(xié)助其跳出局部最優(yōu)的約束。

為了克服標(biāo)準(zhǔn)TLBO算法的弱點(diǎn)，本文提出了一種具有自適應(yīng)學(xué)習(xí)的教與學(xué)優(yōu)化算法，在“教”算子中引入非線(xiàn)性自適應(yīng)變化的學(xué)習(xí)因子δ，以克服算法的早熟。算法后期令教師個(gè)體執(zhí)行動(dòng)態(tài)隨機(jī)搜索（Dynamic Random Searching，DRS）策略，加強(qiáng)最優(yōu)個(gè)體勘探新解的能力。

2 教與學(xué)優(yōu)化算法

標(biāo)準(zhǔn)教與學(xué)優(yōu)化算法有兩個(gè)主要算子，分別是“教”和“學(xué)”。

3 動(dòng)態(tài)自適應(yīng)教與學(xué)優(yōu)化算法

3.1 動(dòng)態(tài)自適應(yīng)學(xué)習(xí)

TLBO算法思想源于模擬班級(jí)的教學(xué)過(guò)程，所以從生活中的現(xiàn)象著手改進(jìn)算法是一種可行的途徑?？紤]在教師的“教”過(guò)程中，學(xué)生新?tīng)顟B(tài)的生成取決于自身狀態(tài)的轉(zhuǎn)化比例和通過(guò)學(xué)習(xí)所獲得知識(shí)的轉(zhuǎn)化比例之和。而標(biāo)準(zhǔn)算法中公式（1）的rand(0,1)×(Xt(t)-β×Xm(t))部分為學(xué)生向教師學(xué)習(xí)獲得的知識(shí)，而該式中學(xué)生自身的知識(shí)狀態(tài)完全向新?tīng)顟B(tài)轉(zhuǎn)化，與現(xiàn)實(shí)情況不相符。故將式（1）修改成為式（3），學(xué)生的原狀態(tài)按比例向新?tīng)顟B(tài)進(jìn)行轉(zhuǎn)換。

δ=1/(1+exp(k×(T-2×t)/T))∈(0,1)是一個(gè)非線(xiàn)性自適應(yīng)因子，T 為預(yù)設(shè)最大迭代次數(shù)，t 為當(dāng)前迭代次數(shù)，k 為變化速率。很容易看出來(lái)，在算法早期，種群主要向教師個(gè)體學(xué)習(xí)，可以快速向最優(yōu)個(gè)體周?chē)繑n。而隨著迭代的進(jìn)行δ 逐漸增大，個(gè)體維持自身狀態(tài)能力增強(qiáng)，減緩了向最優(yōu)個(gè)體靠近的速度，避免過(guò)早的聚集于教師周?chē)?。而這種機(jī)制也與生活中學(xué)生的學(xué)習(xí)行為一致，在早期學(xué)生能力較差時(shí)，主要向教師學(xué)習(xí)，快速提升班級(jí)的平均分。后期學(xué)生狀態(tài)提升之后，學(xué)生會(huì)有選擇的吸收教師傳授的知識(shí)，保持自己狀態(tài)的能力增強(qiáng)。

3.2 教師的動(dòng)態(tài)隨機(jī)搜索

DRS 通過(guò)動(dòng)態(tài)調(diào)整步長(zhǎng)實(shí)現(xiàn)對(duì)個(gè)體周?chē)臻g的精細(xì)搜索。在群智能算法中，種群的最優(yōu)個(gè)體包含了較多的引導(dǎo)種群向全局最優(yōu)收斂的信息。如果群智能算法能夠?qū)崿F(xiàn)全局收斂，最優(yōu)個(gè)體所形成的搜索空間，一定包含著全局最優(yōu)解形成的搜索空間。所以，為了提高算法的精度，在算法后期（本文為預(yù)設(shè)迭代次數(shù)的2/3后開(kāi)始）引入教師個(gè)體執(zhí)行DRS。

算法1DRS算法

輸入：個(gè)體X，迭代次數(shù)n。

輸出：個(gè)體X。

步驟1 初始化步長(zhǎng)d。

步驟2 生成向量X′∈[-d,d]。

步驟4 生成向量X1=X+X′和X2=X-X′。

步驟5 選擇X1,X2,X 中優(yōu)者作為X 。

步驟6 調(diào)整步長(zhǎng)d。

步驟7 迭代沒(méi)有結(jié)束，則轉(zhuǎn)步驟2；否則輸出X ，結(jié)束算法。

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

算法2動(dòng)態(tài)自適應(yīng)教與學(xué)優(yōu)化算法（Dynamic Selfadapting Learning TLBO，DSLTLBO）

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

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

步驟1 在解空間內(nèi)初始化種群POP。

步驟2 挑選出最優(yōu)個(gè)體，即教師個(gè)體，標(biāo)記為Xt(t)。

步驟3 基于公式（3）執(zhí)行“教”。

步驟4 執(zhí)行“學(xué)”算子。

步驟5 如果是算法后期，則教師個(gè)體執(zhí)行DRS算法。

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

3.4 算法的收斂性

證明分析DSLTLBO中個(gè)體Xi(t)的搜索。算法早期，“教”算子執(zhí)行過(guò)程，該個(gè)體主要向Xt(t)學(xué)習(xí)，即向最優(yōu)個(gè)體靠近。這種能力，隨著δ 的逐漸增加而被抑制，Xi(t)保持自身狀態(tài)的能力逐漸加強(qiáng)，豐富了種群多樣性，減輕了“教”算子帶來(lái)的過(guò)早的收斂壓力。算法后期，Xt(t)開(kāi)始執(zhí)行DRS 算法，加強(qiáng)搜索周?chē)木植靠臻g，算法全局、局部搜索得以平衡。DSLTLBO中的“學(xué)”算子，賦予了Xi(t)跳出局部最優(yōu)約束的能力。

不失一般性，以最小化問(wèn)題min f(X)為研究對(duì)象。設(shè)解空間A 內(nèi)有s 個(gè)局部最優(yōu)區(qū)域A1,A2,…,As，則DSLTLBO迭代過(guò)程中，個(gè)體Xi(t)負(fù)責(zé)區(qū)域Ai的搜索，據(jù)引理2 知，Xi(t)必收斂到該區(qū)域的最優(yōu)值Yi。由于Xi(t)執(zhí)行“學(xué)”，隨機(jī)向某一個(gè)同伴Xk(t)學(xué)習(xí)，所以會(huì)搜索該個(gè)體所在空間Ak(t)。類(lèi)推可得，所有局部最優(yōu)區(qū)域會(huì)被依次訪問(wèn)，且可保證收斂到相應(yīng)的局部最優(yōu)值，將它們分別標(biāo)記為：X1b(t),X2b(t),…,Xsb(t)。

由于采取保優(yōu)策略，如果迭代次數(shù)足夠多，則Xgb=min{X1b(t),X2b(t),…,Xib(t)} 必然會(huì)收斂到全局最優(yōu)，即DSLTLBO算法能夠以概率1收斂到全局最優(yōu)。

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

設(shè)算法的迭代次數(shù)是M ，種群規(guī)模n，則算法的時(shí)間復(fù)雜度是O(M×n) ，空間復(fù)雜度是O(n) ?？梢钥闯觯疚牡乃惴ú](méi)有增加TLBO的時(shí)間復(fù)雜度和空間復(fù)雜度。

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

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)

為了驗(yàn)證算法的性能，基于C 編程實(shí)現(xiàn)DSLTLBO算法，并選擇了文獻(xiàn)[22]中的10個(gè)基準(zhǔn)函數(shù)進(jìn)行性能測(cè)試，分別是：f1：sphere、f2：Rastrigin、f3：Schwefel、f4：Rosenbroke、f5：Griewank、f6：Ackley、f7：Quadric、f8：Schwefel、f9：Six-Hump Camel-Back、f10：Schaffer。除f9最優(yōu)值是-1.031 628 5，f10的最優(yōu)值是-1，其余函數(shù)的最優(yōu)值均為0，函數(shù)維度設(shè)為30 和100。選擇了DE、PSO、AFSA、TLBO[4]、ITLBO[12]、FETLBO[14]、HSTLBO[15]等算法來(lái)做對(duì)比，DE、PSO、AFSA是較為典型的群智能算法，其他為近年來(lái)出現(xiàn)的典型TLBO改進(jìn)策略。

算法的參數(shù)設(shè)置：函數(shù)維度為30時(shí)，所有算法的種群規(guī)模均為30，迭代次數(shù)為500次。函數(shù)維度為100時(shí)，種群規(guī)模為50；迭代次數(shù)設(shè)為f1：1 000次，f2：1 500次，f3：1 000 次，f4：1 000 次，f5：2 000 次，f6：1 500 次，f7：1 000 次，f8：1 000 次，f9：2 000 次，f10：2 000 次。函數(shù)的評(píng)價(jià)精度為：f1～f8：10-6，f9和f10的精度為：10-3。為了對(duì)比公平，且忽略掉其他因素的干擾，算法都獨(dú)立運(yùn)行30 次。DE、PSO、AFSA 參數(shù)均參考相關(guān)文獻(xiàn)設(shè)置。

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

表1 和表2 分別列出了函數(shù)維度是30 和100 時(shí)，參與對(duì)比實(shí)驗(yàn)算法的解精度和解方差。當(dāng)函數(shù)維度為30時(shí)，f1是一個(gè)比較容易優(yōu)化的單峰函數(shù)，此時(shí)的FETLBO算法表現(xiàn)最優(yōu)，DSLTLBO 和HSTLBO 算法稍遜，但是比較ITLBO、TLBO、DE 三個(gè)算法有較大的優(yōu)勢(shì)。對(duì)于f2、f4兩個(gè)多峰函數(shù)，本文的DSLTLBO 算法表現(xiàn)是最優(yōu)的，在其他的幾個(gè)多峰和單峰函數(shù)上的表現(xiàn)，或者稍遜于HSTLBO 或者稍遜于FETLBO，但是總體要強(qiáng)于ITLBO 等算法。f9、f10是兩個(gè)比較難以?xún)?yōu)化的函數(shù)，需要算法具有較好的跳出局部最優(yōu)約束的能力，DSLTLBO算法的表現(xiàn)還是很優(yōu)秀，和FETLBO、HSTLBO兩個(gè)算法在精度和解方差上旗鼓相當(dāng)，要較ITLBO、TLBO 算法的解精度高出了很多。另外，觀察表1 中各個(gè)算法的解方差，可以看出DSLTLBO 算法的穩(wěn)定性在f1、f6、f7、f9、f10上是最好的。

表1 30維時(shí)算法在Benchmark函數(shù)上的運(yùn)算結(jié)果（均值/方差）

表2 100維時(shí)算法在Benchmark函數(shù)上的運(yùn)算結(jié)果（均值/方差）

當(dāng)待優(yōu)化函數(shù)維度增加為100時(shí)，對(duì)群智能算法擺脫局部最優(yōu)約束的能力要求更高，同時(shí)對(duì)算法后期勘探新解的能力要求也有所增加。對(duì)比表2 和表1 的數(shù)值，可以看出，參與對(duì)比算法的解精度和解方差均有所下降，橫向?qū)Ρ瓤梢钥闯鯰LBO、DE、AFSA、PSO四個(gè)算法相對(duì)下降較多，對(duì)比算法中的FETLBO、HSTLBO、DSLTLBO 相對(duì)下降較少；DSLTLBO 的解精度在f1、f2、f3、f8四個(gè)函數(shù)上表現(xiàn)最好優(yōu)于其他算法，在f6、f7、f9、f10上和HSTLBO、FETLBO 算法基本一樣。但是f4、f5兩個(gè)函數(shù)上的表現(xiàn)稍差，略遜于FETLBO 和HSTLBO算法，但差距也并非太大，DE、TLBO、ITLBO算法要明顯遜色于這三個(gè)算法。從解方差上看，本文中提出的DSLTLBO算法處于前列。

在表3 中，給出了30 次獨(dú)立運(yùn)算中的成功次數(shù)，可以看出，無(wú)論是較低維度還是較高的維度，DSLTLBO算法均具有較高的成功率。為了更好地展示算法在收斂速度等方面的優(yōu)勢(shì)，繪制了部分算法在f1～f6函數(shù)上的收斂曲線(xiàn)，分別為圖1～圖6，繪圖工具為WPS2019個(gè)人版。從六個(gè)圖的收斂曲線(xiàn)可以看出，DSLTLBO 算法的收斂明顯優(yōu)于其他算法，通常都能經(jīng)過(guò)1 000或2 000次迭代，即可快速收斂到最優(yōu)解周?chē)瑥亩M(jìn)行精細(xì)搜索。TLBO算法則在幾個(gè)函數(shù)上存在跳躍點(diǎn)，而且收斂曲線(xiàn)較平直，DE 算法也存在此問(wèn)題。ITLBO 算法收斂較好，在f5的收斂較DSLTLBO 算法快速，但是在其他函數(shù)上的收斂速度均輸于DSLTLBO算法。

表3 算法的收斂成功次數(shù)對(duì)比（30維/100維）

綜合以上的對(duì)比結(jié)果，可以看出DSLTLBO 算法的魯棒性和勘探新解的能力均較優(yōu)秀。之所以如此，得益于其自身的演化理念和種群的競(jìng)爭(zhēng)合作方式。算法迭代初期，“學(xué)生”主要向“教師”學(xué)習(xí)。因?yàn)棣妮^小，所以學(xué)生個(gè)體主要向教師個(gè)體學(xué)習(xí)，快速向最優(yōu)解周?chē)諗?，有利于算法的收斂速度。算法的中期，學(xué)生個(gè)體保持自身狀態(tài)的能力增強(qiáng)，放緩了向“教師”個(gè)體靠近的速度，算法全局搜索占據(jù)主要地位，可以較好地發(fā)現(xiàn)未知的新解。算法進(jìn)入迭代后期，教師個(gè)體開(kāi)始執(zhí)行DRS算法，加強(qiáng)對(duì)于最優(yōu)周?chē)臻g的精細(xì)搜索，提升算法解的精度。同時(shí)，種群內(nèi)的其他個(gè)體保持自身狀態(tài)的能力繼續(xù)增強(qiáng)，使種群具有一定發(fā)散性，避免被局部最優(yōu)約束，出現(xiàn)早熟。從收斂曲線(xiàn)圖可知很直觀的看到，DSLTLBO 算法的收斂曲線(xiàn)下降非?？?，種群跳出局部最優(yōu)約束的能力也較好。

4 結(jié)論

針對(duì)TLBO算法的弱點(diǎn)，本文提出了如下兩方面的改進(jìn)。

（1）在“教”階段，引入了自適應(yīng)學(xué)習(xí)因子δ，該因子在（0，1）區(qū)間內(nèi)非線(xiàn)性逐漸變化，以使種群在早期快速向最優(yōu)個(gè)體周?chē)臻g收斂，而在后期種群多樣性得以保持，平衡算法的局部搜索和全局搜索。

（2）為了提高算法的求精精度，在算法的后期令教師個(gè)體執(zhí)行DRS 算法，強(qiáng)化對(duì)教師個(gè)體周?chē)鷧^(qū)域的精細(xì)搜索。

利用馬爾科夫鏈技術(shù)分析了該算法的收斂性，并在10個(gè)經(jīng)典的測(cè)試函數(shù)上進(jìn)行了相關(guān)實(shí)驗(yàn)。實(shí)驗(yàn)表明本文提出的DSLTLBO算法具有較好的收斂速度和求解精度，比較適合于求解較高維度連續(xù)型的數(shù)值優(yōu)化問(wèn)題。作為一種具有較高效率的群智能算法，未來(lái)將會(huì)借鑒傳統(tǒng)演化算法的思想，提高TLBO的效率。探索開(kāi)拓新的應(yīng)用領(lǐng)域，也是主要的研究方向之一。