自適應變異麻雀搜索優化算法

唐延強，李成海，宋亞飛，陳晨，曹波

(1.空軍工程大學 研究生院，西安 710051；2.空軍工程大學 防空反導學院，西安 710051；3.西安衛星測控中心 ，西安 710043)

元啟發式算法又稱群智能優化算法，是一種模擬自然界中某些生物的行為或受到某種物理現象啟發提出的一類仿生學算法，其中心思想是在某個空間平衡全局搜索和局部搜索尋找最優解。由于元啟發式算法操作簡單、求解高效，吸引了眾多學者的關注，目前這些算法被廣泛應用于圖像處理[1]、訓練神經網絡[2]、信號處理[3]和特征選擇[4]等領域。

近年來相繼出現了越來越多的元啟發式算法，常見的算法有：粒子群優化(particle swarm optimization,PSO)算法[5]、灰狼優化(grey wolf optimization, GWO)算法[6]、鯨魚優化算法(whale optimization algorithm,WOA)[7]、樽海鞘群算法(salp swarm algorithm, SSA1)[8]、正弦余弦算法(sine cosine algorithm, SCA)[9]和麻雀搜索算法(sparrow search algorithm, SSA2)[10]等，由于樽海鞘群算法和麻雀搜索算法的英文縮略詞相同，本文以SSA1 表示樽海鞘群算法，SSA2 表示麻雀搜索算法。雖然元啟發式算法越來越多，但都離不開2 個階段：探索和開發。探索階段即算法以高度隨機性進行全局搜索，隨著迭代次數的增加，算法開始在已探索的區域進行深度開發。因此，保證探索和開發之間的平衡顯得尤為重要。若探索階段比重過大，將會導致收斂速度變慢，相反，將會導致過早收斂，易陷入局部極值點。

針對這些問題，眾多學者已經提出一些有效的改進方法：陳忠云等[11]提出一種多子群的共生非均勻高斯變異SSA1，較好的平衡了樽海鞘群的探索和開發能力；劉景森等[12]針對SSA1 求解結果不穩定問題，引入自適應領導者-跟隨者調整策略，增強了算法的穩定性；周嬌等[13]為避免WOA 早熟收斂的缺陷，采用貓映射混沌序列結合反向解方法取代隨機產生初始種群，使WOA 在初始種群多樣性及尋解遍歷性上有所增強；周璟[14]采用Tent 混沌映射改進了狼群初始化方法，使狼群初始分布更加均勻，加強了算法的全局搜索能力；文獻[15]在WOA的慣性權重中引入隨機因子，然后將Levy 飛行的隨機搜索模式引入算法中，進一步增強了WOA 的全局和局部搜索能力；文獻[16]對煙花算法進行基于對立的學習初始化種群，對非最優個體采用自適應t 分布變異，對最優個體采用精英對立學習，減少了算法的運行時間；何慶等[17]采用柯西變異提高算法跳出局部極值點的能力。

SSA2 是2020 年新提出的一種元啟發式算法，該算法將搜索群體分為探索者、跟隨者和預警者3 部分，其相互分工尋找最優值。雖然易于實現，但如何調節各部分之間的控制參數，以及如何保證3 部分之間可以較好的相互配合是一個必須考慮的問題。目前有一些對SSA2 的改進：呂鑫等[18]將麻雀種群通過Tent 混沌序列初始化，同時通過高斯變異和Tent 混沌擾動對個體進行變異和擾動，克服了SSA2 易陷入局部極值點的缺陷；文獻[19]利用重心反向學習機制初始化種群，使種群具有更好的空間解分布，其次在探索者的位置更新部分引入學習系數，提高算法的全局搜索能力，最后使用變異算子來改善加入者的位置更新；文獻[20]引入混沌策略來增強算法種群的多樣性，并采用自適應慣性權重來平衡算法的收斂速度和探索能力。這些改進措施在一定程度上提高了算法的尋優性能，但都沒有更加深入考慮探索者和跟隨者之間的關系。基于此，本文提出一種自適應變異麻雀搜索算法(adaptive mutation sparrow search optimization algorithm,AMSSA),首先通過貓映射混沌序列對種群初始化，提高麻雀個體的隨機性及遍歷性，再通過柯西變異和Tent 混沌擾動對個體進行調整，避免種群過于“集中”或“分散”，最后引入自適應探索者-跟隨者數量調整式來平衡尋找全局和局部最優的能力。通過對16 個基準函數進行測試，并進行Wilcoxon 秩和檢驗分析，驗證了本文所提算法的有效性和可行性。

1 麻雀搜索算法

SSA2 的思想來自于麻雀種群的覓食行為和反捕食行為，可抽象為探索者-跟隨者-預警者模型。探索者具有較高的能量儲備，適應度值高，主要為跟隨者提供覓食區域和方向。跟隨者跟隨適應度值最優的探索者尋找食物以獲得自己的能量儲備，增加自身的適應度值。部分跟隨者也可能不斷地監視探索者，從而爭奪食物。預警者在意識到危險時會發出警報，同時迅速向安全區域移動來獲得更好的位置，處于種群中間的麻雀則隨機行走靠近別的麻雀，即反捕食行為。同時若警報值大于安全閾值時，探索者需要將所有的跟隨者帶離危險區域。

在SSA2 中，假設有N 只麻雀在一個D 維搜索空間中，則每只麻雀的位置為

式中：i=1,2,···, N；d=1,2,···, D；xi,d為第i 只麻雀在第d維的位置。

由于探索者引導著整個麻雀群體的流動，可在任何地方尋找食物，所以其位置更新為

2 改進麻雀搜索算法

2.1 貓映射混沌初始化種群

混沌作為一種非線性的自然現象，以其混沌序列具有遍歷性、隨機性等優點，被廣泛用于優化搜索問題。為了保持種群的多樣性，使個體之間盡可能均勻分布，本文采用混沌序列初始化策略代替SSA2 算法中隨機生成種群的方法。目前在優化領域形成了多種混沌映射，包括Logistic 映射、Tent映射和貓映射等。Logistic 映射作為一種典型的混沌系統，其序列的概率密度函數由于服從切比雪夫分布，映射點呈現出中間密度低，兩邊密度高的特點，導致遍歷不均勻性，影響算法的搜索效率。文獻[21]提出Tent 映射的遍歷均勻性和收斂速度皆優于Logistic 映射，然而Tent 映射易在小循環周期和不動點上出現問題，只有最優解僅為邊緣值時才可求得最優解。針對Logistic 映射和Tent 映射的缺點，本文通過貓映射來生成SSA2 算法的初始種群。貓映射表達式為

2.2 Tent 混沌和柯西變異擾動策略

2.2.1 Tent 混沌擾動

2.2.2 柯西變異

柯西變異來源于連續型概率分布的柯西分布[23]，主要特點為0 處峰值較小，從峰值到0 下降緩慢，使變異范圍更均勻，變異式為

式中：x 為原來個體位置；mutation(x)為經過柯西變異后的個體位置；u 為(0,1)區間內的隨機數。

2.3 改進探索者位置更新公式

m 值的選取影響著麻雀探索者對于全局和局部搜索之間的平衡關系。從圖1 可以看出，每條曲線都是前期收斂速度快，后期收斂速度慢，為了選取最合適的m 值，選取Schaffer 函數對該參數進行測試，Schaffer 函數的特點是在全局最優點3.14 范圍左右存在大量的局部極小點，函數強烈振蕩。經過7 次改變m 值，每次進行50 次尋優計算取平均值，得出m 值對SSA2 算法的影響如表1所示。可以看出，由于SSA2 算法本身良好的尋優性能，可以避過Schaffer 函數的局部極小點，尋找到最佳值0，因此，m 值對SSA2 算法的影響主要體現在收斂次數上，當m 值增加時，平局收斂次數先減少后增加，m 值為2 時平均收斂迭代次數最小。由表1 可知，m=2 時，參數c 可以使SSA2 算法的探索能力和覓食能力達到較好的平衡，此時探索者可在前期充分廣泛搜索目標，后期著重對最優位置進行挖掘。

圖1 c 變化曲線Fig.1 Variation curves of c

表1 參數 m 對SSA2 的影響Table 1 Influence of parameter m on SSA2

2.4 探索者-跟隨者自適應調整策略

在SSA2 算法中，探索者和跟隨者的數目比例保持不變，這會導致在迭代前期，探索者的數目相對較少，無法對全局進行充分的搜索，在迭代后期，探索者的數目又相對較多，此時已不需要更多的探索者進行全局搜索，而需要增加跟隨者的數量進行精確的局部搜索。為解決這個問題，本文提出探索者-跟隨者自適應調整策略，該策略在迭代前期，探索者可以占種群數目的多數，隨著迭代次數的增加，探索者的數目自適應減少，跟隨者的數目自適應增加，逐步從全局搜索轉為局部精確搜索，從整體上提高算法的收斂精度。探索者和跟隨者數目調整式為

式中：pNum 為探索者數目；sNum 為跟隨者數目；b 為比例系數，用于控制探索者和跟隨者之間的數目；k 為擾動偏離因子，對非線性遞減值r 進行擾動。

2.5 改進后麻雀搜索算法

AMSSA 流程如圖2 所示。

圖2 AMSSA 流程Fig.2 Flow chart of AMSSA

3 本文所提算法性能測試

為驗證本文所提算法的尋優能力及可行性，將AMSSA 與PSO、GWO、WOA、SSA1、SSA2 算法同時在16 個基準函數上進行對比測試。

3.1 測試函數

具體基準函數如表2 所示。其中f1～f6為高維單峰函數，f7～f11為高維多峰函數，f12～f16為低維多峰函數。高維單峰函數只有一個全局最優點，沒有局部極值點，主要為了測試函數的收斂速度。多峰函數有多個局部極值點，從高維和低維2 種角度出發，用來觀察函數在不同維度跳出局部極值點的性能。

表2 基準函數Table 2 Benchmark function

3.2 結果分析

3.2.1 收斂精度及穩定性分析

在MATLAB R2016b 環境下對6 種算法進行仿真對比實驗，為了避免偶然誤差過大，在實驗中選取各基準函數獨立運行40 次，取最佳值、平均值和標準差作為評價指標，實驗中設定種群規模為30，最大迭代次數為500，最終得到表3。

表3 基準函數測試結果對比Table 3 Comparison of benchmark function test results

首先，在6 個高維單峰函數中，AMSSA 在求解f1、f2和f3函數時尋找到理論最優值0，f1和f3函數標準差也為0，除此之外只有SSA2 在求解f1時得到最優值0；其次，在求解f4和f5函數時，AMSSA 得出的最優值、平均值和標準差比其他5 種算法提升了至少2 個數量級；在求解f6函數時，雖然提升程度不高，但最優值和穩定性仍高于其他算法。在5 個高維多峰函數中，對于f7的求解，6 種算法的尋優能力基本相同，AMSSA 并未表現出算法的優越性；對于f8和f10的求解，在WOA、SSA2 中已經可以達到最優值，改進后AMSSA 中保持了原算法的性能；對于f9的求解，AMSSA 并未突出其優越性，同SSA2 一樣，在達到某個極值點后就跳不出該極值點，但標準差為0，穩定性強；高維多峰函數中只有對f11的求解突出體現了AMSSA 算法尋優性能的提高。對于5 個低維多峰函數，除f16外，f12～f15在6 種算法的求解下均可以達到最優值，說明在低維條件下算法可以更好的尋優；在f12中，SSA2、AMSSA相較于其他4 種算法穩定性不足，但AMSSA 比SSA2穩定性高；f13中AMSSA 的穩定性僅次于WOA；f14和f15中AMSSA 的穩定性最好；在f16中，只有GWO、SSA2 和AMSSA 這3 種算法尋找到最優解，穩定性依次增加。

通過分析說明，對于每一種算法，單峰函數的求解精度比多峰函數要高，低維函數比高維函數的求解精度要高，但不論單峰多峰、高維低維函數，AMSSA 相比于其他5 種算法，不僅在尋優準度上有相對應的提升，并且穩定性更優。

3.2.2 收斂曲線分析

為了直觀地比較6 種算法的收斂速度，再分別用6 種算法對16 個基準函數進行實驗，結果如圖3所示。

圖3 基準函數平均收斂曲線Fig.3 Average convergence curve of benchmark function

圖3 所示可以清晰地表達各算法在尋優過程中 適 應 度 值 的 變 化 情 況。圖3（a）～圖3（f）中AMSSA 的收斂速度較快，這是因為加入貓映射混沌初始化的結果，并且除圖3(b)外，AMSSA 的收斂精度遠遠高于其他算法。圖3(b)中AMSSA 的收斂精度僅次于WOA，這與表3 中的數值剛好對應。其次，圖3(a)～圖3(f)中可以清晰的看出有斷層現象和AMSSA 跳出局部極值點的特征，而PSO、GWO、WOA、SSA1 基本陷入局部極值點就再未能跳出。在圖3(g)～圖3(k)高維多峰函數的5 幅圖中，圖3(g)中AMSSA 陷入局部極值點后未跳出，這也與表格中f7函數相對應，圖3(h)、圖3(j)和圖3 (k)中表現出AMSSA尋優精度和收斂性能明顯優于其他算法。同時，圖3(h)和圖3(j)中AMSSA的曲線未顯示完全，這是因為已經達到最佳值0，算法性能優異。在圖3(l)～圖3(p)低維多峰的5 幅圖中，圖3(l)、圖3 (m)、圖3 (n)和圖3 (o)中每種算法皆能夠尋找到最優解，圖3(p)只有AMSSA、SSA2和GWO 尋找到最優解，并且AMSSA 收斂速度最快。圖3(o)中由于f15函數對每種算法來說都易尋找到最優點，所以迭代開始每種算法都立刻找到最優點，圖形只有一條豎直的線。

3.2.3 Wilcoxon 秩和檢驗分析

文獻[24]提出，對于改進算法性能的評估，應該進行統計檢驗。換而言之，僅基于平均值和標準偏差值來比較算法優劣還不夠，需要進行統計檢驗以證明所提算法比其他算法具有顯著的改進優勢。通過對每一次的結果進行獨立比較，來體現算法的穩定性和公平性。本文采用Wilcoxon 秩和檢驗在5%的顯著性水平下進行判斷AMSSA 的每次結果是否統計上顯著與其他5 種算法的最佳結果不同，當p 值小于5%時，拒絕假設，說明對比算法具有顯著性差異；否則接受假設，表明對比算法的尋優能力整體上相同。表4 給出了16 個基準函數下AMSSA 與其他5 種算法之間的秩和檢驗p 值，因為當2 個對比算法都達到最佳值時，無法進行比較，所以表4 中NaN 表示“不適用”，即不能進行顯著性判斷，R 為顯著性判斷的結果，“+”、“-”、“=”分別表示AMSSA 性能優于、劣于和相當于對比算法。

從表4 中可以得出，大部分p 值遠遠小于5%，這說明AMSSA 的優越性比其他5 種算法在統計上是顯著的。在AMSSA 與SSA2 對比，f13～f16函數中R 值為“-”，這是因為本身SSA2 尋優性能較好，AMSSA 與SSA2 皆能尋找到最佳值，只是在平均值的體現上有所不同，AMSSA 在低維多峰函數上的尋優性能有一定的提升，但提升空間不大。

表4 Wilcoxon 秩和檢驗p 值Table 4 p-value for Wilcoxon’s rank-sum test

3.2.4 模型消融實驗

由于AMSSA 的各種添加機制導致其尋優性能比較好，但具體哪一種添加機制起作用，是否有某一種添加機制不起作用還未知，為了表明各種機制的作用，使實驗更具說服力，本文進行了AMSSA 模型的消融實驗。分別以SSA、自適應SSA(ASSA)、變異SSA(MSSA)與AMSSA 在16 個基準函數上做對比實驗，最終結果如表5 所示，其中Mean 為平均值，Std 為標準值。

從表5 中可以看出，在高維單峰函數f1～f6中：除f6外，其他函數中的ASSA 與MSSA 皆對尋優性能起到了一定作用；在f6中，雖然ASSA 與MSSA相較于SSA 沒有提升效果，但二者結合后，AMSSA的穩定性最高。在高維多峰函數f7～f11中：函數f7的測試結果與f6類似，穩定性提升，但尋優性能提升效果不大；函數f8～ f10中所有算法都可以找到最優值；函數f11中，ASSA 和MSSA 的效果都比SSA2 好，同時AMSSA 的效果最好。在低維多峰函數f12～ f16中，由于每種算法可以無限接近最優值，因此AMSSA 性能提升不大，而且在f13中，ASSA、MSSA 和AMSSA 的性能不如SSA2。

表5 模型消融實驗結果Table 5 Experimental results of model ablation

3.2.5 AMSSA 時間復雜度分析

假設算法中種群規模為 N ,維度為 D,最大迭代次數為 itermax，隨機初始化種群參數時間為s1，求個體適應度值的時間為j(D)；探索者數量為pNum,每一維更新時間為s2；跟隨者數量為sNum,每一維更新時間為s3；預警者每一維更新時間為s4。因此初始階段時間復雜度為：T1=O(s1+N(j(D)+Ds1))；探索者更新時間復雜度為：T2=O(pNum×s2D)；跟隨者更新時間復雜度為：T3=O(sNum×s3D)；預警者更新時間復雜度為：T4=O((N-pNum-sNum)s4D)。綜上，SSA 總的時間復雜度為：T =T1+(T2+T3+T4)itermax=O(D+j(D))。

在AMSSA 中，假設貓映射混沌所需時間為u1，排序選擇時間為u2,因此，初始階段時間復雜度為：T11=O(s1+N(u1+j(D)+Ds1)+u2)；探索者和跟隨者個數更新式為u3，則探索者更新時間復雜度為：T22=O(pNum×s2D+itermaxu3)；跟隨者更新時間復雜度為：T33=O(sNum×s3D+itermaxu3)；預警者更新時間復雜度為：T44=O((N-pNum-sNum)s4D)。在柯西變異和Tent 混沌擾動過程中：設求解平均適應度值favg時間為u4，計算擾動式時間和柯西變異式時間分別為u5、u6。麻雀適應度值與平均適應度值比較和擇優更新目標位置的時間分別為u7、u8，則這個階段的時間復雜度為：T55=O(u4+u5+u6+N(j(D)+u7)+u8)。綜上，AMSSA 的時間復雜度為：T1=T11+(T22+T33+T44+T55)itermax=O(D+j(D))。由于T1=T，表明AMSSA 的時間復雜度沒有增加。

綜和本節分析，通過模型消融實驗證明所提的每一種策略都對AMSSA 算法最終的性能有所幫助，通過時間復雜度分析說明AMSSA 的時間復雜度與SSA2 等價，通過AMSSA 在3 類函數上的實驗得出，雖然AMSSA 相較于SSA2 在低維多峰函數中的尋優性能不明顯，但在高維單峰和高維多峰函數中尋優性能比其他5 種算法高出至少2 個數量級，收斂速度也有明顯的提升，穩定性增強，充分說明AMSSA 算法的各種性能總體上優于其他5 種算法，表明了AMSSA 的優越性和可行性。

4 結 論

本文在標準麻雀搜索算法的基礎上，引入了混沌映射和柯西變異及探索者跟隨者數量的自適應調整策略，提出一種自適應變異麻雀搜索優化算法AMSSA。

1）首先，貓映射混沌加快了種群初始化的收斂速度；其次，自適應探索者-跟隨者調整策略使算法前期著重尋找全局最優，后期著重局部尋優整體上提高了收斂精度；最后，Tent 混動擾動和柯西變異使算法跳出局部極值點，這使得AMSSA 相較于SSA2 尋優精度更高，搜索能力更強。

2）選取16 個基準測試函數與其他5 種算法進行比較，并進行Wilcoxon 秩和檢驗對算法顯著性水平進行驗證。實驗表明，AMSSA 尋優性能提升較明顯，具有良好的開拓能力，魯棒性強，表現出良好的實時能力。

下一步考慮將AMSSA 與其他改進的SSA 做對比，并將其應用到圖像分割、人臉識別等實際工程中，用于解決工程優化領域中的約束優化、多目標優化等問題，從而驗證AMSSA 在實際工程中的優越性。