基于拉格朗日插值的教與學(xué)動態(tài)組自適應(yīng)算法

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

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

0 引 言

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

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

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

1 DGSTLBO

DGSTLBO算法是一種有效的全局優(yōu)化方法，通過隨機學(xué)習(xí)策略或相應(yīng)群體的量子行為學(xué)習(xí)策略進行概率學(xué)習(xí)，該算法的主要內(nèi)容為分組和動態(tài)組策略。其偽代碼如算法1所示。

算法1：DGSTLBO算法

(1)Begin

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

(3) 初始化學(xué)習(xí)者， 計算出所有學(xué)習(xí)者的適應(yīng)值。

(4) 執(zhí)行算法2分組；

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

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

(8) 執(zhí)行算法3動態(tài)組策略；

(9)endfor

(10)endwhile

(11)end

1.1 分 組

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

算法2：分組

(1)Begin

(2) 將所有學(xué)習(xí)者按其結(jié)果的降序排列

(3)while(排序的學(xué)習(xí)者不能為空)

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

(5) 按照距離的升序?qū)λ袑W(xué)習(xí)者進行排序；

(6) 選擇前m個學(xué)習(xí)者， 并將其設(shè)置為一個組；

(7) 從學(xué)習(xí)者中刪除當(dāng)前組學(xué)習(xí)者；

(8)endwhile

(9)end

1.2 動態(tài)組策略

通過引入動態(tài)群體學(xué)習(xí)，提出的改進學(xué)習(xí)策略。當(dāng)群體迭代到一定程度后，周期性地改變?nèi)后w，使信息交換覆蓋班級中的所有學(xué)習(xí)者。該策略主要包括教師階段的學(xué)習(xí)者更新和學(xué)習(xí)者階段的學(xué)習(xí)者更新。

1.2.1 教師階段的學(xué)習(xí)者更新

下面給出了更新學(xué)習(xí)者X學(xué)習(xí)的公式

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

(1)

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

1.2.2 學(xué)習(xí)者階段的學(xué)習(xí)者更新

下面給出了DGSTLBO中X學(xué)員量子行為學(xué)習(xí)的更新公式

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

(2)

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

(3)

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

(4)

其中，GroupTeacher表示組中最好學(xué)習(xí)者；Teacher表示全班最好的學(xué)習(xí)者；GroupMean表示學(xué)習(xí)者X自己相應(yīng)組的平均值；φ、β和u是向量，其中每個元素都是[0,1]范圍內(nèi)的隨機數(shù)。動態(tài)組策略偽代碼如算法3所示。

算法3：動態(tài)組策略

(1)Begin

(2)for對每一組

(3)for當(dāng)前組的每個學(xué)習(xí)者X%教學(xué)階段

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

(6) 按式(1)更新學(xué)習(xí)者；

(7)endfor

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

(9)endfor

(10)for當(dāng)前組的每個學(xué)習(xí)者X%學(xué)習(xí)階段

(11)ifrand(0,1)

(12) 執(zhí)行原TLBO的學(xué)習(xí)策略；

(13)else

(14) 按式(2)進行量子行為學(xué)習(xí)；

(15)ifrand(0,1)<0.5

(16) 按式(3)進行量子行為學(xué)習(xí)；

(17)else

(18) 按式(4)進行量子行為學(xué)習(xí)；

(19)endif

(20)endif

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

(22)endfor

(23)endfor

(24)ifmod(gen,P)=0

(25) 執(zhí)行算法2分組；

(26)end

(27)end

2 ADLTLBO算法

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

2.1 拉格朗日插值

(5)

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

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算法在已經(jīng)具有最佳適應(yīng)度xbest的個體的鄰居處進行局部搜索的開發(fā)能力，為了能夠獲得更加精確的全局最優(yōu)解，針對當(dāng)時的全局最優(yōu)位置作二次拉格朗日插值。

(13)

(14)

其中，xbest是j維中最佳個體參數(shù)，Rj是j維中xbest的搜索半徑。可以根據(jù)式(15)以目前種群的分布情況自適應(yīng)地調(diào)整

(15)

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

算法5：LSLI算法

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

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

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

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

(10)end

2.3 自適應(yīng)參數(shù)策略

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

(16)

算法6：ADLTLBO算法

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

(2)初始化學(xué)習(xí)者， 計算出所有學(xué)習(xí)者的適應(yīng)值;

(3) 執(zhí)行算法2分組;

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

(5)While(G

(6)%自適應(yīng)參數(shù)策略

(7)if(rand(0,1)

(10)end

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

(12) 執(zhí)行算法3動態(tài)組策略記錄并更新;

(13)endwhile

2.4 算法流程

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

步驟2 計算適應(yīng)值：計算出每個個體的適應(yīng)值，并記錄最優(yōu)個體與最優(yōu)適應(yīng)值。

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

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

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

步驟7 進行學(xué)習(xí)：當(dāng)rand<0.5時，進行原TLBO算法學(xué)習(xí)，當(dāng)rand>0.5時，采用量子行為學(xué)習(xí)。記錄并更新最優(yōu)個體與最優(yōu)適應(yīng)值。

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

3 數(shù)值實驗分析

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

為了驗證本文所提算法的性能，選取了經(jīng)典的10個基準(zhǔn)函數(shù)數(shù)值優(yōu)化函數(shù)進行了實驗驗證，將改進算法與DGSTLBO算法、TLBO算法、SaDE算法和jDE算法進行對比實驗。

3.1 基準(zhǔn)函數(shù)

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

表1 函數(shù)的詳細(xì)數(shù)值

3.2 參數(shù)設(shè)置

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

3.3 實驗結(jié)果分析

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

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

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

4 結(jié)束語

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

表2 30維和50維測試函數(shù)結(jié)果對比

表3 30維和50維t檢驗結(jié)果對比