融合變異策略的自適應蝴蝶優化算法

摘 要： 蝴蝶優化算法是近年來提出的一種新型自然啟發式算法。針對基本蝴蝶優化算法收斂速度慢、求解精度低、穩定性差等問題，提出了一種融合變異策略的自適應蝴蝶優化算法。通過引入動態調整轉換概率策略，利用迭代次數和個體適應度的變化信息動態調整轉換概率，有效維持了算法全局探索與局部搜索的平衡；通過引入自適應慣性權重策略和局部變異策略，利用慣性權重值和混沌記憶權重因子進一步提高了算法的多樣性，有效避免算法早熟收斂，同時加快了算法的收斂速度和求解精度。利用改進算法對12個基準測試函數進行仿真實驗，與基本蝴蝶優化算法、粒子群算法、樽海鞘群算法、灰狼優化算法等其他算法對比表明，改進算法具有收斂速度快、尋優精度高、穩定性強等優異性能。

關鍵詞： 自然啟發式算法； 蝴蝶優化算法； 自適應慣性權重； 變異策略

中圖分類號： TP18"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-024-0134-07

doi：10.19734/j.issn.1001-3695.2021.06.0244

Adaptive butterfly optimization algorithm based on mutation strategies

Liu Kai， Dai Yongqiang

（College of Information Science amp; Technology， Gansu Agricultural University， Lanzhou 730070， China）

Abstract： Butterfly optimization algorithm （BOA） is a novel nature-inspired metaheuristics algorithm proposed in recent years. The basic BOA is slow convergence， low accuracy and easy to fall into local optimum. To solve the above problem of basic BOA， this paper proposed an adaptive butterfly optimization algorithm based on mutation strategies （ABOA-MS） . Firstly， it introduced the strategy of adjust the conversion probability dynamically， which effectively balanced the ability of the global exploration and local search， by means of dynamically adjusting the switching probability of the change information of iteration times and individual fitness. Secondly， it introduced the adaptive inertia weight strategy and local mutation strategy. It applied the inertia weight value and chaotic memory weight factor， which further improved the diversity of this algorithm， and effectively avoided its precocious convergence， as well as accelerated its convergence speed and solving accuracy. In order to verify the optimization performance of the modified algorithm， it carried out the simulation experiments among the modified algorithm， the basic BOA algorithm， the particle swarm optimization algorithm， the salp swarm algorithm， the gray wolf optimization and the others. Simulation results illustrate that the modified algorithm has excellent performance of fast convergence speed， high optimization accuracy and strong stability.

Key words： novel nature-inspired metaheuristics algorithm; butterfly optimization algorithm; adaptive inertia weight; mutation strategy

0 引言

隨著求解最優化問題被不斷深入研究，受群體行為和進化等自然現象啟發的元啟發式優化算法也越來越多地被引入到優化問題中。最早出現的群體智能優化算法有粒子群優化算法（particle swarm optimization，PSO）、差分進化算法（differential evolution，DE）、人工蜂群算法（artificial bee colony，ABC）等［1～3］。近年來被提出的有布谷鳥搜索算法（genetic algorithm，GA）、蜘蛛猴優化算法（spider monkey optimization，SMO）、烏鴉搜索算法（crow search algorithm，CSA）、樽海鞘群算法（salp swarm algorithm，SSA）等［4～7］。這些群體智能優化算法都具備更少的感知量、更廣的作業范圍及更強的求解能力等優點。

蝴蝶優化算法（butterfly optimization algorithm，BOA）是由Arora等人［8］基于蝴蝶覓食行為的靈感而提出的一種元啟發式優化算法，其參數較少，時間復雜度低，易于實現，現已解決了工程問題中的彈簧設計、焊接梁設計、齒輪系設計［8］等難題，也被廣泛應用于特征選擇、機械設計、投影尋蹤模型、居民CO2排放預測等［9～12］諸多問題的求解中。然而，該算法仍存在收斂速度慢、求解精度低、易陷入局部最優等不足。針對該算法存在的以上問題，文獻［13］提出了一種基于正態分布和基于威布爾分布的感覺模態自適應模型，并運用支持向量機和反向傳播預測模型及KCV-SVM模型對其進行了驗證，結果表明該算法在精度和穩定性方面具有較強的競爭力；文獻［14］通過在全局搜索階段加入空間分散值保證了算法對最優解的自適應探索能力，并在局部搜索階段引入全局最優解，利用最優個體的引導從而提高了局部搜索性能；文獻［15］通過在算法初始化階段引入混沌映射，增強了算法的遍歷能力，通過將香味因子a改為非線性參數有效地平衡了算法的全局探索和局部搜索能力，通過將粒子群算法與蝴蝶優化算法進行混合提高了全局優化能力；文獻［16］通過在算法中引入自適應學習機制提高了尋優能力，并降低了陷入局部最優的概率；文獻［17］通過將算法引入余弦相似度位置調整策略保持了算法的種群多樣性，并引入動態切換概率平衡了算法局部搜索和全局搜索，以及增加混合慣性權重策略提高了算法收斂速度；文獻［18］通過在算法初始化階段采用ICMIC映射策略，避免了算法陷入局部最優，同時在自身認知飛行部分引入正弦余弦算子，平衡了算法的局部搜索與全局搜索能力，另外通過改進香味因子a提高了可行解質量；文獻［19］借鑒精英策略思想重新定義蝴蝶優化算法的局部搜索迭代公式，以及融合遺傳算法的選擇、交叉和變異操作提高了算法的尋優能力。上述各種BOA的改進算法，不同程度地使BOA的尋優能力得到了提高，但針對算法收斂速度慢、求解精度低、局部搜索與全局搜索平衡性差等問題仍存在較大的提升空間。

為了更好地提高算法的優化性能，提高多樣性及增強算法的全局尋優能力，本文提出了一種融合變異策略的自適應蝴蝶優化算法（adaptive butterfly optimization algorithm based on mutation strategies，ABOA-MS）。改進算法通過將參數p調整為隨種群迭代次數和個體適應度變化而動態調整的轉換概率，p的取值因受二者動態變化的影響，局部搜索與全局探索同步進行的概率增大，且逐漸遞減的規律使算法在迭代后期收斂速度加快，從而有效地平衡算法的全局探索能力與局部搜索能力；通過將自適應慣性權重因子引入全局位置更新階段，受正態分布的影響，種群的多樣性得到良好的保持，進而避免算法早熟收斂；通過將改進的變異操作引入局部位置更新階段，利用最優或較優個體的位置和方向信息指引算法進行二次精細化搜索，從而加快算法的收斂速度，并進一步提高算法的收斂精度。將改進算法對12個測試函數進行仿真實驗，并與基本蝴蝶優化算法、其他幾種群智能優化算法及其他文獻中改進的蝴蝶優化算法進行比較，從而驗證改進算法的有效性。

1 蝴蝶優化算法

1.1 蝴蝶優化算法原理

蝴蝶優化算法是通過模仿自然界蝴蝶的覓食行為而衍生出來的。在BOA中，每個蝴蝶作為搜索算子，在搜索空間中執行優化過程，蝴蝶能夠感知并區分不同的香味強度，每只蝴蝶散發出的香味都有一定的強度。假設蝴蝶產生香味的強度與蝴蝶的適應度有關，即蝴蝶從一個地方移動到另一個地方，它的適應度也會隨之變化。蝴蝶散發出的香味會在空氣中傳播，令其他蝴蝶都能感覺到，這是蝴蝶個體與其他蝴蝶個體分享個人信息的過程，因此形成一個集體的社會知識網絡。當蝴蝶能夠感覺到其他蝴蝶的香味時，它會向那只香味最大的蝴蝶移動，這個階段被稱為全局搜索。反之，當蝴蝶無法感知其他蝴蝶的香味時，它則會隨機移動，這個階段稱為局部搜索。在搜索過程中，全局與局部的搜索通過轉換概率p來進行切換。

假設Xi=（xi1，xi2，…，xiD）為第i（i=1，2，…，N）只蝴蝶個體，D為搜索空間維度，N為蝴蝶種群規模，蝴蝶個體的位置更新如式（1）所示。

xt+1i

xti+（r2×g*-xti）fi

xti+（r2×xtj-xtk）fi

（1）

其中：xt+1i是在t+1次迭代中第i只蝴蝶的解向量;r是［0，1］的隨機數;g*表示當前迭代中全局最優個體;xtj和xtk是隨機產生的蝴蝶個體，表示解空間中第j只和第k只蝴蝶的解向量，第i只蝴蝶發出的香味用fi表示，f的具體表達式為

f= cIa（2）

其中：f是香味感知量;c是感知形式;a是依賴感知形式的冪指數，反映吸收香味的不同程度。

1.2 蝴蝶優化算法缺點分析

BOA中轉換概率p的初始值為常數0.8，表示算法在一次迭代過程中，有80%的概率做全局探索，而僅有20%的概率做局部搜索。算法在迭代前期，應進行大概率全局尋優以確保可以較快速度向全局或局部最優位置靠攏，而在迭代后期，在全局或局部最優位置鄰域進行精細化局部開發。如果轉換概率在算法迭代整個過程保持固定值，那么算法在迭代全過程始終以較高概率處于探索開發狀態，而局部的精細化搜索能力較弱，因而不利于算法在迭代后期進行全局最優或局部最優值的搜索，無法快速找到最優解。另外，若算法在搜索過程中的全局探索和局部搜索階段概率始終設定為定值，算法的多樣性也無法得到有效保持，因此適當對轉換概率進行動態調整，通過引入迭代次數和個體適應度的動態信息，可有效平衡算法全局探索與局部搜索之間的關系，以進一步提高算法的尋優能力。

BOA算法采用雙策略的位置更新方式，通過轉換概率p控制算法的全局探索與局部搜索。式（1）中，g*-xti表示全局最優個體與第i個個體之間的距離，即當前個體向全局最優個體附近位置進行探索，全局搜索過程僅采用全局最優個體g*和當前個體xti的信息，當前個體i一旦聞到強烈香味會迅速向g*靠攏，算法的多樣性較差，容易掉入局部極值。同時，式（1）中xtj-xtk表示兩個隨機產生的解向量之間的距離，即解空間中每個個體隨機更新位置，局部搜索始終圍繞在隨機個體鄰域附近，算法易錯失最優解或較優解。因此本文在位置更新階段引入自適應慣性權重因子和變異因子，利用慣性權重值和混沌記憶權重因子提高算法的多樣性，有效避免了算法早熟收斂。另外，本文利用變異因子中最優個體的引導，保證算法可以從個體鄰域跳轉到最優解鄰域，并在最優解附近展開精細化搜索，從而加快算法的收斂速度和求解精度。

2 融合變異策略的自適應蝴蝶優化算法

以提高BOA的求解精度、收斂速度、魯棒性等為目標，在BOA中分別引入動態調整轉換概率策略、自適應慣性權重策略、局部變異策略三種策略對該算法進行改進。

2.1 動態調整轉換概率策略

在BOA種群個體位置更新過程中，主要通過轉換概率p切換蝴蝶個體的搜索區域，p的取值越大全局搜索的概率就越大，反之，局部搜索概率越大。在算法運行過程中，有效地平衡全局探索與局部搜索之間的能力至關重要。因此，本文引用文獻［20］的參數自適應調整策略對轉換概率p進行動態調整。改進后的轉換概率如式（3）所示。

pti=0.8×2－tNiter×12+ftmax－fti|ftmax－ftmin|×12（3）

其中：t表示當前迭代次數;Niter表示最大迭代次數;fti表示第i個個體在第t代的適應度;ftmin表示第t代最優的適應度;ftmax表示第t代最差的適應度。由式（3）可以看出，考慮轉換概率改進的同時，也考慮了迭代次數與個體適應度的影響，且兩者所占權重相同［21］。

圖1是p的動態變化圖。由圖1可以看出，BOA中轉換概率p取的為固定值0.8，ABOA-MS算法中轉換概率pti的值隨著迭代次數的增加逐漸減少，符合算法由全局探索到局部搜索的規律。算法在迭代前期，以較大概念進行全局尋優，以較快的速度向全局最優或較優的位置靠攏；算法在迭代中后期，在全局或局部最優位置鄰域進行二次精細化局部搜索，一定程度上加快收斂速度，提高了最優解的質量。隨著迭代信息的占比越小，pti的取值更多的受蝴蝶個體適應度的影響，若第i只蝴蝶個體在第t代的適應度值較優（fti較小），pti的值越大，此時利于全局搜索，若當前適應度較差（fti較大），pti的值越小，則更利于局部范圍的探索。由于在迭代過程中，算法的全局探索和局部搜索階段可同時進行，保證了算法在全局探索時不易遺失個體鄰域內更好的解。因此，動態調整轉換概率有效平衡了全局探索與局部搜索二者的關系。

2.2 自適應慣性權重策略

蝴蝶個體在位置更新時只有全局最優個體和當前個體兩個算子，導致基本算法在全局探索時易陷入局部最優，降低搜索精度。因此，為增強并保證種群良好的多樣性，同時平衡算法在全局探索和局部開發階段的能力，通過引入自適應慣性權重策略，使種群個體每一次迭代時隨機選取正態分布中的一個慣性權重值，即，ω～N（μ，σ）。當慣性權重值較大時，可以避免算法陷入局部最優，反之，可以提高算法迭代后期的收斂精度［22］。自適應慣性權重ω公式為

ω=（μmax－μmin）normrnd（）+σrandn（）+μmin（4）

其中：μmin、μmax表示慣性權重的最小值與最大值;normrnd（）表示產生均勻分布的隨機數;randn（）表示產生正態分布的隨機數;σ表示慣性權重與期望值之間的偏差程度。改進后的蝴蝶個體全局位置更新公式為

xt+1i=ω×（xti+（r2×g*-xti）×fi）（5）

算法迭代過程中，μmin、μmax、σ的取值對算法性能至關重要，經多次實驗測試證明，在單峰函數中μmin取值在［0.2，0.5］，μmax取值在［0.3，0.7］效果最佳。在多峰函數中μmin、μmax取值均在［0.1，0.9］效果最佳。偏差程度σ取值為0.5時，算法的尋優精度與收斂速度最佳。

假設搜索空間為二維，種群規模為30，選取Schwefel 2.22函數對BOA與ABOA-MS算法在不同迭代時期種群分布情況進行比較，如圖2所示。當自變量趨近于無窮大時，Schwefel 2.22函數會形成大量局部極值區域，選取該函數反映種群分布圖可以更直觀地體現算法的性能。由圖2可知，算法在迭代100次后，BOA的種群集中分布在四周，幾乎沒有靠近全局最優（0，0）的個體，ABOA-MS算法分布則較為分散，無論是（0，0）點附近還是邊界鄰域均分布有個體；算法在迭代200次后，BOA算法因為分散不夠均勻，已有部分個體陷入局部極值，而ABOA-MS算法少部分個體已向（0，0）點靠近，且同時其他區域仍存在少部分個體繼續探索，降低了陷入局部最優的概率；算法在迭代300次后，通過觀察圖（d）和（f）可以看出，ABOA-MS算法右上部分陷入局部極值的個體已經及時跳出，且已有大部分個體趨向（0，0）點周圍，而BOA此時在（0，0）點附近仍沒有分布個體；算法在迭代400次后，ABOA-MS算法的（0，0）點已聚集大部分個體，BOA則因為前期的分散不夠均勻，多樣性較差，個體仍是陷入局部最優狀態，無法正確地收斂到最優個體。這表明均勻分布和正態分布的隨機算子使個體位置更新獲得了更多位置分布信息，加強了算法全局探索能力。隨著慣性權重ω不斷變化，全局探索階段的蝴蝶個體可以更好地尋得全局最優解或較優解大概位置，進而在局部精細搜索過程中，算法可以更快更容易地發現最優值。因此，加入了自適應慣性權重因子有效增強了種群多樣性，平衡了算法在全局探索和局部開發階段的能力，進一步提高了算法的求解精度。

2.3 局部變異策略

由于基本蝴蝶優化算法局部搜索能力弱，本文引入差分進化的變異策略，利用全局最優個體的引導作用，使種群個體從局部極值鄰域跳轉到全局最優解鄰域，從而增強算法的局部搜索能力，更好地平衡算法的全局探索和局部搜索能力。

變異個體Vi=（vi1， vi2， …， xiD）是利用父代種群中隨機兩個不同個體的差向量作為第三個個體的隨機變化源，再將差向量加權后與第三個個體進行求和后產生，其表達式詳見式（6）。基本變異操作雖然種群多樣性較好，但是缺少最優解個體的引導機制，搜索效率相對較低，因此將變異成分改進后引入BOA局部搜索階段，改進后的變異操作如式（7）（8）所示，局部搜索按式（9）進行位置更新。

vt+1i，j=xr1，j+F（xr2，j－xr3，j）（6）

vt+1i，j=Fxr1，j+w（t+1）（g*－xi，j）+λ（xr2，j－xr3，j）（7）

w（t+1）=0.4×w（t）×（1－w（t））（8）

xt+1i=vt+1i，j×（xti+（r2×xtj-xtk）×fi）（9）

其中：r1、r2、r3∈{1，2，…，N}為隨機選取的互不相同的正整數，且r1、r2、r3需保持與當前目標個體i不相等;F、λ∈［0，2］，兩者均為縮放因子，此處F=0.5，λ=0.3;w為混沌因子。圖3為依據式（9）計算得到的w在算法迭代50次過程中的邏輯斯蒂圖［21］。w的變化在［0，1］。通過圖3可以看到，w隨著算法迭代次數的增加呈現出不可預測的隨機變化狀態。根據混沌理論可知，當w初值不等于0.25、0.5、0.75時，序列完全處于混沌態，此處w的初始值為0.65。由于w的變化影響使得vt+1i，j的變異強度保持隨機狀態且不重復的特性。當w的取值較大時，vt+1i，j受全局最優解的位置和方向信息的影響更大，可以增強算法的局部搜索精度；當w的取值較小時，vt+1i，j的取值受最優解的引導性較弱，隨機因子的占比繼而增大，可以保持算法局部搜索的多樣性。

分析該更新策略可知，局部搜索階段引入變異策略后，由于最優解的引導和混沌因子的影響，算法在運行周期內，不僅保持了種群多樣性，防止算法陷入局部極值，提高了算法的局部搜索能力，同時算法的全局探索能力和局部搜索能力得到了較好的平衡。

綜上所述，本文ABOA-MS算法中引入了三種不同策略，并對BOA的改進起到了不同的優化效果。算法在一次迭代過程中，由于自適應慣性權重的引入，增強了種群多樣性，有利于發現區域內潛在的更優解，提高了算法的全局探索能力；由于動態轉換概率的影響，算法的全局探索和局部搜索階段同時進行的幾率增大，收斂速度提升，保證了算法在全局探索時不易漏掉個體鄰域內更好的解；而變異策略的引入，使種群個體可以從局部極值鄰域跳轉到全局最優解鄰域，而且又能在全局最優解鄰域進行高精度的搜索［23］，提高了算法的局部搜索效率，進而更好地平衡了算法的全局探索和局部搜索能力，有效地提高了BOA的整體尋優性能。

2.4 ABOA-MS算法流程

ABOA-MS算法的流程如圖4所示。

2.5 ABOA-MS算法實現步驟

a）設置初始化種群規模N、維度D、當前迭代次數t，最大迭代次數N_iter等參數;b）計算每只蝴蝶個體的適應度值fitness，并尋找出全局最優解g*;c）若動態轉換概率pgt;rand，利用式（5）更新全局蝴蝶個體位置;d）若動態轉換概率plt;rand，利用式（9）更新局部蝴蝶個體位置;e）重新計算新種群適應度fitness，更新全局最優解g*;f）更新迭代次數t=t+1，如果達到最大迭代次數N_iter，則終止程序，輸出全局最優解，否則轉向步驟b）。

2.6 ABOA-MS算法時間復雜度分析

在BOA中，蝴蝶種群規模為N，根據蝴蝶優化算法的流程，假設在初始化階段產生隨機個體的執行時間為t1，種群迭代前計算每只蝴蝶個體的適應度值執行時間為t2，計算目標函數的時間是維度n的函數f（n），則時間復雜度為O（N（t1n+t2n f（n）））=O（n+f（n））。在蝴蝶個體位置更新階段，計算每只蝴蝶香味感知量的時間為t3，蝴蝶個體更新一次產生當前最優個體的時間為t4，得到當前最優個體與全局最優個體進行比較的時間為t5，若當前最優個體比全局最優個體更好則替換掉，所需時間為t6，則時間復雜度為O（N（t3n+t4n+f（n）+t5+t6n））=O（n+f（n））。比較當前最優個體與全局最優個體的執行時間是t5，替換全局最優個體的執行時間是t6，因此，記錄BOA最優個體的時間復雜度為O（N（t5+t6n））=O（n），最后，對于每一代產生最優個體的時間復雜度為T（n）=2O（n+f（n））+O（n）=O（n+f（n））［24］。

按照BOA的時間復雜度分析同理對ABOA-MS算法進行時間復雜度分析，種群規模、維度、目標函數和BOA一致。在初始化階段，產生隨機個體的執行時間為t1，在種群迭代前計算每只蝴蝶個體的適應度值執行時間為t2，則時間復雜度為O（N（t1n+t2n f（n）））=O（n+f（n））。在蝴蝶個體位置更新階段，計算每只蝴蝶香味感知量的時間為t3，假設動態轉換概率p更新一次的執行時間為t4，自適應慣性權重更新一次的執行時間為t5，變異個體更新一次的執行時間為t6，蝴蝶個體更新階段產生當前最優個體的時間為t7，得到當前最優個體與全局最優個體進行比較的時間為t8，如果當前最優個體比全局最優個體更好則替換掉，所需時間為t9，則時間復雜度為O（N（t3n+t4n+t5n+f（n）+t6n+t7n+t8+t9n））=O（n+f（n））。比較當前最優個體與全局最優個體的執行時間是t8，替換全局最優個體的執行時間是t9，因此記錄ABOA-MS算法最優個體的時間復雜度為O（N（t8+t9n））=O（n）。最后，對于每一代產生最優個體的時間復雜度為：T（n）=2O（n+f（n））+O（n）=O（n+f（n））。因此，與BOA相比，ABOA-MS的時間復雜度并未增加。

3 仿真實驗

本仿真實驗測試環境為：操作系統Windows 10，CPU為Intel CoreTM i5-4210U，主頻1.7 GHz，內存為8 GB，仿真軟件為MATLAB 2019b。本文通過12個基準測試函數對改進算法ABOA-MS的優化性能進行評價，其中測試函數分為不同的類別：第一類是檢驗算法收斂性能的單峰函數：F1～F7；第二類是檢驗全局尋優以及跳出局部最優性能的復雜多峰函數：F8～F12。12個函數的具體表達式如表1所示。

為了全面驗證ABOA-MS改進的有效性，將改進算法ABOA-MS與BOA、PSO［2］、SSA［8］、文獻［16］基于自適應學習的蝴蝶優化算法（learning automata based butterfly optimization algorithm，LABOA）、文獻［25］基于自適應擾動的瘋狂蝴蝶算法（crazy improve butterfly optimization algorithm，CIBOA）、郊狼優化算法（coyote optimization algorithm，COA） ［26］、灰狼優化算法（grey wolf optimizer，GWO）［27］，共八種算法進行對比實驗。為保證實驗的公平性與有效性，仿真實驗中，各算法初始種群和迭代次數統一設置為30和500，其余參數則采用相應文獻中推薦設置，詳見表2。

3.1 ABOA-MS與BOA的性能比較

表3是兩種算法在12個測試函數上獨立運行30次的實驗結果。空間維度設為30，評價標準有最優值、最差值、平均值、標準差、運行時間，表中最優結果用黑體標出。

在解決極小值問題時，平均值可以反映算法的尋優能力與收斂精度，標準差可以反映算法的魯棒性，最優值與最差值可以反映算法可行解的質量，運行時間可以反映算法的效率。由表3可知，ABOA-MS的整體尋優能力比BOA明顯增強。從算法取得的最優值來看，12個函數中有9個函數均尋到理論最優值0，且ABOA-MS可行解的質量較高，這說明在ABOA-MS中全局探索階段引入的自適應慣性權重策略有效保持了種群多樣性，提升了全局尋優能力，進而獲取了更好的最優解；從算法取得的平均值來看，在單峰函數F1、F2、F4～F7，多峰函數F9、F11、F12上，ABOA-MS的平均值均為0，F8和F10雖然沒有明顯的提高，但相比基本算法BOA還是有進步趨勢，這說明ABOA-MS的局部變異策略通過混沌記憶權重因子保持了算法局部搜索過程的多樣性，利用全局最優解的引導作用不僅加快了算法的收斂速度，也進一步增強了算法后期的精細搜索質量；從算法取得的標準差來看， ABOA-MS的結果明顯優于BOA，除了F3、F10兩個函數，剩余10個測試函數的值均為0，這表明ABOA-MS的動態轉換概率平衡了算法全局探索與局部搜索的尋優能力，整個搜索過程保持了較強的魯棒性；從算法取得的運行時間來看，ABOA-MS因為更多算子的加入增加

了工作量，但由于局部變異策略的引入一定程度上加快了收斂速度，所以ABOA-MS相較于BOA耗時略微增加，但仍在可接受的范圍內。

3.2 ABOA-MS與BOA改進算法及其他算法的比較

表4是八種算法在12個測試函數上獨立運行50次的結果，空間維度為30，評價標準為平均值與標準差。其中“-”表示參考文獻未給出相應數據，最優結果用黑體表示。

由表4可以看出，在單峰函數F1、F2、F4、F5、F6、 F7，多峰函數F9、F11、F12中，ABOA-MS的平均值均取得了最優解0，相較于其余七種算法，ABOA-MS的收斂精度與可行解質量明顯較佳。其中，在連續凸狀幾乎沒有局部極小值的函數F2上，COA、SSA、PSO效果最差，BOA、LABOA、GWO稍微強些，但是均未取到最優值，只有ABOA-MS找到了理論最優值0。由于函數F8存在許多局部極值點，算法在求解過程中很難跳出局部最優，但改進后的ABOA-MS在求解精度上比BOA增加了七個數量級。同樣為改進算法的CIBOA尋優結果相對較佳，但是該算法在函數F4、F5、F6上并沒有尋到最優值，故相比ABOA-MS在12個測試函數上尋到了九個最優解， ABOA-MS的尋優效果更佳。同理，分析標準差結果可知，改進后的ABOA-MS在10個測試函數上均為0，說明算法在迭代過程中整體波動小，相較于其余七種算法穩定性較好。

綜上分析可得，八種算法的性能排名分別是ABOA-MS、CIBOA、GWO、LABOA、BOA、PSO、SSA、COA。通過ABOA-MS尋優精度的表現，充分證明了改進算法的有效性，最終可以得出，改進算法ABOA-MS不僅保持了種群多樣性、加快了收斂速度，并且實現了局部搜索和全局探索的平衡，降低了算法陷入局部最優的概率，進一步提高了算法的優化精度。

3.3 ABOA-MS與BOA、GWO、PSO、SSA、COA收斂曲線比較

為更直觀地體現各算法的尋優性能，利用六種算法在測試函數上進行收斂性測試，通過收斂曲線的情況對算法進行評價。各算法的平均收斂曲線圖如圖5所示，為方便區分曲線間的差異，將測試函數的適應度值設置為對數形式。

從圖5收斂曲線可以看出，在單峰函數中，對于F1、F2、F5、F7，ABOA-MS在迭代200次左右尋到了理論最優值0，其他五種算法均在ABOA-MS的上方，適應度值波動較小，迭代近500次仍未向最優值靠近。對于F6，當自變量趨近于無窮大時，函數會形成大量局部極值區域，但是改進算法ABOA-MS的收斂曲線平滑且均勻，且收斂曲線始終處于BOA、GWO、PSO、SSA、COA算法下方，以上結果表明因為自適應慣性權重策略的引入，種群在搜索空間保持了良好的多樣性，使得 ABOA-MS在多個函數上收斂精度較高，具有較強的優化能力。在多峰函數中，對于具有許多局部最小值，易陷入局部最優的函數F8而言，ABOA-MS在迭代20次左右已求得最優解并且繼續保持勘探狀態。

對于F9、F11、F12，較BOA、GWO、PSO、SSA、COA算法，ABOA-MS的收斂速度與尋優精度效果更為顯著，收斂曲線始終位于最下方，約在迭代10次左右已經尋到理論最優值0，表明由于動態調整轉換概率策略與局部變異策略的引入，算法在運行中全局探索與局部搜索隨著迭代次數可以進行動態調整，局部搜索階段又因為最優個體的引導，不僅防止算法陷入局部最優，同時很大程度上提高了收斂速度以及收斂精度。對于F10，ABOA-MS的收斂效果相對較弱，僅比基本BOA高出了一個數量級的優化效果，但是從整體上看，ABOA-MS在其余11個函數中收斂效果均較強。綜合對比，較基本BOA及其他智能優化算法，本文ABOA-MS算法收斂速度更快，穩定性更強，優化精度更高。

3.4 ABOA-MS在高維情況下與BOA、CIBOA比較

為進一步測試改進算法在優化高維函數時的性能，將BOA、CIBOA和ABOA-MS算法對12個測試函數分別在50維和100維的情況下獨立運行50次，并記錄平均值與標準差進行比較，“-”表示參考文獻未給出相應數據，最優結果用黑體表示。實驗結果如表5所示。

由表5實驗數據可得，在高維度50和100的情況下，與BOA和CIBOA相比，改進算法ABOA-MS在九個基準測試函數中全部尋找到了理論最優值0。表中可見ABOA-MS算法的可行解質量和穩定性均為最優，CIBOA算法次之。在函數F4、F5、F6上，CIBOA算法的平均值為4.35E-78、8.40E-165、2.82E-07，與全部找到最優值的ABOA-MS算法相比還是略有欠佳。對于函數F3和F8而言，雖然 ABOA-MS無法尋到理論最優值0，但平均值相比BOA分別提高了五個和七個數量級。因此可以說明，ABOA-MS在復雜高維的情況下優化精度和穩定性能較強，可以有效地應用于高維復雜的優化問題中，對比其他算法具有明顯優勢。

4 結束語

針對基本蝴蝶優化算法尋優精度低、收斂速度慢、易陷入局部最優等缺陷，本文提出了一種融合變異策略的自適應蝴蝶優化算法，主要研究工作有：a）通過將轉換概率改進為逐漸遞減，使算法在迭代中后期可以更好地進行精細化搜索，有效平衡了算法全局探索與局部搜索能力；b）通過引入自適應權重因子增強種群多樣性，提高了全局搜索范圍內發現最優解的概率，避免算法早熟收斂，進而更好地平衡了算法全局探索與局部搜索能力；c）通過將改進的變異策略引入到局部搜索階段，使算法在局部求解過程利用全局最優解的引導，防止陷入局部極值，加快收斂速度的同時提高了算法的局部搜索能力和求解精度；d）通過在12個測試函數上對改進算法進行驗證，結果顯示ABOA-MS具有收斂速度快、穩定性強、求解精度高、能及時跳出局部最優等優點。這僅是對算法的多種策略改進研究，未來將進一步研究ABOA-MS在工業領域的拓展及應用。

參考文獻：

[1]Kennedy J， Eberhart R. Particle swarm optimization［C］//Proc of IEEE International Conference on Neural Networks.Piscataway，NJ：IEEE Press，2002：1942-1948.

［2]Storn R， Price K. Differential evolution—a simple and efficient he-uristic for global optimization over continuous spaces［J］.Journal of Global Optimization，1997，11（4）：341-359.

［3]Karaboga D， Basturk B. A powerful and efficient algorithm for nume-rical function optimization： artificial bee colony （ABC） algorithm［J］.Journal of Global Optimization，2007，39（3）：459-471.

［4]Yang Xinshe， Deb S. Cuckoo search via Lévy flights［C］//Proc of World Congress on Nature amp; Biologically Inspired Computing.Pisca-taway，NJ：IEEE Press，2009：210-214.

［5]Bansal J C， Sharma H， Jadon S S， et al. Spider monkey optimization algorithm for numerical optimization［J］.Memetic Computing，2014，6（1）：31-47.

［6]Askarzadeh A. A novel metaheuristic method for solving constrained engineering optimization problems： crow search algorithm［J］.Computers amp; Structures，2016，169：1-12.

［7]Sayed G I， Khoriba G， Haggag M H. A novel chaotic salp swarm algorithm for global optimization and feature selection［J］.Applied Intelligence，2018，48（3）：3462-3481.

［8]Arora S， Singh S. Butterfly optimization algorithm： a novel approach for global optimization［J］.Soft Computing，2018，23（3）：715-734.

［9]Sadeghian Z， Akbari E， Nematzadeh H. A hybrid feature selection method based on information theory and binary butterfly optimization algorithm［J］.Engineering Applications of Artificial Intelligence，2021，97：104079.

［10]Arora S， Singh S， Yetilmezsoy K. A modified butterfly optimization algorithm for mechanical design optimization problems ［J］.Journal of the Brazilian Society of Mechanical Sciences amp; Engineering，2018，40（21）：1-17.

［11]崔東文.改進蝴蝶優化算法—投影尋蹤模型在區域河長制考核評價中的應用［J］.三峽大學學報：自然科學版，2019，41（5）：12-18.（Cui Dongwen. Application of improved butterfly optimization algorithm-projection pursuit model to regional river chief system［J］.Journal of China Three Gorges University： Natural Sciences，2019，41（5）：12-18.）

［12]Wen L， Cao Y. A hybrid intelligent predicting model for exploring household CO2 emissions mitigation strategies derived from butterfly optimization algorithm［J］.Science of the Total Environment，2020，727：138572.

［13]Hu Kun， Jiang Hao， Ji Chenguang， et al. A modified butterfly optimization algorithm： an adaptive algorithm for global optimization and the support vector machine［J］.Expert Systems，2020，38（3）：12642.

［14]Ustun D. An enhanced adaptive butterfly optimization algorithm rigo-rously verified on engineering problems and implemented to ISAR image motion compensation［J］.Engineering Computations，2020，37（9）：3543-3566.

［15]Zhang Mengjian， Long Daoyin， Qin Tao， et al. A chaotic hybrid butterfly optimization algorithm with particle swarm optimization for high-dimensional optimization problems［J］.Symmetry，2020，12（11）：1800.

［16]Arora S， Anand P. Learning automata based butterfly optimization algorithm for engineering design problems［J］.International Journal of Computational Materials Science and Engineering，2018，7（4）：1-28.

［17]陳俊，何慶.基于余弦相似度改進的蝴蝶優化算法［J］.計算機應用，2021，41（9）：2668-2677.（Chen Jun， He Qing. Improved butterfly optimization algorithm based on cosine similarity［J］.Journal of Computer Applications，2021，41（9）：2668-2677.

［18]王依柔，張達敏.融合正弦余弦和無限折疊迭代混沌映射的蝴蝶優化算法［J］.模式識別與人工智能，2020，33（7）：660-669.（Wang Yirou， Zhang Damin. Butterfly optimization algorithm combining sine cosine and infinite folding iterative chaotic mapping［J］.Pattern Re-cognition and Artificial Intelligence，2020，33（7）：660-669.）

［19]鄭洪清.改進的蝴蝶優化聚類算法［J］.計算機系統應用，2020，29（10）：217-221.（Zheng Hongqing. Improved butterfly optimization algorithm for clustering［J］.Computer Systems amp; Applications，2020，29（10）：217-221.）

［20]肖婧，許小可，張永健，等.差分進化算法及其高維多目標優化應用［M］.北京：人民郵電出版社，2018：29-31.（Xiao Jing， Xu Xiao-ke， Zhang Yongjian， et al. Differential evolution algorithm and its application in multi-objective optimization［M］.Beijing：Posts amp; Telecom Press，2018：29-31.）

［21]Sharifi M B， Georgakakos K P， Rodrigueziturbe I. Evidence of deterministic chaos in the pulse of storm rainfall［J］.Journal of the Atmospheric Sciences，2010，47（7）：888-893.

［22]周歡，李煜.具有動態慣性權重的布谷鳥搜索算法［J］.智能系統學報，2015，10（4）：645-651.（Zhou Huan， Li Yu. Cuckoo search algorithm with dynamic inertia weight［J］.CAAI Trans on Intelligent Systems，2015，10（4）：645-651.）

［23]劉小娟，王聯國.一種基于差分進化的正弦余弦算法［J］.工程科學學報，2020，42（12）：1674-1684.（Liu Xiaojuan， Wang Lianguo. A sine cosine algorithm based on differential evolution［J］.Chinese Journal of Engineering，2020，42（12）：1674-1684.）

［24]張永韡，汪鐳，吳啟迪.動態適應布谷鳥搜索算法［J］.控制與決策，2014，29（4）：617-622.（Zhang Yongwei， Wang Lei， Wu Qidi. Dynamic adaptation cuckoo search algorithm［J］.Control and Decision，2014，29（4）：617-622.）

［25]王依柔，張達敏，徐航，等.基于自適應擾動的瘋狂蝴蝶算法［J］.計算機應用研究，2020，37（11）：3276-3280.（Wang Yirou， Zhang Damin， Xu Hang， et al. Crazy butterfly algorithm based on adaptive perturbation［J］.Application Research of Computers，2020，37（11）：3276-3280.）

［26]Nguyen T T， Nguyen T T， Nguyen N A， et al. A novel method based on coyote algorithm for simultaneous network reconfiguration and distribution generation placement［J］.Ain Shams Engineering Journal，2021，12（1）：665-676.

［27]Teng Zhijun， Lyu Jinling， Guo Liwen. An improved hybrid grey wolf optimization algorithm［J］.Soft Computing，2019，23（15）：6617-6631.