辛梓蕓，張達敏，陳忠云，張繪娟，閆 威

貴州大學 大數(shù)據(jù)與信息工程學院，貴陽550025

1 引言

近年來元啟發(fā)式算法作為一種有效的演化計算技術(shù)，已受到眾多學者的重視。元啟發(fā)式算法是指受到現(xiàn)實環(huán)境的啟發(fā)提出的一類算法，其核心思想是實現(xiàn)搜索過程中隨機性行為和局部搜索的平衡。常用的元啟發(fā)式算法包括布谷鳥搜索算法（Cuckoo Search，CS）、粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）、蟻群優(yōu)化算法（Ant Colony Optimization，ACO）等以及較新的蝴蝶優(yōu)化算法（Butterfly Optimization Algorithm，BOA）都簡單易行、參數(shù)少、運行時間短等特點，因此在解決眾多非線性和多模態(tài)的現(xiàn)實尋優(yōu)問題中，元啟發(fā)式算法呈現(xiàn)了優(yōu)良的可操作性以及尋優(yōu)能力[1-6]。

烏鴉搜索算法[7]（Crow Search Algorithm，CSA）是由Askarzaden 學者在2016 年提出的一種新興的元啟發(fā)式算法，該算法基于長期對烏鴉習性的研究，模擬了該群體之間相互追蹤竊取食物的社會行為，這一特性使算法種群的多樣性并不會隨著迭代有較大的降低，也就增加了跳出局部最優(yōu)的概率。目前該算法已經(jīng)成功應(yīng)用于眾多工程優(yōu)化和函數(shù)優(yōu)化問題中。文獻[8]提出了一種混沌烏鴉算法（Chaotic Crow Search Algorithm，CCSA），引入混沌理論調(diào)整CSA參數(shù)，從四種變體中找到最好的變體以提高全局收斂速度增強尋優(yōu)能力，并將算法用于求解分數(shù)優(yōu)化問題。文獻[9]提出了一種自適應(yīng)步長的烏鴉算法（Modified Crow Search Algorithm，MCSA），有效地開發(fā)了算法的搜索能力，將算法應(yīng)用在非凸經(jīng)濟負荷調(diào)度。文獻[10]提出了基于Levy 飛行策略的混沌烏鴉搜索算法（Levy Differential Evolution Crow Search Algorithm，LDECSA），提高算法跳出局部最優(yōu)的概率，改變編碼方式，將該算法用于求解{0-1}背包問題上。以上算法均主要針對全局搜索性能的提升進行改進，沒有將平衡烏鴉算法的全局搜索性能與局部搜索性能作為研究的重點，算法收斂速度較慢的問題沒有較好地解決。因此本文提出一種基于多段擾動的共享型烏鴉算法（Multi-segment Interference Sharing Crow Search Algorithm，MISCSA），通過引入向最優(yōu)粒子學習的思想，以及在迭代的不同階段加入擾動，使算法同時兼具收斂速度與精度的提升。

2 烏鴉搜索算法

烏鴉被認為是世界上最聰明的動物之一，它們會使用工具、復(fù)雜地交流。在不同的時節(jié)烏鴉會藏匿多余的食物，并在需要時取回。同時它們也互相跟隨，竊取別的烏鴉所藏匿的食物以獲得更好的食物來源。但是當一只烏鴉發(fā)現(xiàn)被跟隨時，它會試圖通過改變藏匿的地點來避免被盜。因此基于以上烏鴉的行為。烏鴉搜索算法有以下原則：

（1）烏鴉以群體形式生活。

（2）烏鴉能夠記得藏匿食物的位置。

（3）烏鴉相互跟隨盜竊食物。

（4）烏鴉對于跟隨者有一定的感知能力，感知到被跟隨就會改變藏匿地點。

其中，fl 表示烏鴉的飛行長度（一般設(shè)置為0.8～2）；APi,iter表示在iter 次迭代中第i 只烏鴉的感知概率（一般設(shè)置0.1～0.4）；ri，rj是[0，1]內(nèi)服從均勻分布的隨機數(shù)。mj,iter表示第j 只烏鴉藏匿食物的位置，其實質(zhì)是第j 只烏鴉在iter 次迭代的最優(yōu)位置。藏食位置的更新公式如下：

CSA的偽代碼如下：

設(shè)置參數(shù)步長fl、感知概率AP、迭代次數(shù)iter 、種群大小N 、維度n；

初始化N 只烏鴉的位置和藏食位置；

While iter ＜itermax

For i=1∶N

隨機選擇一只烏鴉j

If r ≥AP

Else

End If End For

計算適應(yīng)度值FIT(iter)

評估烏鴉的新位置

更新烏鴉的藏食位置

End while

迭代完畢后，m 中儲存的最優(yōu)位置即尋優(yōu)問題中最優(yōu)解的位置。

3 基于多段擾動的共享型烏鴉算法

3.1 加入共享機制的位置更新方式

在烏鴉算法中，烏鴉(i)以隨機方式跟蹤某一烏鴉(j)進行位置更新，這樣的更新方式可以在迭代的前期保持種群較好的多樣性，但是也會使算法的盲目性較大，收斂速度變緩，無法在較短時間收斂到最優(yōu)值。

1995 年Kennedy 學者提出了粒子群算法（PSO）[11]，通過群體內(nèi)個體之間的信息共享來對問題的解進行協(xié)同搜索，即粒子的飛行速度不僅參考自身歷史最優(yōu)位置，也會參考群體中最優(yōu)粒子的位置進行動態(tài)調(diào)整，這使算法具有收斂速度快的特點。因此為了增強算法的領(lǐng)導(dǎo)能力，在烏鴉搜索算法的位置更新部分引入粒子群算法中向最優(yōu)粒子學習的思想，使烏鴉種群共享出環(huán)境中最優(yōu)的藏食位置，即在隨機跟隨某一個體的同時也參考種群中最優(yōu)藏食位置來進行自身更新。烏鴉種群在最優(yōu)藏食位置的領(lǐng)導(dǎo)下，算法大大地提高了收斂速度。新的位置更新公式如下：

3.2 加入擾動策略更新最優(yōu)藏食位置

CSA是一種非貪婪型算法，即當前解如果不優(yōu)于上一代則不會被保留。因此，烏鴉搜索算法到了迭代后期極易陷入局部最優(yōu)。特別是在應(yīng)用于較復(fù)雜的多峰函數(shù)中時，收斂過早且精度低下的缺點更為明顯。其次，3.1節(jié)中改進后的位置更新公式也一定情況影響算法在多峰函數(shù)中最優(yōu)解的精度。對此本文引入趙新超等提出的多段擾動策略[12]用于更新最優(yōu)藏食位置mgbest,iter，即對全局最優(yōu)藏食位置根據(jù)方差可調(diào)的正態(tài)隨機分布進行擾動得到新的全局最優(yōu)藏食位置mgbest′,iter，速度更新公式如下：

其中δ 表示正態(tài)隨機分布的方差，δ 的更新方式如下：

其中，δ 表示正態(tài)擾動的半徑參數(shù)且δ1＞δ2；α1,α2是半徑變化的控制參數(shù)，且α1＜α2；t 是當前函數(shù)值計算次數(shù)，T 是最大函數(shù)計算次數(shù)。在迭代早期δ1取值較大，群體會向全局最優(yōu)藏食位置較大的鄰域內(nèi)搜索；在迭代后期干擾半徑δ2取值較小，則在全局最優(yōu)藏食位置較小的鄰域進行搜索，使得當前解幾乎不再從較優(yōu)區(qū)域跳出保證算法群體僅向全局最優(yōu)解學習，從而保證算法具有較好的收斂性。

結(jié)合3.1、3.2 節(jié)對算法的改進，即在加強全局最優(yōu)藏食位置的領(lǐng)導(dǎo)力的同時，依靠對全局最優(yōu)藏食位置進行不同階段大小不同的擾動可以極大增加算法跳出局部最優(yōu)的概率，使算法達到了全局搜索與局部搜索的平衡，既提高了搜索精度也加快了收斂速度。

MISCSA算法的偽代碼如下：

設(shè)置參數(shù)：步長fl、感知概率AP、迭代次數(shù)iter、最大迭代次數(shù)T、種群大小N、維度n；擾動參數(shù)α1、α2、δ1、δ2；

初始化N 只烏鴉的位置x(0)和藏食位置m(0)；

記錄最優(yōu)藏食位置mgbest,0；

計算初始適應(yīng)度值FIT（0）

While iter ＜itermax

For i=1∶N

隨機選擇一只烏鴉j

If r ≥AP

xi,iter+1=xi,iter+ri×fl×(mj,iter-xi,iter)+sm

Else

xi,iter+1=任意位置

End if

End for

計算適應(yīng)度值FIT(iter)

評估烏鴉的新位置

更新烏鴉的藏食位置

If α1T ＜iter ＜α2T

mgbest′,iter=N(mgbest,iter,δ1)

End

If iter ＞α2T

mgbest′,iter=N(mgbest,iter,δ2)

End

End while

4 仿真實驗

為了驗證MISCSA 算法在求解各類優(yōu)化問題的有效性，本文選取8 個典型的基準測試函數(shù)[13]在不同維度下對CS[14]、CSA[7]、PSO[11]、BOA、MISCSA 的優(yōu)化性能進行比較。

4.1 實驗平臺

該實驗的操作系統(tǒng)為Windows 10，CPU 為Intel Core i5-7300U，主頻2.6 GHz，內(nèi)存8 GB，編程語言為Matlab R2014b。

4.2 實驗設(shè)計

為了公平起見，將最大迭代次數(shù)設(shè)置為1 000，5 種算法針對每一個測試函數(shù)獨立運行50 次，將測試函數(shù)的全局最小值的平均值、標準差、平均耗時作為衡量優(yōu)化性能的指標。并采用Wilcoxon 秩和檢驗比較各算法的優(yōu)越性。

表1中選取的測試函數(shù)中包含單峰、多峰等不同特征的測試函數(shù)。單峰函數(shù)為在定義上下限內(nèi)只有一個嚴格上的極大值（或極小值），通常用來檢測算法收斂速度。多峰函數(shù)為含有多個局部最優(yōu)解或全局最優(yōu)解的函數(shù)，經(jīng)常用于檢測算法探索能力和開發(fā)能力。

表1 基準函數(shù)

5種算法參數(shù)設(shè)置如表2所示。

表2 參數(shù)設(shè)置

4.3 實驗結(jié)果分析

實驗1 CS、CSA、PSO、BOA 和MISCSA 的函數(shù)優(yōu)化結(jié)果比較

為了更好地研究MISCSA算法的優(yōu)化性能，分別在10、30、50 的算法維度下進行50 次獨立尋優(yōu)，并記錄這50次的平均值以及計算其標準差進行比較。結(jié)果如表3～表5所示。

表3 10維實驗結(jié)果分析

通過分析表3～5 的數(shù)據(jù)可知，當求解維度為10 維，CS、CSA在求解單峰函數(shù)(f1～f5)時精度較高，特別CS算法在求解sphere 函數(shù)時高達1E-12，表現(xiàn)出了較好的尋優(yōu)能力，稍優(yōu)于CSA，但是隨著變量維度的增加，這兩個算法的搜索能力均有明顯的下降，對于50 維的sphere 函數(shù)算法CS、CSA 求解的精度均為1E+00，降低了9 個數(shù)量級以上。對于f6～f8 這一類復(fù)雜的多峰函數(shù)，明顯CS和CSA不論低維還是高維的求解的精度都不理想，即使在10維條件下，最高精度也沒有超過1E+2，說明算法的全局開采能不足，存在不同程度的早熟收斂現(xiàn)象。

表4 30維實驗結(jié)果分析

作為新型智能算法BOA，除了f5 和10 維的f6 其余函數(shù)在高維度和低維度問題均收斂到了10E-10 精度以上，明顯相較于CSA和CS算法都表現(xiàn)出更強的尋優(yōu)能。但是對比3個維度上BOA算法在求解某些函數(shù)，比如Rastigin、Griewank，可以發(fā)現(xiàn)收斂情況不穩(wěn)定，均值的波動較大，說明函數(shù)維度的改變對該函數(shù)影響較大。

表5 50維實驗結(jié)果分析

本文提出的MISCSA 算法不僅在簡單的單峰函數(shù)的求解均值都相較于以上3種算法更高，大部分函數(shù)的精度遠高出CS、CSA 算法10 個數(shù)量級以上，高出BOA算法7個數(shù)量級以上，而且在求解復(fù)雜的多峰函數(shù)時表現(xiàn)出了優(yōu)秀的尋優(yōu)能力，特別是具有大量按照正弦拐點排列的局部最優(yōu)值的Rastigin 函數(shù)和Griewank 函數(shù)，MISCSA 算法分別在10、30 和50 維均搜索到了函數(shù)最優(yōu)值。由此認為在位置更新中加入共享機制促使烏鴉群體快速向優(yōu)良解區(qū)域移動，提高收斂速度。并且多段擾動策略的加入使MISCSA 在進化的過程中很大程度上保持種群多樣性，避免陷入局部最優(yōu)。其次，表3～5中的標準差也反映了算法在求解中的穩(wěn)定性。算法CS、CSA 隨著求解維度的增高，標準差值明顯增加，說明兩個算法在求解高維度問題時算法的穩(wěn)定性較差。而MISCSA 算法相較于CS、CSA、BOA 都低，說明算法的穩(wěn)定性更好。

在算法運行時間方面，明顯PSO在不同的維度下以及不同測試函數(shù)的平均耗時都最少，CSA 第二，而MISCSA又要優(yōu)于CS和BOA。MISCSA改進了原始算法位置更新公式，使個體加速向全局最優(yōu)的位置靠近，因此也增加了算法的耗時。在不同迭代階段加入擾動，也一定程度增加了耗時，但是在10 維下的平均耗時與CSA相比沒有超過0.2 s，30維下沒有超過0.5 s，而50維的搜索維度下也沒有超過1 s，均是在可接受范圍內(nèi)。

實驗2 CS、CSA、PSO、BOA 和MISCSA 的迭代曲線對比

為了更加直觀地分析5 種算法在迭代過程中的尋優(yōu)能力。記錄下算法在30 維度下求解8 個函數(shù)的迭代曲線如圖1～8 所示。迭代圖的橫縱坐標分別表示迭代次數(shù)和平均適應(yīng)度值取對數(shù)（lg）。

圖1 Sphere函數(shù)平均收斂曲線

圖2 Schwefel2.22函數(shù)平均收斂曲線

圖3 Schwefel2.2函數(shù)平均收斂曲線

圖4 Schwefel2.21函數(shù)平均收斂曲線

圖5 Quartic函數(shù)平均收斂曲線

圖6 Rastigin函數(shù)平均收斂曲線

圖7 Quartic函數(shù)平均收斂曲線

圖8 Griewank函數(shù)平均收斂曲線

由圖1～8可看出，原始CSA的曲線在尋優(yōu)前期大概30 代左右相較CS 有較快速的下降，但是后期沒能保持優(yōu)勢，收斂速度放緩，表現(xiàn)出算法后期的全局開采能力較弱的問題。BOA 作為全局性搜索算法與MISCSA 具有相似的收斂趨勢，并且是除MISCSA外具有最好的收斂速度與精度。本文提出的MISCSA 在計算每一個函數(shù)的進化初期其個體質(zhì)量就明顯優(yōu)于CS、CSA和BOA算法，隨著迭代次數(shù)的增加，MISCSA 的曲線下降非?？?，并且在迭代后期具有持續(xù)尋優(yōu)的能力。圖5～8 是多峰函數(shù)的平均收斂曲線，可以看出算法MISCSA具有良好的收斂速度與精度。對于Griewank 函數(shù)和Rastigin，PSCSA 在200 代以內(nèi)搜索到函數(shù)的最優(yōu)值0，并且在迭代過程中并沒有出現(xiàn)明顯的拐點。由此說明對于這一類的多峰函數(shù)，MISCSA 具有很強的搜索能力，可以快速跳出局部最優(yōu)值束縛向全局最優(yōu)點靠近。

實驗3 統(tǒng)計檢驗

基于50次獨立運行算法的平均值和標準差不會比較每次運行結(jié)果。Derrac 等在文獻[15]中提出，對于改進進化算法性能的評估，僅基于平均值和標準偏差值來比較算法優(yōu)劣不夠嚴謹，應(yīng)該進行統(tǒng)計檢驗。通過統(tǒng)計檢驗以證明所提出的改進算法比其他現(xiàn)有算法具有顯著的改進優(yōu)勢。為了判斷MISCSA 的每次結(jié)果是否在統(tǒng)計上顯著地與其他算法的最佳結(jié)果不同，Wilcoxon統(tǒng)計檢驗在5%的顯著性水平下進行。在表6中給出所有基準函數(shù)的MISCSA 和其他算法的Wilcoxon 秩和檢驗中計算的p-value。例如，如果最佳算法是MISCSA，則在MISCSA/CS、MISCSA/CSA 等之間進行成對比較。由于最佳算法無法與自身進行比較，因此，針對每個函數(shù)中的最佳算法標記為N/A，表示“不適用”。這意味著相應(yīng)的算法可以在秩和檢驗中沒有統(tǒng)計數(shù)據(jù)與自身進行比較。根據(jù)Derrac 等人的論文，那些p-value ＜0.05 的可以被認為是拒絕零假設(shè)的有力驗證。

根據(jù)表6中的結(jié)果，因為BOA計算50維的f6 和10維的f8 也同時收斂到全局最小值0所以該統(tǒng)計檢驗不適用。其他的MISCSA的p-value 全部小于0.05，這表明該算法的優(yōu)越性在統(tǒng)計上是顯著的，即認為MISCSA算法比CS、CSA和BOA具有更高的收斂精度。

表6 Wilcoxon秩和檢驗的p 值

綜上所示，基于多段干擾的共享型烏鴉算法對于大部分的基準函數(shù)具有良好的尋優(yōu)結(jié)果，有效地解決了原始烏鴉算法收斂速度緩慢和在搜索后期易陷入局部最優(yōu)問題，在沒有增加太多運行時間以及編程步驟的情況下使烏鴉算法的收斂速度和搜索精度有較大的提升。

5 結(jié)束語

通過對原始烏鴉算法的原理和更新公式進行研究與分析，針對算法收斂速度緩慢以及后期的搜索精度低等問題，本文提出了MISCSA算法。MISCSA在位置更新公式中加入了共享機制，在單純的隨機性跟隨行為中加入跟隨全局最優(yōu)位置的思想，達到了多樣性與收斂性的共存；針對全局最優(yōu)解在不同的迭代時期進行擾動，可以使算法擴大了種群的搜索范圍，在迭代后期具有強大的跳出局部最優(yōu)的能力。結(jié)合以上兩點改進，使算法在全局搜索與局部搜索之間達到了平衡。文中的測試結(jié)果也表明了MISCSA 的尋優(yōu)能力優(yōu)于原始算法與其他算法。下一步工作中，將MISCSA算法應(yīng)用于工程問題上，進一步地驗證算法的有效性。