融合柯西變異和反向?qū)W習的改進麻雀算法

毛清華，張 強

燕山大學 經(jīng)濟管理學院，河北 秦皇島066004

+通信作者E-mail:1456642771@qq.com

群智能優(yōu)化算法是受到大自然生物界的啟發(fā)，模擬自然界中的一些事物或生物的行為規(guī)律，在解空間內(nèi)進行全局尋優(yōu)。近幾年新的群智能優(yōu)化算法不斷涌現(xiàn)，學者們通過螞蟻、狼、鳥類、飛蛾、鯨魚、麻雀等生物行為，提出了一系列的群智能優(yōu)化算法，如：蟻群算法（ant colony optimization，ACO）、灰狼優(yōu)化算法（grey wolf optimization，GWO）、飛蛾火焰優(yōu)化算法（moth-flame optimization，MFO）、鯨魚優(yōu)化算法（whale optimization algorithm，WOA）、麻雀搜索算法（sparrow search algorithm，SSA）等。由于群智能優(yōu)化算法具有易操作、魯棒性強、應用范圍廣的優(yōu)點，被眾多學者所關(guān)注。其中麻雀搜索算法于2020年由Xue 等[1]首次提出，是一種新型群智能優(yōu)化算法。麻雀搜索算法與其他算法相比，具有求解效率更高的特點。然而，在算法迭代后期仍然和其余智能算法一樣，容易出現(xiàn)困于局部極值的問題。

為改善群智能優(yōu)化算法在迭代后期容易陷入局部最優(yōu)的不足，提高全局尋優(yōu)能力，眾多學者都提出了不同的改進策略：Oliva 等[2]利用混沌算子對鯨魚位置更新概率進行混沌映射，提高全局尋優(yōu)性能。楊萬里等[3]將Logistic 混沌映射應用到粒子群算法中，增強了解的多樣性，一定程度降低了算法困于局部空間的概率。Hegazy 等[4]通過添加自適應權(quán)重因子，加快算法的收斂速度，并成功應用于特征選擇問題。Wang 等[5]提出一種自適應慣性權(quán)重，改變了速度的更新方式，使蝙蝠在搜索過程中能夠動態(tài)自適應地調(diào)整速度。王依柔等[6]加入正弦變化的慣性權(quán)重因子改變園丁鳥的位置更新方式，有效平衡了全局與局部的開發(fā)能力。Wang 等[7]引入柯西變異算子，避免螢火蟲算法陷入局部最優(yōu)，提高了全局搜尋能力。Li 等[8]通過引入非線性控制參數(shù)和柯西變異，提高了粒子群算法收斂速度和精度。Wen 等[9]將反向?qū)W習策略應用到粒子群算法中，不但豐富了種群的多樣性，而且全局探索能力得到有效提高。Xu 等[10]將高斯變異與柯西變異融合到飛蛾算法中，增強了局部和全局的探索能力。Pappula 等[11]借助柯西突變能力使貓群朝全局最優(yōu)解靠近，防止早熟現(xiàn)象的發(fā)生。

以上文獻對群智能算法的改進，在一定程度上減小了算法落入局部極值的可能性，但是，仍存在收斂精度低、開發(fā)能力不足等缺陷。考慮到Sin 混沌映射具有較好的混沌特性、自適應權(quán)重，可以有效地協(xié)調(diào)局部開采和全局探索以及柯西變異和反向?qū)W習策略具備較強的擾動變異能力，能有效提升算法逃離局部空間等特點，提出一種融合柯西變異和反向?qū)W習的改進麻雀算法（improved sparrow algorithm combining Cauchy mutation and opposition-based learning，ISSA）。利用Sin 混沌映射初始化麻雀種群，豐富解的多樣性；在發(fā)現(xiàn)者位置更新方式中引入上一代全局最優(yōu)解，提升全局搜索的充分性，同時添加自適應權(quán)重，協(xié)調(diào)局部挖掘和全局的開采能力，并加快收斂速度；融合柯西變異和反向?qū)W習策略，對最優(yōu)解位置進行擾動變異，提升抗局部極值能力；最后對8 個基準測試函數(shù)進行仿真實驗以及Wilcoxon 秩和檢驗，并對時間復雜度進行分析，驗證了ISSA 的有效性與可行性。

1 基本麻雀搜索算法

麻雀搜索算法受到生物界麻雀捕食和反捕食行為的啟發(fā)而提出。麻雀集合矩陣如下：

式中，N是麻雀的規(guī)模，i=1,2,…,N，d是變量的維數(shù)。

麻雀的適應度值矩陣表示如下：

其中，N表示麻雀的數(shù)量，而Fx中的每個值表示個體的適應度值。適應度值更優(yōu)的麻雀率先取得食物，并作為發(fā)現(xiàn)者帶領(lǐng)整個種群向食物源靠近。發(fā)現(xiàn)者的位置更新方式如下：

其中，表示第i個麻雀在第j維的位置，t表示當前迭代次數(shù)，j=1,2,…,d。itermax表示最大迭代次數(shù)，α∈(0,1) 范圍的一個隨機數(shù)，R2（R2∈[0,1]）、ST（ST∈[0.5,1.0]）依次代表預警值和安全值。Q為服從[0,1]正態(tài)分布的隨機數(shù)。L為1×d的矩陣，且矩陣內(nèi)每個元素為1。當R2＜ST，表示附近沒有天敵，發(fā)現(xiàn)者實行廣泛搜索模式；如果R2≥ST，這意味著一些麻雀已經(jīng)察覺到了天敵，則整個種群需要盡快前往其他安全區(qū)域。

跟隨者的位置更新公式如下：

式中，Xworst表示全局最差的位置，A為1×d的矩陣，且矩陣中每個元素隨機賦值1 或-1，其中A+=AT(AAT)-1。當i＞N/2 時，表示適應度值較差的第i個跟隨者未取得食物，能量值較低，需要前往別的區(qū)域?qū)ふ沂澄?，以補充能量。

偵查預警行為：

種群覓食時，會選取部分麻雀負責警戒，當天敵靠近時，無論是發(fā)現(xiàn)者還是跟隨者，都將會放棄當前的食物而飛往到另一個位置。每代從種群中隨機選取SD（一般取10%～20%）只麻雀進行預警行為。其位置更新公式為：

其中，Xbest表示全局最佳的位置，β為步長調(diào)整系數(shù)，是一個均值為0、方差為1 的正態(tài)分布隨機數(shù)，k∈[-1,1]范圍內(nèi)的一個均勻隨機數(shù)。這里，fi是當前麻雀的適應度值。fg和fw依次為目前全局最優(yōu)和最差適應度值。ε為最小常數(shù)，防止分母出現(xiàn)0 的情況。當fi＞fg時，表示麻雀處于種群的邊緣地帶，非常容易被天敵所襲擊；fi=fg表明在種群中心的麻雀察覺到了被天敵襲擊的危險，需要向其他麻雀靠攏。k表示麻雀運動的方位，為步長調(diào)整系數(shù)。

2 融合柯西變異和反向?qū)W習的改進麻雀算法

2.1 Sin 混沌初始化種群

混沌經(jīng)常被運用于優(yōu)化搜索問題，其中Tent 模型和Logistic 模型是最常用的混沌模型，但是兩者皆為映射折疊次數(shù)有限的混沌模型。Sin 混沌模型是一種映射折疊次數(shù)無限的模型，楊海東等[12]研究證明，Sin 模型比Logistic模型具備更佳的混沌特性，因此本文采用Sin 混沌對麻雀算法進行種群初始化，Sin 混沌一維自映射表達式如下：

式（7）中為防止在[-1,1]產(chǎn)生不動點和零點，初始值不能設(shè)置為0。Sin 混沌一維自映射的隨機性、初值敏感性、遍歷性與迭代次數(shù)關(guān)系如圖1 所示[12]。從圖1（a）、圖1（b）發(fā)現(xiàn)設(shè)置不同的初始值，會產(chǎn)生完全不同的混沌序列，從圖1（c）看出當更新一定代數(shù)時，系統(tǒng)將遍覽整個解區(qū)域。

2.2 動態(tài)自適應權(quán)重

發(fā)現(xiàn)者從迭代開始就向全局最優(yōu)解靠近，導致搜索范圍不夠，容易跌入局部極值空間，造成搜索精度不足，本文在發(fā)現(xiàn)者位置更新公式中，引入上一代全局最優(yōu)解，使得發(fā)現(xiàn)者位置既受上一代發(fā)現(xiàn)者位置的影響，同時也受上一代全局最優(yōu)解的影響，由此可以有效防止算法陷入局部最優(yōu)。此外，借鑒慣性權(quán)重的思想，在發(fā)現(xiàn)者位置更新方式中繼續(xù)引入動態(tài)權(quán)重因子ω[13]，使其在迭代初期具有較大的值，能夠更好地進行全局探索，在迭代后期自適應地減小，從而更好地進行局部搜索，同時提高收斂速度。權(quán)重系數(shù)ω的計算公式和改進后的發(fā)現(xiàn)者位置更新方式如下：

Fig.1 Relationship between Sin chaos characteristics and number of iterations圖1 Sin 混沌特性與迭代次數(shù)關(guān)系圖

式（9）中，為上一代中第j維的全局最優(yōu)解。

2.3 改進的偵查預警麻雀更新公式

改進后的公式表示若該麻雀是最優(yōu)位置的麻雀，它會逃到最優(yōu)位置和最差位置間的隨機位置，否則，它會逃到自己和最優(yōu)位置之間的隨機位置。

2.4 融合柯西變異和反向?qū)W習策略

反向?qū)W習是Tizhoosh 于2005 年提出的一種新方法，其目的是以當前解為基礎(chǔ)，通過反向?qū)W習機制尋到對應的反向解，然后經(jīng)過評估比較保存更好的解。為讓個體能夠更好地尋到最優(yōu)解，將反向?qū)W習策略融入到麻雀算法中，數(shù)學表征如下：

其中，X′best(t)為第t代最優(yōu)解的反向解，ub、lb分別是上下界，r是服從（0,1）標準均勻分布的1×d（d為空間維數(shù)）的隨機數(shù)矩陣，b1表示信息交換控制參數(shù)[14]，公式如下：

柯西變異源自柯西分布，一維柯西分布概率密度如下：

當a=1 時，稱為標準柯西分布。圖2 為高斯分布與柯西分布的概率密度函數(shù)曲線。

從圖2 中可以清晰看出，柯西分布兩端形狀又長又扁，逼近于0 的過程比較平緩，速度相較于高斯分布更慢，并且在原點附近的峰值與高斯分布相比更小，因此柯西變異在擾動能力方面比高斯變異更強。將柯西變異引入目標位置更新方式中，發(fā)揮柯西算子的擾動能力，使算法的全局尋優(yōu)性能得到提升。

Fig.2 Probability density function curves of standard Cauchy distribution and Gaussian distribution圖2 標準柯西分布、高斯分布概率密度函數(shù)曲線

式（15）中，cauchy(0,1)為標準柯西分布。柯西分布隨機變量生成函數(shù)為η=tan[(ξ-0.5)π]。

為進一步提升算法尋優(yōu)性能，采取一種動態(tài)選擇策略更新目標位置，將反向?qū)W習策略和柯西變異算子擾動策略在一定概率下交替執(zhí)行，動態(tài)更新目標位置。反向?qū)W習策略中，通過反向?qū)W習機制得到反向解，擴大算法的搜索領(lǐng)域。柯西變異策略中，運用柯西變異算子在最優(yōu)解位置進行擾動變異操作得出新解，改善了算法跌入局部區(qū)域的缺陷。至于采取何種策略進行目標位置更新，由選擇概率Ps[14]決定，其計算公式如下：

式中，θ為調(diào)整參數(shù)，其值可取0.05。

具體選擇策略方式如下：

如果rand＜Ps，選擇式（11）～（13）反向?qū)W習策略進行位置更新，否則選取式（15）柯西變異擾動策略進行目標位置更新。

通過上述兩種擾動策略雖然能增強算法躍出局部空間的能力，但是無法確定擾動變異之后得到的新位置要優(yōu)于原位置的適應度值，因此在進行擾動變異更新后，引入貪婪規(guī)則，通過比較新舊兩個位置的適應度值，確定是否要更新位置。貪婪規(guī)則如式（17）所示，f(x)表示x的位置適應度值。

融合柯西變異和反向?qū)W習的改進麻雀算法步驟如下：

（1）初始化參數(shù)，如種群數(shù)量N、最大迭代次數(shù)、發(fā)現(xiàn)者比例PD、偵察者比例SD、警戒閾值R2等，并利用式（7）Sin 混沌映射初始化麻雀種群。

（2）計算各只麻雀的適應度值，找出當前最優(yōu)適應度值和最差適應度值，以及相對應的位置。

（3）從適應度值較優(yōu)的麻雀中，選取部分麻雀作為發(fā)現(xiàn)者，并按照式（9）更新位置。

（4）余下麻雀作為跟隨者，并按照式（5）更新位置。

（5）從麻雀中隨機選擇部分麻雀作為警戒者，并按照式（10）更新位置。

（6）根據(jù)概率Ps選擇柯西變異擾動策略和反向?qū)W習策略對當前最優(yōu)解進行擾動，產(chǎn)生新解。

（7）依據(jù)貪婪規(guī)則式（17），確定是否進行位置更新。

（8）判斷是否達到結(jié)束條件，若是，則進行下一步，否則跳轉(zhuǎn)步驟（2）。

（9）程序結(jié)束，輸出最優(yōu)結(jié)果。

3 算法性能測試

基于8 個基準測試函數(shù)，比較ISSA 與3 種基本算法SSA[1]、GWO[15]和MFO[16]，以及兩種改進的麻雀算法ASSA（adaptive sparrow search algorithm，引進第2 章中的自適應權(quán)重）和CASSA（Cauchy adaptive sparrow search algorithm，引進自適應權(quán)重和在跟隨者中引入柯西變異策略）的性能。測試函數(shù)中包括單峰、多峰函數(shù)，維度d分別為10/30/100。為公平驗證ISSA 算法有效性，測試在同一運行環(huán)境下進行，運用MATLAB2019a 版本完成仿真，操作系統(tǒng)Microsoft Windows 8.1，通用條件設(shè)置為相同，種群數(shù)量為30，迭代次數(shù)為500，各算法獨立運行50 次。

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

各個算法的參數(shù)設(shè)置如表1 所示，8 個基準測試函數(shù)的取值范圍、最優(yōu)解等信息如表2 所示。

3.2 算法性能結(jié)果對比分析

6 種算法優(yōu)化8 個基準測試函數(shù)的具體結(jié)果如表3 所示。

由表3 可知，對于單峰函數(shù)f1至f5中，除了f2和f3，3 種改進的麻雀算法在不同維度下的求解精度基本一致，但是ISSA 收斂速度更快，相比其余3 種算法均有較大的提升，并且平均值均能接近理論最優(yōu)解，標準差最小；在優(yōu)化多峰函數(shù)f6至f8中，3 種改進的麻雀算法不論是在10 維、30 維還是100 維，均能夠有效跳出局部最優(yōu)，取得理想效果，說明改進的策略是可行有效的，但ISSA 求解效率最高。另外，隨著維度逐漸增大，基本SSA 求解精度出現(xiàn)降低的現(xiàn)象，而ISSA 求解精度基本沒有發(fā)生變化，甚至在f2精度進一步提高，表現(xiàn)出了極強的穩(wěn)定性。結(jié)合單峰函數(shù)和多峰函數(shù)的優(yōu)化效果和收斂圖3 至圖10 可以發(fā)現(xiàn)，ISSA 在求解精度、收斂速度兩方面，均表現(xiàn)出了更為出色的性能。從多次尋優(yōu)的平均值和標準差這兩項指標可以看出，ISSA 的值更小，表明了ISSA 的穩(wěn)定性和魯棒性明顯優(yōu)于其余5 種算法。

Table 1 Parameter settings表1 參數(shù)設(shè)置

Table 2 Benchmark test functions表2 基準測試函數(shù)

3.3 算法收斂曲線對比分析

基準測試函數(shù)曲線能夠直觀地體現(xiàn)各個算法的收斂速度和收斂精度，同時也能清楚地顯示算法跳出局部空間的能力。8 個基準測試函數(shù)（維度d=30）的收斂曲線如圖3 至圖10 所示，其中橫軸代表更新代數(shù)，縱軸代表適應度值以e為底的對數(shù)ln。

從以上收斂曲線圖可知，在求解不同測試函數(shù)時，ISSA 算法的收斂速度更快，曲線更平滑。對數(shù)值越低，代表尋優(yōu)精度越高。先出現(xiàn)曲線拐點，代表求解速度更快。

Table 3 Comparison of optimal results of benchmark test functions表3 基準測試函數(shù)優(yōu)化結(jié)果比較

3.4 與最新的改進麻雀算法（CSSA）比較

Fig.3 f1 convergence curve圖3 f1 收斂曲線

Fig.5 f3 convergence curve圖5 f3 收斂曲線

Fig.7 f5 convergence curve圖7 f5 收斂曲線

由于麻雀搜索算法過于新穎，當前對其改進的只有呂鑫等[17]所提出的混沌麻雀搜索算法（chaos sparrow search algorithm，CSSA）。為進一步體現(xiàn)ISSA的有效性，選取幾個具有代表性的測試函數(shù)與混沌麻雀搜索算法在同一條件下（以文獻[17]中的通用條件為準）進行算法性能比較，實驗比較結(jié)果如表4 所示。

Fig.4 f2 convergence curve圖4 f2 收斂曲線

Fig.6 f4 convergence curve圖6 f4 收斂曲線

Fig.8 f6 convergence curve圖8 f6 收斂曲線

Fig.9 f7 convergence curve圖9 f7 收斂曲線

Table 4 Comparison of CSSA and ISSA algorithm performance表4 CSSA 與ISSA 算法性能比較

由表4 可知，對于函數(shù)f1、f2、f3、f5，ISSA 在平均值和標準差上比CSSA 至少提升了6 個數(shù)量級，雖然提升得不多，但是求解精度更高。對于優(yōu)化多峰函數(shù)f6至f8，ISSA 與CSSA 優(yōu)化效果相當?？傮w來說，從平均值和標準差兩個指標來看，ISSA 的值更小，表明ISSA 全局尋優(yōu)能力比CSSA 更強，穩(wěn)定性更高，是一種更為高效的算法。

3.5 Wilcoxon 秩和檢驗

僅憑50 次獨立運行的平均值和標準差不能夠完全說明ISSA 的優(yōu)越性，需要進行統(tǒng)計檢驗。為體現(xiàn)公平性，本文采用Wilcoxon 秩和檢驗驗證ISSA 每次運行結(jié)果在p=5%的顯著性水平下是否與其他算法存在顯著性差異。當p＜5%時，可以被認為拒絕H0假設(shè)，表明兩種算法之間存在顯著性差異；當p＞5%時，可以被認為接受H0 假設(shè)，表明兩種算法之間的差異性不明顯，即兩種算法尋優(yōu)性能相當。

Fig.10 f8 convergence curve圖10 f8 收斂曲線

表5 給出了ISSA 與GWO、MFO、SSA、ASSA、CASSA 在顯著性水平p=5%、維度d=30 下的結(jié)果，其中N/A 表示兩者之間性能相當，無法比較。由于算法本身無法比較，故用N/A 表示。

Table 5 Wilcoxon rank test p values表5 Wilcoxon 秩和檢驗p 值

從表5 可知，大部分的p值均小于0.05，表明ISSA 與其余5 種算法之間存在顯著差異性。對于函數(shù)f6至f8，ISSA 與SSA、ASSA、CASSA 之間的顯著差異性不明顯，優(yōu)化性能相當。

3.6 改進算法（ISSA）的時間復雜度分析

時間復雜度是評價算法求解速度的一個重要指標，本文對改進后的麻雀算法（ISSA）進行時間復雜度分析。

基本SSA 算法中，設(shè)置種群規(guī)模為N，空間維度為d，最大迭代次數(shù)為itermax，初始化種群參數(shù)的時間為η0，每一維產(chǎn)生隨機數(shù)時間為η1，求解目標適應度函數(shù)時間為f(d)，則初始階段時間復雜度為：

發(fā)現(xiàn)者數(shù)量為r1N，假設(shè)r1為發(fā)現(xiàn)者比例，每一維按式（4）進行位置更新的時間為η2，Q、α均為（0,1）的隨機數(shù)，其生成時間均為η3，則發(fā)現(xiàn)者位置更新階段時間復雜度為：

警戒者數(shù)量為r2N，假設(shè)r2為警戒者比例，每一維按式（6）進行位置更新的時間為η4，β、k均為正態(tài)分布隨機數(shù)，其生成時間均為η5，此階段時間復雜度為：

跟隨者數(shù)量為(1-r1-r2)N，假設(shè)每一維按式（5）進行位置更新的時間為η6，產(chǎn)生參數(shù)Q、α的時間分別為η3、η7，則跟隨者位置更新階段時間復雜度為：

綜上，基本SSA 的時間復雜度為：

改進算法（ISSA）初始階段時間復雜度T′1與基本SSA 相同，均為式（18）所示，假設(shè)式（8）產(chǎn)生的自適應權(quán)重ω的時間為t1，每一維按式（9）進行位置更新的時間為t2，則改進后發(fā)現(xiàn)者位置更新階段時間復雜度為：

假設(shè)每一維按照式（10）進行位置更新的時間為t3，產(chǎn)生β的時間與基本SSA 相同，均為η5，則改進后的預警階段時間復雜度為：

跟隨者階段時間復雜度T′4與基本SSA 相同，均為式（21）所示。融合柯西變異和反向?qū)W習策略過程中：假設(shè)計算參數(shù)b1、Ps的時間分別為t4、t5，依據(jù)貪婪規(guī)則比較位置優(yōu)劣和擇優(yōu)更新目標位置的時間分別為t6、t7，此階段時間復雜度為：

綜上，ISSA 的時間復雜度為：

綜上發(fā)現(xiàn)，ISSA 與SSA 相比較，時間復雜度相同，表示本文對SSA 提出的改進策略并沒有增加時間復雜度，降低求解效率。

4 結(jié)束語

針對基本麻雀算法的缺陷，本文提出一種融合柯西變異和反向?qū)W習的改進麻雀算法（ISSA），并對8個基準測試函數(shù)進行仿真實驗以及Wilcoxon 秩和檢驗，比較算法性能，得出以下結(jié)論：

（1）ISSA 尋優(yōu)性能提升明顯，可以有效地跳出局部最優(yōu)。麻雀位置初始化對全局搜索非常重要，通過Sin 混沌初始化麻雀種群，豐富解的多樣性；引入動態(tài)自適應權(quán)重因子，有效平衡了算法全局和局部的開掘能力；融合柯西變異和反向?qū)W習策略，降低算法跌入局部極值的概率，提高全局探索性能。

（2）8 個基準測試函數(shù)表明：ISSA 在收斂精度、求解速度、跳出局部最優(yōu)能力相較于GWO、MFO、SSA、CSSA、ASSA、CASSA 表現(xiàn)出了更為出色的尋優(yōu)性能，證實了算法改進的有效性。

（3）下一步可以考慮繼續(xù)改進麻雀算法尋優(yōu)機理和算法結(jié)構(gòu)，或者融合其他智能算法的優(yōu)點，提出性能更佳的智能算法，以及將ISSA 應用到復雜的優(yōu)化問題中，擴展本文算法的應用領(lǐng)域。