具備反向學習和局部學習能力的磷蝦群算法

肖素瓊，羅 可

1.長沙理工大學 計算機與通信工程學院，長沙 410114

2.長沙理工大學 綜合交通運輸大數據智能處理省重點實驗室，長沙 410114

1 引言

2012年，Gandomi和Alavi通過對磷蝦群活動規律進行研究發現，磷蝦群個體在運動過程中會受到周圍磷蝦和估算的食物位置的綜合影響，并不斷向最優位置（食物）移動。他們采用拉格朗日模型來解釋該行為，并提出了一種新型仿生優化算法—磷蝦群算法（Krill Herd，KH）[1]。

KH算法相比其他的智能優化算法具有控制參數少（僅有時間間隔參數Δt需要微調）、易于實現，且在連續空間的非線性優化性能強等優點，已被廣泛應用于工程技術和科學研究等領域[2-4]。但其存在的易陷入局部最優以及收斂速度慢等問題嚴重制約它的發展。造成KH早熟的直接原因是由于代表全局最優值的食物位置實際是由所有磷蝦當前位置所估計的，在進化末期，一旦磷蝦群個體聚集在極值點附近，形成高密度蝦群，優質個體的影響力趨于同質，便很難跳出局部最優解，這種現象在處理復雜多峰優化問題時顯得尤為突出[5-8]。針對這些問題，文獻[5]提出了一種模擬退火算法的磷蝦群優化算法以解決全局優化任務。文獻[6]將KH算法與整合增量學習算法相結合，解決KH算法多式聯運時收斂速度慢的問題。文獻[7]將布谷鳥搜索思想引入磷蝦群算法，通過對磷蝦個體的遺棄和更新來達到快速收斂的目的。文獻[8]提出混合KH算法的量子粒子群優化算法，以增強算法的全局探索能力。文獻[9]以反向學習為基礎，結合柯西變異算子和定位夾緊算子，以提高種群多樣性和逃離局部最優解的能力。類似的研究包括文獻[10-12]，一定程度克服了KH算法的不足，但大都僅針對單方面的缺陷進行改進。

鑒于上述分析，本文提出具備反向學習和局部學習能力的磷蝦群算法。首先利用混沌映射和反向學習的思想初始化種群，然后改進廣義的精英反向學習策略，引入根據算法迭代次數自適應調整學習維度的思想，對精英個體進行反向學習，擴大搜索區域范圍，提高種群的多樣性，迅速逼近全局最優解，最后，選取精英群體，通過自適應的Lévy飛行分布和改進的差分變異算子，提高種群局部搜索能力和算法的收斂速度。

2 相關基礎

2.1 KH算法

KH算法是對自然界磷蝦群覓食活動的模擬。磷蝦群個體在運動過程中通常形成一定的結構，磷蝦群密度和食物吸引是影響該結構的兩大主要因素。磷蝦個體的移動位置可以用拉格朗日模型建模：

KH算法中，引導移動向量Ni()k不僅受到周圍磷蝦個體的局部吸引，也受到當前全局最優個體的吸引。因此，Ni(k)定義為：

其中，Nmax為最大引導速度，ωn∈[ ]0,1為慣性權重，表示受周圍磷蝦個體吸引的運動向量，表示受當前最優個體吸引的運動向量。

覓食移動向量Fi(k)由覓食經驗及食物指引兩部分構成，定義為：

其中，νf為覓食速度，ωf∈[0 ,1]為慣性權重，為食物的吸引程度，為個體歷史最優的覓食位置的吸引值。

物理擴散向量Di()k被看作是一個隨機搜索過程，定義為：

其中，最大擴散速度用Dmax表示，δ∈[-1,1]表示當前的隨機方向向量。

基于以上定義的三種運動，磷蝦個體位置更新公式為：

其中，Δt是與實際應用有關的時間間隔。更詳細的KH算法參數取值方法及步驟參見文獻[1]。

2.2 精英反向學習

反向學習（Opposition-Based Learning，OBL）策略是由Tizhoosh[13]提出的智能計算領域中的一種新技術，其基本思想是對于一個可行解，生成其反向解，同時評估當前解和反向解，選擇較優的解作為下一代個體。并說明了反向解要比當前解有約50%的概率靠近全局最優。

定義1反向點[14]（Opposite Point），設X=(x1,x2,…,xD)是D維空間中的一個點（可視為可行解），xj∈[aj,bj]，其對應的反向點可定義為

定義2精英反向解[15（]elite opposition solution）。設當前群體中的精英個體為Xi=(xi,1,xi,2,…,xi,D)，相應的精英反向解定義如下：

其中，Xi,j∈[aj,bj],k∈[ ]0,1為一般化系數。

3 改進后的KH算法

KH算法在優化過程中，種群的多樣性和算法的收斂速度之間始終存在著矛盾。對標準KH算法的改進，無論是參數的選取還是其他算法與KH的融合，其目的都是希望在保持種群的多樣性的同時，加強算法局部的搜索能力，防止算法在快速收斂的同時出現早熟。本文所提出算法也是基于這一思想，即利用混沌映射和反向學習的思想初始化種群，并通過改進的自適應維度的精英反向學習策略，保持種群的多樣性，同時，選取精英群體，通過自適應的Lévy飛行分布和改進的差分變異算子，提高種群的局部搜索能力。具體采用的改進策略如下。

3.1 基于混沌反向學習的種群初始化

基本的KH算法隨機確定初始磷蝦群的位置，若隨機生成的初始值不佳，則對算法的收斂速度以及最終的實驗結果造成影響。最近有研究表明，利用混沌初始化和反向學習初始化均取得了較好的實驗結果。混沌映射因具有隨機性、靈敏性等特點，可以滿足算法搜索的多樣性[16]。同時，文獻[17]已經從理論上證明了基于反向學習的種群初始化可以得到較好的初始解，進而加快收斂速度。因此，本文利用這兩種初始化方法的優點，提出了基于混沌映射和反向學習的思想生成初始化種群。混沌映射表達式為：

其中，k為迭代次數，Max_k是混沌迭代設定的最大次數。

算法1初始化種群算法

步驟2 生成反向種群

步驟3比較初始種群和反向種群，選擇N個適應度最優的個體組成初始種群。

3.2 基于自適應維度的精英反向學習

文獻[15]提出了精英反向解的概念，并從理論上證明了大多數精英粒子的反向解比普通粒子的反向解更靠近最優解。因而，在搜索過程中引入精英粒子的反向解，可拓寬群體的活動區域，提高種群多樣性，有利于避免算法陷入局部最優。但在KH改進算法中，若每次迭代都對精英個體位置所有維度進行反向學習，則有一定的盲目性。受文獻[18]采用的基于部分維度反向學習策略啟發，提出了根據算法迭代次數自適應調整學習維度的精英反向學習策略。一般而言，在進化初期，對精英個體位置選擇較大維度進行學習，能有效提高種群的多樣性，有更多向全局最優解逼近的機會。在末期，磷蝦群已基本接近最優解，可以保留精英個體位置大部分維度優勢信息，而僅進行較小維度學習，開發更高精度解。維度更新公式如下：

其中，dim_size表示反向學習維度大小，iter為當前迭代次數，max_iter為最大迭代次數，D為維度表示不大于?的整數。

本文采用群體選擇機制，設p()g為當前群體，選擇適應值最優的個體作為精英個體，根據公式（8）計算當前迭代下進行精英反向學習的維度數，再隨機選擇相應數量維度根據公式（6）進行精英反向學習產生精英個體所對應的反向群體Eop(g )，從中選擇NP個最好的個體組成下一代個體p(g +1)。其中，NP為種群大小，精英個體由適應度最低的a%磷蝦個體向量組成，取值為a=10。

顯然，與KH改進算法采用單純的精英反向學習策略相比，自適應調整學習維度的精英反向學習策略能在相同迭代次數下，節省算法運行的時間。同時，精英反向學習策略的采用有利于保持種群的多樣性，一定程度地避免算法陷入局部極值。

3.3 精英磷蝦群局部學習

基本的KH算法，搜索完全取決于隨機游走，因此不能保證算法快速收斂。針對這一問題，用改進的精英磷蝦群局部學習代替基本KH算法的隨機擴散，主要進行了三方面的改進。（1）改進差分變異搜索算子。以差分進化算法思想為基礎，選取了變異選擇操作，并對其進行了優化設計，以加強種群的局部搜索能力。（2）基于Lévy飛行引入自適應步長α。α在迭代的過程中自適應減少，這是類似基本KH[1]中慣性常數遞減的原因，目的是為了更好的進行搜索，以接近全局最優解。（3）考慮到精英群體比普通群體具有更優的搜索信息空間，所以，在改進算法中，僅添加精英群體之間的局部搜索以達到更快收斂的目的。通過測試基準函數，選取的精英群體占35%能取得最好的結果。

實現思路如下：

（1）在精英群體中，對每個個體xi，在搜索半徑內隨機選擇第二個精英個體xj，并利用兩者之間的差分結果指導xi進行局部搜索，增強xi鄰域內的搜索能力，如式（9）所示：

在式（9）中，r∈[-1,1]是服從均勻分布的隨機數，用于控制搜索方向；dt為第t代時的縮放因子，搜索前期，進行全局大范圍的搜索，加快收斂速度；而進化末期，通過較小的步長逐步求得更高精度的解。因此，dt采用線性遞減策略控制搜索半徑，表示為：

（2）考慮選擇的隨機性，以及到進化后期，磷蝦群形成高密集型種群，可能導致同時選中同一位置的磷蝦。在這種情況下，采用自適應Lévy飛行方程進行局部搜索，則xi位置更新為：

其中levy(λ)表示隨機游走路徑，服從概率分布levy～u=為點乘積，步長，A為最大Lévy飛行步長，G為當前迭代次數，用于控制搜索范圍。

（3）對局部搜索的結果x′i采用貪婪保留策略，即：

上式中，fit()

x為x的適應值。

3.4 改進算法—RLKH算法

（1）初始化參數：種群規模NP，設置覓食速度Vf，最大擴散速度Dmax，最大誘導速度Nmax，最大Lévy飛行步長A，精英磷蝦占總磷蝦群的比例Pa，精英磷蝦的數量，迭代次數G=1。

（2）執行算法1，初始化種群 p(g)。

（3）從 p(g)中選擇適應度最優的前10%的個體作為精英群，根據公式（6）、（8）產生精英個體的反向解，加入反向種群Eop(g)，從中選擇NP個適應值最好的個體組成下一代種群p(g+1)。

根據公式（1）進行誘導運動；

根據公式（2）進行覓食運動；

選取當前磷蝦所處位置xi，隨機從精英磷蝦群中選擇磷蝦xj；ifxi=xjthen

計算Lévy飛行步長，生成新的磷蝦 x′i，并計算適應值 fx′i；

else

x′i=xi+r?dt(xi-xj)并計算適應值 fx′i；

比較 fx′i與 fxi，保留適應值較優的磷蝦個體；

重新評價種群適應值及當前最優個體；

（5）若G

4 實驗與結果分析

為了檢驗本文所改進算法的性能，將RLKH算法與基本的KH算法以及最近提出的KH-QPSO算法[8]和OKH算法[9]進行性能對比。

4.1 測試函數與參數設置

本文選用8個經典測試函數進行測試，其中，f1～f3為單峰連續優化函數，常用于考察算法的執行效率。f4～f8為多峰連續優化函數，存在多個局部極值，且數量隨維度增加，常用于測試算法擺脫局部極值和全局尋優能力。實驗基準函數見表1。

實驗參數設置為：（1）對于四種算法的共同參數，依據文獻[19]的模型進行如下設置：種群規模NP=50，最大誘導速度Nmax=0.01，最大覓食速度Vf=0.02，最大擴散速度Dmax=0.005，慣性權重ωf和ωn的值隨著迭代次數從0.9線性變換為0.1。（2）KH-QPSO算法和OKH算法除共同參數外，均按照其參考文獻提供的最優參數進行設置。（3）對于本文的RLKH算法，設置最大Lévy飛行步長A=1，經過反復的實驗對比，精英磷蝦比率Pa設置為0.35。

此外，所有實驗均在操作系統為Windows 10，雙核Intel處理器和4 GB內存，Matlab2014的平臺上完成。

4.2 時間復雜度

設種群規模為NP，算法最大迭代次數為Imax，評價磷蝦個體適應值1次的時間復雜度為O(f)。對于基本的KH算法，時間復雜度為O(Imax?(f?NP))。KH-QPSO算法每次迭代操作時都要計算每個粒子的局部最優位置，以此達到函數的最優解決方案，而平均最優位置計算消耗了較多的時間。例如，若測試函數維數為D，則每次迭代更新該種群最少需要進行NP(D+1)次計算。算法時間復雜度為O(Imax?f?NP(D+1))。OKH利用反向學習初始化種群，引入了柯西變異算子和定位加緊算子，其中每個磷蝦個體位置更新都需要計算權重w(j)，則算法時間復雜度為 O(Imax?f?(NP+1))。本文RLKH算法采用混沌反向學習初始化方法，雖然增加了NP次計算，但僅在種群初始化時構建一次。利用精英反向學習策略也僅是選擇種群10%的個體。采用改進的精英磷蝦群局部搜索代替標準KH算法的隨機擴散，只是改變了學習方式，并未增加額外的時間消耗。同時，本文選取35%的精英磷蝦個體執行主體改進算法，大大節省了整個算法收斂時間。RLKH算法整體的時間復雜度為O(0.35?Imax?f?NP)。因此本文改進算法比其他三種算法耗時要少。

表1 基準測試函數

4.3 實驗結果及分析

為了消除算法的隨機性影響，每種算法在函數上獨立執行30次，最大迭代次數設置為2 000次，并統計優化結果均值（Mean）和標準差（Std）。優化結果均值反映了給定最大迭代次數下算法的尋優精度，標準差反映了算法的魯棒性。具體統計數據見表2。

從表2可以看出，固定函數迭代次數下，RLKH算法在單模態函數和多模態函數上均取得了最優的表現。對于形式簡單的單峰函數 f1，RLKH算法能快速收斂到全局最優解0。對于最優解附近陡峭而極其難以極小化的病態二次函數 f2，RLKH在迭代后的最終收斂精度為2.59×10-2，比其他算法至少提高3個數量級。對于相對容易收斂的多峰函數 f4，RLKH的收斂精度在10-11以上。對于存在大量局部極值的復雜多峰函數 f5～f8，RLKH仍能收斂到最優值附近，收斂精度顯著優于其他三種算法。此外，KH算法的收斂精度在所有函數上最差，OKH算法的收斂精度優于KH-QPSO算法，但在8個基準測試函數上明顯劣于本文算法。

為了更加直觀地比較各算法的收斂速度和尋優性能，圖1給出了各算法在不同測試函數上的收斂曲線。限于篇幅，只給出了6個函數上的實驗結果。可以觀察到以下主要現象：（1）RLKH算法能夠獲得較好的初始值。（2）RLKH算法具有最優的精度和最快的收斂速度。例如，在Rosenbrock函數上迭代次數約為250次的尋優精度甚至優于其他三種算法在迭代次數2 000次的結果。（3）RLKH算法的收斂曲線在中后期仍有減緩的下降趨勢。實驗現象（1）表明本文采用的混沌反向學習的種群初始化可以得到較好的初始解，進而加快收斂速度。實驗現象（2）和現象（3）表明本文算法采用的精英局部搜索策略具有優異的尋優效率，采用的自適應的Lévy飛行分布和改進的差分變異算子使得算法能迅速向最優解靠近，具有很強的局部尋優和跳出局部最優解的能力。

表2 四種算法的實驗結果比較

圖1 測試函數的進化曲線

與本文RLKH算法相比，KH算法的收斂曲線下降緩慢，除函數 f1和 f4外，基本上陷入了局部極值且收斂精度最低。KH-QPSO算法混合了量子粒子群算法，一定程度增加了種群的多樣性，但尋優機制未發生變化，因而其收斂速度和精度并沒有得到明顯的改善。OKH算法利用柯西變異算子能提高算法的探索能力，使種群能快速靠近最優解，因此算法前期的收斂速度較快，但后期缺乏有效的擺脫局部極值的機制，收斂速度趨緩，未能達到較高的收斂精度。

綜上所述，相比其他三種算法，RLKH算法在收斂速度和精度方面具有明顯的優勢，是一種有效的全局優化算法。

5 結論

為了改善基本KH算法在處理復雜多峰優化問題時容易早熟、收斂速度慢等不足，提出具備反向學習和局部學習能力的磷蝦群算法。利用混沌映射和反向學習的思想初始化種群，可以得到較好的初始解。通過改進的自適應維度的精英反向學習策略，提高種群的多樣性，并迅速逼近全局最優解。最后選取精英群體，通過自適應的Lévy飛行分布和改進的差分變異算子，加強種群局部搜索能力的同時使算法能更快的收斂。實驗結果表明，本文提出的RLKH算法相對于標準的KH算法及最近的KH-QPSO算法和OKH算法具有更高的收斂速度和較高的求解精度，具有良好的應用前景。