一種新的結合獎勵機制的ETLBO算法

吳云鵬,崔佳旭,張永剛

(吉林大學 計算機科學與技術學院,符號計算與知識工程教育部重點實驗室,長春 130012)

近年來,群智能算法由于其收斂速度快、具有良好的適應性等特點,在工業調度[1]、網絡服務優化[2]等領域應用廣泛.目前較流行的新型群智能算法主要有：差分進化(differential evolution,DE)算法[3]、遺傳(genetic algorithms,GA)算法[4]、粒子群優化(particle swarm optimization,PSO)算法[5]、蟻群優化(ant colony optimization,ACO)算法[6]、TLBO(teaching-learning-based optimization)算法[7-9]等.TLBO算法是一種模擬班級教學過程的新型智能算法.由于TLBO算法具有參數少、易實現、收斂速度快等優點[10],因此在機械參數設計[8]、連續函數優化[9]、平面鋼架設計[11]等方面應用廣泛.為進一步提高TLBO算法的性能,目前已有許多研究對其進行了改進,其中影響力最大的是ETLBO(elitist teaching-learning-based optimization)算法[12].在ETLBO算法中,根據成績對學生進行排序,拋棄表現較差的學生,從而使算法一直向當前最優方向搜索.

本文針對ETLBO算法進行改進,通過引入獎勵制度,給出相應的ETLBO-reward算法.在ETLBO-reward算法中,學生在“學”階段能盡可能地選擇表現更優的個體進行學習,從而提升算法的收斂能力.在ETLBO-reward算法的基礎上,本文又提出一種簡單的自適應精英個數策略——隨機精英數策略,并提出了帶獎勵制度的自適應精英個數算法RETLBO-reward.最后,在RETLBO-reward算法的基礎上又給出了一種離散的TLBO算法——D-RETLBO-reward.

1 TLBO算法

在TLBO算法中,將一組學生定義為一個種群.學生學習的科目對應經典優化問題中的決策變量,學習效果則對應優化問題中的適應度函數值.一個種群中學習效果最好的學生被定義為教師.決策變量包含在指定優化問題的目標函數中,最優解是具有最優目標函數值的學生對應所有科目的一組完全賦值.根據向不同身份人學習的方式,基本TLBO算法把學生的學習過程分為兩個階段：“教師教”階段和“學生學”階段,算法流程如圖1所示.

圖1 TLBO算法流程Fig.1 Flow chart of TLBO algorithm

“教師教”階段：教師根據所負責科目的水平盡力提高全部學生在該科目成績的平均值.假設有m個要學習的科目(即決策變量),n個學生(即種群大小),k為學生索引(k=1,2,…,n),j為科目索引(j=1,2,…,m).第i次迭代時,對于j個科目教師與所有學生學習成果的平均值差異如下：

(1)

(2)

(3)

(4)

(5)

“學生學”階段：學生主動向其他同學學習,以提高學習成果.學生k隨機選擇同學q作為學習對象進行學習：

(6)

2 ETLBO算法

基于精英的TLBO(elitist TLBO algorithm,ETLBO)算法是受進化算法和群智能算法的啟發,在基本TLBO算法中增加精英策略,以加速算法收斂.初始假設精英數為e,精英策略分為兩個步驟：1) 算法每次迭代中,在“學”階段后,選學習成果最好的e個學生和學習成果最差的e個學生,分別將他們確定為精英集(EliteSet)和差生集(WorstSet),用精英集替換差生集;2) 在替換差生集后,若出現冗余個體,則根據

(7)

進行修改,通過保證種群多樣性避免陷入局部最優.其中:jr是隨機整數(取值為[1,m]);Lowjr和Upjr分別表示第jr個決策變量的下界和上界.文獻[13]的實驗結果表明,ETLBO算法在求解連續非線性優化問題方面明顯優于粒子群優化、差分進化、人工蜂群等算法.

3 基于獎勵制度的ETLBO算法

3.1 ETLBO-reward算法

ETLBO算法在“學”階段,一個學生選取另一個學生通過式(6)進行差異學習,選取過程是隨機的,從而可能出現學習成果差的學生尋找的學習對象也可能是差生集的情形,使學習成果提高較小甚至未提高.為了加強除精英學生外的學生學習程度,本文在ETLBO算法的基礎上引入獎勵制度：

1) 對表現好的學生給予獎勵；

2) 在“學”階段根據獲得的獎勵通過輪盤賭方法選擇學習對象.

學生Xk在第i次迭代獲得的獎勵定義為

(8)

ETLBO-reward算法.

輸入：學生個數n,科目數m,精英個數elitist,最大迭代次數MAXITER,每個科目對應的上下界Upj和Lowj;

輸出：最優解;

步驟1) FORkin 1..nDO

步驟2) 按式(7)對學生Xk的所有科目初始化；

步驟3) 計算f(Xk)和RXk,并把RXk加入Xk的獎勵隊列中；

步驟4) END

步驟5)Xteacher←getTeacher( )；

步驟6) WHILE當前迭代次數i≤MAXITER DO

步驟7) FORkin 1..nDO

步驟8) FORjin 1..mDO

步驟12) END

步驟13) 邊界檢查；

步驟15) IF更新THEN

步驟17) END

步驟18)h←根據獎勵的平均值進行輪盤賭選擇得到一個學習對象；

步驟(20) 邊界檢查；

步驟22) IF更新THEN

步驟24) END

步驟25) END

步驟26) 得到elitist個精英學生EliteSet；

步驟27) 得到elitist個差生學生WorstSet；

步驟28) FORuin 1..elitist DO

步驟29)XWorstSet[u]←XEliteSet[u]；

步驟30) 根據式(7)修改冗余；

步驟32) END

步驟33) WHILE 存在相同的學生p和qDO

步驟34) 根據式(7)修改冗余；

步驟36) END

步驟37) END.

ETLBO-reward算法的步驟1)～4)為初始化階段;步驟5)根據學習成果優劣得到表現最好的學生賦給Xteacher;步驟6)～36)是整個迭代過程,步驟6)的終止條件是迭代次數達到規定的最大迭代次數MAXITER;步驟8)～17)為算法的“教”階段,其中步驟8)～12)是學生k的差異學習階段,步驟13)是邊界檢查階段：

(9)

3.2 RETLBO-reward算法

4 實驗結果與分析

實驗環境為：ubuntu 14.04 LTS 64位操作系統,Intel i7-3770處理器,8 GB內存.連續非線性優化問題測試集采用較流行的CEC08中6個測試函數F1,F2,F3,F4,F5,F6[14].TLBO算法種群規模設為50,最大評估函數次數為240 000.可根據

noef=2×NP×Iter,

(10)

noef=2×NP×Iter+de_noef

(11)

分別計算出TLBO和ETLBO算法的函數評估次數.其中：noef表示函數評估次數；NP表示種群大??；Iter表示迭代次數；de_noef表示去掉重復的函數評估次數.

TLBO和ETLBO算法函數評估次數的計算只相差變異重復個體的函數評估次數,因此在確保滿足評估次數公平的前提下,本文設置TLBO算法和ETLBO算法的最大迭代次數為2 400和2 300,從而可保證兩種算法函數評估的最大次數都近似為240 000.取ETLBO算法的精英個數為4,8,12,16,20,24.每種算法在每個測試函數上都運行10次.表1為TLBO算法和ETLBO算法的參數設置.表2～表7分別為TLBO基本算法、ETLBO算法和ETLBO-reward算法在測試函數F1～F6上的對比結果.其中,B,W,M,SD分別表示算法10次運行的最好解、最壞解、平均解、標準差.

表1 TLBO算法和ETLBO算法的參數設置

表2 不同算法在測試函數F1(-450)的對比結果

續表2

表3 不同算法在測試函數F2(-450)的對比結果

表4 不同算法在測試函數F3(390)的對比結果

表5 不同算法在測試函數F4(-330)的對比結果

續表5

表6 不同算法在測試函數F5(-180)的對比結果

表7 不同算法在測試函數F6(-140)的對比結果

由表2～表7可見,F1～F6測試函數中,ETLBO算法和ETLBO-reward算法都能求出比TLBO算法更高質量的解;在測試函數F1中,ETLBO算法和ETLBO-reward算法均能求出最優解,但ETLBO-reward算法比ETLBO算法更穩定;在測試函數F2中,ETLBO-reward算法的平均求解質量優于ETLBO算法;在測試函數F3中,ETLBO-reward算法和ETLBO算法表現相近,但當精英個數為8,12,24時,ETLBO-reward算法求解穩定性明顯優于ETLBO算法;在測試函數F4～F6中,ETLBO-reward算法在求解質量和穩定性方面均優于ETLBO算法.

表8為TLBO,ETLBO,ETLBO-reward和RETLBO-reward算法在F1～F6測試函數上的對比結果,分別用A1,A2,A3和A4表示TLBO,ETLBO,ETLBO-reward和RETLBO-reward算法.ETLBO算法與ETLBO-reward算法是分別選擇在每個測試函數上表現最好的結果.由表8可見：在測試函數F3上,ETLBO算法表現最好;在函數F5上,ETLBO-reward算法表現最好;在測試函數F1,F2,F4,F6上,RETLBO-reward算法整體上優于其他算法.

表8 不同算法在6個測試函數上的對比結果

綜上所述,本文針對ETLBO算法進行優化,通過提出一種獎勵機制,在“學”階段學生有更大的概率向優秀個體學習,從而加快收斂速度.根據該機制提出了相應的ETLBO-reward算法,并提出一種簡單的自適應精英個數RETLBO-reward算法.實驗部分應用ETLBO-reward算法和RETLBO-reward算法求解連續非線性函數F1～F6.實驗結果表明,ETLBO-reward算法在整體上優于ETLBO算法,并且RETLBO-reward算法在省略了確定精英個數過程的同時保證了較好的求解效率.