柯西變異和自適應權重優化的蝴蝶算法

高文欣，劉 升，肖子雅，于建芳

上海工程技術大學 管理學院，上海 201620

1 引言

群智能算法模擬自然界中動植物的行為，例如蟻群和蜂群，模仿它們的求偶行為、捕食行為、筑巢行為等。蟻群算法和粒子群算法是兩種早期提出的算法，現如今又提出了許多新穎的算法比如象群游牧算法[1]、磷蝦群算法[2]、蟻獅算法[3]、烏鴉搜索算法[4]、雞群算法[5]等。群智能算法也用于一些問題的解決，例如，旅行商問題、無線傳感器網絡節點定位問題、支持向量機優化問題、投資組合優化問題等。

Sankalap Arora和Satvir Singh兩位學者，通過觀察蝴蝶覓食行為而受到啟發，提出了一種新的群智能優化算法——蝴蝶優化算法（Butterfly Optimization Algorithm）[6]。該算法的主要思想是模擬蝴蝶的覓食和求偶行為實現對目標問題的求解。蝴蝶的行為可以描述為它們向食物源位置的合作運動。蝴蝶接收、感知和分析空氣中的氣味以確定食物源或配對伴侶的潛在方向。BOA算法模擬此行為在搜索空間中尋找最優解。與現有的一些元啟發式算法相比，基本BOA操作簡單、調整的參數少、魯棒性好，并在工程實踐的初步應用中取得了良好的效果。然而在求解較高維函數問題時，BOA具有與其他的群智能仿生算法類似的問題，即容易陷入局部最優值、收斂性差等缺陷。為了改進蝴蝶算法容易陷入局部最優和收斂性能差等問題，文獻[7]提出了基于萊維飛行的蝴蝶優化算法，在全局位置更新和局部位置更新處引入萊維飛行策略，提高了算法的搜索能力；文獻[8]提出了一種基于學習自動機機制的蝴蝶優化算法，引入學習自動機機制，加速了全局搜索的速度，達到真正的全局最優；文獻[9]提出了一種基于感覺模態變化的蝴蝶優化算法，采用動態變化的感覺模態參數策略，改變了收斂精度，提高了收斂速度；文獻[10]提出了一種混合人工蜂群算法的蝴蝶優化算法，克服了蝴蝶優化算法后期搜索能力不足，提高了算法的收斂速度。對于現存的BOA改進策略的研究，雖然在一定程度上改進了算法的尋優性能，但是一般的也只是針對蝴蝶優化中某一個更新策略進行改進或者是改變初始化種群的方式，并沒有有效的改進全局尋優和局部尋優的盲目性。

基本的蝴蝶優化算法存在著依賴初始種群、收斂精度低和易陷入局部最優等問題，針對這些問題本文提出了一種多策略改進的蝴蝶優化算法。利用柯西分布函數對蝴蝶的全局位置更新進行變異，提升算法的全局搜索能力，在蝴蝶算法的局部位置更新處引入自適應慣性權重因子，改進了算法的局部開采能力，并且使用動態切換概率來平衡局部搜索和全局搜索的比重，提高了尋優性能。通過14個基準測試函數測試，結果表明改進算法具有更高的收斂精度和魯棒性。

2 蝴蝶優化算法

在自然界之中，蝴蝶可以使用它們的各種感官如：嗅覺、視覺、味覺、觸覺和聽覺去尋找食物和求偶，這些感覺能夠幫助它們遷徙、躲避狩獵者以及幫助它們找到合適的地方產卵。在所有的感覺中最重要的是嗅覺，嗅覺能夠幫助蝴蝶尋找食物（花蜜），即使在很遠的地方也不例外。為了能夠找到食物，蝴蝶使用感覺受體用于嗅覺，這些受體分散在蝴蝶的身體部位，如觸角、腿和手掌等。這些受體實際上是蝴蝶身體表面的神經細胞，被稱為化學感受器。這些化學感受器引導蝴蝶找到最佳的交配伙伴，以便繼續強大的遺傳系統。雄性蝴蝶能夠通過信息素來識別雌性，這是雌性蝴蝶發出的氣味分泌物引起特異性反應。

蝴蝶會產生一些強度與其適應性相關的香味，即當蝴蝶從一個位置移動到另一個位置時，它的適應性會相應地變化，香味會在遠處傳播，其他蝴蝶個體能夠感知它，這就是蝴蝶個體如何與其他蝴蝶共享個體信息，形成一個群體的社會知識網絡。當一只蝴蝶能夠聞到來自其他的蝴蝶分泌的香味的時候，它將會朝著香味最濃的方向移動，該階段在算法中被稱為全局搜索。在另一種情況下，當蝴蝶不能從周圍感知香味時它將隨機移動，這一階段是局部搜索階段。

針對上述行為，提出如下假設：

（1）所有的蝴蝶都應該散發一些香味，使蝴蝶能夠相互吸引。

（2）每只蝴蝶都會隨機移動或向發出最多香味的蝴蝶移動。

（3）蝴蝶的刺激強度受目標函數的影響或決定。

（4）全局搜索和局部搜索使用切換概率 p來控制，受到物理接近度以及風、雨、雷、電等各種其他自然因素，局部搜索和全局搜索中的切換概率p具有重要意義。

在BOA算法中，每一只蝴蝶有它自己獨特的感覺和個體感知能力。這同時也是區分于其他元啟發式算法的一個主要特征。蝴蝶個體產生的香味數學公式如下：

其中，f是香味的感知強度，即香味被其他蝴蝶感知的強度，c是感覺模態，I是刺激強度，a是依賴于模態的冪指數，它解釋了不同程度的吸收。本文在[0，1]范圍內取a，參數a是取決于模態的功率指數（在此為香味），這意味著它表征吸收的變化。

在每次迭代中，搜索空間中的所有蝴蝶移動到新位置，然后評價它們的適應值。該算法首先計算解空間中不同位置上所有蝴蝶的適應度值。然后這些蝴蝶將通過計算公式（1）在它們的位置產生香味。在全局搜索階段，蝴蝶朝著最優的蝴蝶(g*)移動，它可以用公式（2）表示：

算法1基本蝴蝶算法

輸入：目標函數 f(x)，蝴蝶群體的規模N，刺激濃度I，感覺模態c，冪指數a的初始值，全局更新和局部更新的轉換概率p，最大迭代次數MaxIter

1.初始化種群

2.Whilet

3. fori=1∶N

4. 計算每只蝴蝶的香味濃度

5. end for

6. 找到最優蝴蝶個體g*

7. fori=1∶N

8. 隨機產生[0，1]之間的隨機數r

9. ifrand>p

10． 進行全局位置更新，按照公式（2）進行計算

11. else

12. 進行局部隨機游走，按照公式（3）進行計算

13. end if

15. end for

16. 更新a的值

17.end while

輸出：全局最優解

3 蝴蝶優化算法的改進

為了改進蝴蝶算法容易陷入局部最優和收斂精度低的問題，本文從三個方面對蝴蝶算法進行改進。首先通過引入柯西分布函數的方法對全局搜索的蝴蝶位置信息進行變異，提高蝴蝶的全局搜索能力；其次通過引入自適應權重因子來提高蝴蝶的局部搜索能力；最后采用動態切換概率p平衡算法局部搜索和全局搜索的比重，提升了算法的尋優性能。因此本文提出一種混合策略改進的蝴蝶優化算法（CWBOA）。

3.1 柯西變異

針對蝴蝶優化算法易陷入局部最優的特點，利用柯西變異來增加種群的多樣性，提高算法的全局搜索能力，增加搜索空間。柯西分布函數在原點處的峰值較小但在兩端的分布比較長，利用柯西變異能夠在當前變異的蝴蝶個體附近生成更大的擾動從而使得柯西分布函數的范圍比較廣[11]，采用柯西變異兩端分布更容易跳出局部最優值。本文融入柯西算子，充分利用柯西分布函數兩端變異的效果來優化算全局最優個體，使得算法能夠更好地達到全局最優。標準柯西分布函數公式如下：

柯西分布函數從峰值向兩側下降相對平緩，蝴蝶個體受局部的極值點約束力在進行柯西變異后下降，并且柯西分布函數的峰值相對較小，蝴蝶個體在變異后會使用相對較少的時間來搜索相鄰區間，把更多的時間放在搜尋全局最優值上，使得改進的蝴蝶優化算法在尋找全局的最優值方面具備很好的調節能力。用柯西變異進行隨機擾動有利于增加種群的多樣性從而避免算法陷入局部最優，提高全局搜索最優值的能力。柯西分布的特征使其能夠產生與原點相距較遠的隨機數，這意味著經過柯西變異后的蝴蝶個體具備了能夠迅速逃離局部極值的能力。另外，柯西分布函數的峰值較低，該特點能夠縮短變異后的蝴蝶個體在鄰域周圍搜索的時間。因此在求得當前最優解后，本文使用公式（5）所示的更新公式對當前全局最優解進行變異處理。

3.2 自適應權重

慣性權重因子是很重要的一個參數，當慣性權重比較大時，算法全局搜索能力較強，能夠增加種群多樣性，可以搜索較大的區域；當慣性權重比較小時，算法局部搜索能力較強，可以在最優解周圍精細搜索，加快收斂速度。蝴蝶進行局部尋優時，是以公式（3）進行局部搜索的，其中當蝴蝶以公式（3）向局部最優解靠近時，這時只能靠近局部最優解，而不能進行更好的局部尋優[12]，針對這個問題受文獻[13]、文獻[14]的啟發，提出了新的自適應權重方法，蝴蝶接近食物的時候，采用較小的自適應權重改變此時最優的蝴蝶的位置，使得蝴蝶局部尋優能力得到提高。自適應權重公式如式（6）所示：

式（6）中，t為當前迭代次數，itmax是最大迭代次數。

改進式（3）的公式如（7）所示：

通過融合自適應權重因子w，使蝴蝶個體具有更好的局部尋優能力，改進后的蝴蝶算法流程圖如圖1所示。

3.3 動態切換概率策略

在基本蝴蝶優化算法中，局部搜索和全局尋優過程用常量切換概率 p∈[0,1]來控制，一個合理的搜索過程在算法的前期應該進行較強烈的全局搜索，迅速定位搜索空間中全局最優解所在范圍，在探索后期局部開采能力應增強，以提升算法的尋優精度。本文引入動態切換概率來平衡局部開采和全局開采的比重，來實現更好的尋優策略。動態切換概率p的公式如下：

3.4 算法描述

CWBOA的具體執行步驟如下：

圖1 改進算法的流程圖

步驟1初始化種群及各個參數設置。

步驟2計算每只蝴蝶的香味濃度，得到每個個體的適應度值，并且求出當前最優解。

步驟3若動態轉換概率p>rand，則按照式（2）、（5）對全局位置進行更新。

步驟4若動態轉換概率p

步驟5越界處理。

步驟6計算步驟4和步驟5的函數適應度值，若得到新的函數適應度值，則更新全局最優適應度值和全局最優解。

步驟7判斷結束條件，如果滿足，則退出程序，輸出最優值及最優解，否則轉步驟3。

3.5 改進算法（CWBOA）的時間復雜度分析

設蝴蝶群體的規模為N，迭代次數為MaxIter，維度為D，則根據CWBOA算法的描述和時間復雜度符號O的運算規則，隨機初始化種群的時間復雜度為O(N?D)，以及找到當前最香的蝴蝶的時間的復雜度O(N?D)，利用柯西分布函數對于全局位置更新進行變異的時間復雜度為O(D)，引入慣性權重因子對局部位置更新的時間復雜度為O(MaxIter?D?N)，CWBOA算法的總的時間復雜度為O(D?N?MaxIter)，所以CWBOA的時間復雜度與BOA相同，并沒有增加計算負擔。

4 函數測試與結果分析

4.1 仿真實驗環境

本仿真測試環境為：操作系統Windows 7，CPU為Intel?Core? i5-4210U，主頻1.7 GHz，內存為4 GB，仿真軟件為Matlab2018b。

4.2 實驗的初始參數設置

本文選取了基于柯西變異和動態自適應權重的蝴蝶優化算法（CWBOA）、基本蝴蝶算法（BOA）、鯨魚算法（WOA）[15]，以及花授粉算法（FPA）[16]進行對比。為了實驗的公平、客觀性，本文將所有算法的初始種群規模統一設為30，迭代次數設置為500，四個算法的共有參數保持一致。CWBOA和BOA中的c感官形態設置為0.01，a冪指數在迭代過程從0.1迭代到0.3；基本的BOA和FPA中的切換概率均為p=0.8。

4.3 測試函數

為了驗證改進后的BOA在收斂性和魯棒性兩方面的性能上更優，本文基于14個測試函數進行對比實驗，標準測試函數的信息見表1。

4.4 實驗結果與分析

為了驗證本文中改進CWBOA算法具有更好的收斂性和穩定性，本文用14個基準測試函數進行了驗證，為了避免由于偶然的因素帶來的結果的偏差，每個算法在每個測試函數上面獨立運行30次。表2將給CWBOA、BOA、BA、FPA四個算法在多個測試函數上通過獨立運行30次后所得到的實驗結果。

表2分別列出了CWBOA、BOA、WOA、FPA算法獨立運行30次所得到的最優值、最差值、平均值和標準差。很容易看出對于所選測試函數，CWBOA的尋優性能最強，明顯優于BOA、WOA、FPA。函數f1、f5、f6、f7、f8、f9、f12、f13、f14可以直接搜索到最優值0，尋優效果可以達到100%；對于函數f4，CWBOA的尋優平均值和基本花授粉算的尋優性能差不多，略優于基本BOA；對于函數f11，CWBOA的尋優精度平均值達到了8.881 8E?16的水平，比基本的蝴蝶優化算法提高了7個精度，算法整體的穩定性比較好；對于函數f13，CWBOA、BOA、WOA均最優值均為0，但是在穩定性上面，CWBOA的尋優性能要遠遠優于BOA和WOA，而FPA的尋優效果都是比較差的，可見改進后算法的性能具有明顯的競爭優勢。

為了直觀展示CWBOA的尋優性能，本文選取了7個基準測試函數的收斂迭代曲線圖。這里僅給出f1、f3、f7、f9、f11、f12、f14的函數圖像。如圖2所示。

由函數的收斂曲線可知，改進的CWBOA在收斂的速度上要優于BOA、WOA、FPA。f1是單峰函數，比較容易達到最優值，因此常常用來測試收斂能力，由函數的收斂曲線圖可以直觀地看出改進后的算法CWBOA的收斂精度較高，克服了基本的BOA尋優精度不高的問題。f7和f14是兩個低維測試函數，由收斂曲線圖可知在迭代過程中有多個拐點出現，證明改進后的算法容易跳出局部最優并且以較快的速度收斂到最優值，f11函數是一種很難找到全局最優值的爬山形態的多模態函數，對比基本BOA算法，改進后的蝴蝶優化算法提高了7個數量級的尋優精度。f12是一個復雜的多峰函數有許多廣泛的局部最小值，并且它們是有規律地分布的，在（0，0）處取得最優值0，CWBOA在不到50代已經達到最優值而且尋優速度也遠遠快于BOA、WOA和FPA，由收斂曲線圖可以知，CWBOA的收斂性要優于基本的BOA、WOA、FPA。

表1 測試函數的基本信息

表2 測試函數實驗結果

另外，本文的改進算法與文獻[7]中的BA、文獻[8]中的LBOA、文獻[9]中的IBOA分別進行比較，每個算法的初始化種群數均為30，其中BA和LABOA的最大迭代次數為1 000，CWBOA和IBOA的最大迭代次數為500，均參考原文獻實驗參數設置，本文設置最大迭代次數為500次的實驗結果已經明顯優于文獻[7-9]中的對比算法的實驗結果了。根據實驗結果可知本文改進算法的尋優效果更佳。對比結果如表3所示。“—”表示原文獻的實驗中不涉及的測試函數。

圖2 函數的收斂曲線

4.5 求解高維函數的實驗分析

根據上述低維實驗結果對比分析可知，本文的改進算法在低維測試函數上無論在最優值還是標準差上面均得到了較好的收斂效果。但是一般的改進策略在較為復雜的工程問題上面，特別是高維測試函數上極易失效，為了測試本文改進算法的有效性，進行了CWBOA的高維函數優化求解實驗，因為在實際的問題中普遍存在的是大規模的、復雜的優化問題。為了更好地證明本文改進算法能夠應用于求解大規模復雜問題，高維參數設置與4.2節相同。

表3 改進算法的實驗結果對比

根據表4的實驗結果，發現CWBOA求解高維函數上面的效果比較好，但是在解決100維、500維的f3函數的時候失效。f3是連續的，平滑的多峰函數，當自變量趨近于無窮大時，函數會形成大量局部極值區域，易陷入局部最優且不易跳出，在高維測試函數下求解難度較大，在測試函數維數大于100維時，就屬于大規模函數優化問題。隨著搜索空間維數的增加，問題的復雜度以及指數級數的增長，從而出現“維數災難”問題[17]，根據無萬能算法理論，沒有任何一個算法適合解決所有問題，所以這個結果是可以接受的。函數f1、f5～f9、f12、f13均能達到最優值0，所以在求解高維測試函數時，本文的改進策略依然具有較強的穩定性，能夠有效地處理復雜的高維問題。選取本文的測試函數f1、f4、f6、f10、f11測試結果與文獻[18]中的對立學習策略的鯨魚優化算法（IWOA）在500維的情況下的結果進行對比（實驗結果如表5所示）。函數f1、f6這兩個測試函數的結果始終能精確達到最優值0，尋優效果能達到100%，說明CWBOA在處理復雜的大規模問題上魯棒性較強；對于函數f4和f11，CWBOA的尋優精度略優于IWOA，但是標準差始終穩定在0，表明其較強的尋優穩定性，對于函數f10，本文的改進算法要比IWOA的尋優精度提高近70個單位。綜上，能夠證明本文改進算法的可行性和有效性。

表5 CWBOA與IWOA對比結果

5 結束語

本文提出了一種混合策略的蝴蝶優化算法（CWBOA），在全局位置更新后的值引入柯西變異算子，增加了種群多樣性，降低算法陷入局部最優的可能性；在BOA局部位置更新中引入自適應權重因子，提高了算法的局部搜索能力，并且采用動態切換概率p來權衡局部開采和全局搜索的比重，基于三種改進策略提升了算法的尋優能力和魯棒性。接下來的研究方向主要是拓展改進算法的實際應用領域。

表4 CWBOA的高維函數求解結果