基于余弦相似度的改進(jìn)蝴蝶優(yōu)化算法

陳 俊，何 慶

（貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴陽 550025）

（*通信作者電子郵箱qhe@gzu.edu.cn.）

0 引言

近些年，許多學(xué)者受到自然界動(dòng)物習(xí)性的啟發(fā)，對自然界生物種群所表現(xiàn)出群體性行為進(jìn)行總結(jié)，設(shè)計(jì)出一類具有分布式智能行為的算法（群智能優(yōu)化算法）。這類優(yōu)化算法對目標(biāo)函數(shù)性質(zhì)要求低、容易實(shí)現(xiàn)、穩(wěn)定性好，自提出以來就受到電力系統(tǒng)、工程設(shè)計(jì)，網(wǎng)絡(luò)以及通信等領(lǐng)域的廣泛關(guān)注。

常見的群智能優(yōu)化算法有：模擬果蠅靠嗅覺定位食物方向行為提出的果蠅優(yōu)化算法（Fruit fly Optimization Algorithm，F(xiàn)OA）［1］；模擬布谷鳥寄生育繁殖行為和萊維飛行搜索機(jī)制的布谷鳥搜索（Cuckoo Search，CS）算法［2］；通過模擬鯨魚隨機(jī)搜索撲食，氣泡攻擊，收縮包圍行為的鯨魚優(yōu)化算法（Whale Optimization Algorithm，WOA）［3］等。

2017 年，Arora 等［4］受到蝴蝶覓食行為的啟發(fā)，提出了蝴蝶優(yōu)化算法（Butterfly Optimization Algorithm，BOA）。蝴蝶個(gè)體通過感知和分析空氣中氣味確定食物的潛在方向，進(jìn)行合作式的移動(dòng)。相較于其他的群智能優(yōu)化算法，蝴蝶優(yōu)化算法具有結(jié)構(gòu)簡單、控制參數(shù)少以及算法易實(shí)現(xiàn)的特點(diǎn)，在工程上得到廣泛的應(yīng)用。例如張達(dá)敏等［5］將改進(jìn)的蝴蝶優(yōu)化算法應(yīng)用于認(rèn)知智能電網(wǎng)中的能效優(yōu)化頻譜分配上；Wen 等［6］提出一種增強(qiáng)的蝴蝶優(yōu)化算法，并將改進(jìn)的蝴蝶優(yōu)化算法應(yīng)用于支持向量機(jī)參數(shù)優(yōu)化上，最后還預(yù)測了長三角地區(qū)住宅的二氧化碳年排放量；Malisetti 等［7］提出一種基于對抗的蝴蝶優(yōu)化算法，并應(yīng)用于無線傳感器的方案選擇，延長了無線傳感器網(wǎng)絡(luò)的使用壽命。與其他群智能優(yōu)化相比，雖然蝴蝶優(yōu)化算法在設(shè)計(jì)上具有優(yōu)越性，但是該算法依舊存在尋優(yōu)精度低、收斂性差以及易受到局部極值影響的問題。

針對以上問題，許多學(xué)者對蝴蝶優(yōu)化算法進(jìn)行改進(jìn)，Arora 等［8］提出了一種基于萊維飛行策略的蝴蝶優(yōu)化算法，在全局和局部位置上引入萊維函數(shù)，增強(qiáng)了算法種群的多樣性。Arora 等［9］還提出了一種基于學(xué)習(xí)自動(dòng)機(jī)的蝴蝶優(yōu)化算法，通過引入學(xué)習(xí)自動(dòng)機(jī)策略，提高了全局階段的搜索速度。王依柔等［10］提出了基于自適應(yīng)擾動(dòng)的瘋狂蝴蝶算法，在全局搜索階段引入自適應(yīng)慣性權(quán)重和擾動(dòng)策略，避免蝴蝶優(yōu)化算法易陷入局部最優(yōu)的同時(shí)平衡了算法的局部開發(fā)和全局探索能力，最后還在花蜜位置上引入瘋狂因子，增強(qiáng)了蝴蝶種群的多樣性。高文欣等［11］提出柯西變異和自適應(yīng)權(quán)重優(yōu)化的蝴蝶算法，通過在全局位置更新上引入柯西分布函數(shù)對蝴蝶個(gè)體進(jìn)行變異，解決了算法容易陷入局部最優(yōu)的問題，其次在局部開發(fā)位置更新處引入自適應(yīng)慣性權(quán)重，加強(qiáng)了蝴蝶算法的局部開發(fā)能力；最后還引入了動(dòng)態(tài)轉(zhuǎn)換概率來平衡算法的全局探索和局部開發(fā)的比重。謝聰?shù)龋?2］通過參數(shù)優(yōu)化和差分進(jìn)化兩個(gè)角度提升了算法性能，首先針對蝴蝶優(yōu)化算法內(nèi)感知強(qiáng)度參數(shù)和感覺因子進(jìn)行微調(diào)，優(yōu)化了算法內(nèi)參數(shù)；其次引入了差分進(jìn)化策略，加強(qiáng)了蝴蝶個(gè)體之間信息交流能力。高文欣等［13］提出了全局優(yōu)化的蝴蝶優(yōu)化算法，通過引入limit 閾值來限制蝴蝶優(yōu)化算法陷入局部最優(yōu)解的次數(shù)，解決蝴蝶優(yōu)化算法易陷入早熟的問題；其次融合了單純刑法策略，使得適應(yīng)度較差的蝴蝶個(gè)體也能較快靠近當(dāng)前最優(yōu)蝴蝶個(gè)體。上述改進(jìn)策略雖然在算法的種群多樣性上有一定程度的提升，但沒有解決算法在迭代中后期種群多樣性下降的問題；而且部分策略調(diào)整了蝴蝶優(yōu)化算法中全局探索和局部開發(fā)的轉(zhuǎn)換概率，并沒有充分利用蝴蝶個(gè)體信息動(dòng)態(tài)調(diào)整轉(zhuǎn)換概率。

針對上述的問題，本文提出了一種多策略改進(jìn)的蝴蝶優(yōu)化算法（Multi-Strategy improved BOA，MSBOA）。首先，提出了基于余弦相似度的位置更新策略，通過構(gòu)建當(dāng)前蝴蝶個(gè)體位置到最優(yōu)蝴蝶位置的向量，計(jì)算向量之間的余弦相似度，并設(shè)置閾值，更新余弦相似度超過閾值的蝴蝶個(gè)體，該策略能有效地保持了種群的多樣性；其次，根據(jù)蝴蝶個(gè)體的適應(yīng)度動(dòng)態(tài)調(diào)整轉(zhuǎn)換概率，使適應(yīng)度較差的個(gè)體有更大的概率受到最優(yōu)蝴蝶個(gè)體的引導(dǎo)，加快BOA 收斂；最后，在全局搜索階段加入自適應(yīng)混合慣性權(quán)重，根據(jù)蝴蝶個(gè)體自身適應(yīng)度動(dòng)態(tài)平衡當(dāng)前個(gè)體的局部開發(fā)與全局探索能力。通過對16 個(gè)典型的測試函數(shù)的求解、Wilcoxon 秩和檢驗(yàn)以及部分CEC2014 函數(shù)的求解驗(yàn)證了MSBOA的有效性和魯棒性。

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

蝴蝶優(yōu)化算法是Arora 等［4］通過觀察蝴蝶覓食和尋偶行為提出的一種新的群智能優(yōu)化算法。由于真實(shí)的蝴蝶覓食和尋偶行為有很多不確定的因素，無法在算法中體現(xiàn)出來，因此蝴蝶優(yōu)化算法建立在兩個(gè)理想化的條件下：1）假設(shè)每只蝴蝶都能產(chǎn)生不同程度的香味并且能嗅到來自不同方向的香味，使得蝴蝶個(gè)體之間能夠相互吸引。這種香味的強(qiáng)度與蝴蝶個(gè)體的適應(yīng)度有關(guān)，用于在蝴蝶迭代過程中分享自身的相關(guān)信息。2）每只蝴蝶都有一定的概率嗅到來自最優(yōu)蝴蝶個(gè)體的香味并朝向最優(yōu)蝴蝶位置方向移動(dòng)，該行為稱為全局探索。其中該概率在蝴蝶優(yōu)化算法中稱為轉(zhuǎn)換概率。若蝴蝶嗅不到來自最優(yōu)蝴蝶個(gè)體的香味，蝴蝶個(gè)體將隨機(jī)移動(dòng)，這一行為稱為局部開發(fā)。其中轉(zhuǎn)換概率P的大小受到風(fēng)雨雷電等各種情況的影響，全局探索和局部開發(fā)的轉(zhuǎn)換概率P值取固定值0.8。

蝴蝶產(chǎn)生香味強(qiáng)度大小表達(dá)式如下：

其中：f是香味的感知強(qiáng)度，即香味被其他蝴蝶感知的強(qiáng)度；I是刺激強(qiáng)度，取值大小與當(dāng)前個(gè)體適應(yīng)度有關(guān)；a取固定值0.1，通常參數(shù)a的取值取決于模態(tài)的功率指數(shù)。c是感覺因子，數(shù)學(xué)模型描述如式（2）所示：

其中：ct+1是t+1次迭代群體的感知因子；ct是t次迭代中的感知因子；b通常取固定值0.025；MaxIter是最大迭代次數(shù)。每一次迭代生成一個(gè)區(qū)間為［0，1］的隨機(jī)數(shù)與轉(zhuǎn)換概率P進(jìn)行比較，若隨機(jī)數(shù)小于轉(zhuǎn)換概率P，BOA 進(jìn)行全局搜索，反之進(jìn)行局部搜索。

全局搜索階段，蝴蝶朝向最優(yōu)蝴蝶位置移動(dòng)，數(shù)學(xué)模型如式（3）所示：

其中：是第t次迭代中第i只蝴蝶的解向量；r是區(qū)間［0，1］內(nèi)的隨機(jī)數(shù)；g*表示在當(dāng)前迭代的所有解中的最優(yōu)位置；fi表示第i只蝴蝶發(fā)出的香味強(qiáng)度。

在局部搜索階段，蝴蝶將隨機(jī)移動(dòng)，蝴蝶位置更新公式為：

2 本文算法MSBOA

根據(jù)BOA 的設(shè)計(jì)可知，每只蝴蝶個(gè)體都要受到當(dāng)前最優(yōu)蝴蝶個(gè)體的香味吸引進(jìn)行移動(dòng)。該機(jī)制雖然一定程度上矯正蝴蝶位置更新的方向，但是在迭代中后期，蝴蝶個(gè)體聚集到當(dāng)前最優(yōu)蝴蝶位置附近導(dǎo)致蝴蝶種群的多樣性會(huì)下降，若當(dāng)前最優(yōu)蝴蝶個(gè)體陷入局部最優(yōu)，聚集的蝴蝶種群很難跳出局部極值點(diǎn)。其次采用固定概率為0.8 的兩段式更新策略，使得大部分的蝴蝶個(gè)體圍繞著全局探索的更新方式，更多時(shí)候接收全局最優(yōu)位置信息。由于BOA 這兩個(gè)特征，使得在迭代后期種群的多樣性下降，甚至出現(xiàn)多個(gè)蝴蝶位置重疊的情況，從而導(dǎo)致BOA容易陷入局部最優(yōu)且收斂精度較低。

為了解決以上BOA 的問題，本文提出MSBOA。本文從3個(gè)方面對BOA 進(jìn)行改進(jìn)。首先是基于余弦相似度的蝴蝶位置更新策略，取當(dāng)前蝴蝶位置和當(dāng)前最優(yōu)蝴蝶位置構(gòu)建向量，依次計(jì)算向量之間的余弦相似度，并通過設(shè)置閾值C，將余弦相似度大于閾值的蝴蝶個(gè)體與當(dāng)前蝴蝶個(gè)體進(jìn)行適應(yīng)度比較，通過位置更新策略更新適應(yīng)度較差的蝴蝶個(gè)體，解決迭代后期算法種群多樣性下降的問題；其次通過適應(yīng)度動(dòng)態(tài)調(diào)整切換概率，使得適應(yīng)度較好的個(gè)體有更大的概率進(jìn)行全局引導(dǎo)；最后引入混合自適應(yīng)慣性權(quán)重策略，較大的權(quán)重能使BOA保持較好的全局探索能力，較小的慣性權(quán)重有助于BOA 局部開發(fā)，根據(jù)蝴蝶個(gè)體的自身適應(yīng)度以及迭代情況動(dòng)態(tài)平衡BOA搜索偏向。

2.1 基于余弦相似度位置更新策略

余弦相似度反映兩個(gè)向量方向一致性關(guān)系，取值范圍為［-1，1］，其中：1 表示兩個(gè)向量之間的夾角為0°，有重合部分；-1 表示兩個(gè)向量方向相反。由于BOA 的特點(diǎn)，在迭代中后期，蝴蝶移動(dòng)圍繞當(dāng)前最優(yōu)蝴蝶位置，甚至于移動(dòng)過程中出現(xiàn)重疊的現(xiàn)象，很難保持種群多樣性。本文引入余弦相似度衡量最優(yōu)蝴蝶位置與周圍蝴蝶的分布情況，通過構(gòu)造當(dāng)前蝴蝶個(gè)體位置和最優(yōu)個(gè)體之間的向量，采用余弦相似度作為分布情況的指標(biāo)，更新余弦相似度較高且適應(yīng)度較差的蝴蝶個(gè)體位置，既提高算法收斂的速度，又保持了種群的多樣性。策略具體細(xì)節(jié)如下：

首先構(gòu)建a、b向量：

其中：表示在第t次迭代中第i只蝴蝶的個(gè)體，即當(dāng)前蝴蝶位置；表示第t次迭代其他蝴蝶個(gè)體中的一個(gè)；g*屬于第t代中的最優(yōu)蝴蝶個(gè)體的位置。

定義cos（ja，b）為兩個(gè)向量之間的相似度，取值范圍為［-1，1］，個(gè)體位置之間相似度計(jì)算公式為：

其中：分子為向量a、b的內(nèi)積，分母分別為向量a、b的模的積。余弦相似度越高，代表蝴蝶個(gè)體和越容易在方向上重合。將當(dāng)前蝴蝶位置i與其他蝴蝶位置j依次計(jì)算余弦相似度，并設(shè)置閾值C，將與當(dāng)前蝴蝶位置余弦相似度較高的蝴蝶進(jìn)行篩選，經(jīng)多次調(diào)試，當(dāng)C取0.5 時(shí)，算法性能達(dá)到最優(yōu)。通過比較當(dāng)前蝴蝶個(gè)體與篩選后個(gè)體的適應(yīng)度，將適應(yīng)度較差的個(gè)體引入狀態(tài)轉(zhuǎn)移算法中的旋轉(zhuǎn)變換算子或伸縮變換算子［14］進(jìn)行位置更新，并保留適應(yīng)度較好的蝴蝶個(gè)體位置，位置更新公式如下：

2.2 根據(jù)適應(yīng)度動(dòng)態(tài)調(diào)整轉(zhuǎn)換概率策略

在基本的BOA 中，切換概率P，使用固定的常數(shù)來調(diào)整BOA的局部開發(fā)和全局探索。本文采用文獻(xiàn)［15］提出的自適應(yīng)機(jī)制來描述切換概率，并且作了改進(jìn)。如式（8）所示：

2.3 自適應(yīng)混合慣性權(quán)重

本文還在全局搜索階段當(dāng)前個(gè)體的位置更新式（3）中引入動(dòng)態(tài)慣性權(quán)重w來影響更新蝴蝶的位置，慣性權(quán)重較大或者較小都有可能引起B(yǎng)OA 陷入局部最優(yōu)，從而影響B(tài)OA 的效率。為了協(xié)調(diào)BOA 的全局和局部搜索能力，本文提出了自適應(yīng)混合慣性權(quán)重：

其中：K為是調(diào)整過的sigmoid函數(shù)，該函數(shù)是神經(jīng)網(wǎng)絡(luò)中最常用的激活函數(shù)之一。該函數(shù)在線性和非線性之間展現(xiàn)出極好的平衡性，擁有平滑的上界域和下邊界域。在迭代前期參數(shù)K能保持較大值，保持蝴蝶優(yōu)化算法在迭代初期階段的全局搜索強(qiáng)度；并且前期K值伸縮的范圍較大，更好地保留了BOA的多樣性。中期K值隨著迭代次數(shù)的增加而減少，從而加快BOA 的收斂。在迭代后期的一段保持一個(gè)較小的權(quán)重，延長了迭代后期的局部搜索時(shí)間，更有利于進(jìn)行局部搜索，更新后的全局階段搜索過程為：

權(quán)重引入了式（9）的一部分，其目的在于控制最優(yōu)蝴蝶位置對新的蝴蝶位置的影響程度，參數(shù)β為影響程度因子。蝴蝶個(gè)體適應(yīng)度接近當(dāng)前最好的適應(yīng)度時(shí)，其權(quán)重接近最小值，較小的權(quán)重有利于進(jìn)行局部開發(fā)；反之當(dāng)前個(gè)體的適應(yīng)度與最好的適應(yīng)度相差較大時(shí)，其權(quán)重接近最大值，保留當(dāng)前個(gè)體的更多信息，下一次迭代保持較強(qiáng)的全局搜索能力。

2.4 MSBOA步驟

MSBOA的基本流程如下：

Step1 初始化。初始化MSBOA 參數(shù)，隨機(jī)生成種群位置，計(jì)算適應(yīng)度并擇優(yōu)保存。

Step2 蝴蝶位置更新階段。根據(jù)式（5）構(gòu)建向量，并根據(jù)式（6）計(jì)算蝴蝶個(gè)體位置的余弦相似度，設(shè)置閾值C將相似度高于閾值的蝴蝶位置通過式（7）進(jìn)行位置更新。

Step3 計(jì)算當(dāng)前個(gè)體適應(yīng)度，并根據(jù)式（8）計(jì)算P值，判斷當(dāng)前迭代當(dāng)前個(gè)體是進(jìn)行全局搜索還是局部搜索，并通過式（10）計(jì)算當(dāng)前個(gè)體的自適應(yīng)慣性權(quán)重，對應(yīng)蝴蝶位置的更新式（11）或式（4）。

Step4 計(jì)算位置更新后每只蝴蝶所在位置適應(yīng)度，并且更新最優(yōu)位置。

Step5 重復(fù)Step2～4 的更新迭代過程，若達(dá)到設(shè)置收斂精度要求或規(guī)定的最大迭代次數(shù)，終止MSBOA 并輸出最優(yōu)解。

MSBOA流程如圖1所示。

圖1 MSBOA流程Fig.1 MSBOA flowchart

2.5 MSBOA的時(shí)間復(fù)雜度分析

時(shí)間復(fù)雜度是體現(xiàn)算法的性能的關(guān)鍵因素，反映了算法的運(yùn)行效率。通過閱讀文獻(xiàn)［16］和文獻(xiàn)［13］對混合柯西變異和均勻分布的蝗蟲優(yōu)化算法和全局優(yōu)化的蝴蝶優(yōu)化算法（Simplex Method Sine-Cosine Algorithm Butterfly Optimization Algorithm，SMSCABOA）的時(shí)間復(fù)雜度進(jìn)行了分析方式。本文擬采用了類似的方式對MSBOA進(jìn)行時(shí)間復(fù)雜度分析。

在基本的BOA 中，假設(shè)種群的規(guī)模為N，空間維度為n，最大迭代的次數(shù)為MaxIter，計(jì)算適應(yīng)度函數(shù)時(shí)間復(fù)雜度為（fn）。根據(jù)算法時(shí)間復(fù)雜度（O）的計(jì)算規(guī)則。則有：

1）種群初始化階段，假設(shè)參數(shù)初始化所需要的時(shí)間為x1，初始化一個(gè)個(gè)體位置需要的時(shí)間為x2，則產(chǎn)生隨機(jī)初始化種群位置的時(shí)間復(fù)雜度為O（x1+x2×N×n）=O（N×n）。

2）找到當(dāng)前最優(yōu)蝴蝶位置的時(shí)間復(fù)雜度為O（N×（fn）），此時(shí)的時(shí)間復(fù)雜度為O（N×n+N×（fn））。

3）基于余弦相似度位置更新策略的時(shí)間復(fù)雜度計(jì)算分為兩個(gè)部分，分別是計(jì)算蝴蝶個(gè)體之間的余弦相似度和位置更新算子的時(shí)間復(fù)雜度。其中構(gòu)建向量部分需要的時(shí)間復(fù)雜度為O（N×n）；計(jì)算蝴蝶個(gè)體之間的余弦相似度需要的時(shí)間復(fù)雜度為O（（N-1）×n）=O（N×n）；進(jìn)行位置更新的時(shí)間復(fù)雜度最大也是O（N）級(jí)別的時(shí)間復(fù)雜度。則該部分的時(shí)間復(fù)雜度為O（N×n）。

4）根據(jù)適應(yīng)度動(dòng)態(tài)調(diào)整轉(zhuǎn)換概率策略，對單個(gè)體在一次迭代中增加的時(shí)間復(fù)雜度為O（1+（fn））=O（（fn））。

5）在自適應(yīng)混合權(quán)重階段，參數(shù)大多數(shù)是繼承目前已存在的，在原本基礎(chǔ)上對個(gè)體增加的時(shí)間復(fù)雜度也是O（1）級(jí)別。

第2）～5）階段均是單個(gè)個(gè)體在一次迭代中產(chǎn)生的時(shí)間復(fù)雜度。當(dāng)以N個(gè)體進(jìn)行MaxIter次迭代時(shí)，MSBOA 在2）至5）階段的時(shí)間復(fù)雜度為O（MaxIter×N×（fn）×n）。

綜上，MSBOA 的總的時(shí)間復(fù)雜度為O（N×（fn）+MaxIter×N×N×n）=O（MaxIter×N×N×n）。MSBOA 與BOA 在時(shí)間復(fù)雜度上相比，MSBOA 在基于余弦相似度位置更新策略上增加了時(shí)間復(fù)雜度，相當(dāng)于在算法內(nèi)層加了循環(huán)。

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

為了全面的驗(yàn)證MSBOA 的性能以及3 個(gè)改進(jìn)策略的有效性，本文的驗(yàn)證實(shí)驗(yàn)分為以下4個(gè)部分進(jìn)行：

1）將MSBOA 與僅采用基于余弦相似度位置更新策略的蝴蝶優(yōu)化算法BOA1、僅采用結(jié)合動(dòng)態(tài)調(diào)整概率策略的蝴蝶優(yōu)化算法BOA2、僅采用自適應(yīng)混合慣性權(quán)重的蝴蝶優(yōu)化算法BOA3 以及基本的蝴蝶優(yōu)化算法BOA 進(jìn)行比較，來驗(yàn)證不同改進(jìn)策略的有效性；并將改進(jìn)算法與PSO、SSA 進(jìn)行收斂性分析，驗(yàn)證MSBOA的優(yōu)越性。

2）將MSBOA 與向量粒子群優(yōu)化（Phasor Particle Swarm Optimization，PPSO）算法［17］、改進(jìn)的灰狼優(yōu)化（Improved Grey Wolf Optimization，IGWO）算法［18］、基于對數(shù)慣性權(quán)重和高斯差分變異的鯨群優(yōu)化算法（Whale Optimization Algorithm based on logarithmic Inertia weight and Gaussian difference mutation，IGWOA）［19］、優(yōu)選策略的自適應(yīng)蟻獅優(yōu)化（Preferred Strategy self-adaptive Ant Lion Optimizer，PSALO）算法［20］、基于折射反向?qū)W習(xí)與自適應(yīng)控制因子的改進(jìn)樽海鞘群算法（modified Salp Swarm Algorithm based on Refracted oppositional learning and adaptive Control factor，RCSSA）［21］進(jìn)行比較，驗(yàn)證MSBOA的優(yōu)越性。

3）通過Wilcoxon 秩和檢驗(yàn)驗(yàn)證MSBOA 和其他算法之間的顯著性差異。

4）在CEC2014 基準(zhǔn)函數(shù)中選取部分單峰和多峰，混合和復(fù)合類型的函數(shù)進(jìn)行優(yōu)化測試，再次驗(yàn)證MSBOA的有效性和魯棒性。

實(shí)驗(yàn)引入16 個(gè)基準(zhǔn)測試函數(shù)，分為三類：第一類為單峰基準(zhǔn)測試函數(shù)，表1 中F1～F6 所示；第二類為多峰基準(zhǔn)測試函數(shù)，如表1 中的F7～F10 所示；第三類為固定維度的多峰基準(zhǔn)測試函數(shù)，如表1中的F11～F16所示。

表1 基準(zhǔn)測試函數(shù)Tab.1 Benchmark test functions

算法的基本參數(shù)：種群規(guī)模為30，空間維度為30、100、500，MaxIter=500。算法內(nèi)的參數(shù)如表2所示。

表2 算法參數(shù)設(shè)置Tab.2 Algorithm parameter setting

3.1 改進(jìn)策略有效性分析

將基本BOA 與BOA1、BOA2、BOA3、MSBOA 在空間維度為30 的條件下對16 個(gè)函數(shù)進(jìn)行求解并通過均值以及標(biāo)準(zhǔn)差評估仿真結(jié)果，獨(dú)立運(yùn)算30次數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，如表3～4所示。首先，表3和表4中的平均值可以反映算法的收斂精度和尋優(yōu)能力，而標(biāo)準(zhǔn)差可以反映算法的魯棒性。具體來說，對于單峰值函數(shù)F1～F4、F6、F7，以及多峰值函數(shù)F9～F11、F13～F16，MSBOA 均可以尋找到理論最優(yōu)值，且標(biāo)準(zhǔn)差最小；對于函數(shù)F5、F8、F12，雖然沒有尋到理論最優(yōu)，但是對于函數(shù)F5、F8、F12，無論是平均搜索精度還是穩(wěn)定性上，MSBOA均體現(xiàn)出明顯的優(yōu)勢。在固定維度函數(shù)上，MSBOA 的尋優(yōu)化精度和穩(wěn)定性也明顯好于BOA。單從3 個(gè)改進(jìn)策略上來看，BOA1和BOA3對函數(shù)F1～F4以及F5～F15改進(jìn)效果明顯。從評價(jià)指標(biāo)上可以看出BOA1 在無論在單峰函數(shù)還是多峰值函數(shù)上尋優(yōu)精度與MSBOA效果持平，這和引入的基于余弦相似度更新策略密切相關(guān)，該策略有效地提高了BOA 的尋優(yōu)能力。BOA2對函數(shù)的尋優(yōu)精度提升幅度不大，在3個(gè)改進(jìn)策略里面相對最差。其中對于F2函數(shù)，BOA2收斂精度雖然不及BOA，但穩(wěn)定性上優(yōu)于BOA。BOA3 在函數(shù)F7、F9 上均能尋到理論最優(yōu)值，該策略整體效果優(yōu)于BOA。綜合表3 中標(biāo)準(zhǔn)差以及均值上表現(xiàn)，3 個(gè)改進(jìn)策略都在一定程度上提升了BOA 的性能，且融合3 個(gè)改進(jìn)策略的MSBOA 表現(xiàn)出更高的尋優(yōu)精度以及算法穩(wěn)定性。

表4 固定維度多峰基準(zhǔn)測試函數(shù)測試結(jié)果Tab.4 Test results of multimodal benchmark test functions in fixed dimension

圖2 給出了BOA、BOA1、BOA2、BOA3 以及MSBOA 的單峰和多峰值函數(shù)收斂曲線圖。如圖2 所示，由于MSBOA 收斂精度高，為方便觀察算法收斂情況，圖2 中縱坐標(biāo)表示為lg（適應(yīng)度值）。從圖2 可知，在單峰值函數(shù)和多峰值函數(shù)上，MSBOA 具有更高的收斂速度和尋優(yōu)精度。具體來說，對于F6、F7、F9、F10 函數(shù)，MSBOA 能在200 代能找到最優(yōu)值，體現(xiàn)出較強(qiáng)的優(yōu)化能力。從改進(jìn)策略上來看，BOA1 尋優(yōu)效果最好，其次是BOA3，BOA2 最差。BOA1 和BOA3 收斂曲線大部分位于BOA 收斂曲線的下方，且收斂較快，這說明引入基于余弦相似度位置更新策略，有效地保持了蝴蝶種群在搜索空間的多樣性，使得BOA1 在迭代前期收斂較快，且在多個(gè)函數(shù)上能找到最優(yōu)值。在迭代后期，MSBOA 在單峰函數(shù)的收斂速度比其他的算法要高，且精度和BOA1 保持一致，這與BOA2和BOA3 密切相關(guān)。對于多峰函數(shù)，BOA1 和MSBOA 在收斂速度上接近。總體來說，在基準(zhǔn)函數(shù)上，無論收斂速度還是尋優(yōu)精度上MSBOA都遠(yuǎn)遠(yuǎn)優(yōu)于BOA。

針對時(shí)間復(fù)雜度的問題，在1～200 維度上對F1～F10 函數(shù)進(jìn)行仿真實(shí)驗(yàn)。從如圖3 所示的實(shí)驗(yàn)結(jié)果來看，與BOA 運(yùn)行時(shí)間相比，改進(jìn)后算法耗時(shí)較長，耗時(shí)主要來自于基于余弦相似度位置更新策略。隨著維度的增加，在5 種算法的平均耗時(shí)上都增加，這是由于從低緯度到高緯度，搜索空間增大，搜索的難度也呈現(xiàn)指數(shù)增加。

圖3 基準(zhǔn)函數(shù)維度對應(yīng)平均耗時(shí)曲線Fig.3 Curve between benchmark function dimension and average time consumption

從表3～4和圖2～3可看出，對MSBOA在尋優(yōu)精度的表現(xiàn)，驗(yàn)證了有效性，不過耗時(shí)相較于BOA有所增加。

表3 單峰和多峰值基準(zhǔn)測試函數(shù)測試結(jié)果Tab.3 Test results of unimodal and multimodal benchmark test functions

圖2 基準(zhǔn)函數(shù)平均收斂曲線Fig.2 Benchmark function average convergence curve

3.2 與其他的群智能算法比較

將MSBOA 與PPSO、RCSSA、IGWO、IGWOA、PSALO 在100 維度的條件下進(jìn)行對比。對比數(shù)據(jù)直接引用文獻(xiàn)［17-21］，且MSBOA 內(nèi)參數(shù)與表2 保持一致，最大迭代次數(shù)和種群個(gè)數(shù)與對比算法保持一致。在100維度的條件下運(yùn)行50次取平均值的實(shí)驗(yàn)結(jié)果如表5所示。

表5 不同群智能算法在100維度下的結(jié)果比較Tab.5 Result comparison with different swarm intelligence algorithms in 100 dimensions

表5中的最優(yōu)值和平均值反映算法的尋優(yōu)能力。MSBOA對于給定的5 個(gè)單峰值函數(shù)，其中有4 個(gè)能找到理論最優(yōu)值，并且穩(wěn)定性優(yōu)于其他算法。MSBOA 對單峰函數(shù)F5 最優(yōu)值與其他對比算法相比在最優(yōu)值上相差一個(gè)數(shù)量級(jí)。在3 個(gè)多峰值函數(shù)，MSBOA在能找到兩個(gè)函數(shù)的理論最優(yōu)值。在求解F8時(shí)，MSBOA、IGWOA 以及RCSSA 尋優(yōu)精度持平，PSALO 次之，PPSO 效果最差；在平均值和標(biāo)準(zhǔn)差上，MSBOA 比其他算法的表現(xiàn)更好；在求解其他函數(shù)時(shí)，MSBOA 比其他的算法求解精度都要高且效果穩(wěn)定。

為了進(jìn)一步說明MSBOA 的有效性，在相同的實(shí)驗(yàn)環(huán)境下，將MSBOA 與其他改進(jìn)的BOA 進(jìn)行對比，引用CIBOA［10］、CWBOA［11］、SMSCSABOA［13］，以及SIBOA［22］數(shù)據(jù)，分別在30 維度、100 維度和500 維度上對8 個(gè)基準(zhǔn)函數(shù)進(jìn)行對比，如表6所示。

表6 不同群智能算法在不同維度下的結(jié)果比較Tab.6 Result comparison with different swarm intelligence algorithms in different dimensions

總體上CIBOA 以及CWBOA 尋優(yōu)結(jié)果較差，SMSCSABOA 和SIBOA 尋優(yōu)精度上相差不大，MSBOA 無論收斂精度還是穩(wěn)定性上均優(yōu)于其他4 種算法。具體來看，在30維度，CWBOA 在求解函數(shù)F1、F7 和F9 上能尋到理論最優(yōu)值，CIBOA 在求解F7 和F9 能尋找到理論最優(yōu)值，MSBOA 和SMSCSABOA 在其中給出的5 個(gè)函數(shù)上效果持平，其中MSBOA 能找到理論最優(yōu)值基準(zhǔn)函數(shù)有6個(gè)，在求解函數(shù)F5問題上，CWBOA 優(yōu)于其他算法，CIBOA 次之。橫向?qū)Ρ龋?00維度上，MSBOA 保持較高的尋優(yōu)精度以及穩(wěn)定性，其中有6個(gè)基準(zhǔn)函數(shù)（F1、F2、F3、F4、F7 和F9）找到理論最優(yōu)值；即便在500 維度下，MSBOA 也有4 個(gè)函數(shù)（F1、F3、F7 和F9）能找到理論最優(yōu)值，且在函數(shù)F2、F4 和F5 的尋優(yōu)上，求解精度和穩(wěn)定性優(yōu)于CWBOA 和SMSCSABOA。在函數(shù)F6 上，MSBOA 的尋優(yōu)精度以及穩(wěn)定性與其他算法持平。綜上可知，對于以上基本測試函數(shù)，MSBOA 都有較優(yōu)的穩(wěn)定性以及尋優(yōu)能力，能有效地解決BOA求解精度不高的問題。

3.3 Wilcoxon秩和檢驗(yàn)

在文獻(xiàn)［23］中提出，對于改進(jìn)的算法，需要進(jìn)行統(tǒng)計(jì)檢驗(yàn)來驗(yàn)證改進(jìn)算法在特定問題是否與現(xiàn)有的算法有顯著改進(jìn)。為了判斷MSBOA 的每次尋優(yōu)結(jié)果是否在統(tǒng)計(jì)上與其他算法的最佳結(jié)果顯著不同，Wilcoxon 秩和檢驗(yàn)統(tǒng)計(jì)檢驗(yàn)在5%的顯著性水平下進(jìn)行：當(dāng)p值小于5%（即5.00E-02）時(shí)，“R”為“+”，即拒絕H0 假設(shè)，說明兩種算法的差異性顯著；否則就是接受H0 假設(shè)，說明兩種算法在整體上是相同的。表7 給出了在10個(gè)基準(zhǔn)測試函數(shù)下，MSBOA 對BOA、BOA1、BOA2、BOA3 以及樽海鞘算法（Salp Swarm Algorithm，SSA）和粒子群優(yōu)化（Particle Swarm Optimization，PSO）共計(jì)6種算法的秩和檢驗(yàn)p值。從表7 中可以觀察到大部分的p值是小于5%，因此總體上說明MSBOA與其他的6種算法之間差異性顯著更優(yōu)。

表7 基準(zhǔn)測試函數(shù)的Wilcoxon 秩和檢驗(yàn)p值Tab.7 p-value for Wilcoxon rank-sum test on benchmark test functions

3.4 CEC2014基準(zhǔn)函數(shù)上進(jìn)行測試

為再次驗(yàn)證MSBOA的有效性和魯棒性，在CEC2014單目標(biāo)優(yōu)化函數(shù)中選取部分單峰函數(shù)（Unimodal Function，UN）、多峰函數(shù)（Multimodal Function，MF）、混合函數(shù)（Hybrid Function，HF）和復(fù)合函數(shù)（Composition Function，CF）進(jìn)行優(yōu)化求解，對選取的部分函數(shù)總結(jié)如表8 所示，該實(shí)驗(yàn)在最大迭代次數(shù)上設(shè)置為1 000，算法的其他參數(shù)設(shè)置與表2保持一致。

CEC2014 函數(shù)因?yàn)榫哂袕?fù)雜的特征，常用來驗(yàn)證算法的魯棒性，將MSBOA 與BOA1、BOA2、BOA3、PSO、SSA、WOA 進(jìn)行比較，部分CEC2014函數(shù)獨(dú)立運(yùn)行30次后取平均值的結(jié)果如表9 所示。MSBOA 在其中7 個(gè)函數(shù)上的表現(xiàn)優(yōu)于BOA，說明本文提出的改進(jìn)策略有效。其次對于CEC05、CEC12、CEC13、CEC16 測試函數(shù)，MSBOA 基本收斂到最優(yōu)值的附近，表現(xiàn)出較強(qiáng)的尋優(yōu)能力。對于CEC05，MSBOA 的尋優(yōu)精度略低于SSA，但是MSBOA 的標(biāo)準(zhǔn)差優(yōu)于SSA 和WOA，表現(xiàn)出較強(qiáng)的穩(wěn)定性。對于較復(fù)雜的復(fù)合型特征函數(shù)CEC26，MSBOA同樣展現(xiàn)出較強(qiáng)的尋優(yōu)能力，其尋優(yōu)精度僅略低于WOA。綜上所述，本文提出的MSBOA 在CEC2014 函數(shù)上，同樣表現(xiàn)出較強(qiáng)的尋優(yōu)能力。與主流算法相比，MSBOA 的尋優(yōu)精度和尋優(yōu)穩(wěn)定性上表現(xiàn)出較強(qiáng)的競爭能力，同時(shí)再次驗(yàn)證MSBOA的有效性和魯棒性。

表9 CEC2014函數(shù)的優(yōu)化結(jié)果比較Tab.9 Comparison of optimization results of CEC2014 functions

4 結(jié)語

為了改善BOA 容易陷入局部最優(yōu)和收斂性差等問題，受余弦相似度的啟發(fā)，本文提出了基于余弦相似度的位置更新策略，通過設(shè)置閾值，將相似度大的蝴蝶個(gè)體位置進(jìn)行更新，并且融合旋轉(zhuǎn)算子和伸縮變換算子，有效增加了全局探索能力；在此基礎(chǔ)上，對BOA 引入了動(dòng)態(tài)轉(zhuǎn)換概率，更好地平衡了全局探索和局部開發(fā)；最后引入混合的自適應(yīng)慣性權(quán)重，加快了BOA 收斂。四組實(shí)驗(yàn)顯示，MSBOA 在基準(zhǔn)的函數(shù)上求解的結(jié)果優(yōu)于BOA，其次與CWBOA、CIBOA、SMSCSABOA、SIBOA 相比，MSBOA 具有很強(qiáng)的競爭能力。通過Wilcoxon 秩和檢驗(yàn)，顯示本文算法更優(yōu)的顯著性差異性；最后通過對CEC2014 部分函數(shù)的求解結(jié)果在次驗(yàn)證了本文提出的MSBOA 的有效性。在后續(xù)的研究中，可以考慮將MSBOA 應(yīng)用到改進(jìn)機(jī)器學(xué)習(xí)參數(shù)優(yōu)化的問題上，進(jìn)一步驗(yàn)證MSBOA的性能。