融合柯西變異和反向學習的改進麻雀算法

毛清華，張 強

燕山大學 經濟管理學院，河北 秦皇島066004

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

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

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

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

1 基本麻雀搜索算法

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

式中，N是麻雀的規模，i=1,2,…,N，d是變量的維數。

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

其中，N表示麻雀的數量，而Fx中的每個值表示個體的適應度值。適應度值更優的麻雀率先取得食物，并作為發現者帶領整個種群向食物源靠近。發現者的位置更新方式如下：

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

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

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

偵查預警行為：

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

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

2 融合柯西變異和反向學習的改進麻雀算法

2.1 Sin 混沌初始化種群

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

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

2.2 動態自適應權重

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

Fig.1 Relationship between Sin chaos characteristics and number of iterations圖1 Sin 混沌特性與迭代次數關系圖

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

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

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

2.4 融合柯西變異和反向學習策略

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

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

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

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

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

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

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

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

式中，θ為調整參數，其值可取0.05。

具體選擇策略方式如下：

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

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

融合柯西變異和反向學習的改進麻雀算法步驟如下：

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

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

（3）從適應度值較優的麻雀中，選取部分麻雀作為發現者，并按照式（9）更新位置。

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

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

（6）根據概率Ps選擇柯西變異擾動策略和反向學習策略對當前最優解進行擾動，產生新解。

（7）依據貪婪規則式（17），確定是否進行位置更新。

（8）判斷是否達到結束條件，若是，則進行下一步，否則跳轉步驟（2）。

（9）程序結束，輸出最優結果。

3 算法性能測試

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

3.1 參數設置

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

3.2 算法性能結果對比分析

6 種算法優化8 個基準測試函數的具體結果如表3 所示。

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

Table 1 Parameter settings表1 參數設置

Table 2 Benchmark test functions表2 基準測試函數

3.3 算法收斂曲線對比分析

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

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

Table 3 Comparison of optimal results of benchmark test functions表3 基準測試函數優化結果比較

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）。為進一步體現ISSA的有效性，選取幾個具有代表性的測試函數與混沌麻雀搜索算法在同一條件下（以文獻[17]中的通用條件為準）進行算法性能比較，實驗比較結果如表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 可知，對于函數f1、f2、f3、f5，ISSA 在平均值和標準差上比CSSA 至少提升了6 個數量級，雖然提升得不多，但是求解精度更高。對于優化多峰函數f6至f8，ISSA 與CSSA 優化效果相當。總體來說，從平均值和標準差兩個指標來看，ISSA 的值更小，表明ISSA 全局尋優能力比CSSA 更強，穩定性更高，是一種更為高效的算法。

3.5 Wilcoxon 秩和檢驗

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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

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

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

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