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

陳怡君,任春年,黨妍潔,李會榮

(1.西安航空學院 圖書館,陜西 西安 710077;2.商洛學院 數學與計算機應用學院,陜西 商洛 726000)

0 引 言

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

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

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

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

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

1.1 教學階段

(1)

(2)

1.2 學習階段

在學習階段,學習者會通過兩兩互動交流認識自己的差距,并以此提高自己的知識水平。對于第k個學習者Xk來說,更新機制如下:

(3)

一直重復上述步驟直至達到最大迭代次數或者停止準則時,算法停止,輸出最優(yōu)個體。

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

2.1 考慮歷史知識記憶的教學階段

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

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

w=(t/T)2

(5)

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

2.2 改進的學習階段

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

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

(7)

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

(8)

2.3 MTLBO算法實現流程

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

步驟2:根據式(2)和式(4)更新教學階段個體。

步驟3:計算班級內個體的適應度f(X),并使用貪婪策略更新學生個體。

步驟4:根據式(6)更新學習階段個體。

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

3 結果與分析

3.1 測試函數

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

表1 測試函數的性質

實驗設置如下:班級學習人數均為N=50,最大的迭代次數均為Tmax=300。為了測試算法對復雜高維優(yōu)化問題的尋優(yōu)性能,分別在空間維數為30維、50維和100維進行實驗,每種算法獨立運行30次。30次運行的實驗結果的最優(yōu)值、最差值、平均值和標準差如表2～表4所示。

表2 在空間維數D=30下的測試結果對比

3.2 結果分析

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

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

表3 在空間維數D=50下的測試結果對比

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

表4 在空間維數D=100下的測試結果對比

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

圖1 函數值隨著迭代次數的進化曲線

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

4 結束語

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

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