融合正弦余弦算法的蝴蝶優(yōu)化算法*

鄭洪清,馮文健,周永權(quán)

(1.廣西外國語學(xué)院信息工程學(xué)院，廣西南寧 530222；2.柳州鐵道職業(yè)技術(shù)學(xué)院，廣西柳州 545616；3.廣西民族大學(xué)人工智能學(xué)院，廣西南寧 530006)

0 引言

由于群智能算法無需先驗(yàn)知識，無需分析數(shù)據(jù)內(nèi)部規(guī)律和內(nèi)在關(guān)聯(lián)，只需對數(shù)據(jù)本身進(jìn)行學(xué)習(xí)，自組織、自適應(yīng)地完成優(yōu)化問題的求解，近年來大批群智能算法被相繼提出，如布谷鳥搜索算法(Cuckoo Search Algorithm,CS)[1]、樽海鞘群算法(Salp Swarm Algorithm,SSA)[2]、狼群算法(Grey Wolf Optimizer,GWO)[3]、正弦余弦算法(Sine Cosine Algorithm,SCA)[4]、鯨魚優(yōu)化算法(Whale Optimization Algorithm)[5]、花朵授粉算法(Flower Pollenation Algorithm,FPA)[6]等。這些群智能算法基本上是模擬生物的群體行為，按照某種合作方式一起求解優(yōu)化問題，并在工程優(yōu)化、圖像處理、特征選擇和機(jī)器學(xué)習(xí)等領(lǐng)域得到廣泛應(yīng)用。蝴蝶優(yōu)化算法(Butterfly Optimization Algorithm,BOA)[7]是模擬自然界的蝴蝶覓食或求偶行為而衍生出的一種仿生群智能算法，已成功解決圖像分割[8]、經(jīng)濟(jì)負(fù)荷調(diào)度[9]等問題。但基本BOA也存在收斂速度慢、計(jì)算精度差和易陷入局部最優(yōu)等缺陷，許多學(xué)者提出不同改進(jìn)策略。如高文欣等[10]首先引入limit閾值來限定BOA陷入局部最優(yōu)次數(shù)，然后結(jié)合單純形法和正弦余弦算法提升算法性能，但同時(shí)也增加了算法時(shí)間復(fù)雜度且其函數(shù)4求解精度較低。王依柔等[11]首先在自身認(rèn)知部分引入自適應(yīng)慣性權(quán)重，其次在全局最優(yōu)位置引入擾動策略，在花蜜位置引入瘋狂因子來平衡算法的局部與全局搜索能力，提出無限折疊迭代混沌映射的蝴蝶優(yōu)化算法(SIBOA)，但該優(yōu)化后的算法其精度還有待于進(jìn)一步提升。寧杰瓊等[12]首先利用Circle映射初始化種群，然后在局部搜索階段利用動態(tài)切換概率，控制改進(jìn)正弦余弦算法與蝴蝶優(yōu)化算法的轉(zhuǎn)換，并在全局和局部位置引入自適應(yīng)權(quán)重系數(shù)和逐維變異策略，從而改進(jìn)算法的性能，使求解的精度較高。但該算法的測試函數(shù)較少且回避了最難求解的Rosenbrock函數(shù)測試。高文欣等[13]在全局位置引入柯西分布函數(shù)，在局部位置引入自適應(yīng)權(quán)重因子，并引入動態(tài)切換概率來改進(jìn)算法性能，但函數(shù)Apline未達(dá)到理論最優(yōu)。高文欣等[14]引入收斂因子和黃金正弦指引機(jī)制來提升算法效果，但測試函數(shù)較少，精度還有待于進(jìn)一步提升。謝聰?shù)萚15]融入差分進(jìn)化策略和精英策略改進(jìn)算法，但算法的串聯(lián)操作相應(yīng)地增加了算法的時(shí)間開銷。

雖然上述算法在一定程度上提高了算法性能，但仍有提升空間。本文提出一種融合正弦余弦算法的蝴蝶優(yōu)化算法(Sine Cosine Algorithm and Butterfly Optimization Algorithm，SCABOA)，在BOA基礎(chǔ)之上從以下4個(gè)方面進(jìn)行改進(jìn)：在蝴蝶自身認(rèn)知部分引入非線性自適應(yīng)因子；重新定義香味濃度計(jì)算公式；在局部搜索階段引入改進(jìn)的正弦余弦算法；為回避轉(zhuǎn)換概率對算法的影響，將種群一分為二。

1 蝴蝶優(yōu)化算法

蝴蝶優(yōu)化算法是模擬蝴蝶覓食和繁衍行為而衍生出的一種仿生群智能算法，在BOA中每只蝴蝶都會散發(fā)出香味，蝴蝶個(gè)體能感知香味而互相吸引，香味濃度的計(jì)算公式如下：

fi=cIa，

(1)

其中，fi表示蝴蝶個(gè)體i感知香味的強(qiáng)度；c表示感知模態(tài)參數(shù)；I表示蝴蝶散發(fā)香味的刺激強(qiáng)度，其值由目標(biāo)函數(shù)值決定；a表示香味吸收程度，a∈[0,1]。

當(dāng)蝴蝶能感知到周圍有更濃香味時(shí)便朝其聚集，此階段稱為全局搜索，其計(jì)算公式如下：

(2)

當(dāng)蝴蝶未能感知周圍香味時(shí)便隨機(jī)移動，此階段稱為局部搜索，其計(jì)算公式如下：

(3)

2 融合正弦余弦算法的蝴蝶優(yōu)化算法

2.1 非線性自適應(yīng)因子

大量文獻(xiàn)記載了引入自適應(yīng)權(quán)重因子的優(yōu)勢，有線性的，也有非線性的，其主要目的是為了更好地平衡算法的全局搜索和局部搜索能力。這也是算法改進(jìn)的一個(gè)突破口，本文首先在自身認(rèn)知部分引入非線性自適應(yīng)因子，使算法迭代初期在較寬范圍內(nèi)搜索，迭代后期在較小范圍內(nèi)搜索。非線性自適應(yīng)因子的計(jì)算公式如下:

ω(t)=2×exp(-(4×t/Ngen)2)，

(4)

其中，exp為指數(shù)函數(shù)，Ngen為最大迭代次數(shù)。

2.2 更改香味濃度計(jì)算表達(dá)式

在BOA中，香味濃度的計(jì)算公式如式(1)所示，其值取決于感知模態(tài)參數(shù)c、香味吸收程度a和蝴蝶散發(fā)香味的刺激強(qiáng)度I，其中I值是由目標(biāo)函數(shù)值決定，首先觀察Sphere函數(shù)香味濃度變化趨勢(其他函數(shù)變化曲線類似)，如圖1所示。

圖1 香味濃度fi變化曲線

由圖1可知，在迭代過程中香味濃度值變化曲線由小變大再變小，變化的范圍較小，不利于全局搜索，而且中后期曲線斜率變化較小導(dǎo)致收斂速度緩慢且計(jì)算精度不高。因此用變化范圍較寬和斜率變化較大的自適應(yīng)權(quán)重因子重新定義香味濃度計(jì)算表達(dá)式，其計(jì)算公式如下：

b=2-2×t/Ngen。

(5)

fi=2×b×r-b，

(6)

b表示隨迭代次數(shù)變化參數(shù)，則蝴蝶全局搜索公式更改為

(7)

2.3 正弦余弦算法指引機(jī)制

正弦余弦算法于2016年由澳大利亞學(xué)者M(jìn)irjalili[4]提出，該算法利用正余弦函數(shù)的周期性和振蕩性趨于全局最優(yōu)，算法中自適應(yīng)參數(shù)能較好地平衡算法的全局搜索和局部開發(fā)。計(jì)算公式如下：

(8)

其中，r1等于式(5)，r2∈[0,2π]之間的隨機(jī)數(shù)，r3,r4∈[0,1]之間的隨機(jī)數(shù)。

高文欣等[10]和寧杰瓊等[12]也使用正弦余弦算法來改進(jìn)BOA，高文欣等[10]在算法迭代后期讓所有蝴蝶個(gè)體執(zhí)行正弦余弦算法，本質(zhì)上實(shí)行算法的串聯(lián)操作，但在一定程度上增加了算法的時(shí)間開銷；寧杰瓊等[12]在局部搜索過程中以一定概率將正弦余弦算法與基本BOA的局部搜索公式共同尋優(yōu)。而本文的操作方式與其不同，首先使用非線性自適應(yīng)因子式(4)替換式(8)中r1，然后用正弦余弦算法替換基本BOA的局部搜索公式，更好地平衡正弦余弦算法的全局搜索和局部勘探能力。因此改進(jìn)后的正弦余弦算法公式如下：

(9)

2.4 SCABOA的偽代碼

輸入：種群規(guī)模n、函數(shù)名稱和最大迭代次數(shù)。

①在邊界范圍內(nèi)隨機(jī)產(chǎn)生種群，并計(jì)算此時(shí)最優(yōu)解和最優(yōu)值

②Whilet

③計(jì)算式(4)和式(5)

④Fori=1∶n

⑤計(jì)算式(6)

⑥Ifi≤n/2

⑦執(zhí)行式(7)

⑧Else

⑨Forj=1∶dim

⑩執(zhí)行式(9)

輸出：最優(yōu)值和最優(yōu)解

3 仿真實(shí)驗(yàn)與結(jié)果

為檢驗(yàn)SCABOA的性能，選取19個(gè)基準(zhǔn)函數(shù)進(jìn)行測試，函數(shù)的具體表達(dá)式、維度、取值范圍和理論值最優(yōu)值如表1所示。實(shí)驗(yàn)環(huán)境為Matlab2016a和Windows10，機(jī)器主頻為2.60 GHz ，內(nèi)存為8 GB。

表1 基準(zhǔn)函數(shù)

利用SCABOA對19個(gè)基準(zhǔn)函數(shù)進(jìn)行求解，并與基本BOA、SCA、SSA、GWO和CS算法進(jìn)行對比，以驗(yàn)證SCABOA的效果。參數(shù)設(shè)置：種群規(guī)模為30，最大迭代次數(shù)為500，其余參數(shù)設(shè)置與原論文相同。為避免偶然性，每種算法在Matlab2016a軟件中獨(dú)立運(yùn)行30次，計(jì)算每個(gè)函數(shù)的平均值Mean和方差Std，結(jié)果如表2所示，表中“-”表示文獻(xiàn)未對相關(guān)函數(shù)進(jìn)行測試，表中的加粗字體為所有實(shí)驗(yàn)中的最佳結(jié)果。

表2 基準(zhǔn)函數(shù)的實(shí)驗(yàn)結(jié)果

由表2第3-8列可知，SCABOA求解的19個(gè)基準(zhǔn)函數(shù)測試中，有8個(gè)函數(shù)(f1-f4、f8、f9、f11和f19)的平均計(jì)算結(jié)果達(dá)到理論最優(yōu)值，完全勝出BOA、SCA、SSA、GWO和CS算法。未達(dá)到理論最優(yōu)值的11個(gè)函數(shù)中，有4個(gè)函數(shù)f15-f18比BOA、SCA、SSA、GWO和CS算法的平均計(jì)算結(jié)果稍差且差別較小以外,另外7個(gè)函數(shù)的平均計(jì)算結(jié)果精度高出比較算法十幾個(gè)數(shù)量級。尤其值得一提的是Rosenbrock函數(shù)，該函數(shù)理論最優(yōu)值位于一個(gè)平滑、狹長的拋物線形山谷中，由于函數(shù)為優(yōu)化算法提供的信息非常有限，使得眾多算法求解其最優(yōu)值變得十分困難，如BOA、SCA、SSA、GWO和CS算法求解的平均值從個(gè)位數(shù)到百位數(shù)不等，而SCABOA算法求解的平均值竟達(dá)到1×10-16，與理論最優(yōu)值更為接近?？梢姡倪M(jìn)的SCABOA算法計(jì)算精度更高。

為直觀展示SCABOA的收斂速度和尋優(yōu)精度，給出部分函數(shù)前100代的收斂曲線圖。從圖2-7可知，SCABOA收斂曲線位于圖形最下方，收斂速度最快,且計(jì)算精度最高。

圖2 f4函數(shù)收斂曲線

與高文欣等[10,14]的改進(jìn)蝴蝶優(yōu)化算法進(jìn)行比較，其測試函數(shù)部分與本文相同，求解結(jié)果相同部分未列出(具體數(shù)據(jù)可參考文獻(xiàn))，挑選求解結(jié)果不同的函數(shù)進(jìn)行比較。如高文欣等[10]的f4即本文中的f12，高文欣等[10]求解的平均值精度僅為10-7，而本文算法求解的平均精度高達(dá)10-19，高出12個(gè)數(shù)量級;如高文欣等[14]使用的f2即本文中的f2，高文欣等[14]求解的平均值精度僅為1.36e-81，而本文算法求解的平均精度達(dá)到理論值。再與王依柔等[11]的算法(SIBOA)進(jìn)行比較，由于本文中19個(gè)測試函數(shù)全部包含王依柔等[11]使用的測試函數(shù)，故將其結(jié)果列于表2，王依柔等[11]使用的種群規(guī)模為40，最大迭代次數(shù)為1 000。比較結(jié)果：函數(shù)f9-f11的計(jì)算結(jié)果相同，f7的計(jì)算結(jié)果略次于王依柔等[11]，函數(shù)f1-f4均優(yōu)于王依柔等[11]；本文算法在種群規(guī)模為30和最大迭代次數(shù)為500的情況下，總體效果依然優(yōu)于王依柔等[11]的算法，可見本文算法的優(yōu)越性。

圖3 f5函數(shù)收斂曲線

圖4 f6函數(shù)收斂曲線

圖5 f8函數(shù)收斂曲線

圖6 f9函數(shù)收斂曲線

圖7 f10函數(shù)收斂曲線

4 結(jié)束語

本文在BOA基礎(chǔ)之上引入非線性自適應(yīng)因子、重新定義香味濃度計(jì)算公式，嵌入正弦余弦算法，提出一種融合正弦余弦算法的改進(jìn)蝴蝶優(yōu)化算法(SCABOA)。比較實(shí)驗(yàn)結(jié)果可知，SCABOA算法性能表現(xiàn)優(yōu)越，這與文章第2部分的改進(jìn)策略分析相吻合：①通過在自身認(rèn)知部分引入非線性自適應(yīng)因子，使得算法迭代初期在較寬范圍內(nèi)搜索，而迭代后期在較窄范圍搜索；②設(shè)計(jì)變化范圍較寬和斜率變化較大的香味濃度計(jì)算公式；③在后半個(gè)種群中利用正弦余弦算法替換基本BOA的隨機(jī)搜索，使得算法搜索更具有目標(biāo)性。這3種策略的合力結(jié)果使得SCABOA算法具有更好的全局搜索和局部搜索能力。