張琳琳, 陳俊杰, 倪培洲

(東南大學(xué) 儀器科學(xué)與工程學(xué)院，江蘇 南京 210096)

0 引 言

教與學(xué)優(yōu)化 (teaching-learning-based optimization,TLBO) 算法是由Rao R V等人于2011年提出的一種新型群智能優(yōu)化算法[1～3]。該算法基于教師對學(xué)生知識水平的影響，通過模擬教師教學(xué)和學(xué)生相互學(xué)習(xí)來實現(xiàn)群體的進(jìn)化。相比其他智能算法，TLBO算法的優(yōu)勢在于算法參數(shù)極少，具有較強(qiáng)的并行性，且易于實現(xiàn)。因此，該算法已成功應(yīng)用于比例—積分—微分(proportional-integral-differential,PID)控制器優(yōu)化[4]、經(jīng)濟(jì)調(diào)度問題參數(shù)優(yōu)化[5]、熱電冷卻器優(yōu)化[6]以及飛行器氣動形狀優(yōu)化[7]等領(lǐng)域，且均取得了良好的效果。

相關(guān)研究表明，TLBO算法存在易早熟、易陷入局部最優(yōu)以及尋優(yōu)精度低等缺點。為解決該算法的缺陷，Rao R V等人保留精英個體，用精英個體的變異個體替換種群內(nèi)最差個體，提出了精英教學(xué)優(yōu)化算法(elitist TLBO,ETLBO)，使得算法后期收斂速度得到提高[8]。Yu K J等人[9]在ETLBO算法基礎(chǔ)上，在學(xué)習(xí)階段后加入反饋階段，提出反饋精英教學(xué)優(yōu)化算法(feedback ETLBO,FETLBO)，在加速種群收斂的同時提高了求解精度。Chen D B等人[10]提出可變種群規(guī)模的教與學(xué)優(yōu)化算法(variable-population TLBO,VPTLBO)，通過種群數(shù)量的線性遞增和遞減來精簡計算成本，提高算法收斂速度和精度。Zou F等人[11]提出了借鑒其他學(xué)習(xí)者經(jīng)驗的改進(jìn)教與學(xué)優(yōu)化算法(TLBO with learning experience of other learners,LETLBO)，該算法在教學(xué)和學(xué)習(xí)階段，新增了利用其他學(xué)習(xí)者學(xué)習(xí)經(jīng)驗對自身進(jìn)行更新的過程，改進(jìn)后的算法全局優(yōu)化性能得到改善。Yu K J等人[12]針對約束優(yōu)化問題提出改進(jìn)教與學(xué)優(yōu)化算法(improved constrained TLBO,ICTLBO)，算法在教學(xué)階段將種群分為多個子群，以加快收斂速度，同時子群間通過個體交換避免早熟。

為克服TLBO算法容易陷入局部最優(yōu)的缺點，本文提出一種基于元胞自動機(jī)的教與學(xué)優(yōu)化算法(cellular automaton TLBO,CATLBO)。在教學(xué)階段提出以一定的概率接收退步個體的策略，以改善優(yōu)勝劣汰導(dǎo)致種群多樣性快速下降的缺陷；學(xué)習(xí)階段利用元胞自動機(jī)的鄰域結(jié)構(gòu)，個體按照規(guī)則進(jìn)行相互學(xué)習(xí)或自我學(xué)習(xí)，以提高局部搜索能力。

1 TLBO

標(biāo)準(zhǔn)的TLBO算法描述了教學(xué)過程的兩個階段：教師教學(xué)階段和學(xué)生相互學(xué)習(xí)階段。教師通過“教”提高種群平均水平，學(xué)生間通過相互“學(xué)”，使得劣勢個體向優(yōu)勢個體靠近，進(jìn)一步提高種群水平。種群中的每個個體都是優(yōu)化問題的一個可行解。不失一般性，以最小化問題為例，問題描述如下

min(f(X))=f(x1,x2,…,xn)

(1)

X=(x1,x2,…,xn)∈S,S?Rn

(2)

式中S為可行解空間；n為優(yōu)化問題的維數(shù)；xi∈[Li,Ui]，1≤i≤n。

2 CATLBO算法

2.1 模型建立

從數(shù)學(xué)角度可將元胞自動機(jī)[13]描述為一個四元組：A=(Ld,S,N,f)。A為元胞自動機(jī)系統(tǒng)；Ld為元胞空間，d為空間維數(shù)；S為離散狀態(tài)集；N為鄰居集合；f為狀態(tài)轉(zhuǎn)換規(guī)則。

針對多維函數(shù)優(yōu)化問題，算法在有限的迭代次數(shù)內(nèi)只能搜索可行解的一個子集,即在確定的迭代次數(shù)內(nèi)，種群中個體的狀態(tài)可視為有限。為利用元胞自動機(jī)的局部性特征，將元胞自動機(jī)的作用機(jī)理與TLBO算法相結(jié)合建立模型，將班級的教學(xué)活動類比為一個元胞自動機(jī)演化系統(tǒng)，將班級視為元胞空間，采用四邊形網(wǎng)格拓?fù)浣Y(jié)構(gòu)，將個體視為元胞，放置于網(wǎng)格中的一格，個體狀態(tài)根據(jù)規(guī)則f更新。教學(xué)階段仍然針對整個班級，個體在學(xué)習(xí)階段根據(jù)規(guī)則f確定不同的學(xué)習(xí)方式。

2.2 教學(xué)階段改進(jìn)

原始算法采用當(dāng)前最優(yōu)個體指導(dǎo)種群進(jìn)化，并采用優(yōu)勝劣汰機(jī)制接收新個體，使得種群快速向最優(yōu)個體周圍聚集。種群多樣性的快速降低，導(dǎo)致算法早熟，陷入局部最優(yōu)解。考慮在現(xiàn)實教學(xué)中，教學(xué)初期由于教學(xué)次數(shù)較少，可以容忍學(xué)生成績的退步，隨著教學(xué)的反復(fù)進(jìn)行，成績退步的表現(xiàn)越來越不被接受。因此，為保持種群多樣性，提高算法全局搜索的能力，將個體適應(yīng)度的降低視為成績的退步，以一定的概率接收適應(yīng)度退步的個體，該接收概率為

(3)

種群進(jìn)化初期，包容性強(qiáng)，當(dāng)新個體出現(xiàn)退步時仍以一定的概率接收。隨著迭代次數(shù)增加，接收概率逐漸下降至零，促使算法向全局最優(yōu)收斂。

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

為減緩算法早熟，學(xué)習(xí)階段不再隨機(jī)選擇學(xué)習(xí)對象，而是與元胞空間中的鄰居個體相互學(xué)習(xí)。將學(xué)習(xí)過程限制在鄰域內(nèi)，減緩優(yōu)秀個體影響種群的速度。為了加強(qiáng)算法局部搜索能力，提高解的精度，在學(xué)習(xí)階段根據(jù)規(guī)則采用了不同的學(xué)習(xí)策略。

2.3.1 鄰域結(jié)構(gòu)

本文選擇馮—諾依曼型個體鄰域[15]，即每個元胞都有上、下、左、右4個鄰居。

2.3.2 個體更新規(guī)則

1)若滿足?Xj∈N,f(Xj)

(4)

式中Xbest_nei為鄰域中適應(yīng)度最好的個體，即當(dāng)所有鄰居都比中心元胞優(yōu)秀時，中心個體向鄰居中的最優(yōu)個體學(xué)習(xí)。

2)若滿足?Xj∈N,f(Xj)>f(Xi)，則進(jìn)行個體更新

(5)

即當(dāng)所有鄰居都劣于中心元胞時，中心元胞利用自學(xué)習(xí)算子g進(jìn)行自我學(xué)習(xí)提升，以提高算法的局部勘探能力。

本文采用文獻(xiàn)[16]中提出的分段Logistic映射，該映射比基本Logistic映射具有更好的遍歷性。通過分段Logistic 映射對個體中的某兩維決策變量進(jìn)行擾動，產(chǎn)生新個體。對第i維的擾動按式(6)～式(8)執(zhí)行，其中,(li,ui)為第i維變量的取值范圍

(6)

(7)

(8)

3)若滿足fmin≤f(Xi)≤fmax，進(jìn)行個體更新

(9)

(10)

2.4 CATLBO算法流程

1)設(shè)置算法參數(shù)并初始化種群。算法參數(shù)包括種群規(guī)模NP、最大迭代次數(shù)Tmax、優(yōu)化問題維數(shù)D以及決策變量取值范圍；根據(jù)初始化參數(shù)按高斯分布規(guī)律生成NP個隨機(jī)個體。

2)以目標(biāo)函數(shù)值為適應(yīng)度，對種群進(jìn)行評價，選出教師個體Xtea。

3) 進(jìn)行教師教學(xué)階段個體更新，對于產(chǎn)生的進(jìn)步個體，直接接收；針對退步個體，生成(0,1)范圍均勻分布的隨機(jī)數(shù)R，根據(jù)適應(yīng)度和當(dāng)前代數(shù)按式(3)計算接收概率Pacc_new:若R

4)學(xué)習(xí)階段，學(xué)生按照學(xué)習(xí)規(guī)則，采取不同的學(xué)習(xí)方式；若滿足條件(1)，根據(jù)式(4)以最優(yōu)鄰居個體為學(xué)習(xí)對象相互學(xué)習(xí)；若滿足條件(2)，則以式(6)～式(8)進(jìn)行自我學(xué)習(xí)；若滿足條件(3)，按式(10)計算每個鄰居被選中的概率Psort_j，通過賭輪選擇選出鄰居，根據(jù)式(9)與選中的鄰居相互學(xué)習(xí)。

5)判斷算法是否滿足終止條件，即是否已達(dá)最大迭代次數(shù)Tmax：若否，則轉(zhuǎn)向步驟(2)；若是，已達(dá)到,則輸出最優(yōu)解。

6)輸出最優(yōu)解。

3 仿真測試與分析

3.1 無約束優(yōu)化測試

為了驗證算法的有效性，選取文獻(xiàn)[10]中具有代表性的6個無約束測試函數(shù)，在這6個測試函數(shù)中，f1，f2和f3為單峰值函數(shù)，其極值只有一個，解的精度在一定程度上可以反映算法的局部勘探能力;f4，f5，f6為多峰函數(shù)，在取值范圍內(nèi)存在大量局部極值點，可用于檢驗算法跳出局部最優(yōu)的能力和全局收斂能力。

算法中種群規(guī)模設(shè)置為50，最大迭代次數(shù)設(shè)為500，最大函數(shù)評價次數(shù)50 000，算法終止條件為達(dá)到最大迭代次數(shù)。算法獨立運(yùn)行30次，以平均值和標(biāo)準(zhǔn)差作為評價指標(biāo)。對于最小化問題，平均值越小越接近全局最優(yōu)，表明算法尋優(yōu)性能更好；標(biāo)準(zhǔn)差反映數(shù)據(jù)的離散程度，標(biāo)準(zhǔn)差越小則算法越穩(wěn)定。為測試算法在處理低維和高維優(yōu)化問題中的尋優(yōu)效果，分別將待優(yōu)化函數(shù)設(shè)置為10維和30維，測試結(jié)果列于表1。同時選取文獻(xiàn)[10]中差分進(jìn)化 (differential evolution,DE) 算法、基本(TLBO) 算法和 ETLBO 算法在相同條件下的仿真結(jié)果作為對比。

表1 10維和30維測試函數(shù)尋優(yōu)結(jié)果

表1的結(jié)果表明，無論是處理單峰值還是多峰值問題、低維還是高維問題，CATLBO算法的尋優(yōu)性能都明顯優(yōu)于DE算法。在處理單峰值優(yōu)化問題上，CATLBO算法在低維和高維上表現(xiàn)出的優(yōu)勢并不明顯。其中f1函數(shù)優(yōu)化結(jié)果精度略低TLBO和ETLBO算法，穩(wěn)定性稍差。f2,f3的求解精度略高于其他算法，穩(wěn)定性與其他算法相當(dāng)。

在處理多峰值優(yōu)化問題時，對于f5和f6，CATLBO算法都能準(zhǔn)確找到全局最優(yōu)值，尋優(yōu)性能明顯優(yōu)于其他算法，同時方差為零，表明算法在處理該函數(shù)時穩(wěn)定。在處理另一個多峰值函數(shù)f4時，10維和30維上的實驗所得平均值約為TLBO算法、ETLBO算法的1 %和0.1 %，雖未能到達(dá)全局最優(yōu)，但是其尋優(yōu)精度更高，更接近全局最優(yōu)。TLBO算法和ETLBO算法在處理30維f4時，解的精度相對于10維時并未提高，雖然方差為零，算法穩(wěn)定，但每次都陷入局部最優(yōu)，顯然尋優(yōu)性能不如CATLBO算法。f4，f5，f6三個函數(shù)具有多個峰值，難于優(yōu)化，很容易陷入局部最優(yōu)，但CATLBO算法能夠跳出局部最優(yōu)，求解結(jié)果在均值和標(biāo)準(zhǔn)差兩個指標(biāo)上表現(xiàn)均比較優(yōu)秀。因此，綜合來看，CATLBO算法全局收斂性比其他算法強(qiáng)，能夠在高維多峰值優(yōu)化問題中表現(xiàn)出突出的優(yōu)勢。

3.2 帶約束優(yōu)化測試

在實際工程應(yīng)用中，更多的是帶有約束條件的優(yōu)化問題，因此,選取文獻(xiàn)[17]中的5個帶約束函數(shù)進(jìn)行測試。ETLBO算法中精英個數(shù)取4。種群規(guī)模取50，最大迭代次數(shù)取500，每種算法獨立運(yùn)行30次，以最優(yōu)值、平均值和標(biāo)準(zhǔn)差作為評價指標(biāo)，測試結(jié)果列于表2。同時選取文獻(xiàn)[8]中基本TLBO算法和ETLBO算法在相同條件下的仿真結(jié)果作為對比。

表2 約束測試結(jié)果

可以看出，對于f7和f9，CATLBO算法都能穩(wěn)定地收斂到全局最優(yōu)解，對于f8，TLBO算法和ETLBO算法均未能找到最優(yōu)解，CATLBO算法求解精度和穩(wěn)定性與二者差距不大，但能夠搜索到全局最優(yōu)解，表明其全局搜索能力更強(qiáng)。在處理f10和f11上，CATLBO均能逼近全局最優(yōu)解，求解精度介于TLBO算法和ETLBO算法之間。綜上，在處理帶約束優(yōu)化問題上，CATLBO算法求解精度比基本TLBO算法有較大的提升，全局搜索能力比其他算法更具優(yōu)勢。

3.3 組合優(yōu)化測試

在實際工程優(yōu)化中，除了上述函數(shù)優(yōu)化問題，還有很多離散變量的組合優(yōu)化問題。因此，為了驗證CATLBO算法在組合優(yōu)化中的應(yīng)用效果，本文在包含13個城市的旅行商問題(TSP)[18]上對算法進(jìn)行測試。除使用標(biāo)準(zhǔn)TLBO算法作為參考算法之外，還選擇了遺傳算法(genetic algorithm,GA)，因為GA是解決組合優(yōu)化的經(jīng)典方法。由于TLBO算法針對的是連續(xù)函數(shù)優(yōu)化，因此在解決組合優(yōu)化問題時需做適當(dāng)調(diào)整，算法采用自然數(shù)編碼，將個體更新公式中的加減操作改為遺傳算法中的交叉算子，自學(xué)習(xí)算子改為交換兩個城市的位置。為了消除初始種群對算法的影響，測試時使用同一組初始種群，測試結(jié)果如圖1所示。

圖1 TSP收斂曲線

可知，收斂最快的是標(biāo)準(zhǔn)TLBO算法，但很快陷入局部最優(yōu)。收斂最慢的是GA，但解的精度比基本TLBO算法略高，從曲線的波動可以看出GA波動較大，說明搜索范圍比基本TLBO算法更廣。CATLBO算法得到的解最接近全局最優(yōu)，收斂速度介于二者之間。從曲線中的一段平坦區(qū)域可以看出，算法在陷入局部最優(yōu)若干代后仍然能夠跳出局部最優(yōu)，向全局最優(yōu)收斂，表明該算法全局搜索能力較強(qiáng)，在處理組合優(yōu)化問題中也表現(xiàn)出一定的優(yōu)勢。

4 結(jié) 論

本文針對TLBO算法易陷入局部最優(yōu)的缺陷，提出一種CATLBO算法。仿真實驗的結(jié)果驗證了CATLBO算法的有效性，該算法的尋優(yōu)性能較基本TLBO算法有較大提高，比ETLBO等算法具有更強(qiáng)的全局搜索能力，適合求解高維多峰值優(yōu)化問題。