一種新的結(jié)合獎(jiǎng)勵(lì)機(jī)制的ETLBO算法

吳云鵬,崔佳旭,張永剛

(吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,長春 130012)

近年來,群智能算法由于其收斂速度快、具有良好的適應(yīng)性等特點(diǎn),在工業(yè)調(diào)度[1]、網(wǎng)絡(luò)服務(wù)優(yōu)化[2]等領(lǐng)域應(yīng)用廣泛.目前較流行的新型群智能算法主要有：差分進(jìn)化(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算法是一種模擬班級(jí)教學(xué)過程的新型智能算法.由于TLBO算法具有參數(shù)少、易實(shí)現(xiàn)、收斂速度快等優(yōu)點(diǎn)[10],因此在機(jī)械參數(shù)設(shè)計(jì)[8]、連續(xù)函數(shù)優(yōu)化[9]、平面鋼架設(shè)計(jì)[11]等方面應(yīng)用廣泛.為進(jìn)一步提高TLBO算法的性能,目前已有許多研究對(duì)其進(jìn)行了改進(jìn),其中影響力最大的是ETLBO(elitist teaching-learning-based optimization)算法[12].在ETLBO算法中,根據(jù)成績對(duì)學(xué)生進(jìn)行排序,拋棄表現(xiàn)較差的學(xué)生,從而使算法一直向當(dāng)前最優(yōu)方向搜索.

本文針對(duì)ETLBO算法進(jìn)行改進(jìn),通過引入獎(jiǎng)勵(lì)制度,給出相應(yīng)的ETLBO-reward算法.在ETLBO-reward算法中,學(xué)生在“學(xué)”階段能盡可能地選擇表現(xiàn)更優(yōu)的個(gè)體進(jìn)行學(xué)習(xí),從而提升算法的收斂能力.在ETLBO-reward算法的基礎(chǔ)上,本文又提出一種簡單的自適應(yīng)精英個(gè)數(shù)策略——隨機(jī)精英數(shù)策略,并提出了帶獎(jiǎng)勵(lì)制度的自適應(yīng)精英個(gè)數(shù)算法RETLBO-reward.最后,在RETLBO-reward算法的基礎(chǔ)上又給出了一種離散的TLBO算法——D-RETLBO-reward.

1 TLBO算法

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

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

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

(1)

(2)

(3)

(4)

(5)

“學(xué)生學(xué)”階段：學(xué)生主動(dòng)向其他同學(xué)學(xué)習(xí),以提高學(xué)習(xí)成果.學(xué)生k隨機(jī)選擇同學(xué)q作為學(xué)習(xí)對(duì)象進(jìn)行學(xué)習(xí)：

(6)

2 ETLBO算法

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

(7)

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

3 基于獎(jiǎng)勵(lì)制度的ETLBO算法

3.1 ETLBO-reward算法

ETLBO算法在“學(xué)”階段,一個(gè)學(xué)生選取另一個(gè)學(xué)生通過式(6)進(jìn)行差異學(xué)習(xí),選取過程是隨機(jī)的,從而可能出現(xiàn)學(xué)習(xí)成果差的學(xué)生尋找的學(xué)習(xí)對(duì)象也可能是差生集的情形,使學(xué)習(xí)成果提高較小甚至未提高.為了加強(qiáng)除精英學(xué)生外的學(xué)生學(xué)習(xí)程度,本文在ETLBO算法的基礎(chǔ)上引入獎(jiǎng)勵(lì)制度：

1) 對(duì)表現(xiàn)好的學(xué)生給予獎(jiǎng)勵(lì)；

2) 在“學(xué)”階段根據(jù)獲得的獎(jiǎng)勵(lì)通過輪盤賭方法選擇學(xué)習(xí)對(duì)象.

學(xué)生Xk在第i次迭代獲得的獎(jiǎng)勵(lì)定義為

(8)

ETLBO-reward算法.

輸入：學(xué)生個(gè)數(shù)n,科目數(shù)m,精英個(gè)數(shù)elitist,最大迭代次數(shù)MAXITER,每個(gè)科目對(duì)應(yīng)的上下界Upj和Lowj;

輸出：最優(yōu)解;

步驟1) FORkin 1..nDO

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

步驟3) 計(jì)算f(Xk)和RXk,并把RXk加入Xk的獎(jiǎng)勵(lì)隊(duì)列中；

步驟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ù)獎(jiǎng)勵(lì)的平均值進(jìn)行輪盤賭選擇得到一個(gè)學(xué)習(xí)對(duì)象；

步驟(20) 邊界檢查；

步驟22) IF更新THEN

步驟24) END

步驟25) END

步驟26) 得到elitist個(gè)精英學(xué)生EliteSet；

步驟27) 得到elitist個(gè)差生學(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)是整個(gè)迭代過程,步驟6)的終止條件是迭代次數(shù)達(dá)到規(guī)定的最大迭代次數(shù)MAXITER;步驟8)～17)為算法的“教”階段,其中步驟8)～12)是學(xué)生k的差異學(xué)習(xí)階段,步驟13)是邊界檢查階段：

(9)

3.2 RETLBO-reward算法

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

實(shí)驗(yàn)環(huán)境為：ubuntu 14.04 LTS 64位操作系統(tǒng),Intel i7-3770處理器,8 GB內(nèi)存.連續(xù)非線性優(yōu)化問題測試集采用較流行的CEC08中6個(gè)測試函數(shù)F1,F2,F3,F4,F5,F6[14].TLBO算法種群規(guī)模設(shè)為50,最大評(píng)估函數(shù)次數(shù)為240 000.可根據(jù)

noef=2×NP×Iter,

(10)

noef=2×NP×Iter+de_noef

(11)

分別計(jì)算出TLBO和ETLBO算法的函數(shù)評(píng)估次數(shù).其中：noef表示函數(shù)評(píng)估次數(shù)；NP表示種群大??；Iter表示迭代次數(shù)；de_noef表示去掉重復(fù)的函數(shù)評(píng)估次數(shù).

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

表1 TLBO算法和ETLBO算法的參數(shù)設(shè)置

表2 不同算法在測試函數(shù)F1(-450)的對(duì)比結(jié)果

續(xù)表2

表3 不同算法在測試函數(shù)F2(-450)的對(duì)比結(jié)果

表4 不同算法在測試函數(shù)F3(390)的對(duì)比結(jié)果

表5 不同算法在測試函數(shù)F4(-330)的對(duì)比結(jié)果

續(xù)表5

表6 不同算法在測試函數(shù)F5(-180)的對(duì)比結(jié)果

表7 不同算法在測試函數(shù)F6(-140)的對(duì)比結(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)精英個(gè)數(shù)為8,12,24時(shí),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ù)上的對(duì)比結(jié)果,分別用A1,A2,A3和A4表示TLBO,ETLBO,ETLBO-reward和RETLBO-reward算法.ETLBO算法與ETLBO-reward算法是分別選擇在每個(gè)測試函數(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個(gè)測試函數(shù)上的對(duì)比結(jié)果

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