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

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

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

0 引言

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

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

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

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

fi=cIa，

(1)

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

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

(2)

當蝴蝶未能感知周圍香味時便隨機移動，此階段稱為局部搜索，其計算公式如下：

(3)

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

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

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

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

(4)

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

2.2 更改香味濃度計算表達式

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

圖1 香味濃度fi變化曲線

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

b=2-2×t/Ngen。

(5)

fi=2×b×r-b，

(6)

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

(7)

2.3 正弦余弦算法指引機制

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

(8)

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

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

(9)

2.4 SCABOA的偽代碼

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

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

②Whilet

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

④Fori=1∶n

⑤計算式(6)

⑥Ifi≤n/2

⑦執(zhí)行式(7)

⑧Else

⑨Forj=1∶dim

⑩執(zhí)行式(9)

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

3 仿真實驗與結(jié)果

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

表1 基準函數(shù)

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

表2 基準函數(shù)的實驗結(jié)果

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

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

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

與高文欣等[10,14]的改進蝴蝶優(yōu)化算法進行比較，其測試函數(shù)部分與本文相同，求解結(jié)果相同部分未列出(具體數(shù)據(jù)可參考文獻)，挑選求解結(jié)果不同的函數(shù)進行比較。如高文欣等[10]的f4即本文中的f12，高文欣等[10]求解的平均值精度僅為10-7，而本文算法求解的平均精度高達10-19，高出12個數(shù)量級;如高文欣等[14]使用的f2即本文中的f2，高文欣等[14]求解的平均值精度僅為1.36e-81，而本文算法求解的平均精度達到理論值。再與王依柔等[11]的算法(SIBOA)進行比較，由于本文中19個測試函數(shù)全部包含王依柔等[11]使用的測試函數(shù)，故將其結(jié)果列于表2，王依柔等[11]使用的種群規(guī)模為40，最大迭代次數(shù)為1 000。比較結(jié)果：函數(shù)f9-f11的計算結(jié)果相同，f7的計算結(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)因子、重新定義香味濃度計算公式，嵌入正弦余弦算法，提出一種融合正弦余弦算法的改進蝴蝶優(yōu)化算法(SCABOA)。比較實驗結(jié)果可知，SCABOA算法性能表現(xiàn)優(yōu)越，這與文章第2部分的改進策略分析相吻合：①通過在自身認知部分引入非線性自適應(yīng)因子，使得算法迭代初期在較寬范圍內(nèi)搜索，而迭代后期在較窄范圍搜索；②設(shè)計變化范圍較寬和斜率變化較大的香味濃度計算公式；③在后半個種群中利用正弦余弦算法替換基本BOA的隨機搜索，使得算法搜索更具有目標性。這3種策略的合力結(jié)果使得SCABOA算法具有更好的全局搜索和局部搜索能力。