基于元胞自動機的教與學優化算法*

張琳琳, 陳俊杰, 倪培洲

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

0 引 言

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

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

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

1 TLBO

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

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

(1)

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

(2)

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

2 CATLBO算法

2.1 模型建立

從數學角度可將元胞自動機[13]描述為一個四元組：A=(Ld,S,N,f)。A為元胞自動機系統；Ld為元胞空間，d為空間維數；S為離散狀態集；N為鄰居集合；f為狀態轉換規則。

針對多維函數優化問題，算法在有限的迭代次數內只能搜索可行解的一個子集,即在確定的迭代次數內，種群中個體的狀態可視為有限。為利用元胞自動機的局部性特征，將元胞自動機的作用機理與TLBO算法相結合建立模型，將班級的教學活動類比為一個元胞自動機演化系統，將班級視為元胞空間，采用四邊形網格拓撲結構，將個體視為元胞，放置于網格中的一格，個體狀態根據規則f更新。教學階段仍然針對整個班級，個體在學習階段根據規則f確定不同的學習方式。

2.2 教學階段改進

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

(3)

種群進化初期，包容性強，當新個體出現退步時仍以一定的概率接收。隨著迭代次數增加，接收概率逐漸下降至零，促使算法向全局最優收斂。

2.3 學習階段改進

為減緩算法早熟，學習階段不再隨機選擇學習對象，而是與元胞空間中的鄰居個體相互學習。將學習過程限制在鄰域內，減緩優秀個體影響種群的速度。為了加強算法局部搜索能力，提高解的精度，在學習階段根據規則采用了不同的學習策略。

2.3.1 鄰域結構

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

2.3.2 個體更新規則

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

(4)

式中Xbest_nei為鄰域中適應度最好的個體，即當所有鄰居都比中心元胞優秀時，中心個體向鄰居中的最優個體學習。

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

(5)

即當所有鄰居都劣于中心元胞時，中心元胞利用自學習算子g進行自我學習提升，以提高算法的局部勘探能力。

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

(6)

(7)

(8)

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

(9)

(10)

2.4 CATLBO算法流程

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

2)以目標函數值為適應度，對種群進行評價，選出教師個體Xtea。

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

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

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

6)輸出最優解。

3 仿真測試與分析

3.1 無約束優化測試

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

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

表1 10維和30維測試函數尋優結果

表1的結果表明，無論是處理單峰值還是多峰值問題、低維還是高維問題，CATLBO算法的尋優性能都明顯優于DE算法。在處理單峰值優化問題上，CATLBO算法在低維和高維上表現出的優勢并不明顯。其中f1函數優化結果精度略低TLBO和ETLBO算法，穩定性稍差。f2,f3的求解精度略高于其他算法，穩定性與其他算法相當。

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

3.2 帶約束優化測試

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

表2 約束測試結果

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

3.3 組合優化測試

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

圖1 TSP收斂曲線

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

4 結 論

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