分段權重和變異反向學習的蝴蝶優化算法

李守玉，何 慶，杜逆索

1.貴州大學 大數據與信息工程學院，貴陽550025

2.貴州大學 貴州省大數據產業發展應用研究院，貴陽550025

蝴蝶優化算法（Butterfly Optimization Algorithm，BOA）[1]是由Arora和Singh兩位學者于2019年提出的一種基于全局優化的新型蝴蝶算法。盡管BOA算法提出的時間短，但其展現出的優勢不僅與較成熟的粒子群算法（Particle Swarm Optimization，PSO）[2]、遺傳算法（Genetic Algorithm，GA）[3]有一定可比性，與新型的元啟發式算法，如樽海鞘算法（Slap Swarm Algorithm，SSA）[4]、鯨魚算法（Whale Optimization Algorithm，WOA）[5]、正弦余弦算法（Sine Cosine Algorithm，SCA）[6]及蟻獅算法（Ant Lion Optimizer，ALO）[7]也具有可比性。同時，蝴蝶優化算法也被應用于一些工程領域。

BOA算法根據仿生學原理得來，其原理簡單，參數少，易于實現，但也存在尋優精度低、收斂速度慢以及易陷入局部最優等問題。因此，許多學者不斷對BOA 算法進行改進。文獻[8]在BOA 算法的基礎上，引入學習自動機，通過矯正蝴蝶的行為來提高平衡全局搜索和局部搜索的能力。文獻[9]引入混沌映射來提高算法的收斂速度和跳出局部最優的能力，但其尋優精度依然不高。文獻[10]提出一種自適應的蝶形優化算法，通過改變感官模態的方式獲得比原始算法更好的效果。文獻[11]通過將BOA 和ABC 兩種算法的優點結合使用來達到探索與開發平衡的目的。文獻[12]將交叉熵方法引入到BOA 算法中，利用協同進化技術增強算法的全局搜索能力，避免算法陷入局部最優。盡管對BOA 的尋優能力有所提升，但在平衡全局搜索和局部搜索能力、容易陷入局部最優、收斂速度慢等方面仍需要大量的深入研究。

本文針對BOA 算法所存在的問題進行改進，提出了分段權重和變異反向學習的蝴蝶優化算法（Piecewise Weight and Mutation opposition-based learning Butterfly Optimization Algorithm，PWMBOA）。首先，為了降低蝴蝶盲目跟隨飛行，采用飛行引領策略矯正蝴蝶自身飛行；其次，采用分段權重的思想增強算法的全局搜索和局部開發的能力；最后，對位置更新進行干擾，增加種群多樣性和提高收斂速度。通過實驗仿真來驗證所提算法的魯棒性和有效性，實驗結果表明PWMBOA算法不僅能提高尋優精度，也能加快算法的收斂速度。

1 蝴蝶算法

蝴蝶優化算法（BOA）的尋優原理如下：蝴蝶通過嗅覺感知空氣中其他蝴蝶所散發的香味強弱來矯正自身飛行路線，并向著食物源或尋找配偶移動，進而實現蝴蝶位置更新，通過建立適當的數學關系將蝴蝶個體映射為搜索空間的點；通過數學模型模擬蝴蝶個體之間的信息交互；尋找食物源或尋找配偶為尋優過程；蝴蝶位置為搜索空間中的解；蝴蝶位置不斷變化為尋找最優解的求解過程；蝴蝶所散發的香味為適應度。蝴蝶尋優過程中，考慮到香味受距離、風速、溫度、濕度等影響，當蝴蝶能從空氣中感知到其他蝴蝶散發的香味時，向香味最強的蝴蝶飛去，執行全局搜索；當不能感知到其他蝴蝶所散發的香味時，蝴蝶隨機飛行，執行局部搜索。因此用轉換概率P來控制蝴蝶在全局搜索和局部搜索之間進行切換。

BOA算法中，香味強度與適應度相關，當蝴蝶位置變化時，適應度也會隨之變化。香味是物理刺激強度的函數，公式如下：

其中，f為香味強弱；c是感覺模態；I是物理刺激強度；a是與模態有關的冪指數，它說明香味的吸收變化。a和c的取值范圍是（0，1）。

全局搜索，蝴蝶向最優解g*移動，公式如下：

局部搜索，公式如下：

算法1 BOA算法

2 基于自適應收斂的蝴蝶優化算法

2.1 飛行引領策略

BOA 算法中，蝴蝶是通過香味傳播構建的社會信息共享網絡來交互彼此信息用于尋找食物源。尋優過程中，蝴蝶個體具有盲目跟隨性，具體表現為蝴蝶個體之間信息交互頻率低，可能向某個局部最優個體所在方向飛行，導致算法陷入局部最優。針對BOA 算法存在蝴蝶個體盲目飛行的現象，利用當前蝴蝶與最優蝴蝶之間的香味強弱引領種群的尋優方向，進而增強種群跳出局部最優的能力。在種群尋優過程中，計算兩者之間適應度并比較適應度值大小，然后確定當前蝴蝶的飛行模式，即若當前蝴蝶個體適應度值小于最優蝴蝶適應度值，種群受當前蝴蝶吸引較大；反之，受最優蝴蝶影響較大，再利用約束引領蝴蝶個體的飛行方向，避免種群陷入局部最優。飛行引領策略數學表達式：

2.2 分段權重的位置更新策略

由BOA 算法的位置更新公式可知，蝴蝶的位置更新由蝴蝶之間信息交互以及食物源決定，因此，BOA具有較強的局部開發能力，但全局搜索的能力明顯不足，這也是導致BOA 尋優精度不高、收斂速度慢的主要原因。為了更好地改善BOA 存在的缺陷，提高算法的性能，本節采用分段的思想對算法進行處理。受文獻[13]的非線性分段平衡全局與局部搜索能力的啟發，蝴蝶個體的尋優能力與種群的尋優能力通過分段權重更好地結合，確保蝴蝶個體在種群空間中進行廣泛搜索，更好地克服BOA存在的缺點。具體改進如下：

搜索前半段，蝴蝶個體需要具備較強全局搜索的能力，確保算法能在搜索空間中進行廣泛尋優。因此，蝴蝶個體在下一次迭代中需要較大且穩定的權重進行全局尋優，采用指數與對數結合權重不僅保證權重變化范圍穩定，也能實現自適應調整，同時增強種群跳出局部最優和提高尋優精度的能力，公式如下：

搜索后半段，蝴蝶個體需要具備較強的局部搜索能力，才能保證種群進行更好的尋優。因此，蝴蝶個體需要一個穩定較小的權重幫助種群進行深度挖掘，采用指數型權重，隨著迭代的進行自適應調小權重，從而實現種群的深度挖掘，公式如下：

其中，c(t)為分段權重，a=1/2,γ是（0，1]的調節因子。搜索前半段c(t)的取值范圍是（0，1），搜索后半段c(t)取值范圍是[－1,1)。

最終的位置更新公式，全局搜索公式如下：

局部搜索如下：

2.3 變異反向學習

BOA 算法中，蝴蝶位置更新主要是每次迭代后的位置變化，重新計算位置的適應度，并與之前位置的適應度進行比較，擇優進入下一次迭代，沒有對蝴蝶位置進行干擾更新，導致算法迭代后期種群多樣性減少，進而使得算法陷入局部最優。因此，受GA中變異概率思想的啟發，結合反向學習策略對蝴蝶位置進行干擾更新，增加種群多樣性，避免算法陷入局部最優。

反向學習（Opposition-Based Learning，OBL）是Tizhoosh[14]于2005年提出的數學方法，其本質原理是通過估計和比較可行解及其反向解，選擇最好的解進入下一次迭代。

反向點定義：若p(x1,x1,…,xn)是n維坐標系中的一個點，x1,x1,…,xn∈?，同時滿足xi∈[ai,bi]，則反向點完全由坐標確定。

其中，R3是服從（0，1）均勻分布1×dim的隨機矩陣；b2是（0，1）之間的隨機數；pr是變異概率，范圍是（0.01，0.10），經測試pr=0.08 算法性能最好；lbi、ubi是搜索空間的下邊界和上邊界；代表第i只蝴蝶在dim維搜索空間中的位置，表示第i只經過變異反向學習得到新位置的蝴蝶。當b2≤pr時，通過隨機反向學習擴大算法的搜索范圍；當b2＞pr時，通過一般反向學習擴大搜索范圍，同時相對于固定的邊界，動態變化的lbi、ubi對于算法尋優更有利。

雖然變異反向學習策略產生的新解一定程度上增強算法跳出局部最優的能力，但是不能保證產生的新解一定優于原位置的解，因此經過變異反向學習之后，需要比較新舊位置的適應度大小，使用貪心策略將最好的位置進入下一次迭代。數學表達如下：

基于這種動態比較的策略可以促進算法向著目標位置方向進化，使得算法獲得更好的收斂速度。

2.4 PWMBOA算法

PWMBOA算法根據2.1～2.3節的改進策略，首先利用飛行引領策略加強蝴蝶個體之間的信息交互，矯正飛行方向，降低陷入局部最優的可能性；然后根據式（9）、（10）提高全局勘探和局部開采能力，更新蝴蝶位置；最后根據式（12）、（13）對蝴蝶位置進行擾動，豐富種群多樣性以及加快算法收斂。本文所提PWMBOA 算法步驟如算法2所示。

算法2 PWMBOA算法

2.5 時間復雜度分析

時間復雜度反映了算法的運行效率。若種群規模為N，優化問題維度為D，則標準BOA 的時間復雜度由參數初始化所需O(1)，計算函數適應度所需O(N)，迭代過程中種群復雜O(ND)構成，因此標準BOA總的時間復雜度為：

同理，PWMBOA 參數初始化和計算函數適應度同標準BOA一樣，迭代過程中，飛行引領階段所需O(ND)，分段權重階段所需O(ND)，變異反向學習階段所需O(ND)，因此PWMBOA總的時間復雜度為：

基于上述分析，PWMBOA 與標準BOA 相比，時間復雜度并未增加。兩種算法的時間復雜度主要由種群規模和優化問題的維度決定，由此可判定PWMBOA對最終的時間復雜度未產生負面影響。

四個標準分別賦予4、3、2、1的分值，一張問卷滿分為40分。家長與幼兒對該活動的評價總分為3192分，平均分為37.55分，在滿分為40分的情況下，家長與幼兒的總體評分很高。

3 仿真實驗與結果分析

實驗環境為Windows7，64位操作系統，CPU為Intel Core i5-6500H，主頻3.2 GHz，內存8 GB，算法基于MATLAB2014b，使用M語言編寫。

為了測試PWMBOA算法的魯棒性和有效性，引用9 個具有不同特征的基準測試函數，如表1 所示。為保證對比的公平性，算法基本參數設置相同：種群規模為30，測試函數維數30/50/200，最大迭代次數1 000。OBOA與PWMBOA的pr=0.08，其余改進的BOA與基本BOA保持一致。

表1 測試函數Table 1 Test functions

3.1 與基本BOA算法對比

在維數30的條件下，將PWMBOA與基本BOA在9個測試函數上進行求解，并讓每個算法獨立運行30次，同時用5個性能指標來評估實驗結果，如表2所示。

表2 PWMBOA與BOA結果對比Table 2 Comparison of results of PWMBOA and BOA

算法的尋優質量由最優值和最差值反映，從表2數據可知，對于F1～F3、F5、F7～F9 求解時，改進算法PWMBOA 均能尋到理論最優值0；對于F4 求解時，雖然PWMBOA 沒有尋到理論最優值0，但與BOA 相比最優值提高了3個數量級。對于F6 求解時，PWMBOA沒有尋到最優解，但與基本BOA相比尋優精度提高了4個數量級，能夠尋到更優的結果。

從平均值和標準差的角度分析，標準差反映算法的穩定性，平均值反映算法的收斂速度。對F4 求解時，PWMBOA尋優精度更高且尋優結果更穩定。對于F6，與BOA 相比，PWMBOA 的標準差為0，說明在求解F6時，獲得高精度的結果并非偶然。另外，從平均耗時的角度考慮，同BOA 相比，PWMBOA 平均耗時要長。主要因為PWMBOA 算法中引入的策略需要進行指數對數計算，同時多次計算適應度并進行對比，所以計算耗時相比BOA 增加了，相比尋優結果的精度和尋優結果的穩定性，這樣的耗時是能夠接受的。

綜上分析，對于9 個測試函數進行綜合尋優時，PWMBOA 算法的性能得到了很大的改進，具體表現在PWMBOA 能夠獲得更高的尋優精度，算法的收斂速度也得到了提升，與BOA相比具備更強的尋優能力。

3.2 與不同改進策略的比較

將PWMBOA 與標準BOA、僅加入飛行引領策略（JBOA）、僅加入分段權重（CBOA）以及僅加入變異反向學習（OBOA）策略進行比較，進一步驗證不同策略的有效性和魯棒性。算法的具體參數設置與3.1 節相同，并讓每個改進策略獨立運行30 次得到的實驗結果如表3所示。

由表3的數據可知，對F1～F3、F5、F7～F9 尋優時，PWMBOA都能夠尋到理論值0，對F6 雖然沒有尋到理論值，但相對于其他改進策略尋優精度更高及收斂速度更快。對F4，OBOA尋優精度比PWMBOA略高，主要是F4 含有的噪聲對于引領策略計算適應度干擾的緣故，對蝴蝶信息交互產生一定影響，進而對PWMBOA的尋優性能產生微弱影響。

從每個策略分析，對于單峰函數F1～F2、F5 及多峰函數F7～F9，CBOA 都能尋到最優值，對F3、F4 及F6 的精度也遠高于BOA。因為分段權重在搜索前半段使用指數與對數結合的形式，所以可以保證算法能夠在迭代開始到中期獲得較高權重，增強算法的全局搜索能力，搜索后半段使用指數形式權重，需要讓算法在最優值附近進行深度開發，提高尋優精度和加快收斂速度；對于單峰函數F1～F3 及多峰函數F7～F9，JBOA 尋優精度均有不同幅度的提升，尤其是對于F1～F2，尋優精度與BOA相比提高了10－52和10－94量級，因為通過加強當前蝴蝶與最優蝴蝶之間的信息交流，可以有效引導當前蝴蝶向最優位置進行尋優；對于單峰函數F1～F5，OBOA 與BOA 精度有一定提升，特別是含有大量噪聲的F4 上尋優精度最高，多峰函數F7～F9 上，其尋優精度雖低于BOA 但均值要比BOA 好。OBOA 通過控制變異概率與反向學習結合，比較當前解與可行解，擇優進入下一次迭代，豐富種群多樣性，且在含有噪聲的函數上表現較好。

另外，由表3 可知，BOA 平均耗時最少，改進的JBOA、OBOA、CBOA 相比BOA 平均耗時有小幅度增加，出現這種情況是符合實際情況的。因為改進策略中引入了更多參數，使得PWMBOA能夠在搜索空間中搜索到更多的解，導致算法運行時間變長。PWMBOA 的平均耗時與其他三種改進策略增加不是很大，在可接受范圍內。

表3 不同改進策略的結果比較Table 3 Comparison of results of different improvement strategies

3.3 收斂性分析

根據文獻[17]和文獻[18]對算法進行收斂性分析可以更充分驗證算法的性能。圖1為基準測試函數F1～F9的平均收斂曲線圖，維度均為30維，獨立運行30次的條件下，對每個改進策略進行收斂性分析。為了使曲線不失一般性，采用平均收斂曲線圖描述每個改進策略的收斂性。因為尋優精度過高，為了更好地觀察曲線收斂情況，所以縱坐標取以10為底的對數，其特點是當算法尋到最優值0時，曲線后面將不再顯示。

從圖1 中明顯看出，在單峰函數F1～F2 上，尋到最優值，而且從迭代開始PWMBOA和CBOA與其他改進策略相比平均曲線下降更快且具有更高的收斂速度和尋優精度，這也充分印證了分段權重能夠有效增強算法逃離局部最優的能力，確保算法獲得更高的尋優精度，同時JBOA 的尋優精度與平均曲線收斂也比BOA 和OBOA 更高與更快。在單峰函數F3 上，CBOA 的尋優能力相比其他改進策略更為出色，PWMBOA 的尋優能力雖不如CBOA，但兩者的曲線收斂速度相當。在單峰函數F4 上，迭代開始時各算法的曲線下降迅速，然而隨著迭代的進行，BOA與JBOA陷入局部最優，算法出現停滯，PWMBOA、CBOA和OBOA繼續尋優，其中OBOA尋優能力更為突出，尋優精度最高，OBOA 對于該函數的尋優能力和跳出局部極值的能力遠高于其他函數。在單峰函數F5 上，PWMBOA 和CBOA 的曲線收斂速度最快，OBOA 次之。在多峰函數F6 上，PWMBOA 和CBOA 的曲線收斂速度和尋優精度最高，而且JBOA、OBOA 的曲線收斂速度與尋優精度也高于BOA。在多峰函數F7～F9 上，PWMBOA 和CBOA 都能尋到最優值，PWMBOA 的收斂速度相比其他算法具有明顯的優勢，即收斂速度快且尋優精度高。

綜上，表3 的實驗結果與圖1 的平均曲線驗證了本文所提3種改進策略的有效性。同時融合了3種改進策略的PWMBOA 的綜合尋優能力相比BOA 得到了很大程度的提升。

圖1 不同改進策略的平均收斂曲線Fig.1 Mean convergence curves of different improvement strategies

3.4 與其他群智能算法對比

將PWMBOA與BOA[1]、SSA[4]、WOA[5]與SCA[6]進行對比，分別在搜索空間維度為30/50/200 的條件下，對9個測試函數進行尋優，獨立運行30 次。如表4 所示，SSA的尋優精度最低，SCA和BOA尋優精度相差不大，PWMBOA 尋優精度、收斂速度及穩定性是6 種對比算法中最好的，WOA 的尋優精度和穩定性比其他4 種對比算法要高。

表4 不同維度下各種群智能算法的結果對比Table 4 Comparison of results of swarm intelligence algorithms in different dimensions

從縱向分析，WOA 在對F7、F9 求解時，能夠尋到理論值，SCA僅在F8 尋到理論值。對于F1～F9，在其他對比算法尋優精度低且收斂速度慢的情況下，PWMBOA仍然能保持較高的穩定性和尋優精度。隨著函數由單峰函數變為多峰函數，BOA 陷入局部最優的問題越發明顯，其他對比算法也出現了停滯，僅有PWMBOA 持續尋優，尋優精度也是5種對比算法中最高的。

從橫向分析，當維度從30 維增加至50 維再增加至200 維時，WOA、SSA 和SCA 的尋優精度和魯棒性均有不同程度下降。因為隨著測試函數維度增加，求解函數的復雜度也在隨之升高，尋優過程更加復雜，需要更多的計算和調整，但BOA和PWMBOA相對穩定，PWMBOA的尋優精度和魯棒性仍然是6種算法中最好的。另外，從平均耗時角度看，當維度從30 維到50 維再到200 維時，WOA的平均耗時最長，WOA在F7、F9 上尋到理論值0；SCA在F8 上尋到理論值。30維時，平均耗時最短的是SCA，50 維時，除F1 求解時，SCA 平均耗時最短外，其余函數上SSA平均耗時最短。200維時，對于F2、F4～F7 求解時，SSA 的平均耗時最短，其余函數求解，BOA 的平均耗時最短。改進算法PWMBOA 能對搜索空間進行廣泛搜索，因此可以找到更多的解，進而導致各算法的平均耗時有所增加。

3.5 Wilcoxon秩和檢驗

在上述仿真中，僅通過平均值和標準差不會對每次實驗結果進行獨立對比。為了保證算法的公平性和魯棒性，Derrac 等在文獻[19]中提出使用統計檢驗來評估改進算法的性能。為了驗證PWMBOA 的每次實驗結果是否在統計上有顯著差異，本文采用Wilcoxon統計檢驗[20]，在5%的顯著性水平之下進行，若p值小于5%，則拒絕零假設，說明兩種對比算法之間具有顯著性差異。

9 個測試函數下，將PWMBOA 與BOA、JBOA、OBOA、CBOA 以及新改進的灰狼算法（Improved Grey Wolf Optimizer，IGWO）、混合灰狼和布谷鳥搜索優化算法（Hybrid Grey Wolf and Cuckoo Search Optimization algorithm，GWO_CS）進行比較。若最佳算法是PWMBOA，因為最佳算法無法與自身對比，所以表中標記“NaN”，表示不適用，即無法進行顯著性判斷。“win”表示顯著性判斷結果，符號“+”“-”和“=”分別表示PWMBOA 的性能要優于、劣于和相當于對比算法。從表5 中可知，大部分p值遠小于5%，“win”為“+”，拒絕零假設。因此，PWMBOA 與其他6 種對比算法之間具有顯著性差異，且PWMBOA顯著更優。

表5 Wilcoxon秩和檢驗p 值Table 5 Wilcoxon rank sum test p value

3.6 在CEC2014基準函數上進行測試

為了更好地評估PWMBOA的有效性和魯棒性，根據文獻[21]使用CEC2014來驗證改進算法的性能，因此本文在CEC2014 基準測試函數上選取了部分單峰、多峰、混合（Hybrid）及復合（Composition）類型的函數進行優化求解，如表6所示。其中L-SHADE[2]在CEC2014函數上表現出色，常當作對比算法，同時與TSLPSO[2]進行對比。在該實驗中，種群規模設為30，最大迭代次數為1 000，維度為30，獨立運行30次。

表6 CEC2014函數（部分）Table 6 CEC2014 functions（part）

由表7 可知，L-SHADE 和TSLPSO 在單峰、多峰函數上具有明顯優勢，IGWO和GWO_CS次之，PWMBOA稍差一些，因為PWMBOA 更多的參數計算，造成收斂精度稍有下降；其余函數上，L-SHADE 和PWMBOA 的收斂精度和魯棒性遠高于其他算法，更進一步證明PWMBOA具有較好的魯棒性和有效性。

表7 CEC2014優化結果對比Table 7 Comparison of CEC2014 optimization results

3.7 與其他新改進算法對比

為了突出改進算法的競爭性，與參考文獻中的其他改進算法進行比較。為實現公平對比，迭代次數設為500，種群規模為30，除了F8 維度設為2外，其他函數搜索維度為30/200/500，獨立運行30 次，對比結果如表8所示，表中“—”代表無數據。

由表8可知，分別在30/200/500維度，對各新改進算法從橫向和縱向進行對比，充分驗證PWMBOA的優勢。從橫向看，在F1～F3 上DCWOA的平均值最好，CWOA次之，PWMBOA 略差一點；在F4～F9 上，PWMBOA 的均值都比其他新改進的群智能算法要好。從縱向看，隨著維度的增加，在F3 上DCWOA和CWOA的均值明顯增加，而PWMBOA均值幾乎未變，進一步驗證了PWMBOA的競爭性。

表8 與參考文獻算法均值對比Table 8 Compared with reference algorithms

4 結束語

為了克服BOA存在尋優精度低和收斂速度慢的問題，受分段權重和GA 中變異概率的啟發，提出了新型的蝴蝶位置更新策略以增加種群多樣性，增強跳出局部最優和全局搜索的能力；采用飛行引領策略，加強蝴蝶個體之間的信息交互，降低蝴蝶盲目跟隨飛行的概率，避免算法出現早熟現象；其次為了更好地平衡全局勘探與局部開發，將分段權重用于位置更新，通過反向學習和變異概率對目標位置進行干擾，避免算法陷入局部最優；最后比較變異后的位置與原位置的優劣，選擇最優位置進入下一次迭代。文中不僅使用經典測試函數，也運用統計檢驗Wilcoxon秩和檢驗和CEC2014部分函數驗證PWMBOA算法性能。實驗結果表明，改進算法具有更高的尋優能力和有效性。在未來的研究中，考慮將算法應用到工程實踐上，以進一步驗證算法的性能。