具有動態自適應學習機制的教與學優化算法

李麗榮，李木子，李崔燦，王培崇

1.河北地質大學 藝術設計學院，石家莊050031

2.河北地質大學 信息工程學院，石家莊050031

3.河北地質大學 人工智能與機器學習研究所，石家莊050031

1 引言

群智能[1-3]算法是通過模擬生活中的自然現象或某些動、植物群體間競爭、協作進化等行為，實現對優化問題的求解。Rao 和何雨潔等人[4-5]提出的教與學優化（Teaching and Learning Based Optimization，TLBO）就是具有代表性的群智能算法之一，且已被應用于多個工業或學術領域。如：Data Clustering[6]，生物醫學中的TDC時間數字轉換器的優化[7]，工業機器人裝配序列規劃優化[8]，拆卸服務生產線中的服務平衡優化問題[9]，集合聯盟背包問題[10]等。

在TLBO 算法中，標記最優個體為“教師”，其他個體為“學生”，通過模擬一個班級中的“教”和“學”兩種行為，實現對問題的求解。算法原理簡單、參數較少、易理解，且收斂速度較快。但是，相關的研究表明，當待優化問題的維度較高時，該算法也容易出現收斂速度變慢、陷入局部最優等弱點[10]。為了克服算法的這些弱點，改善其性能，文獻[11]提出了一種改進算法（ICTLBO），該算法將種群劃分成多個子種群。“教”過程中，個體通過所在子種群的平均位置和教師個體間的差異信息，被引導著向全局最優所在區域收斂。同時子種群間實施信息交換，以逃離局部最優的約束。在“學”階段引入了全新的學習機制，提高種群的多樣性，并設計了針對三種不同約束情況的處理策略。文獻[12]在TLBO中引入多教師，并將“教”過程中的TF參數修改為自適應變化，同時又引入了討論學習和自我激勵學習機制。一系列的實驗表明，算法改進后效果明顯。文獻[13]在TLBO 中引入局部學習機制和自適應學習機制，以提高算法的搜索能力。在“學”階段，當前個體不僅向種群內的最優個體學習，而且也向隨機產生的個體學習。在自我學習階段，當前個體要么依賴自身的梯度信息更新自身狀態，要么依據種群的平均位置和個體的差異度，隨機勘探新位置。迭代多次后，所有的個體重新排列。于坤杰等[14]針對TLBO算法中種群間缺少信息交流和反饋的問題，提出了一種精英反饋學習機制，利用精英個體的強反饋能力引導種群內狀態較差的個體快速收斂。王滔高等[15]提出了一種基于種群結構分層的改進機制。將學生種群依班級的平均成績劃分為多個等級層次，種群的進化狀態自底向上更新，有效緩解了算法易陷入局部最優的問題。張琳琳等[16]提出了一種基于四邊形網狀元胞自動機模型來處理種群的鄰域和種群更新規則。何杰光等[17]提出將個體分為全局和局部兩種維度。種群內的個體采用全局維度和局部維度混合更新，并設置兩種權重動態調整更新的維度數量。后期引入自我學習機制，強化搜索最優個體周邊和邊界信息。文獻[18]提出了一種應用經驗信息和變異操作的改進TLBO 算法。參考DE算法的變異操作，在“教”和“學”兩個階段引入不同的變異操作。文獻[19]在精英教與學優化算法基礎上提出了一種具有多教師和自我激勵學習的改進TLBO。文獻[20]在TLBO中引入基于個體差異的自主多機制學習，同時令當前個體執行融合高斯搜索的反思機制，協助其跳出局部最優的約束。

為了克服標準TLBO算法的弱點，本文提出了一種具有自適應學習的教與學優化算法，在“教”算子中引入非線性自適應變化的學習因子δ，以克服算法的早熟。算法后期令教師個體執行動態隨機搜索（Dynamic Random Searching，DRS）策略，加強最優個體勘探新解的能力。

2 教與學優化算法

標準教與學優化算法有兩個主要算子，分別是“教”和“學”。

3 動態自適應教與學優化算法

3.1 動態自適應學習

TLBO算法思想源于模擬班級的教學過程，所以從生活中的現象著手改進算法是一種可行的途徑。考慮在教師的“教”過程中，學生新狀態的生成取決于自身狀態的轉化比例和通過學習所獲得知識的轉化比例之和。而標準算法中公式（1）的rand(0,1)×(Xt(t)-β×Xm(t))部分為學生向教師學習獲得的知識，而該式中學生自身的知識狀態完全向新狀態轉化，與現實情況不相符。故將式（1）修改成為式（3），學生的原狀態按比例向新狀態進行轉換。

δ=1/(1+exp(k×(T-2×t)/T))∈(0,1)是一個非線性自適應因子，T 為預設最大迭代次數，t 為當前迭代次數，k 為變化速率。很容易看出來，在算法早期，種群主要向教師個體學習，可以快速向最優個體周圍靠攏。而隨著迭代的進行δ 逐漸增大，個體維持自身狀態能力增強，減緩了向最優個體靠近的速度，避免過早的聚集于教師周圍。而這種機制也與生活中學生的學習行為一致，在早期學生能力較差時，主要向教師學習，快速提升班級的平均分。后期學生狀態提升之后，學生會有選擇的吸收教師傳授的知識，保持自己狀態的能力增強。

3.2 教師的動態隨機搜索

DRS 通過動態調整步長實現對個體周圍空間的精細搜索。在群智能算法中，種群的最優個體包含了較多的引導種群向全局最優收斂的信息。如果群智能算法能夠實現全局收斂，最優個體所形成的搜索空間，一定包含著全局最優解形成的搜索空間。所以，為了提高算法的精度，在算法后期（本文為預設迭代次數的2/3后開始）引入教師個體執行DRS。

算法1DRS算法

輸入：個體X，迭代次數n。

輸出：個體X。

步驟1 初始化步長d。

步驟2 生成向量X′∈[-d,d]。

步驟4 生成向量X1=X+X′和X2=X-X′。

步驟5 選擇X1,X2,X 中優者作為X 。

步驟6 調整步長d。

步驟7 迭代沒有結束，則轉步驟2；否則輸出X ，結束算法。

3.3 算法實現

算法2動態自適應教與學優化算法（Dynamic Selfadapting Learning TLBO，DSLTLBO）

輸入：種群規模n，最大迭代次數M 。

輸出：最優個體Xt(t)。

步驟1 在解空間內初始化種群POP。

步驟2 挑選出最優個體，即教師個體，標記為Xt(t)。

步驟3 基于公式（3）執行“教”。

步驟4 執行“學”算子。

步驟5 如果是算法后期，則教師個體執行DRS算法。

步驟6 算法不滿足終止條件，則轉步驟2；否則輸出最佳個體Xt(t)，終止算法。

3.4 算法的收斂性

證明分析DSLTLBO中個體Xi(t)的搜索。算法早期，“教”算子執行過程，該個體主要向Xt(t)學習，即向最優個體靠近。這種能力，隨著δ 的逐漸增加而被抑制，Xi(t)保持自身狀態的能力逐漸加強，豐富了種群多樣性，減輕了“教”算子帶來的過早的收斂壓力。算法后期，Xt(t)開始執行DRS 算法，加強搜索周圍的局部空間，算法全局、局部搜索得以平衡。DSLTLBO中的“學”算子，賦予了Xi(t)跳出局部最優約束的能力。

不失一般性，以最小化問題min f(X)為研究對象。設解空間A 內有s 個局部最優區域A1,A2,…,As，則DSLTLBO迭代過程中，個體Xi(t)負責區域Ai的搜索，據引理2 知，Xi(t)必收斂到該區域的最優值Yi。由于Xi(t)執行“學”，隨機向某一個同伴Xk(t)學習，所以會搜索該個體所在空間Ak(t)。類推可得，所有局部最優區域會被依次訪問，且可保證收斂到相應的局部最優值，將它們分別標記為：X1b(t),X2b(t),…,Xsb(t)。

由于采取保優策略，如果迭代次數足夠多，則Xgb=min{X1b(t),X2b(t),…,Xib(t)} 必然會收斂到全局最優，即DSLTLBO算法能夠以概率1收斂到全局最優。

3.5 算法復雜度分析

設算法的迭代次數是M ，種群規模n，則算法的時間復雜度是O(M×n) ，空間復雜度是O(n) 。可以看出，本文的算法并沒有增加TLBO的時間復雜度和空間復雜度。

4 仿真實驗與分析

4.1 實驗環境及參數

為了驗證算法的性能，基于C 編程實現DSLTLBO算法，并選擇了文獻[22]中的10個基準函數進行性能測試，分別是：f1：sphere、f2：Rastrigin、f3：Schwefel、f4：Rosenbroke、f5：Griewank、f6：Ackley、f7：Quadric、f8：Schwefel、f9：Six-Hump Camel-Back、f10：Schaffer。除f9最優值是-1.031 628 5，f10的最優值是-1，其余函數的最優值均為0，函數維度設為30 和100。選擇了DE、PSO、AFSA、TLBO[4]、ITLBO[12]、FETLBO[14]、HSTLBO[15]等算法來做對比，DE、PSO、AFSA是較為典型的群智能算法，其他為近年來出現的典型TLBO改進策略。

算法的參數設置：函數維度為30時，所有算法的種群規模均為30，迭代次數為500次。函數維度為100時，種群規模為50；迭代次數設為f1：1 000次，f2：1 500次，f3：1 000 次，f4：1 000 次，f5：2 000 次，f6：1 500 次，f7：1 000 次，f8：1 000 次，f9：2 000 次，f10：2 000 次。函數的評價精度為：f1～f8：10-6，f9和f10的精度為：10-3。為了對比公平，且忽略掉其他因素的干擾，算法都獨立運行30 次。DE、PSO、AFSA 參數均參考相關文獻設置。

4.2 實驗結果分析

表1 和表2 分別列出了函數維度是30 和100 時，參與對比實驗算法的解精度和解方差。當函數維度為30時，f1是一個比較容易優化的單峰函數，此時的FETLBO算法表現最優，DSLTLBO 和HSTLBO 算法稍遜，但是比較ITLBO、TLBO、DE 三個算法有較大的優勢。對于f2、f4兩個多峰函數，本文的DSLTLBO 算法表現是最優的，在其他的幾個多峰和單峰函數上的表現，或者稍遜于HSTLBO 或者稍遜于FETLBO，但是總體要強于ITLBO 等算法。f9、f10是兩個比較難以優化的函數，需要算法具有較好的跳出局部最優約束的能力，DSLTLBO算法的表現還是很優秀，和FETLBO、HSTLBO兩個算法在精度和解方差上旗鼓相當，要較ITLBO、TLBO 算法的解精度高出了很多。另外，觀察表1 中各個算法的解方差，可以看出DSLTLBO 算法的穩定性在f1、f6、f7、f9、f10上是最好的。

表1 30維時算法在Benchmark函數上的運算結果（均值/方差）

表2 100維時算法在Benchmark函數上的運算結果（均值/方差）

當待優化函數維度增加為100時，對群智能算法擺脫局部最優約束的能力要求更高，同時對算法后期勘探新解的能力要求也有所增加。對比表2 和表1 的數值，可以看出，參與對比算法的解精度和解方差均有所下降，橫向對比可以看出TLBO、DE、AFSA、PSO四個算法相對下降較多，對比算法中的FETLBO、HSTLBO、DSLTLBO 相對下降較少；DSLTLBO 的解精度在f1、f2、f3、f8四個函數上表現最好優于其他算法，在f6、f7、f9、f10上和HSTLBO、FETLBO 算法基本一樣。但是f4、f5兩個函數上的表現稍差，略遜于FETLBO 和HSTLBO算法，但差距也并非太大，DE、TLBO、ITLBO算法要明顯遜色于這三個算法。從解方差上看，本文中提出的DSLTLBO算法處于前列。

在表3 中，給出了30 次獨立運算中的成功次數，可以看出，無論是較低維度還是較高的維度，DSLTLBO算法均具有較高的成功率。為了更好地展示算法在收斂速度等方面的優勢，繪制了部分算法在f1～f6函數上的收斂曲線，分別為圖1～圖6，繪圖工具為WPS2019個人版。從六個圖的收斂曲線可以看出，DSLTLBO 算法的收斂明顯優于其他算法，通常都能經過1 000或2 000次迭代，即可快速收斂到最優解周圍，從而進行精細搜索。TLBO算法則在幾個函數上存在跳躍點，而且收斂曲線較平直，DE 算法也存在此問題。ITLBO 算法收斂較好，在f5的收斂較DSLTLBO 算法快速，但是在其他函數上的收斂速度均輸于DSLTLBO算法。

表3 算法的收斂成功次數對比（30維/100維）

綜合以上的對比結果，可以看出DSLTLBO 算法的魯棒性和勘探新解的能力均較優秀。之所以如此，得益于其自身的演化理念和種群的競爭合作方式。算法迭代初期，“學生”主要向“教師”學習。因為δ較小，所以學生個體主要向教師個體學習，快速向最優解周圍收斂，有利于算法的收斂速度。算法的中期，學生個體保持自身狀態的能力增強，放緩了向“教師”個體靠近的速度，算法全局搜索占據主要地位，可以較好地發現未知的新解。算法進入迭代后期，教師個體開始執行DRS算法，加強對于最優周圍空間的精細搜索，提升算法解的精度。同時，種群內的其他個體保持自身狀態的能力繼續增強，使種群具有一定發散性，避免被局部最優約束，出現早熟。從收斂曲線圖可知很直觀的看到，DSLTLBO 算法的收斂曲線下降非常快，種群跳出局部最優約束的能力也較好。

4 結論

針對TLBO算法的弱點，本文提出了如下兩方面的改進。

（1）在“教”階段，引入了自適應學習因子δ，該因子在（0，1）區間內非線性逐漸變化，以使種群在早期快速向最優個體周圍空間收斂，而在后期種群多樣性得以保持，平衡算法的局部搜索和全局搜索。

（2）為了提高算法的求精精度，在算法的后期令教師個體執行DRS 算法，強化對教師個體周圍區域的精細搜索。

利用馬爾科夫鏈技術分析了該算法的收斂性，并在10個經典的測試函數上進行了相關實驗。實驗表明本文提出的DSLTLBO算法具有較好的收斂速度和求解精度，比較適合于求解較高維度連續型的數值優化問題。作為一種具有較高效率的群智能算法，未來將會借鑒傳統演化算法的思想，提高TLBO的效率。探索開拓新的應用領域，也是主要的研究方向之一。