基于元胞自動(dòng)機(jī)的教與學(xué)優(yōu)化算法*

張琳琳, 陳俊杰, 倪培洲

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

0 引 言

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

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

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

1 TLBO

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

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

(1)

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

(2)

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

2 CATLBO算法

2.1 模型建立

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

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

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

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

(3)

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

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

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

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

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

2.3.2 個(gè)體更新規(guī)則

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

(4)

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

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

(5)

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

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

(6)

(7)

(8)

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

(9)

(10)

2.4 CATLBO算法流程

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

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

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

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

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

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

3 仿真測(cè)試與分析

3.1 無(wú)約束優(yōu)化測(cè)試

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

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

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

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

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

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

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

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

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

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

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

圖1 TSP收斂曲線

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

4 結(jié) 論

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