一種帶有附加記憶策略的改進(jìn)教與學(xué)優(yōu)化算法

陳怡君,任春年,黨妍潔,李會(huì)榮

(1.西安航空學(xué)院 圖書館,陜西 西安 710077;2.商洛學(xué)院 數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院,陜西 商洛 726000)

0 引 言

群體智能優(yōu)化算法是通過模擬生活中的自然現(xiàn)象或某些動(dòng)物、植物群體間的競爭、協(xié)作進(jìn)化等行為,實(shí)現(xiàn)對優(yōu)化問題的求解,目前已經(jīng)受到國內(nèi)外許多研究者的廣泛關(guān)注[1-6]。例如,遺傳算法模擬了生物界“適者生存,優(yōu)勝劣汰”達(dá)爾文進(jìn)化論觀點(diǎn)[1];粒子群優(yōu)化算法模擬鳥類的覓食行為,通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解[2];人工蜂群算法模仿蜜蜂的覓食行為[3],模擬退火算法模擬物理系統(tǒng)退火過程提出的一種智能算法等等[4],這些算法目前已經(jīng)應(yīng)用于數(shù)據(jù)聚類、生物醫(yī)學(xué)、電力優(yōu)化等多個(gè)工業(yè)或?qū)W術(shù)領(lǐng)域[2-6]。

Rao等人于2011年模擬課堂教學(xué)過程提出了一種新的優(yōu)化算法,即教與學(xué)的優(yōu)化(Teaching Learning Based Optimization,TLBO)[7]。TLBO工作的基本原理在于教師對學(xué)習(xí)者在課堂上的輸出的影響,學(xué)習(xí)者的表現(xiàn)是由他學(xué)習(xí)到的結(jié)果或?qū)W習(xí)成績來衡量的,教師扮演著知識傳授者的角色,經(jīng)驗(yàn)豐富的老師能夠培養(yǎng)出更好的學(xué)生。算法可分為教學(xué)階段(Teaching Phase)和學(xué)習(xí)階段(Learning Phase)。教學(xué)階段是指向最好的學(xué)生學(xué)習(xí),學(xué)習(xí)階段是指通過互異學(xué)習(xí)者之間的互動(dòng)、討論進(jìn)行學(xué)習(xí),學(xué)習(xí)者學(xué)習(xí)的越多,解決方案就越好。該算法具有參數(shù)少、易于編程、收斂速度快等優(yōu)點(diǎn),已經(jīng)成功應(yīng)用于函數(shù)優(yōu)化、機(jī)械優(yōu)化、車間調(diào)度、資源分配等實(shí)際問題中[8-13]。例如,Wan等人將優(yōu)等生與差等生的區(qū)別對待進(jìn)行分班,認(rèn)為課堂教學(xué)行為是小班級教學(xué)并行,優(yōu)等生在一個(gè)班級,差生在一個(gè)班級,優(yōu)等生班級和差生班級是動(dòng)態(tài)流動(dòng)的[14]。侯景偉等人認(rèn)為學(xué)生是可以通過課外輔導(dǎo)鞏固知識的,每次教師教學(xué)表現(xiàn)可能是不一樣的,學(xué)生每次學(xué)習(xí)知識的接受程度也是不一樣的,借此提出了動(dòng)態(tài)非線性自適應(yīng)教學(xué)因子、課外輔導(dǎo)因子、動(dòng)態(tài)自適應(yīng)學(xué)習(xí)因子等隨機(jī)線性變化的改進(jìn)TLBO算法[15]。李子揚(yáng)等人認(rèn)為教師也可以自學(xué)的,將TLBO的經(jīng)典兩階段擴(kuò)充為教師自學(xué)階段、教學(xué)階段和學(xué)習(xí)階段三個(gè)階段,使得教師也在算法每次迭代循環(huán)中有改進(jìn)提升機(jī)會(huì),但在提升優(yōu)化性能的同時(shí)引入其他算子,提高了算法的復(fù)雜度[16]。何杰光等人創(chuàng)造性地認(rèn)為學(xué)生在一輪學(xué)習(xí)階段并不僅僅向另一個(gè)學(xué)生學(xué)習(xí),也可以在一輪學(xué)習(xí)階段向其他多位同學(xué)學(xué)習(xí),然后再選擇與多位同學(xué)知識流通的平均值或最大值作為學(xué)到的新知識[17]。此外,王滔等人從學(xué)到知識的層面出發(fā),認(rèn)為當(dāng)前適應(yīng)度值大,下次迭代時(shí)教學(xué)因子就小,當(dāng)前適應(yīng)度值小,下次迭代時(shí)教學(xué)因子就大[18],即表明本次教學(xué)效果好,下次迭代時(shí)教學(xué)程度就低些,本次教學(xué)效果差,下輪迭代時(shí)教學(xué)程度就高些,這樣可以在一定程度上防止過擬合或早熟。而康佳惠等人將TLBO算法與其它群體智能優(yōu)化算法相結(jié)合,利用其它智能優(yōu)化算法中的優(yōu)勢來提高TLBO算法的性能,例如將回溯搜索算法和輪盤賭選擇機(jī)制引入TLBO以提高TLBO的全局搜索能力和收斂精度[19]。文獻(xiàn)[20]引入自適應(yīng)教學(xué)因子和教師的反饋意見對學(xué)生學(xué)習(xí)的影響來提高TLBO算法的學(xué)習(xí)性能?？傊?以上TLBO算法的改進(jìn)策略在一定程度上提高了算法的性能,并且已經(jīng)取得了廣泛的應(yīng)用。

但是,以上對TLBO改進(jìn)的算法中幾乎沒有考慮到知識記憶過程對當(dāng)前學(xué)習(xí)的影響,同時(shí)歷史知識對學(xué)習(xí)當(dāng)前知識的啟發(fā)也很有幫助。為了彌補(bǔ)這一缺陷,基于學(xué)習(xí)記憶策略,該文提出了一種帶有附加記憶策略的教與學(xué)優(yōu)化(MTLBO)算法。該算法在教學(xué)階段增加了一個(gè)學(xué)習(xí)過去知識的記憶過程,同時(shí)學(xué)習(xí)當(dāng)前知識和歷史知識可以提高學(xué)習(xí)產(chǎn)出;在學(xué)習(xí)階段引入了多個(gè)學(xué)生學(xué)習(xí)的策略,提高了算法的搜索能力。在多個(gè)基準(zhǔn)測試函數(shù)的實(shí)驗(yàn)結(jié)果表明,MTLBO算法在性能上優(yōu)于其比較算法。

1 基本教與學(xué)優(yōu)化算法(TLBO)

基本TLBO算法主要依靠教師對學(xué)習(xí)者在課堂上輸出的影響,不斷提高學(xué)習(xí)者的學(xué)習(xí)水平。主要分為教學(xué)階段和學(xué)習(xí)階段,基本過程如下。

1.1 教學(xué)階段

(1)

(2)

1.2 學(xué)習(xí)階段

在學(xué)習(xí)階段,學(xué)習(xí)者會(huì)通過兩兩互動(dòng)交流認(rèn)識自己的差距,并以此提高自己的知識水平。對于第k個(gè)學(xué)習(xí)者Xk來說,更新機(jī)制如下:

(3)

一直重復(fù)上述步驟直至達(dá)到最大迭代次數(shù)或者停止準(zhǔn)則時(shí),算法停止,輸出最優(yōu)個(gè)體。

2 一種帶有附加記憶策略的改進(jìn)教與學(xué)優(yōu)化算法(MTLBO)

2.1 考慮歷史知識記憶的教學(xué)階段

標(biāo)準(zhǔn)TLBO算法是一種基于當(dāng)前狀態(tài)改進(jìn)搜索點(diǎn)的優(yōu)化算法,并沒有考慮到學(xué)生的歷史記憶知識。一般情況下,學(xué)生的歷史狀態(tài)知識對當(dāng)前狀態(tài)的學(xué)習(xí)能力的影響同樣重要,能夠反映現(xiàn)實(shí)班級教學(xué)行為,教師會(huì)要求學(xué)生課后練習(xí),復(fù)習(xí)所學(xué)知識,提高學(xué)習(xí)能力,同時(shí)并預(yù)習(xí)下一次新課;教師也會(huì)根據(jù)學(xué)生的學(xué)習(xí)情況動(dòng)態(tài)調(diào)整新課教學(xué)內(nèi)容與教學(xué)方法,提高班級的整體學(xué)習(xí)水平。因此學(xué)生的歷史記憶知識與教師歷史教學(xué)能力對提高班級的整體教學(xué)水平具有重要的作用。

所以,在基本的教學(xué)優(yōu)化算法中引入教師歷史記憶知識,即在每次更新學(xué)習(xí)者的同時(shí)均要同時(shí)考慮教師上一代的最優(yōu)值和當(dāng)代的最優(yōu)值,則第t代教師的知識水平更新為:

w=(t/T)2

(5)

其中,Teacher(t)是第t代的教師,Xbest(t-1)和Xbest(t)為第t-1代和第t代的最優(yōu)學(xué)生,j是維度;w為權(quán)重因子,決定著教師上一代知識水平對下代學(xué)習(xí)能力的影響程度。權(quán)重w越大,教師歷史記憶知識對當(dāng)前的影響越小。

2.2 改進(jìn)的學(xué)習(xí)階段

由式(3)可以看出,標(biāo)準(zhǔn)TLBO算法學(xué)習(xí)階段主要通過學(xué)習(xí)者與最優(yōu)個(gè)體之間互動(dòng)交流而提高自己的知識水平,然而只局限于兩個(gè)學(xué)生之間的互動(dòng)交流,并沒有考慮到班級內(nèi)最優(yōu)學(xué)生、小組學(xué)習(xí)、互動(dòng)學(xué)習(xí)等學(xué)習(xí)方式的帶動(dòng)作用。因此,將班級最優(yōu)學(xué)生、隨機(jī)學(xué)習(xí)策略引入到學(xué)習(xí)階段中,則將學(xué)習(xí)階段的迭代方程更新如下:

α=1-(1-t/T)(2·t/T)

(7)

β=(et/T-1)/(e-1)

(8)

2.3 MTLBO算法實(shí)現(xiàn)流程

步驟1:設(shè)置最大迭代次數(shù)Tmax、空間維數(shù)D、種群規(guī)模N,設(shè)置當(dāng)前的迭代次數(shù)t=1,并初始化種群X,計(jì)算班級內(nèi)個(gè)體的適應(yīng)度f(X)。

步驟2:根據(jù)式(2)和式(4)更新教學(xué)階段個(gè)體。

步驟3:計(jì)算班級內(nèi)個(gè)體的適應(yīng)度f(X),并使用貪婪策略更新學(xué)生個(gè)體。

步驟4:根據(jù)式(6)更新學(xué)習(xí)階段個(gè)體。

步驟5:設(shè)置迭代次數(shù)t=t+1,返回到步驟2,直到t達(dá)到設(shè)定的最大迭代次數(shù)Tmax,輸出全局最優(yōu)值。

3 結(jié)果與分析

3.1 測試函數(shù)

為了驗(yàn)證所提MTLBO算法的性能,與基本的教學(xué)優(yōu)化算法(TLBO)[21]、一種多反向?qū)W習(xí)的教與學(xué)優(yōu)化算法(MOTLBO)[17]和具有動(dòng)態(tài)自適應(yīng)學(xué)習(xí)機(jī)制的教與學(xué)優(yōu)化算法(DSLTLBO)[22]進(jìn)行對比。選取6個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行實(shí)驗(yàn),其中f1-f5是單峰測試函數(shù),可以測試算法的收斂速度與精度,f6是多峰測試函數(shù),可以測試算法逃出局部最優(yōu)值的能力。測試函數(shù)的表達(dá)式、搜索空間信息如表1所示。

表1 測試函數(shù)的性質(zhì)

實(shí)驗(yàn)設(shè)置如下:班級學(xué)習(xí)人數(shù)均為N=50,最大的迭代次數(shù)均為Tmax=300。為了測試算法對復(fù)雜高維優(yōu)化問題的尋優(yōu)性能,分別在空間維數(shù)為30維、50維和100維進(jìn)行實(shí)驗(yàn),每種算法獨(dú)立運(yùn)行30次。30次運(yùn)行的實(shí)驗(yàn)結(jié)果的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差如表2～表4所示。

表2 在空間維數(shù)D=30下的測試結(jié)果對比

3.2 結(jié)果分析

從表2中可以看出,所提MTLBO算法無論從最優(yōu)值,還是從平均值、方差等方面都優(yōu)于TLBO、MOTLBO、DSLTLBO算法。由于F6函數(shù)是很難優(yōu)化的復(fù)雜函數(shù),原因在于這類函數(shù)的局部最優(yōu)點(diǎn)數(shù)目隨函數(shù)的維數(shù)的增加而呈指數(shù)增長,因此找到全局最優(yōu)點(diǎn)極為困難。但是從實(shí)驗(yàn)結(jié)果看,對于F6函數(shù)四種方法均陷入局部最優(yōu),對于F5函數(shù),三種算法均沒有達(dá)到了最優(yōu)值,但MTLBO算法最優(yōu)值和平均值均優(yōu)于其他三種算法,從而表明所提MTLBO算法是有效的。

表3為在50維下30次獨(dú)立實(shí)驗(yàn)的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差的實(shí)驗(yàn)結(jié)果。由表3可知,對于函數(shù)F1、F2、F3和F4,所提MTLBO算法極大程度地優(yōu)于其它三種算法,而對于F5函數(shù),四種算法的結(jié)果均值都相差不大,但是所提MTLBO算法的最優(yōu)值和平均值相對較小。

表3 在空間維數(shù)D=50下的測試結(jié)果對比

為了測試所提MTLBO算法在高維數(shù)據(jù)上的性能,將搜索空間的維數(shù)增加到100維,表4是在搜索空間的維數(shù)擴(kuò)大到100維每種算法的測試實(shí)驗(yàn)結(jié)果。從表4可以看出,除過測試函數(shù)F6外,所提MTLBO算法在最優(yōu)值方面均優(yōu)于TLBO、MOTLBO、DSLTLBO算法,同時(shí),標(biāo)準(zhǔn)差相對比較小。對于F5函數(shù),雖然四種算法都沒有達(dá)到最優(yōu)值,但是所提MTLBO算法在最優(yōu)值和平均值上略優(yōu)于其他方法。對于測試函數(shù)F6,四種算法均陷入局部最優(yōu),均值都相差不大,除過TLBO算法均在同一個(gè)數(shù)量級。因此,所提MTLBO算法在高維數(shù)據(jù)上具有良好的尋優(yōu)性能。

表4 在空間維數(shù)D=100下的測試結(jié)果對比

圖1為函數(shù)最優(yōu)值隨著迭代次數(shù)的進(jìn)化曲線。由圖1可知,所提MTLBO算法能夠跳出局部極值點(diǎn),具有較快的收斂速度。主要是由于MTLBO算法不但在教學(xué)階段增加了記憶策略,而且在學(xué)習(xí)階段引入了個(gè)體向最優(yōu)個(gè)體和隨機(jī)個(gè)體學(xué)習(xí)策略,保持了種群的多樣性,提高了算法的性能。從圖1(a)和圖1(b)中可以看到,所有方法幾乎都是梯度向下的趨勢,但是所提MTLBO算法收斂速度是最快的。在圖1(e)中,各算法收斂性能的差距相對來說并不大,但仍然能看出MTLBO算法具有較優(yōu)的收斂性,隨著迭代次數(shù)的增加,MTLBO算法優(yōu)于其他三種算法;而在圖1(f)中,DETLBO雖收斂最快,但其收斂結(jié)果并沒有達(dá)到理論最優(yōu)值,與其他三種算法的最終結(jié)果均相同,但是相比之下,所提MTLBO算法收斂速度是最快的。

圖1 函數(shù)值隨著迭代次數(shù)的進(jìn)化曲線

綜上,通過表2～表4與圖1可知,無論搜索空間是低維的還是高維的,MTLBO算法在尋優(yōu)性能上都優(yōu)于TLBO、MOTLBO、DSLTLBO算法,再一次表明MTLBO算法適用于求解中高規(guī)模復(fù)雜優(yōu)化問題。

4 結(jié)束語

為了克服教與學(xué)優(yōu)化算法后期局部收斂現(xiàn)象,在TLBO算法教學(xué)階段增加記憶策略,且考慮到學(xué)習(xí)階段的學(xué)習(xí)者不僅僅會(huì)向最優(yōu)個(gè)體進(jìn)行學(xué)習(xí),還會(huì)向其他學(xué)習(xí)者學(xué)習(xí);在學(xué)習(xí)階段增加隨機(jī)學(xué)習(xí)策略,提出了一種帶有附加記憶策略的改進(jìn)教與學(xué)優(yōu)化(MTLBO)算法。數(shù)值實(shí)驗(yàn)表明,MTLBO算法能有效避免局部收斂,提升了算法的尋優(yōu)性能。

目前,教與學(xué)優(yōu)化算法的應(yīng)用領(lǐng)域有待進(jìn)一步拓寬。就工程優(yōu)化及自動(dòng)化領(lǐng)域而言,問題的多極小性、多約束性、離散連續(xù)變量共存,非線性、多目標(biāo)性、不確定性等復(fù)雜性普遍存在,因此教與學(xué)優(yōu)化算法在該領(lǐng)域的研究應(yīng)用及其適應(yīng)性改進(jìn)仍是一個(gè)很有前景的研究方向。