混沌麻雀搜索優化算法

呂鑫 慕曉冬 張鈞 王震

(1. 火箭軍工程大學 作戰保障學院, 西安 710025; 2. 北京遙感設備研究所, 北京 100854;3. 火箭軍工程大學 導彈工程學院, 西安 710025)

群體智能優化算法的中心思想是通過模擬自然界中一些事物或生物的運動及行為規律,搜索分布在一定范圍內解空間的最優解[1]。 人們通過螞蟻、蜜蜂、狼、鯨魚和鳥類等各種生物的群集行為,提出了許多群體智能優化算法,包括蟻群優化(Ant Colony Optimization, ACO)算法、粒子群優化(Particle Swarm Optimization, PSO)算法、人工蜂群優化(Artifical Bee Colony, ABC)算法、灰狼優化(Grey Wolf Optimization, GWO)算法、鯨魚優化算法(Whale Optimization Algorithm, WOA)、麻雀搜索算法(Sparrow Search Algortihm, SSA)等。 其中,Xue 和Shen[2]于2020 年提出的SSA是一種新型群體智能優化算法。 由于群體智能優化算法具有實現簡單、易于擴充和自組織性等優點,受到越來越多研究者的關注。

SSA 相較于其他群體智能優化算法具有搜索精度高、收斂速度快、穩定性好、魯棒性強等特點。然而,SSA 同其他群體智能優化算法一樣,當其搜索接近全局最優時,依舊會出現種群多樣性減少,易于陷入局部最優等問題。

為改善群體智能優化算法在接近全局最優時,種群多樣性減少,易于陷入局部最優等缺陷,很多學者提出了改進。 劉明霞等[3]將混沌算子引入ACO 算法,提出了一種基于聚度的自適應動態混沌蟻群算法,在增加種群多樣性的基礎上避免算法陷入局部最優。 楊萬里等[4]發現混沌理論可以使PSO 算法的慣性權重具有混沌搜索能力,從而提出一種基于Logistic 映射的新型混沌簡化PSO 算法,降低了算法陷入局部最優的能力。董麗鳳等[5]針對PSO 算法的早熟問題,通過設定種群多樣性閾值,以混沌映射為基礎更新當前最優個體位置,并以新方式進行優化操作,在算法的收斂速度和尋優精度上均得到提高。 韓敏和何泳[6]將一種帶有高斯函數和混沌特性的變異算子引入PSO 算法,協助種群跳出局部最優,增強全局搜索能力。 文獻[7-8]分別將混沌Logistic 映射和Tent 映射用于GWO 算法種群初始化,避免了隨機種群的缺點,提高了算法的收斂性。 郝曉弘等[9]提出了一種混合策略改進的WOA 算法,利用Tent 映射初始化種群,為全局搜索奠定基礎。 匡芳君等[10]為改善ABC 算法的收斂性能,提出了一種自適應Tent 混沌搜索的人工蜂群算法,避免算法陷入局部最優。

上述文獻對群體智能優化算法的改進在一定程度上避免算法陷入局部最優,提高了搜索能力,但仍存在算法搜索精度不足,開拓能力弱等缺陷。考慮到高斯分布較好的局部搜索能力,以及Tent混沌序列遍歷均勻、收斂快等特點,提出一種混沌麻雀搜索優化算法(Chaos Sparrow Search Optimization Algorithm, CSSOA)。 該算法首先利用Tent混沌映射初始化種群,使得初始個體盡可能分布均勻,同時引入高斯變異和混沌擾動,當種群出現“聚集”或者“發散”時對個體進行調整,幫助個體跳出局部最優。 本文對12 個基準函數進行仿真實驗,并將其應用到簡單圖像分割問題,驗證了本文算法的可行性和有效性。

1 麻雀搜索算法

SSA 是受麻雀覓食行為和反捕食行為啟發而提出的一種新型群體智能優化算法,其仿生學原理如下:

麻雀覓食過程可抽象為發現者-加入者模型,并加入偵察預警機制。 發現者本身適應度高,搜索范圍廣,引導種群搜索和覓食。 加入者為獲得更好的適應度,跟隨發現者進行覓食。 同時,加入者為提高自身捕食率,部分加入者會監視發現者以便于進行食物爭奪或在其周圍進行覓食。 而當整個種群面臨捕食者的威脅或者意識到危險時,會立即進行反捕食行為。

在SSA 中,模擬麻雀覓食過程獲得優化問題的解。 假設在一個D維搜索空間中,存在N只麻雀,則第i只麻雀在D維搜索空間中的位置為Xi=[xil,…,xid,…,xiD],i= 1,2,…,N,xid表 示第i只麻雀在第d維的位置。

發現者一般占到種群的10% ～20%,位置更新公式為

式中:t為當前迭代次數;T為最大的迭代次數;α為(0,1]之間的均勻隨機數;Q為服從標準正態分布的隨機數;L為大小為1 ×d,元素均為1 的矩陣;R2∈[0,1]和ST∈[0.5,1]分別為預警值和安全值。 當R2

除了發現者,剩余的麻雀均作為加入者,并根據式(2)進行位置更新:

式中:β為步長控制參數,是服從均值為0,方差為1 的正態分布隨機數;K為[ -1,1]之間的一個隨機數,表示麻雀移動的方向,同時也是步長控制參數;e為一個極小常數,以避免分母為0 的情況出現;fi為第i只麻雀的適應度值;fg和fw分別為當前麻雀種群的最優和最差適應度值。 當fi≠fg時,表明該麻雀正處于種群的邊緣,極易受到捕食者攻擊;當fi=fg時,表明該麻雀正處于種群中間,由于意識到捕食者的威脅,為避免被捕食者攻擊,及時靠近其他麻雀來調整搜索策略。

2 Tent 混沌及高斯變異

2.1 Tent 混沌

2.1.1 Tent 混沌序列

混沌作為自然界普遍存在的一種非線性現象,因混沌變量具有隨機性、遍歷性和規律性的特點[11],被很多學者應用于優化搜索問題,不僅能有效保持種群的多樣性,而且有利于算法跳出局部最優,改善全局搜索能力。 常見的Logistic 映射是一種典型的混沌系統,由圖1 可以看出,其在[0,0.05]和[0. 9,1]2 個范圍的取值概率較高,因此算法尋優速度受Logistic 遍歷不均勻性的影響,尋優效率會降低。 單梁等[12]研究表明,Tent映射的遍歷均勻性和收斂速度均優于Logistic 映射,并通過嚴格的數學推理,證明了Tent 映射可以作為產生優化算法的混沌序列。 Tent 映射表達式為

圖1 Logistic 混沌序列分布Fig.1 Logistic chaotic sequence distribution

式中:NT為混沌序列內的粒子個數;rand(0,1)為[0,1]之間的隨機數。

根據Tent 映射的特性,在可行域中產生混沌序列的步驟如下:

步驟1 隨機產生(0,1)內的初值z0,記i=0。

步驟2 利用式(8)進行迭代,產生Z序列,i自增1。

步驟3 如果迭代達到最大次數,程序運行停止,保存產生的Z序列。

2.1.2 Tent 混沌擾動

本文算法引入混沌擾動,避免其陷入局部最優,提高了全局搜索能力和尋優精度。 混沌擾動的步驟描述如下[14]:

步驟1 應用式(8)產生混沌變量Zd。

步驟2 將混沌變量載波到待求解問題的解空間:

式中:dmin和dmax分別為第d維變量Xdnew的最小和最大值。

步驟3 按式(10)對個體進行混沌擾動:

式中:X′為需要進行混沌擾動的個體;Xnew為產生的混沌擾動量;X′new為混沌擾動后的個體。

2.2 高斯變異

高斯變異來源于高斯分布,具體指在進行變異操作時,用符合均值為μ,方差為σ2的正態分布的一個隨機數來替代原來的參數值[15]。 變異公式為

式中:x為原來的參數值;N(0,1)表示期望為0,標準差為1 的正態分布隨機數;mutation(x)為高斯變異后的數值。

由正態分布特性可知,高斯變異的重點搜索區域為原個體附近的某個局部區域。 高斯分布局部搜索能力強,對具有大量局部極小值的優化問題,有利于算法高效、高精度地找到全局極小值點,同時還提高了本文算法的魯棒性[16]。

3 改進麻雀搜索算法

CSSOA 算法引入Tent 混沌搜索和高斯變異,增加了種群多樣性,提高了算法的搜索性能和開拓性能,避免陷入局部最優,其具體實現步驟如下:

步驟1 初始化,包括種群規模N,發現者個數pNum,偵察預警的麻雀個數sNum,目標函數的維數D,初始值的上下界lb、ub,最大迭代次數T或者求解精度ε。

步驟2 應用2.1.1 節中的Tent 混沌序列初始化種群,生成N個D維向量Zi,并將其各分量通過式(9)載波到原問題空間變量的取值范圍內。

步驟3 計算每只麻雀的適應度fi,選出當前最優適應度fg和其所對應的位置xb,以及當前最劣適應度fw和其對應的位置xw。

步驟4 選取適應度優的前pNum個麻雀作為發現者,剩余的作為加入者,并根據式(1) 和式(3)更新發現者和加入者的位置。

步驟5 從麻雀種群中隨機選取sNum只麻雀進行偵察預警,并根據式(4)更新其位置。

步驟6 一次迭代完成后,重新計算每只麻雀的適應度值fi和麻雀種群的平均適應度值favg。

1) 當fi

2) 當fi≥favg時,表明出現“發散”趨勢,按2.1.2節對個體i進行Tent 混沌擾動,如果擾動后的個體性能更優,則用擾動后的個體替代擾動前的個體,否則保持原個體不變。

步驟7 根據麻雀種群當前的狀態,更新整個種群所經歷的最優位置xb 和其適應度fg,以及最差位置xw 和其適應度fw。

步驟8 判斷算法運行是否達到最大迭代次數或者求解精度,若是,循環結束,輸出尋優結果;否則返回步驟4。

4 仿真實驗與結果分析

4.1 實驗設計與基準函數

為驗證CSSOA 的可行性和優越性,對12 個不同類型的基準函數進行仿真實驗。 如表1 所示,5 個高維單峰函數F1～F5,4 個高維多峰函數F6～F9,3 個低維多峰函數F10～F12。 通過多種類別基準函數可充分考察CSSOA 的尋優能力。

表1 基準函數Table 1 Benchmark functions

4.2 算法性能對比分析

在Intel(R)Core(TM)i5-4300M CPU@2.50 GHz,內 存 4. 00 GB, Windows10 系 統 和 MATLAB R2015a 下對本文算法進行仿真實驗,并與PSO、GWO、WOA 和SSA 算法進行對比。

實驗中取種群規模N=30,最大迭代次數T=100,目標函數的維數D和初始值的上下界ub 和lb 按照表1 中各基準函數具體選定,發現者個數pNum和偵察預警的麻雀個數sNum均取種群規模的20%。 為避免尋優結果的偶然性,以及證明CSSOA 的穩定性,選取各基準函數獨立運行30 次的實驗結果作為實驗數據。 針對12 個基準函數,將各個算法的平均值和標準差作為最終評價指標,如表2 所示,表中數據加粗表示各函數各指標最優值。

表2 基準函數優化結果比較Table 2 Optimization result comparison of benchmark functions

表2 的實驗結果表明,對于高維單峰函數F1～F4,CSSOA 無論是在尋優穩定性還是尋優精度上都比其他4 種算法有極大的提升,且CSSOA多次尋優的平均值和標準差相較于其他4 種算法均提升了23 個數量級以上;而對于函數F5,雖然CSSOA 的尋優性能提升不明顯,但尋優結果和穩定性仍優于其他4 種算法。 對于高維多峰函數F7和函數F9,CSSOA 均能有效跳出局部最優,穩定找到全局最優解,魯棒性強;對于函數F6,CSSOA 尋優性能提升不明顯;對于函數F8,CSSOA尋優性能提升不大,但其多次尋優的標準差為0,因此具有較強的穩定性。 對于低維函數F10～F12,雖然CSSOA 多次尋優的平均值和標準差相較于其他4 種算法提升不高,但是CSSOA 的尋優精度較高,且由CSSOA 多次尋優的標準差可以看出,CSSOA 尋優的穩定性均明顯優于其他4 種算法。

實時性作為評價算法的重要指標,表3 給出了各算法在30 次獨立運行下的平均迭代次數和平均運行時間。 分別將表2 中函數F1～F12的標準差量級作為算法求解精度ε(F6取0.001),當算法尋優過程中前后2 次結果差值的量級小于ε時終止迭代。 以函數F1為例,從表3 可以看出,CSSOA 的平均迭代次數較PSO、GWO 和WOA 均減少了94.00%,較SSA 減少了93.68%,平均運行時間較PSO、GWO、WOA 和SSA 分別提高了36.51%、65. 81%、89. 04%、82. 74%,故CSSOA尋優過程的實時性表現良好。

表3 基準函數的優化結果比較Table 3 Optimization result comparison of benchmark functions

為了反映CSSOA 的動態收斂特性,圖2 給出了12 個基準函數在5 種優化算法下的收斂曲線。對于函數F1、F2、F3、F4、F7、F9,CSSOA 在收斂速度和尋優精度上都明顯優于其他4 種算法,且迭代前期的搜索性能和迭代末期的開拓性能也都優于其他4 種算法,表明CSSOA 在保證開拓能力的同時也能充分保證搜索能力,不失種群多樣性和尋優穩定性。 對于函數F5、F10、F12,CSSOA 的收斂速度也均優于其他4 種算法,雖然在末期有陷入局部最優的趨勢,但是由于引入了高斯變異和Tent 混沌擾動,種群能夠有效地跳出局部最優,得到較好的尋優精度。 對于函數F6,多次尋優的標準差高于PSO 和SSA,穩定性略差,但從平均值可以看出,SSA 可有效收斂到全局最優解,而其他4 種算法則容易陷入局部最優。 對于函數F8,CSSOA 和SSA 收斂結果相近,但可以看出CSSOA收斂速度明顯比SSA 快。 對于函數F11,5 種算法最終都趨于平穩,但CSSOA 在尋優精度上仍優于其他4 種算法。

圖2 5 種算法在基準函數上的收斂曲線比較Fig.2 Comparison of convergence curves of 5 algorithms obtained on benchmark functions

綜上所述,CSSOA 對12 個基準測試函數的尋優性能提升明顯,且穩定性好、魯棒性強,特別是函數F1～F4,CSSOA 的尋優性能相較其他4 種算法高出20 個數量級,優勢明顯;同時,CSSOA的收斂速度明顯優于其他4 種算法,且實時性表現良好,能夠有效避免陷入局部最優,尋優精度高、搜索能力強,由此證明了CSSOA 的可行性和優越性。

5 CSSOA 在工程問題中的應用

本節采用實際工程中常見的圖像分割問題對CSSOA 應用于實際工程問題的可行性進行檢驗。

大津法(Otsu)作為一種圖像二值化處理的高效算法,指的是將原圖像分為前景圖像和背景圖像,并將類間方差作為衡量分割閾值的標準,使得類間方差最大的分割閾值即為最佳閾值。 本節采取類間方差作為CSSOA 的適應度函數,數學表達式為

fitness=w0w1(μ0-μ1)2(12)

式中:w0為前景像素占整幅圖像的比例;μ0為其平均灰度;w1為背景像素占整幅圖像的比例;μ1為其平均灰度。

CSSOA 進行圖像閾值分割,即找到一個最優解(麻雀位置),使得適應度函數取得最大值,并利用該解對圖像進行二值分割。 初始化種群規模N=20,最大迭代次數T=100,目標函數的維數D=1,初始值的上界ub =255,下界lb =0,對2 幅標準測試圖像和SSDD 數據集[17]中的2 幅艦船SAR 圖像分別進行30 次閾值分割,得到分割閾值的最大值、最小值、平均值和標準差,如表4 所示。

通過枚舉法求得4 幅圖像的最佳一維Otsu閾值依次是117、89、123 和124,然后將CSSOA 與Otsu 的分割結果進行比較,如圖3、圖4 所示。

表4 數據表明,CSSOA 圖像分割閾值穩定分布在最佳一維Otsu 閾值周圍,收斂效果明顯。 由圖3和圖4 可以直觀看出,CSSOA 可以得到和Otsu相似的分割結果。 由此驗證了CSSOA 應用到實際工程問題的可行性,為下一步研究奠定了基礎。

表4 圖像分割閾值Table 4 Image segmentation threshold

圖3 標準測試圖像分割結果Fig.3 Segmentation results of standard test image

圖4 艦船SAR 圖像分割結果Fig.4 Segmentation results of ship SAR image

6 結 論

1) CSSOA 尋優性能提升明顯。 例如CSSOA在12 個基準測試函數的尋優結果均優于其他4種優化算法,且對部分函數的性能提升達到20 個數量級以上。

2) CSSOA 尋優精度高,具有優良的開拓能力。 引入高斯變異和Tent 混沌擾動,豐富了種群多樣性,避免CSSOA 陷入局部最優,增強了算法的全局搜索能力。

3) CSSOA 具有良好的穩定性,魯棒性強。CSSOA在12 個基準測試函數上多次尋優的標準差普遍低于其他4 種算法的標準差,且在1 個數量級以上,尋優結果穩定。

4) CSSOA 收斂速度快、搜索能力強,且表現出良好的實時性。 從CSSOA 的收斂曲線直觀看出其收斂速度明顯優于其他4 種算法,同時平均迭代次數和平均運行時間也反映了CSSOA 較其他傳統算法更優異的實時性表現。

CSSOA 的研究還在初始階段,后續考慮將其應用到實際工程問題中,如圖像分割、旅行商問題、人臉識別等,并結合具體問題進一步優化算法性能,檢驗CSSOA 在實際工程問題中的有效性。