麻雀搜索算法(?sparrow?search?algorithm，SSA)是2020?年新提出的一種元啟發(fā)式算法[1]，它是受麻雀種群的覓食和反捕食行為啟發(fā)，將搜索群體分為發(fā)現(xiàn)者、加入者和偵察者?3?部分，其相互分工尋找最優(yōu)值，通過?19?個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)驗(yàn)證?SSA?算法在搜索精度，收斂速度，穩(wěn)定性和避免局部最優(yōu)值方面均優(yōu)于現(xiàn)有算法。

麻雀搜索算法雖有以上優(yōu)點(diǎn)，但如何調(diào)節(jié)各部分之間的控制參數(shù)，以及如何保證?3?部分之間可以較好的相互配合是一個(gè)必須考慮的問題。為解決這個(gè)問題，許多學(xué)者都進(jìn)行了嘗試，諸如混沌初始化、變異、混沌擾動(dòng)、反向?qū)W習(xí)等方法都被引入其中，因此，本文也將嘗試通過混沌初始化、變異、擾動(dòng)等策略提高算法性能。

00?文章目錄

1?麻雀搜索算法原理

2?自適應(yīng)變異麻雀搜索算法

3?代碼目錄

4?算法性能

5?源碼獲取

6?總結(jié)

01?麻雀算法原理

這部分在作者往期文章中已作詳細(xì)闡述，感興趣的讀者可以點(diǎn)擊下方鏈接查看

超詳細(xì)?|?麻雀搜索算法原理及其實(shí)現(xiàn)(Matlab)

02?自適應(yīng)變異麻雀搜索算法

2.1?Chebyshev?混沌映射

與其他群智能算法一樣，原始?SSA?在求解復(fù)雜問題時(shí)，通過隨機(jī)生成位置的方法初始化麻雀種群的個(gè)體位置，會(huì)導(dǎo)致種群的多樣性低，對(duì)問題進(jìn)行尋優(yōu)的收斂速度比較慢。為了能夠讓麻雀?jìng)€(gè)體在算法開始時(shí)有較高的全局搜索能力，需要讓麻雀種群的位置均勻分布在整個(gè)問題的解空間內(nèi)，因此使用混沌算子對(duì)麻雀種群進(jìn)行初始化。

混沌作為一種非線性的自然現(xiàn)象，以其混沌序列具有遍歷性、隨機(jī)性等優(yōu)點(diǎn)，被廣泛用于優(yōu)化搜索問題。利用混沌變量搜索顯然比無(wú)序隨機(jī)搜索具有更大的優(yōu)越性[2]。

目前文獻(xiàn)中常用的混沌擾動(dòng)方程有Logistic映射和Tent映射等。Logistic映射在作者前面的文章中介紹過，由文獻(xiàn)[3]可知Logistic映射的分布特點(diǎn)是:中間取值概率比較均勻,但在兩端概率特別高,因此當(dāng)全局最優(yōu)點(diǎn)不在設(shè)計(jì)變量空間的兩端時(shí),對(duì)尋找最優(yōu)點(diǎn)是不利的。而Tent混沌映射具有比Logistic混沌映射更好的遍歷均勻性和更快的搜索速度。下圖中展示了Logistic和Tent的混沌序列：

可以看到，Logistic混沌映射在邊界區(qū)域取值概率明顯更高，而Tent在可行域的取值概率更為均勻，因此若將Logistic混沌映射用于初始化種群時(shí)，其混沌序列的不均勻性會(huì)影響算法尋優(yōu)的速度和精度。因此本文利用Tent的遍歷性產(chǎn)生更為均勻分布的混沌序列，減少初始值對(duì)算法優(yōu)化的影響。

Tent混沌映射的表達(dá)式如下：

分析Tent混沌迭代序列能夠發(fā)現(xiàn)序列中存在小周期,并且存在不穩(wěn)周期點(diǎn).為避免Tent混沌序列在迭代時(shí)落入小周期點(diǎn)和不穩(wěn)定周期點(diǎn),在原有的Tent?混沌映射表達(dá)式上引入一個(gè)隨機(jī)變量rand(0,?1)?/N?,則改進(jìn)后的Tent混沌映射表達(dá)式如下[4]:

其中:?N?是序列內(nèi)粒子的個(gè)數(shù)。引入隨機(jī)變量rand(0,?1)?/N?不僅仍然保持了Tent混沌映射的隨機(jī)性、遍歷性、規(guī)律性,而且能夠有效避免迭代落入小周期點(diǎn)和不穩(wěn)定周期點(diǎn)內(nèi)。本文算法引入的隨機(jī)變量,既保持了隨機(jī)性,?又將隨機(jī)值控制在一定的范圍之內(nèi),保證了Tent混沌的規(guī)律性.根據(jù)Tent混沌映射的特性。改進(jìn)的Tent混沌序列效果如下：

由圖可知，改進(jìn)后的Tent混沌映射其均勻性得到了提高，因此本文以改進(jìn)Tent混沌性來(lái)代替麻雀搜索算法的隨機(jī)初始化，以提高和改善初始種群在搜索空間上的分布質(zhì)量，加強(qiáng)其全局搜索能力，從而提高算法求解精度。

2.2?趨優(yōu)反向?qū)W習(xí)和混合變異擾動(dòng)策略

對(duì)于迭代中的每一個(gè)麻雀?jìng)€(gè)體，通過比較其適應(yīng)度和平均適應(yīng)度的大小關(guān)系將反向?qū)W習(xí)和混合變異擾動(dòng)動(dòng)態(tài)執(zhí)行，增強(qiáng)算法的局部極值逃逸能力，改善其尋優(yōu)效果。

2.2.1趨優(yōu)反向?qū)W習(xí)

許多群體智能算法都采用隨機(jī)算子對(duì)最優(yōu)解進(jìn)行擾動(dòng)，這將導(dǎo)致收斂速度變慢。2005?年，Tizhoosh［6］提出反向?qū)W習(xí)策略（OBL）。OBL提出對(duì)點(diǎn)的概念，用對(duì)立代替隨機(jī)，在當(dāng)前問題的解空間內(nèi)尋找當(dāng)前解的反向解，然后通過評(píng)估當(dāng)前解和反向解的值，保留更好的解來(lái)取代原解中較差的解。因此本文對(duì)適應(yīng)度較差個(gè)體執(zhí)行趨優(yōu)反向?qū)W習(xí)策略，提高種群質(zhì)量的同時(shí)擴(kuò)大算法的搜索區(qū)域，以補(bǔ)足算法的全局勘探能力。

首先對(duì)當(dāng)前個(gè)體實(shí)施反向?qū)W習(xí)策略，得到反向個(gè)體:

其中:?xlj?和?xuj?分別為第?j?維分量的下界和上界。

文獻(xiàn)［6］指出反向個(gè)體優(yōu)于當(dāng)前個(gè)體的概率高于?50%，考慮到仍有部分個(gè)體在反向?qū)W習(xí)之后個(gè)體質(zhì)量有所降低，為了減少這種現(xiàn)象發(fā)生的概率并保持種群多樣性，將求得的反向個(gè)體和當(dāng)前種群中最優(yōu)個(gè)體進(jìn)行凸組合，得到趨優(yōu)反向個(gè)體:

其中:?a為[0,1]的隨機(jī)數(shù);?xgbest,j是當(dāng)前種群全局最佳個(gè)體的第?j?維分量。

通過實(shí)施該策略，即使最初求得的反向個(gè)體相較于當(dāng)前個(gè)體有所退化，但與當(dāng)前種群中最優(yōu)個(gè)體進(jìn)行凸組合后，反向解還會(huì)接受一部分來(lái)自最優(yōu)個(gè)體的特征，進(jìn)一步提升了反向個(gè)體?的質(zhì)量，同時(shí)也提高了算法的勘探能力、種群多樣性和算法的收斂精度[7]。

2.2.2?混合變異算子

使用標(biāo)準(zhǔn)的柯西分布進(jìn)行變異處理，可以幫助變異之后的麻雀?jìng)€(gè)體迅速跳出局部極值。按照下式對(duì)當(dāng)前麻雀?jìng)€(gè)體進(jìn)行變異：

高斯分布的點(diǎn)分布較為集中，該特征能夠產(chǎn)生于原點(diǎn)相距較近的隨機(jī)數(shù)，經(jīng)過高斯變異之后的麻雀?jìng)€(gè)體在位置進(jìn)行很小的范圍內(nèi)擾動(dòng)，可以提高變異個(gè)體的局部搜索能力。使用標(biāo)準(zhǔn)的高斯分布進(jìn)行變異處理，按照下式對(duì)當(dāng)前麻雀?jìng)€(gè)體進(jìn)行變異：

高斯-柯西混合變異算子通過線性權(quán)重系數(shù)將標(biāo)準(zhǔn)高斯變異得到的新麻雀?jìng)€(gè)體位置和標(biāo)準(zhǔn)柯西變異得到的新麻雀?jìng)€(gè)體位置生成一個(gè)全新的麻雀?jìng)€(gè)體位置?Xtb_new。新麻雀?jìng)€(gè)體的表達(dá)式為：

從上式可以看出，算法開始運(yùn)行時(shí)，t值較小，柯西變異的權(quán)值較大，通過柯西變異獲得較大步長(zhǎng)，避免算法陷入局部最優(yōu)解。隨著算法不斷運(yùn)行，t?值較大，?高斯變異的權(quán)值較大，高斯變異杰出的局部搜索能力使得候選解在局部范圍進(jìn)行精確搜索，提高算法的尋優(yōu)精度[8]。

2.3?發(fā)現(xiàn)者-加入者自適應(yīng)調(diào)整策略

在?SSA算法中，發(fā)現(xiàn)者和加入者的數(shù)目比例保持不變，這會(huì)導(dǎo)致在迭代前期，發(fā)現(xiàn)者的數(shù)目相對(duì)較少，無(wú)法對(duì)全局進(jìn)行充分的搜索，在迭代后期，發(fā)現(xiàn)者的數(shù)目又相對(duì)較多，此時(shí)已不需要更多的發(fā)現(xiàn)者進(jìn)行全局搜索，而需要增加加入者的數(shù)量進(jìn)行精確的局部搜索。為解決這個(gè)問題，提出發(fā)現(xiàn)者-加入者自適應(yīng)調(diào)整策略，該策略在迭代前期，發(fā)現(xiàn)者可以占種群數(shù)目的多數(shù)，隨著迭代次數(shù)的增加，發(fā)現(xiàn)者的數(shù)目自適應(yīng)減少，加入者的數(shù)目自適應(yīng)增加，逐步從全局搜索轉(zhuǎn)為局部精確搜索，從整體上提高算法的收斂精度。發(fā)現(xiàn)者和加入者數(shù)目調(diào)整式為

式中：pNum?為發(fā)現(xiàn)者數(shù)目；sNum為加入者數(shù)目；b為比例系數(shù)，用于控制發(fā)現(xiàn)者和加入者之間的數(shù)目；k為擾動(dòng)偏離因子，對(duì)非線性遞減值?r?進(jìn)行擾動(dòng)[9]。

2.4改進(jìn)后的麻雀搜索算法

自適應(yīng)變異麻雀搜索算法

(Adaptive?Mutation-Sparrow??Search??optimization??Algorithm,?AM-SSA)流程圖如下:

03?代碼目錄

其中，AM_SSA、SSA、PSO、GA都是可獨(dú)立運(yùn)行的主程序，而compare.m則可以比較不同算法的迭代曲線情況。

代碼注釋完整，其中部分AM_SSA程序如下：

04?算法性能

4.1?測(cè)試函數(shù)

為了能夠驗(yàn)證自適應(yīng)變異麻雀搜索算法對(duì)比粒子群算法、遺傳算法以及麻雀搜索算法有更好的效果，本文選用4個(gè)CEC的標(biāo)準(zhǔn)測(cè)試函數(shù)Sphere、Griewank、Rastrigin、Rosenbrock對(duì)算法的尋優(yōu)精度、跳出局部能力、全局尋優(yōu)能力進(jìn)行檢驗(yàn)。4個(gè)函數(shù)的表達(dá)式如下：

4.1.1?Sphere函數(shù)

Sphere?函數(shù)的自變量????的取值的范圍：-100＜????＜100；該函數(shù)存在唯一的一個(gè)全局的最小值，且當(dāng)??=(0,0,…,0)時(shí)，函數(shù)取得全局最小值?f1(x)?=?0。選擇該函數(shù)是對(duì)算法尋優(yōu)的精度進(jìn)行測(cè)試。

4.1.2?Griewank函數(shù)

Griewank?函數(shù)的自變量????的取值的范圍：-600＜????＜600；該函數(shù)在整個(gè)的數(shù)?據(jù)分布含有大量局部極值，但是存在全局最小值?f2(x)?=?0，是一種比較復(fù)雜的多模的復(fù)雜性問題，因此選擇該函數(shù)目的是對(duì)算法是否跳出局部，能夠繼續(xù)搜索的?能力進(jìn)行測(cè)試。

4.1.3?Rastrigin函數(shù)

Rastrigin?函數(shù)的自變量????的取值的范圍：-5.12＜????＜5.12；在?x?=?(?0,0?,…,?0?)?處的時(shí)候存在全局極小點(diǎn)?0，該函數(shù)是一個(gè)非線性的多峰值函數(shù)，存在大量的局部最小值，尋找全局極小值時(shí)有一定的困難，因此用此函數(shù)可以，對(duì)算法的全局尋優(yōu)能力檢驗(yàn)測(cè)試。

4.1.4?Rosenbrock函數(shù)

Rosenbrock?函數(shù)的自變量????的取值的范圍：-30＜????＜30；該函數(shù)是一單峰函數(shù)，?存在全局極小值，位于一個(gè)類似開口向上的拋物線的最低點(diǎn)處，雖然能夠比較容易找到，但是很難收斂到最低處，因此可以測(cè)試全局尋優(yōu)的能力。

4.2?測(cè)試結(jié)果

Sphere函數(shù)

Griewank函數(shù)

Rastrigin函數(shù)

Rosenbrock函數(shù)

可以看到改進(jìn)后的麻雀搜索算法后能夠極大的提升其全局尋優(yōu)的性能，無(wú)論是收斂速度還是精度都得到了極大的提高。這里的測(cè)試函數(shù)還是比較簡(jiǎn)單了，所以效果并沒有太明顯，在后面的文章中作者也會(huì)引入更復(fù)雜的測(cè)試函數(shù)來(lái)對(duì)算法性能進(jìn)行驗(yàn)證。

05?源碼獲取

見評(píng)論

06?總結(jié)

本文通過變異、混沌初始化、反向?qū)W習(xí)等策略對(duì)麻雀搜索算法進(jìn)行了改進(jìn)，并取得了不錯(cuò)的效果。對(duì)于算法的改進(jìn)還可以通過混合其他智能算法來(lái)實(shí)現(xiàn)，后面作者也會(huì)這類方法進(jìn)行更新，歡迎關(guān)注。

參考文獻(xiàn)

[1]?XUE?J?K,?ShEN?B.?A?novel?swarm?intelligence?optimization?approach:?sparrow?search?algorithm?[J].?Systems?Science?&?Control?Engineering,?2020,?8(1):?22-34.

[2]?張?jiān)迄i,左飛,翟正軍.基于雙Logistic變參數(shù)和Cheby-chev混沌映射的彩色圖像密碼算法[J.西北工業(yè)大學(xué)學(xué)報(bào),?2010,28(4):?628-632.

[3]?江善和,王其申,汪巨浪.一種新型SkewTent映射的混沌混合優(yōu)化算法[J.控制理論與應(yīng)用,?2007,24(2):?269-273.

[4]?張娜,趙澤丹,包曉安,等.基于改進(jìn)的Tent混沌萬(wàn)有引力搜索算法[J].控制與決策,2020,35(4):893-900.

[5]?Tizhoosh?H?R.?Opposition-based?learning:?a?new?scheme?for?machine?intelligence[C]?∥International?Conference?on?Computational?Intelligence?for?Modelling,?Control?and?Automation?and?International?Conference?on?Intelligent?Agents,?Web?Technologies?and?Internet?Commerce?(CIMCA-IAWTIC'06),?November?28-30,?2005,?Vienna,?Austria.?New?York:?IEEE?Press,?2005:?695-701.

[6]?Tizhoosh?H?Ｒ．?Opposition-based?learning:?a?new?scheme?for?machine?intelligence［C］/?/Proc?of?International?Conference?on?Computational?Intelligence?for?Modeling，Control?and?Automation．?Piscataway，NJ:?IEEE?Press，2005:?695-701．

[7]左汶鷺,高岳林.基于隨機(jī)鄰域變異和趨優(yōu)反向?qū)W習(xí)的差分進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用研究,2023,40(07):2003-2012.DOI:10.19734/j.issn.1001-3695.2022.11.0785.

[8]陳深,劉以安,宋海凌.改進(jìn)麻雀算法在天波雷達(dá)定位中的應(yīng)用[J].激光與光電子學(xué)進(jìn)展,2023,60(10):350-357.

[9]唐延強(qiáng),李成海,宋亞飛等.自適應(yīng)變異麻雀搜索優(yōu)化算法[J].北京航空航天大學(xué)學(xué)報(bào),2023,49(03):681-692.DOI:10.13700/j.bh.1001-5965.2021.0282.

另：如果有伙伴有待解決的優(yōu)化問題（各種領(lǐng)域都可），可以發(fā)我，我會(huì)選擇性的更新利用優(yōu)化算法解決這些問題的文章。

如果這篇文章對(duì)你有幫助或啟發(fā)，可以點(diǎn)擊右下角的贊/在看(???_??)?(不點(diǎn)也行)