吳云鵬,崔佳旭,張永剛
(吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,符號計算與知識工程教育部重點實驗室,長春 130012)
近年來,群智能算法由于其收斂速度快、具有良好的適應(yīng)性等特點,在工業(yè)調(diào)度[1]、網(wǎng)絡(luò)服務(wù)優(yōu)化[2]等領(lǐng)域應(yīng)用廣泛.目前較流行的新型群智能算法主要有:差分進化(differential evolution,DE)算法[3]、遺傳(genetic algorithms,GA)算法[4]、粒子群優(yōu)化(particle swarm optimization,PSO)算法[5]、蟻群優(yōu)化(ant colony optimization,ACO)算法[6]、TLBO(teaching-learning-based optimization)算法[7-9]等.TLBO算法是一種模擬班級教學(xué)過程的新型智能算法.由于TLBO算法具有參數(shù)少、易實現(xiàn)、收斂速度快等優(yōu)點[10],因此在機械參數(shù)設(shè)計[8]、連續(xù)函數(shù)優(yōu)化[9]、平面鋼架設(shè)計[11]等方面應(yīng)用廣泛.為進一步提高TLBO算法的性能,目前已有許多研究對其進行了改進,其中影響力最大的是ETLBO(elitist teaching-learning-based optimization)算法[12].在ETLBO算法中,根據(jù)成績對學(xué)生進行排序,拋棄表現(xiàn)較差的學(xué)生,從而使算法一直向當(dāng)前最優(yōu)方向搜索.
本文針對ETLBO算法進行改進,通過引入獎勵制度,給出相應(yīng)的ETLBO-reward算法.在ETLBO-reward算法中,學(xué)生在“學(xué)”階段能盡可能地選擇表現(xiàn)更優(yōu)的個體進行學(xué)習(xí),從而提升算法的收斂能力.在ETLBO-reward算法的基礎(chǔ)上,本文又提出一種簡單的自適應(yīng)精英個數(shù)策略——隨機精英數(shù)策略,并提出了帶獎勵制度的自適應(yīng)精英個數(shù)算法RETLBO-reward.最后,在RETLBO-reward算法的基礎(chǔ)上又給出了一種離散的TLBO算法——D-RETLBO-reward.
在TLBO算法中,將一組學(xué)生定義為一個種群.學(xué)生學(xué)習(xí)的科目對應(yīng)經(jīng)典優(yōu)化問題中的決策變量,學(xué)習(xí)效果則對應(yīng)優(yōu)化問題中的適應(yīng)度函數(shù)值.一個種群中學(xué)習(xí)效果最好的學(xué)生被定義為教師.決策變量包含在指定優(yōu)化問題的目標(biāo)函數(shù)中,最優(yōu)解是具有最優(yōu)目標(biāo)函數(shù)值的學(xué)生對應(yīng)所有科目的一組完全賦值.根據(jù)向不同身份人學(xué)習(xí)的方式,基本TLBO算法把學(xué)生的學(xué)習(xí)過程分為兩個階段:“教師教”階段和“學(xué)生學(xué)”階段,算法流程如圖1所示.
圖1 TLBO算法流程Fig.1 Flow chart of TLBO algorithm
“教師教”階段:教師根據(jù)所負(fù)責(zé)科目的水平盡力提高全部學(xué)生在該科目成績的平均值.假設(shè)有m個要學(xué)習(xí)的科目(即決策變量),n個學(xué)生(即種群大小),k為學(xué)生索引(k=1,2,…,n),j為科目索引(j=1,2,…,m).第i次迭代時,對于j個科目教師與所有學(xué)生學(xué)習(xí)成果的平均值差異如下:
(1)
(2)
(3)
(4)
(5)
“學(xué)生學(xué)”階段:學(xué)生主動向其他同學(xué)學(xué)習(xí),以提高學(xué)習(xí)成果.學(xué)生k隨機選擇同學(xué)q作為學(xué)習(xí)對象進行學(xué)習(xí):
(6)
基于精英的TLBO(elitist TLBO algorithm,ETLBO)算法是受進化算法和群智能算法的啟發(fā),在基本TLBO算法中增加精英策略,以加速算法收斂.初始假設(shè)精英數(shù)為e,精英策略分為兩個步驟:1) 算法每次迭代中,在“學(xué)”階段后,選學(xué)習(xí)成果最好的e個學(xué)生和學(xué)習(xí)成果最差的e個學(xué)生,分別將他們確定為精英集(EliteSet)和差生集(WorstSet),用精英集替換差生集;2) 在替換差生集后,若出現(xiàn)冗余個體,則根據(jù)
(7)
進行修改,通過保證種群多樣性避免陷入局部最優(yōu).其中:jr是隨機整數(shù)(取值為[1,m]);Lowjr和Upjr分別表示第jr個決策變量的下界和上界.文獻[13]的實驗結(jié)果表明,ETLBO算法在求解連續(xù)非線性優(yōu)化問題方面明顯優(yōu)于粒子群優(yōu)化、差分進化、人工蜂群等算法.
ETLBO算法在“學(xué)”階段,一個學(xué)生選取另一個學(xué)生通過式(6)進行差異學(xué)習(xí),選取過程是隨機的,從而可能出現(xiàn)學(xué)習(xí)成果差的學(xué)生尋找的學(xué)習(xí)對象也可能是差生集的情形,使學(xué)習(xí)成果提高較小甚至未提高.為了加強除精英學(xué)生外的學(xué)生學(xué)習(xí)程度,本文在ETLBO算法的基礎(chǔ)上引入獎勵制度:
1) 對表現(xiàn)好的學(xué)生給予獎勵;
2) 在“學(xué)”階段根據(jù)獲得的獎勵通過輪盤賭方法選擇學(xué)習(xí)對象.
學(xué)生Xk在第i次迭代獲得的獎勵定義為
(8)
ETLBO-reward算法.
輸入:學(xué)生個數(shù)n,科目數(shù)m,精英個數(shù)elitist,最大迭代次數(shù)MAXITER,每個科目對應(yīng)的上下界Upj和Lowj;
輸出:最優(yōu)解;
步驟1) FORkin 1..nDO
步驟2) 按式(7)對學(xué)生Xk的所有科目初始化;
步驟3) 計算f(Xk)和RXk,并把RXk加入Xk的獎勵隊列中;
步驟4) END
步驟5)Xteacher←getTeacher( );
步驟6) WHILE當(dāng)前迭代次數(shù)i≤MAXITER DO
步驟7) FORkin 1..nDO
步驟8) FORjin 1..mDO
步驟12) END
步驟13) 邊界檢查;
步驟15) IF更新THEN
步驟17) END
步驟18)h←根據(jù)獎勵的平均值進行輪盤賭選擇得到一個學(xué)習(xí)對象;
步驟(20) 邊界檢查;
步驟22) IF更新THEN
步驟24) END
步驟25) END
步驟26) 得到elitist個精英學(xué)生EliteSet;
步驟27) 得到elitist個差生學(xué)生WorstSet;
步驟28) FORuin 1..elitist DO
步驟29)XWorstSet[u]←XEliteSet[u];
步驟30) 根據(jù)式(7)修改冗余;
步驟32) END
步驟33) WHILE 存在相同的學(xué)生p和qDO
步驟34) 根據(jù)式(7)修改冗余;
步驟36) END
步驟37) END.
ETLBO-reward算法的步驟1)~4)為初始化階段;步驟5)根據(jù)學(xué)習(xí)成果優(yōu)劣得到表現(xiàn)最好的學(xué)生賦給Xteacher;步驟6)~36)是整個迭代過程,步驟6)的終止條件是迭代次數(shù)達到規(guī)定的最大迭代次數(shù)MAXITER;步驟8)~17)為算法的“教”階段,其中步驟8)~12)是學(xué)生k的差異學(xué)習(xí)階段,步驟13)是邊界檢查階段:
(9)
實驗環(huán)境為:ubuntu 14.04 LTS 64位操作系統(tǒng),Intel i7-3770處理器,8 GB內(nèi)存.連續(xù)非線性優(yōu)化問題測試集采用較流行的CEC08中6個測試函數(shù)F1,F2,F3,F4,F5,F6[14].TLBO算法種群規(guī)模設(shè)為50,最大評估函數(shù)次數(shù)為240 000.可根據(jù)
noef=2×NP×Iter,
(10)
noef=2×NP×Iter+de_noef
(11)
分別計算出TLBO和ETLBO算法的函數(shù)評估次數(shù).其中:noef表示函數(shù)評估次數(shù);NP表示種群大?。籌ter表示迭代次數(shù);de_noef表示去掉重復(fù)的函數(shù)評估次數(shù).
TLBO和ETLBO算法函數(shù)評估次數(shù)的計算只相差變異重復(fù)個體的函數(shù)評估次數(shù),因此在確保滿足評估次數(shù)公平的前提下,本文設(shè)置TLBO算法和ETLBO算法的最大迭代次數(shù)為2 400和2 300,從而可保證兩種算法函數(shù)評估的最大次數(shù)都近似為240 000.取ETLBO算法的精英個數(shù)為4,8,12,16,20,24.每種算法在每個測試函數(shù)上都運行10次.表1為TLBO算法和ETLBO算法的參數(shù)設(shè)置.表2~表7分別為TLBO基本算法、ETLBO算法和ETLBO-reward算法在測試函數(shù)F1~F6上的對比結(jié)果.其中,B,W,M,SD分別表示算法10次運行的最好解、最壞解、平均解、標(biāo)準(zhǔn)差.
表1 TLBO算法和ETLBO算法的參數(shù)設(shè)置
表2 不同算法在測試函數(shù)F1(-450)的對比結(jié)果
續(xù)表2
表3 不同算法在測試函數(shù)F2(-450)的對比結(jié)果
表4 不同算法在測試函數(shù)F3(390)的對比結(jié)果
表5 不同算法在測試函數(shù)F4(-330)的對比結(jié)果
續(xù)表5
表6 不同算法在測試函數(shù)F5(-180)的對比結(jié)果
表7 不同算法在測試函數(shù)F6(-140)的對比結(jié)果
由表2~表7可見,F1~F6測試函數(shù)中,ETLBO算法和ETLBO-reward算法都能求出比TLBO算法更高質(zhì)量的解;在測試函數(shù)F1中,ETLBO算法和ETLBO-reward算法均能求出最優(yōu)解,但ETLBO-reward算法比ETLBO算法更穩(wěn)定;在測試函數(shù)F2中,ETLBO-reward算法的平均求解質(zhì)量優(yōu)于ETLBO算法;在測試函數(shù)F3中,ETLBO-reward算法和ETLBO算法表現(xiàn)相近,但當(dāng)精英個數(shù)為8,12,24時,ETLBO-reward算法求解穩(wěn)定性明顯優(yōu)于ETLBO算法;在測試函數(shù)F4~F6中,ETLBO-reward算法在求解質(zhì)量和穩(wěn)定性方面均優(yōu)于ETLBO算法.
表8為TLBO,ETLBO,ETLBO-reward和RETLBO-reward算法在F1~F6測試函數(shù)上的對比結(jié)果,分別用A1,A2,A3和A4表示TLBO,ETLBO,ETLBO-reward和RETLBO-reward算法.ETLBO算法與ETLBO-reward算法是分別選擇在每個測試函數(shù)上表現(xiàn)最好的結(jié)果.由表8可見:在測試函數(shù)F3上,ETLBO算法表現(xiàn)最好;在函數(shù)F5上,ETLBO-reward算法表現(xiàn)最好;在測試函數(shù)F1,F2,F4,F6上,RETLBO-reward算法整體上優(yōu)于其他算法.
表8 不同算法在6個測試函數(shù)上的對比結(jié)果
綜上所述,本文針對ETLBO算法進行優(yōu)化,通過提出一種獎勵機制,在“學(xué)”階段學(xué)生有更大的概率向優(yōu)秀個體學(xué)習(xí),從而加快收斂速度.根據(jù)該機制提出了相應(yīng)的ETLBO-reward算法,并提出一種簡單的自適應(yīng)精英個數(shù)RETLBO-reward算法.實驗部分應(yīng)用ETLBO-reward算法和RETLBO-reward算法求解連續(xù)非線性函數(shù)F1~F6.實驗結(jié)果表明,ETLBO-reward算法在整體上優(yōu)于ETLBO算法,并且RETLBO-reward算法在省略了確定精英個數(shù)過程的同時保證了較好的求解效率.