基于拉格朗日插值的教與學動態組自適應算法

張 喆，張義民，張 凱，王一冰

(沈陽化工大學 裝備可靠性研究所，遼寧 沈陽 110142)

0 引 言

目前人工智能優化算法在經典問題上得到了越來越廣泛的應用，如工程優化[1]、圖像處理[2]、機械設計[3]等。然而，大多數優化算法還是存在陷入局部最優和處理復雜問題的收斂速度慢等缺陷[4]，因此，解決上述問題成為當前學者普遍關注的熱門問題。

為了解決上述問題，許多學者對此進行了努力。根據努力方向分為以下兩點，第一種是對局部搜索改進來加強算法的尋優能力，文獻[5]通過將自適應策略、競爭性的局部搜索選擇和增量種群規模策略這3種策略集成到標準ABC算法中，提高了算法的性能；文獻[6]將局部搜索方法與進化算法相結合，使混合算法結合了隨機優化和確定性優化的優點，擺脫了搜索最優解的能力弱的問題；文獻[7]針對灰狼算法具有易陷于局部最優缺點,改進收斂因子和引入動態權重，提高了局部搜索能力；文獻[8]從分布在搜索空間中的局部向量中提取良好的向量信息，該向量可以跳出局部最優進行進一步優化。另一種是通過對全局搜索改進來加強算法的尋優能力，文獻[9]基于布谷鳥3種串行行為，提出了一種多策略串行框架，提高了學習策略的全局搜索能力；文獻[10]采用改進的參數自適應方法，通過加入加權均值策略，避免了過早收斂，實現了最優解的全局優化；文獻[11]提出一種改進TLBO的算法，稱為基于教學的動態組策略優化算法(DGSTLBO)，通過加入動態群策略來求解全局優化問題，從而提高算法的全局搜索能力。

不同策略的改進都在一定程度上提高了算法的性能，但是還是避免不了算法陷入局部最優、收斂速度慢和求解精度低的情況。雖然DGSTLBO算法在全局搜索上表現出極其優異的搜索性能，但在解決一些復雜的優化問題時，它仍然存在求解精度低、收斂過早和收斂速度慢的情況[12]。因此，為了使DGSTLBO算法的性能更加完善，本文加入了一種拉格朗日插值的局部搜索，通過選用拉格朗日插值作為局部搜索方法可處理求解多維度優化問題的加速收斂[13]，使得求解精準度更高，為了平衡算法的全局搜索能力和局部開發能力，本文引入了自適應參數策略，以自適應地確定是否使用拉格朗日插值局部搜索在上一代的性能。最終提出了一種基于拉格朗日插值的教與學動態組自適應算法(ADLTLBO)。

1 DGSTLBO

DGSTLBO算法是一種有效的全局優化方法，通過隨機學習策略或相應群體的量子行為學習策略進行概率學習，該算法的主要內容為分組和動態組策略。其偽代碼如算法1所示。

算法1：DGSTLBO算法

(1)Begin

(2) 初始化N(種群大小)，D(維度)，gen(迭代次數)，genmax(最大迭代次數)。

(3) 初始化學習者， 計算出所有學習者的適應值。

(4) 執行算法2分組；

(5)while(沒到最大評估次數就不停止)

(7) 更新班級的老師和每組的平均值；

(8) 執行算法3動態組策略；

(9)endfor

(10)endwhile

(11)end

1.1 分 組

將學習者分成小范圍的群體，以增加種群的多樣性，進而使每個組的組內成員在搜索空間中搜索更有前景的區域。首先選擇第一批m個學習者，并將其作為一個組，然后從當前的學習者中移除選定的m個學習者，當所有的學習者被分成組時，算法終止。其偽代碼如算法2所示。

算法2：分組

(1)Begin

(2) 將所有學習者按其結果的降序排列

(3)while(排序的學習者不能為空)

(4) 評估從第一個學習者到每個學習者的距離；

(5) 按照距離的升序對所有學習者進行排序；

(6) 選擇前m個學習者， 并將其設置為一個組；

(7) 從學習者中刪除當前組學習者；

(8)endwhile

(9)end

1.2 動態組策略

通過引入動態群體學習，提出的改進學習策略。當群體迭代到一定程度后，周期性地改變群體，使信息交換覆蓋班級中的所有學習者。該策略主要包括教師階段的學習者更新和學習者階段的學習者更新。

1.2.1 教師階段的學習者更新

下面給出了更新學習者X學習的公式

newX=X+r*(Teacher-TF*GroupMean)

(1)

式中：Teacher表示全班最好的學習者；TF是一個教學因子，它決定要改變的均值的值；r是一個向量，其元素是[0,1]范圍內的隨機數。

1.2.2 學習者階段的學習者更新

下面給出了DGSTLBO中X學員量子行為學習的更新公式

tempX=φ*GroupTeacher+(1-φ)*Teacher

(2)

newX=tempX+β|GroupMean-X|*ln(1/u)

(3)

newX=tempX-β|GroupMean-X|*ln(1/u)

(4)

其中，GroupTeacher表示組中最好學習者；Teacher表示全班最好的學習者；GroupMean表示學習者X自己相應組的平均值；φ、β和u是向量，其中每個元素都是[0,1]范圍內的隨機數。動態組策略偽代碼如算法3所示。

算法3：動態組策略

(1)Begin

(2)for對每一組

(3)for當前組的每個學習者X%教學階段

(4)TF=round(1+rand(0,1))；

(6) 按式(1)更新學習者；

(7)endfor

(8) 如果f(newX)比f(X)的值好， 則以newX更新X；

(9)endfor

(10)for當前組的每個學習者X%學習階段

(11)ifrand(0,1)

(12) 執行原TLBO的學習策略；

(13)else

(14) 按式(2)進行量子行為學習；

(15)ifrand(0,1)<0.5

(16) 按式(3)進行量子行為學習；

(17)else

(18) 按式(4)進行量子行為學習；

(19)endif

(20)endif

(21) 如果f(newX)比f(X)的值好， 則以newX更新X；

(22)endfor

(23)endfor

(24)ifmod(gen,P)=0

(25) 執行算法2分組；

(26)end

(27)end

2 ADLTLBO算法

本文提出的ADLTLBO算法基礎思想：為了完善DGSTLBO算法在局部搜索上的計算能力以及收斂速度，增強該算法的有效性和可用性，在DGSTLBO算法的基礎上加入拉格朗日插值局部搜索和自適應參數策略。由于拉格朗日插值可以提高算法的開發能力，并幫助加速收斂速度，因此通過采用一種新的自適應參數策略將其引入到DGSTLBO中。本文算法包括兩個主要元素：帶有拉格朗日插值的局部搜索、自適應參數策略。

2.1 拉格朗日插值

(5)

也可以用式(6)表示成一個二次函數，通過求解二次函數的最值來更進一步優化解

P(xj)=a(xj)2+bxj+c,j=1,…,D

(6)

其中

(7)

(8)

(9)

(10)

(11)

(12)

拉格朗日插值算法的偽代碼如算法4所示。

算法4：拉格朗日插值算法

(3) 按式(6)寫出拉格朗日插值多項式；

(4)if(I≠0)

(5)if(a>0)

(7)elseif(a=0 andb=0)

(9)else

(12)endif

(13)else

(16)endif

2.2 拉格朗日插值的局部搜索(LSLI)

引入LSLI的主要目的是提高DGSTLBO算法在已經具有最佳適應度xbest的個體的鄰居處進行局部搜索的開發能力，為了能夠獲得更加精確的全局最優解，針對當時的全局最優位置作二次拉格朗日插值。

(13)

(14)

其中，xbest是j維中最佳個體參數，Rj是j維中xbest的搜索半徑?？梢愿鶕?15)以目前種群的分布情況自適應地調整

(15)

式中： max(xj)， min(xj) 分別是當前維度最大值、最小值，N是種群的數量。

算法5：LSLI算法

(1)輸入: 種群X, 維數D, 種群邊界up、low， 最佳個體xbest, 最佳適應值f(xbest)。

(2)輸出:xbest,f(xbest)。

(3)%使用算法4在xbest的每個維度上進行局部搜索

(5) 初始化xbest相鄰的兩個臨時個體x1和x2;

(10)end

2.3 自適應參數策略

在ADLTLBO算法中，使用自適應參數策略將LSLI插入到DGSTLBO算法中，首先在整個搜索空間中快速地探索問題的解決方案。然后，該方案根據LSLI率(LR)決定是否使用LSLI。最后，該方案自適應地確定是否使用LSLI在發現的最佳解決方案附近進行局部開發，并更新LR，如式(16)所示

(16)

算法6：ADLTLBO算法

(1) 初始化種群N, 維度D,MaxFEs(評估的最大值),m(每組大小), 初始化LR,LRmax和LRmin,xup,xlow。

(2)初始化學習者， 計算出所有學習者的適應值;

(3) 執行算法2分組;

(4)%評估最初個體記住最佳xbest和最佳適應值f(xbest);

(5)While(G

(6)%自適應參數策略

(7)if(rand(0,1)

(10)end

(11) 更新班級的老師和每組的平均值;

(12) 執行算法3動態組策略記錄并更新;

(13)endwhile

2.4 算法流程

步驟1 初始化種群：種群個數N、維度D、重組周期p、每組成員數m、最大迭代次數MaxDT。學習概率pc，拉格朗日插值局部搜索率LR，評估的最大值MaxFEs。

步驟2 計算適應值：計算出每個個體的適應值，并記錄最優個體與最優適應值。

步驟3 對種群個體進行分組：對所有學生進行排序，評估第一名與每個學生的距離，然后按照距離排序，最后選擇m名學生作為一組。

步驟5 更新各組中的老師：計算各組適應值，選擇成績最好者作為老師。

步驟6 進行教學：按式(1)進行教學。

步驟7 進行學習：當rand<0.5時，進行原TLBO算法學習，當rand>0.5時，采用量子行為學習。記錄并更新最優個體與最優適應值。

步驟8 檢查是否滿足終止條件，若滿足，則迭代止，否則重新分組并轉至步驟4。

3 數值實驗分析

本文所有進行的實驗均是在PC機上運行，PC機的配置如下：Intel(R) Core(TM) i7-4712MQ CPU @ 2.30 GHz、內存為8 GB，Windows10操作系統，仿真軟件為Matlab R2015b。

為了驗證本文所提算法的性能，選取了經典的10個基準函數數值優化函數進行了實驗驗證，將改進算法與DGSTLBO算法、TLBO算法、SaDE算法和jDE算法進行對比實驗。

3.1 基準函數

為了測試算法在不同函數上的性能，本文選擇了10個基準函數進行操作，根據函數的性質分為兩大類，其中函數F1～F6為單峰函數，主要測試算法的求解精度。F7～F10為多峰函數，用來測試算法跳出局部極值的能力。每個函數的搜索范圍和理論最優值已在表1中給出。

表1 函數的詳細數值

3.2 參數設置

為減少統計誤差，在30維和50維的情況下，所有算法種群規模都設定為50，每個函數獨立模擬30次，算法使用相同的停止準則，即達到一定數量評估次數(FEs)。在實驗中，FEs取值為10萬。本文算法參數m=5，p=5，pc=0.5。LR=0.5，LRmax=0.9，LRmin=0.1。其余對比算法的參數與原文獻相同。

3.3 實驗結果分析

為了更清晰地觀察改進后算法的收斂效果，通過10個測試函數在30維的收斂曲線來將ADLTLBO算法與DGSTLBO算法、TLBO算法、SaDE算法和jDE算法的收斂情況作對比，在相同函數下的收斂曲線如圖1所示。可以從圖1中明顯發現，單峰函數F1～F5中，由于加入了拉格朗日差值局部搜索，ADLTLBO求解精度和收斂速度大幅度提高，在整個迭代過程中一直持續更佳的收斂速度，尋優效果大幅提升。雖然ADLTLBO、DGSTLBO、TLBO、SaDE和jDE在函數F6都收斂到了理論最優，但是ADLTLBO在收斂速度上還是超過了其余4個算法。在多峰函數F7、F8和F10中，由于加入了自適應參數策略，ADLTLBO無論是在收斂速度還是求解精度上都優于DGSTLBO、TLBO、SaDE和jDE，更容易跳出局部極值。研究結果表明，在函數F1、F2、F3、F4、F5、F6、F7、F8和F10上ADLTLBO算法結果更具有優勢，收斂速度更快。

通過對5個算法分別在30維和50維的10個測試函數上獨立運行30次得到的均值和最優值實驗結果作對比，好的結果用粗體表示，見表2。然后，采用T檢驗[14,15]對算法進行統計分析，通過得到的t值和p值來比較結果之間的差異，見表3，顯著結果用粗體標出。兩個算法的T檢驗采用了雙尾檢驗，顯著性水平為0.05，符號“+”、“-”和“=”分別表示在相同的運行數量下本文算法的性能明顯優于、明顯劣于和類似于所比較的算。

如表2所示，30維和50維下ADLTLBO在函數F1、F2、F3、F4、F5和F7中的結果都比其它算法要好，并且在函數F1～F4中達到了理論值，在函數F6、F8和F10多個算法都達到了理論值，但是可以從圖1中看出ADLTLBO的收斂速度明顯比其它算法要好。通過在10個基準函數的測試下，ADLTLBO在大多數情況下取得了較好的結果，在30維和50維下T檢驗結果中，ADLTLBO算法優良率分別占92.5%和90%。由此可以驗證ADLTLBO算法的局部尋優能力更強、收斂速度更快和求解精度更高。

4 結束語

為了完善DGSTLBO算法在局部搜索上的計算能力及收斂速度的不足，本文提出了一種基于拉格朗日插值的教與學動態組自適應算法(ADLTLBO)，其同時利用了DGSTLBO算法和拉格朗日插值法的優點，為了平衡算法的全局搜索能力和局部開發能力并加入自適應的參數策略，使拉格朗日插值在最佳個體附近執行，本文算法的性能通過對10個基準測試函數在30維和50維與其它4種經典算法進行了比較。從分析和實驗結果表明，本文算法能有效避免陷入局部最優，使得求解精準度更高，收斂速度更快。因此，采用拉格朗日插值的局部搜索技術使本文算法能夠利用局部更有效地提供信息，更頻繁地生成更高質量的解決方案。所提出的具有自適應參數策略的拉格朗日插值局部搜索方案可以插入任何其它教與學算法中，以提高其局部開發能力。

表2 30維和50維測試函數結果對比

表3 30維和50維t檢驗結果對比