多策略改進的麻雀搜索算法及應(yīng)用

薛 濤,張安杰

(西安工程大學(xué) 計算機科學(xué)學(xué)院,陜西 西安 710048)

0 引 言

隨著算法的不斷發(fā)展,學(xué)者們通過現(xiàn)實生活中的生物行為提出了一系列群體智能優(yōu)化算法[1],如螢火蟲算法(firefly algorithm,FA)[2]、灰狼優(yōu)化(grey wolf optimizer,GWO)[3]算法、布谷鳥搜索(cuckoo search,CS)[4]算法、鯨魚優(yōu)化算法(whale optimization algorithm ,WOA)[5]等。麻雀搜索算法(sparrow search algorithm,SSA)[6]是近年來發(fā)展起來的一種新型元啟發(fā)式算法,具有較高的局部搜索能力和收斂性能。在電力負(fù)荷預(yù)測[7-8]、無人機航跡規(guī)劃[9-10]、圖像處理[11-13]、神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化[14-16]等方面的應(yīng)用研究取得了較大進展,具有一定的研究意義。

與其他智能算法相比,SSA的優(yōu)化效果更好,但在搜索過程中仍然存在全局搜索能力弱和容易陷入局部最優(yōu)的問題。針對此問題,國內(nèi)外學(xué)者做了相關(guān)的研究。文獻[17]提出了一種自適應(yīng)混沌麻雀搜索優(yōu)化算法,采用改進的Tent混沌映射對種群進行初始化,以增加種群的多樣性,進而提高算法的全局搜索能力。文獻[18]在此Tent混沌映射的基礎(chǔ)上引入了高斯變異方法,以避免麻雀搜索算法陷入局部最優(yōu)解。文獻[19]除了利用混沌對立學(xué)習(xí)策略初始化麻雀種群,還改進發(fā)現(xiàn)者位置更新公式,采用非線性權(quán)重因子和柯西算子來平衡該算法的全局探索和局部開發(fā)能力,最后,根據(jù)基于差分進化的GWO算法的思想,對種群個體進行分階段干擾,進一步提高種群多樣性,降低算法陷入局部極值的可能性。文獻[20]提出一種融合柯西變異和反向?qū)W習(xí)的改進SSA,通過在最優(yōu)解位置擾動變異,產(chǎn)生新解,提升算法避免陷入局部最優(yōu)的能力。上述文獻中雖然對于SSA的全局搜索能力和跳出局部最優(yōu)的能力進行了改進和優(yōu)化,但是同時也增加了種群的多樣性,在收斂速度和精確度上并沒有得到較大的改善,需要進一步研究。

為了改善SSA收斂速度慢和精確度不高的問題,本文基于原始SSA,提出了多策略改進的麻雀搜索算法(improved sparrow search algorithm based on multiple strategies,ISSAMS)。首先,采用改進的Circle混沌映射初始化種群,相對于Logistic映射和Tent映射種群分布更均勻、更穩(wěn)定,避免陷入不動點;隨后,在更新跟隨者位置時使用正弦余弦搜索策略,可以避免陷入全局最優(yōu);最后,通過螢火蟲擾動來提升算法的局部搜索能力,加快算法整體的收斂速度。本文選取8個基準(zhǔn)函數(shù)對于改進后的SSA進行驗證,其算法表現(xiàn)出的收斂速度和精確度上明顯優(yōu)于其他算法。通過將改進后的SSA應(yīng)用到優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值中,與其他幾種模型進行比較,來驗證改進的有效性和可行性。

1 SSA理論

SSA主要模擬麻雀的覓食行為和反捕食行為,可以按照其行為將麻雀分為幾種不同的角色。種群中適應(yīng)度值高的個體稱為發(fā)現(xiàn)者,其捕食能力強,自身能量高。剩余個體稱為跟隨者,同時從種群中選取一定比例的麻雀個體作為偵察者,來對種群進行偵察預(yù)警,如果發(fā)現(xiàn)危險則放棄食物向安全位置移動。

在種群中,發(fā)現(xiàn)者大多聚集在種群的中心,捕食能力強。同時,種群中大多數(shù)麻雀為了獲取更多的食物會向能量高的麻雀中心靠攏,即稱為跟隨者。在種群邊緣的個體容易受到其余捕食者的攻擊,因此選取一定的麻雀作為偵察者,一旦發(fā)現(xiàn)捕食者時,便會發(fā)出鳴叫警示種群,并不斷向種群中心靠攏,通過更新位置來確保安全。該具體算法流程步驟如下所示。

1) 初始化種群的位置。種群的初始位置可以用一個矩陣表示,總共有n只麻雀,矩陣的每一行是在d維空間內(nèi)每只麻雀初始的位置:

(1)

在d維空間內(nèi),其所有麻雀的初始適應(yīng)度值為

(2)

2) 更新發(fā)現(xiàn)者位置。在種群中適應(yīng)度值高的麻雀作為發(fā)現(xiàn)者,且發(fā)現(xiàn)者通過不斷地移動來尋找更多的食物,而其他跟隨者也隨之移動位置。如果有麻雀發(fā)現(xiàn)了捕食者,就會向種群發(fā)出鳴叫表示預(yù)警,如果預(yù)警信號值大于閾值時,發(fā)現(xiàn)者就會向安全的位置移動,跟隨者也隨之移動,整個種群會更新到新的位置,其中,發(fā)現(xiàn)者更新公式可表示為

(3)

3) 更新跟隨者位置。在種群中選取70%～80%作為發(fā)現(xiàn)者,其余均為跟隨者,跟隨者隨著發(fā)現(xiàn)者向食物更多的地方移動,所獲取的食物量越來越多,也可能會變?yōu)榘l(fā)現(xiàn)者。跟隨者位置更新公式可表示為

(4)

4) 更新偵察者位置。種群中隨機選取10%～20%的麻雀作為偵察者,其他麻雀在覓食時,它們負(fù)責(zé)警戒,如有危險靠近會立即放棄當(dāng)前食物移動到下一個位置。偵察者位置更新公式可表示為

(5)

2 SSA的改進

針對SSA隨著種群迭代次數(shù)的增加容易陷入局部最優(yōu)解問題,并且收斂速度慢等問題。本文提出了ISSAMS,使用Circle混沌映射初始化種群,提升種群的多樣性和穩(wěn)定性;同時修改種群中發(fā)現(xiàn)者的位置更新公式,改變原始算法中繁瑣的計算,去除向原點收斂的操作,提升全局搜索能力;采用正弦余弦搜索策略更新跟隨者位置和利用螢火蟲擾動進行尋優(yōu),提升算法跳出局部最優(yōu)的能力,避免陷入局部最優(yōu)。

2.1 Circle混沌映射

目前初始化種群常用的是Tent混沌映射[21]、Logistic混沌映射[22],本文選用Circle混沌映射來初始化種群。傳統(tǒng)的Logistic混沌映射分布不均勻?qū)λ惴ǖ氖諗克俣群途扔杏绊?。雖然Tent映射的分布更加均勻,但存在不穩(wěn)定周期,容易陷入不動點。Circle映射比較穩(wěn)定且分布的均勻性和Tent相當(dāng)。其具體公式如下:

(6)

式中:Xi+1代表第i+1個位置,已知Xi位置,通過對其運算求余得到第i+1位置,其中mod為取余函數(shù),以此類推,生成每個位置成功初始化種群。其Circle混沌映射如圖1所示。

圖1 Circle混沌映射分布

從圖1可以看出,原始的Circle混沌映射,混沌值集中在0.2～0.4之間,仍存在種群分布不均勻問題,針對于此,改進Circle混沌映射公式,改進后的具體公式為

(7)

改進后的Circle混沌映射如圖2所示。

圖2 改進后的Circle混沌映射分布

從圖2可以看出,改進后的Circle混沌映射分布共更均勻,在初始化種群時,增強種群的多樣性,提升算法的尋優(yōu)能力。

改進更新發(fā)現(xiàn)者的位置公式:

(8)

去除向原點靠近的操作,當(dāng)R2

2.2 正弦余弦搜索策略

在原始SSA中,當(dāng)更新跟隨者位置時使用正弦余弦搜索策略,利用正弦余弦函數(shù)使解震蕩性地趨于全局最優(yōu)解,避免陷入全局最優(yōu)。

(9)

2.3 螢火蟲擾動

為了提升算法的局部搜索能力,在麻雀每代個體位置更新后用螢火蟲擾動進行尋優(yōu),不僅可以對單峰函數(shù)表現(xiàn)出很好的性能,在優(yōu)化多峰函數(shù)上也有不錯的表現(xiàn),可以在一個較小的區(qū)域內(nèi)快速找到該區(qū)域的最優(yōu)解。

Xi=Xi+β0exp(-γr2)(Xj-Xi)+

α·k

(10)

式中:Xi為螢火蟲i所處的空間位置;Xj為螢火蟲j所處的空間位置;β0為最大吸引度;γ∈[0,1]為吸光系數(shù);α∈[0,1]為步長因子;k為[-0.5,0.5]上服從均勻分布的隨機數(shù)。改進后的具體算法流程如圖3所示。

圖3 算法流程

3 仿真實驗

本文將ISSAMS與其他算法做對比試驗。選取5個基準(zhǔn)測試函數(shù):

其維度均為30,最優(yōu)值均為0;f1～f3為單峰函數(shù),f4～f5為多峰函數(shù)。

為分析算法改進的有效性,本文將SSA、遺傳算法(genetic algorithm,GA)、GWO算法、粒子群優(yōu)化(particle swarm optimization,PSO)算法和本文算法對表1中的基準(zhǔn)函數(shù)進行尋優(yōu)測試,針對這5種算法,每個算法獨立運行30次,取每次的最優(yōu)值。其中,每運行一次的算法迭代次數(shù)為1 000,種群數(shù)量為30。如表1給出了SSA、GA、GWO、PSO、ISSAMS對于5種基準(zhǔn)函數(shù)的仿真實驗結(jié)果。

表1 SSA與GA、GWO、PSO、ISSAMS仿真結(jié)果

從表1可以看出,在單峰函數(shù)中,GA均值最大,同時標(biāo)準(zhǔn)差也最大,說明穩(wěn)定性最差,GWO、PSO算法次之。SSA、ISSAMS雖然都能找到理論最優(yōu)解0,但是通過標(biāo)準(zhǔn)差來看,ISSAMS標(biāo)準(zhǔn)差為0,算法更穩(wěn)定,由于ISSAMS融合了多種策略,并且在局部搜索能力和尋優(yōu)速度上都有所提升,因此ISSAMS在穩(wěn)定性和精確度上都優(yōu)于SSA,而且是實驗中5種算法整體性能最好的。在多峰函數(shù)函數(shù)中,每個函數(shù)都具有多個局部最優(yōu)解,容易陷入局部最優(yōu)。本文的ISSAMS引入正余弦搜索策略,增強局部搜索能力,避免陷入全局最優(yōu)使其具備跳出局部最優(yōu)解的能力。因此,不管是在最優(yōu)值還是標(biāo)準(zhǔn)差上都較優(yōu)于其他4種算法,特別是函數(shù)中ISSAMS相較于另外4種算法在平均值和標(biāo)準(zhǔn)差有著很大的提升。因此,結(jié)合上述分析,對于融合多策略改進的ISSAMS在收斂速度、穩(wěn)定性和精確度上都表現(xiàn)出很好的性能。

為了更進一步分析改進后算法的收斂速度,對于5種算法依次進行了仿真實驗,圖4和圖5為本文中的5種算法分別迭代了1 000次以后得到的收斂曲線。

(a) f1收斂曲線

從圖4可以看出,對于單峰函數(shù) ,ISSAMS收斂速度更快,明顯優(yōu)于其他,4種算法,而且表現(xiàn)出更強的局部搜索能力和更高的精確度,其次是SSA。

從圖5可以看出,對于多峰函數(shù),除了GA和PSO算法,SSA、GWO算法、ISSAMS收斂速度相差不大,但是總體ISSAMS收斂速度還是較優(yōu)于其他算法,而在精確度上ISSAMS明顯優(yōu)于其他4種算法,說明基于多策略改進的麻雀搜索算法具備更強的跳出局部最優(yōu)解的能力。

上述結(jié)果說明,利用改進后的Circle混沌映射初始化種群,增加了種群均勻性,提升了算法的收斂速度;引入正弦余弦搜索策略和螢火蟲擾動,增加了全局搜索范圍,趨于全局最優(yōu)解,加速尋優(yōu)過程,提升了算法的逃離局部最優(yōu)能力。因此,本文提出的ISSAMS對比其他算法,在收斂速度、精確度和跳出局部最優(yōu)的能力都得到了較大的提高。

4 改進的SSA優(yōu)化BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)是一種按照誤差逆向傳播算法訓(xùn)練的多層前饋神經(jīng)網(wǎng)絡(luò),是應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)模型之一[23]。但是傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)在實際應(yīng)用中,可能經(jīng)常陷入到局部極小值中,此時可以通過選取智能優(yōu)化算法對每一輪的權(quán)值和閾值進行優(yōu)化,來獲得全局最優(yōu)值。其中,文獻[24]提出一種基于正弦混沌映射的改進SSA改進BP神經(jīng)網(wǎng)絡(luò)對風(fēng)速進行預(yù)測。文獻[25]將Logistic混沌映射和Lévy飛行策略整合到傳統(tǒng)的SSA,優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)重和閾值來預(yù)測風(fēng)電功率。上述基于SSA的改進結(jié)合BP神經(jīng)網(wǎng)絡(luò)進行預(yù)測,由于改進的有限性,仍存在收斂速度慢,權(quán)值閾值精確度低等問題。針對此問題,本文選取ISSAMS和SSA、CSSA、PSO算法、GWO算法來分別對BP分別進行優(yōu)化;對于同一樣本數(shù)據(jù),比較其相關(guān)指標(biāo),如平均絕對誤差(mean absolute error,MAE)、均方誤差(mean-square error,MSE)、均方根誤差(root mean squared error,RMSE)、平均絕對百分比誤差(mean absolute percentage error,MAPE)、收斂速度等,驗證本文算法的改進在優(yōu)化BP神經(jīng)網(wǎng)絡(luò)上的有效性。

4.1 BP神經(jīng)網(wǎng)絡(luò)模型設(shè)計

首先針對現(xiàn)有的BP神經(jīng)網(wǎng)絡(luò)模型進行改進,優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值,其具體步驟如下:

1) 數(shù)據(jù)歸一化處理,初始化參數(shù);

2) 使用Circle混沌映射初始化適應(yīng)度值,然后找出當(dāng)前最優(yōu)適應(yīng)度值和最差適應(yīng)度值,以及相對應(yīng)的位置;

3) 根據(jù)式(3)、(4)、(5)依次更新發(fā)現(xiàn)者、跟隨者、偵察者位置;

4) 輸出最優(yōu)麻雀位置,即得到BP神經(jīng)網(wǎng)絡(luò)的相關(guān)最優(yōu)參數(shù);

5) 優(yōu)化后的BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練與測試,與優(yōu)化前的BP神經(jīng)網(wǎng)絡(luò)進行誤差分析和精度對比。ISSAMS-BP模型的流程如圖6所示。

圖6 ISSAMS優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)流程

4.2 改進算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)性能分析

4.2.1 實驗數(shù)據(jù)集

本文中選取的數(shù)據(jù)集為工業(yè)互聯(lián)網(wǎng)數(shù)據(jù)湖[26]平臺中的電力負(fù)荷數(shù)據(jù),包含從發(fā)電廠收集的201個數(shù)據(jù)點。數(shù)據(jù)的特征包括每小時平均環(huán)境變量溫度、環(huán)境壓力、相對濕度和排氣真空,以預(yù)測電廠每小時凈電能輸出。選取15組數(shù)據(jù)作為測試集對預(yù)測結(jié)果進行驗證。其中初始種群規(guī)模為30,最大進化代數(shù)50。

4.2.2 實驗環(huán)境

本文實驗采用的PC設(shè)備參數(shù)為:AMDR7-5800H CPU,2.90 Hz,運行內(nèi)存為16 GiB,Windows10系統(tǒng)。仿真實驗使用Matlab2016b軟件進行編程并作圖。

4.2.3 實驗結(jié)果分析

為了驗證改進策略的有效性,通過將ISSAMS、SSA、基于Circle混沌映射初始化改進后的SSA(簡稱CSSA)、PSO算法、GWO算法分別對BP神經(jīng)網(wǎng)絡(luò)模型進行優(yōu)化,優(yōu)化后的模型對數(shù)據(jù)進行預(yù)測,其中將數(shù)據(jù)集中電廠每小時凈電能輸出的預(yù)測結(jié)果的均方誤差作為衡量標(biāo)準(zhǔn),進化代數(shù)表示算法的收斂速度,通過這2個指標(biāo)來說明不同的算法在優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的好壞。具體實驗結(jié)果如圖7所示。

圖7 進化收斂曲線

從圖7可以看出,5種不同的算法對于BP的優(yōu)化效果,其中使用SSA、PSO和GWO算法優(yōu)化的BP模型,其誤差區(qū)別不大,但SSA的收斂速度稍快于PSO和GWO算法,而CSSA和ISSAMS在其收斂速度上保持一致,由于都引入了Circle混沌映射進行種群初始化,增加種群的多樣性,提高全局搜索能力,但是ISSAMS的MSE值更小,表示其模型預(yù)測的精度更精確。

為了更能說明改進算法優(yōu)化BP的性能,通過比較MAE、MSE、RMSE和MAPE,具體對比如表2所示。

表2 性能指標(biāo)

從表2和圖7可以看出,在使用了本文提出的ISSAMS優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)模型預(yù)測,在收斂速度上,本文提出的算法從第2代開始逼近了最優(yōu)值,收斂速度最快,明顯優(yōu)于其他4種模型,而且精確度也最高。在其MAPE值上,ISSAMS-BP模型誤差達到了0.594 2%,比BP、SSA-BP、CSSA-BP、PSO-BP和GWO-BP的MAPE值分別降低了28.05%、12.84%、7.69%、18.59%、19.35%?？傮w來看ISSAMS在優(yōu)化BP神經(jīng)網(wǎng)絡(luò)上具備一定的優(yōu)勢,通過實驗得到了驗證。

5 結(jié) 語

1) 采用改進的Circle混沌映射初始化種群,增加了種群的多樣性和穩(wěn)定性,擴大了麻雀在空間中的搜索范圍,從而提高了算法的尋優(yōu)效率。同時改進發(fā)現(xiàn)者位置更新公式,加快收斂速度;采用正弦余弦搜索策略和螢火蟲擾動來提升算法跳出局部最優(yōu)的能力和增強局部搜索能力。

2) 將融合多策略改進的算法與其他幾種算法做對比實驗,在加入了Circle混沌映射、正弦余弦搜索策略和螢火蟲擾動后,實驗結(jié)果表明ISSAMS有效地改善了SSA的尋優(yōu)能力,同時具備更高的收斂能力、精確度和穩(wěn)定性,大大提升了算法整體性能。

3) SSA可以優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值,提升神經(jīng)網(wǎng)絡(luò)的模型準(zhǔn)確度。通過將融合多策略改進的ISSAMS應(yīng)用到權(quán)值和閾值的優(yōu)化中,得出ISSAMS-BP明顯優(yōu)于原始BP和另外4種預(yù)測模型,同時,進一步驗證了ISSAMS改進的有效性。后續(xù)研究可將ISSAMS應(yīng)用于更多的神經(jīng)網(wǎng)絡(luò)模型中,提升預(yù)測模型的準(zhǔn)確度。