收斂因子和黃金正弦指引機制的蝴蝶優(yōu)化算法

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

(上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620)

0 引 言

蝴蝶優(yōu)化算法(butterfly optimization algorithm，BOA)[1]模擬自然界中的蝴蝶采食花蜜的行為。BOA算法調(diào)節(jié)參數(shù)少，原理簡單，易于實現(xiàn)。BOA算法已經(jīng)成功解決很多問題如：焊接條、壓力器容器、齒輪、輸氣壓縮機和懸臂梁設(shè)計等工程優(yōu)化問題[2]，特征選擇[3]，機器學(xué)習(xí)等。

BOA算法與常見的元啟發(fā)式算法類似，也存在易陷入局部最優(yōu)值(多模態(tài)函數(shù)的鞍點位置)，迭代后期的收斂速度變緩慢，尋優(yōu)精度低等元啟發(fā)式算法常見的缺陷。許多學(xué)者提出了改進策略。參考文獻[4]將自適應(yīng)學(xué)習(xí)機制引入BOA算法中平衡了全局搜索和局部開采的權(quán)重，但是增加了時間復(fù)雜度；文獻[5]將萊維飛行策略引入全局和局部位置更新處，但改進后移動策略仍較為單一使群體多樣性比較低，并未改善BOA算法易陷入鞍點位置的問題；文獻[6]提出了一種基于動態(tài)感覺模態(tài)變化的蝴蝶優(yōu)化算法提升了算法的局部開采和全局搜索能力，該策略針對感覺模態(tài)參數(shù)進行優(yōu)化，沒有從根本上優(yōu)化蝴蝶個體位置更新方式，尋優(yōu)能力差，并未顯著提高BOA算法的收斂性能。

在BOA算法中，全局位置更新是通過向散發(fā)香味最濃的蝴蝶方向飛行，局部位置更新則是通過蝴蝶個體隨機游走，即位置更新具有全局探索能力強而局部開采能力弱的缺陷。針對以上不足，本文提出了改進的個體位置更新方式，受鯨魚優(yōu)化算法(WOA)[7]的啟發(fā)將收縮包圍機制中的收斂因子a引入全局位置更新處以協(xié)調(diào)算法的探索和開發(fā)能力，提高收斂精度；將黃金正弦算法(GSA)[8]作為一種局部算子融入BOA算法中促進信息在種群內(nèi)部快速傳播加快個體間信息交流，彌補迭代后期算法的收斂速度慢，種群多樣性下降等問題，加快算法跳出局部最優(yōu)。

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

蝴蝶優(yōu)化算法是通過模擬蝴蝶進行覓食(花蜜)和繁衍行為而衍生出的一種仿生智能算法，其具體的定義可以參考文獻[9]中的論述。

針對蝴蝶的行為，我們提出如下假設(shè)：

(1)每只蝴蝶個體都能散發(fā)出香味，使蝴蝶個體在接收到來自空氣中的香味時能夠相互吸引。

(2)所有的蝴蝶個體都會隨機或向發(fā)出最多香味的最優(yōu)蝴蝶移動[10]。

(3)蝴蝶個體產(chǎn)生的刺激強度這一參數(shù)受目標函數(shù)的影響或決定。

(4)蝴蝶搜索的局部搜索更新和全局位置開采更新使用轉(zhuǎn)換概率p進行控制，受到物理的因素以及雨、風(fēng)、雷電等各種其它自然因素，局部搜索和全局位置更新中的參數(shù)p具有重要意義。

蝴蝶個體在覓食求偶過程中產(chǎn)生的香味濃度的公式如下

fi=cIa

(1)

fi是第i只蝴蝶個體感知香味的強度，c是一個蝴蝶個體感官模態(tài)參數(shù)，I是受到其它蝴蝶散發(fā)的香味的刺激強度參數(shù)，a是取決于感官模態(tài)的冪指數(shù)參數(shù)，它的大小取決于香味的吸收程度。

在BOA算法的全局探索階段，每只蝴蝶朝著最優(yōu)的蝴蝶/解g*移動。用式(2)表示

(2)

在局部開采過程中，每只蝴蝶的位置更新公式如式(3)

(3)

2 融合收斂因子和黃金正弦指引機制的蝴蝶優(yōu)化算法

2.1 收斂因子

為進一步增強BOA算法的探索能力和提高收斂精度，受到鯨魚優(yōu)化算法的啟發(fā)，將鯨魚優(yōu)化算法中非線性收斂因子a引入基本蝴蝶優(yōu)化算法的全局位置更新處，希望迭代前期a值較大以增強全局勘探能力且遞減速度較快，而迭代后期a值收斂到較小值且遞減速度變緩慢，以實現(xiàn)前期快速收斂，提高算法后期的收斂精度。a隨著迭代次數(shù)的增加由2減小到0。公式如下

a=2-t/tmax

(4)

式中：t是當前迭代次數(shù)，tmax是最大迭代次數(shù)。

改進后全局位置更新公式如下

(5)

2.2 黃金正弦指引機制

黃金正弦算法(golden sine algorithm，Golden-SA)[8]是Tanyildizi提出的新型元啟發(fā)式算法。根據(jù)正弦函數(shù)定義中與單位圓的關(guān)系，遍歷單位圓上所有正弦值的行為與優(yōu)化算法中搜索代理在搜索空間中進行尋優(yōu)的原理是一致的，受此啟發(fā)產(chǎn)生了黃金正弦算法。在該算法中，創(chuàng)建隨機個體的數(shù)量與每個具有均勻分布的搜索代理的數(shù)量相同。與其它元啟發(fā)式方法相比，Gold-SA具有更少的依賴于算法的參數(shù)和運算符，Gold-SA算法通過使當前解空間更接近目標值的方式來搜索以在每次迭代中得到更好的搜索空間，搜索空間被黃金比例系數(shù)縮小以便獲得更小的解空間而不是整個解空間，從而有效提升尋優(yōu)速度。黃金正弦算法的具體定義及推導(dǎo)過程請參考文獻[8,11,12]。

(6)

本文將黃金正弦算法作為局部算子融入基本BOA中，在迭代后期對整個BOA算法進行黃金正弦優(yōu)化，能夠彌補算法在迭代后期的收斂速度慢，收斂精度不高的缺陷，基本的BOA算法在局部搜索階段采用隨機游走的方式，搜索空間比較廣泛；然而元啟發(fā)式算法的主要目標是探索被認為是最佳搜索空間的區(qū)域，并確保盡可能完整地掃描這些區(qū)域，搜索空間的廣泛性是解決問題的主要問題。在解決問題時縮小搜索空間的效果會顯著影響尋優(yōu)效果，而在Gold-SA算法中的參數(shù)r1和r2能夠有效控制位置更新距離和方向，逐步縮小搜索空間，指引蝴蝶個體迅速向最優(yōu)個體靠近，加快種群中信息交流，降低算法陷入局部最優(yōu)值的可能性，從而提高算法的收斂速度和尋優(yōu)精度。本文提出的融合非線性收斂因子和黃金正弦指引機制的蝴蝶優(yōu)化算法(AGSABOA)的具體步驟如下。

步驟1 初始化種群個數(shù)及初始化主要參數(shù)設(shè)置；

步驟2 根據(jù)香味濃度公式計算每只蝴蝶個體的香味濃度，得到每個個體的初始的適應(yīng)度值，并且求出當前算法的最優(yōu)解；

步驟3 若動態(tài)轉(zhuǎn)換概率p>rand，此時根據(jù)式(5)進行全局開采的更新；

步驟4 如果概率p

步驟5 對步驟4生成的蝴蝶個體進行黃金正弦優(yōu)化，即根據(jù)式(6)進行尋優(yōu)位置更新；

步驟6 計算步驟4和步驟5目標函數(shù)的適應(yīng)度值，若得到的函數(shù)值優(yōu)于前一代的值，則進行更新；

步驟7 重復(fù)上述步驟2～步驟6，當?shù)螖?shù)達到給定值，則停止更新，將最優(yōu)值和最優(yōu)解進行輸出。

AGSABOA的算法流程如圖1所示。

圖1 AGSABOA算法的流程

3 仿真實驗結(jié)果及分析

3.1 仿真實驗環(huán)境

本文的仿真環(huán)境為：操作系統(tǒng)是Windows10，CPU為Intel(R) Core(TM) i5-10210U，主頻率2.11 GHz，內(nèi)存為16 GB，仿真軟件為Matlab2018b[9]。

3.2 仿真實驗參數(shù)設(shè)置

本文選取粒子群算法(SSA)[13]、鯨魚優(yōu)化算法(WOA)、基本蝴蝶優(yōu)化算法(BOA)、融合收斂因子和黃金正弦指引機制的蝴蝶優(yōu)化算法AGSABOA進行對比實驗，由此驗證改進策略的有效性。另外本文還進行了單一策略改進的黃金正弦指引機制的蝴蝶算法(GSABOA)與雙策略改進的AGSABOA進行對比實驗，為了驗證混合策略改進的尋優(yōu)效果更佳。最后，選取文獻[4]、文獻[6]中的幾組數(shù)據(jù)與本文的實驗結(jié)果進行對比，驗證本文針對基本BOA算法的改進方法更優(yōu)秀。為保證實驗結(jié)果的有效性和公平性，本文將所有算法的初始化種群數(shù)均設(shè)置為30，最大迭代次數(shù)設(shè)置為500，所有算法的公有參數(shù)保持一致。BOA、GSABOA、AGSABOA的感官形態(tài)c設(shè)置為0.01，冪指數(shù)a在迭代過程從0.1迭代到0.3，切換概率p=0.8。

3.3 測試函數(shù)

為驗證改進算法的有效性，本文選取9個基準測試函數(shù)進行實驗。表1給出本文選取測試函數(shù)的基本信息。

表1 測試函數(shù)

3.4 實驗結(jié)果分析

表2給出SSA、WOA、BOA、GSABOA、AGSABOA在每個測試函數(shù)上獨立運行30次得到的結(jié)果。LABOA、IBOA的實驗結(jié)果是參考其它文獻所得的結(jié)果。

SSA算法具有收斂速度快，易于實現(xiàn)的特點，WOA算法除了具有較強收斂速度之外，其較SSA算法來說，具有較強的局部搜索能力和較高的收斂精度，所選對比算法均有較強的代表性。從表2實驗結(jié)果可以明顯看出，AGSABOA的尋優(yōu)結(jié)果是明顯優(yōu)于所選對比算法的。表2給出了幾個算法的最優(yōu)精度值、平均精度值、精度標準差，其中最優(yōu)精度值可以展示算法求解的質(zhì)量，平均精度值能夠反應(yīng)在固定迭代次數(shù)的情況下算法能夠收斂的精度，可以反應(yīng)算法的收斂速度；而精度的標準差能夠反應(yīng)算法的魯棒性。從表2中的實驗結(jié)果可以看出函數(shù)f1、f3、f4、f5、f7、f9能夠直接搜索到理論最優(yōu)值，說明改進后的AGSABOA算法具有較好的尋優(yōu)性能。函數(shù)f2是一種連續(xù)的、平滑的多峰函數(shù)，在求解過程中比較容易陷入局部最優(yōu)值，本文的改進算法AGSABOA的收斂精度能夠達到e-168，比基本BOA算法在收斂精度上高出159個數(shù)量級的精度，f6是一種復(fù)雜的爬山形函數(shù)，函數(shù)在狹長的全局極值點周圍擁有很多的局部極值，在算法的迭代過程中很難跳出局部最優(yōu)，改進后的AGSABOA比基本的蝴蝶優(yōu)化算法在尋優(yōu)精度上面提高了9個單位，該函數(shù)主要用以測試算法的收斂速度，從標準差上看，AGSABOA的波動較小，穩(wěn)定性更好。f8具有很強烈的震蕩性，有非常多的局部最優(yōu)值，因此在算法迭代過程中很難求得最優(yōu)值，本文的改進策略在求解精度上面比基本的BOA算法高出155個精度單位，說明本文的改進策略能夠提高BOA算法尋優(yōu)成功的概率。

表2 測試函數(shù)結(jié)果

表2(續(xù))

另外，采用雙策略改進基本的BOA算法，在表2中，本文還給出采用單一的黃金正弦算法進行改進的蝴蝶優(yōu)化算法GSABOA進行的對比實驗，從實驗結(jié)果可以看出，在函數(shù)f5、f7、f9上GSABOA和AGSABOA都能較快收斂到全局最優(yōu)值，對于函數(shù)f1，GSABOA不能收斂到最優(yōu)值，但是比基本的BOA算法在平均收斂精度上面高出100個數(shù)量級；在函數(shù)f2上也提高50個數(shù)量級；在函數(shù)f3、f4高出近200個數(shù)量級；從標準差上面看，AGSABOA的精度要小于GSABOA說明雙策略改進算法的魯棒性和收斂精度更好。雙策略改進的AGSABOA算法是要優(yōu)于GSABOA算法的。在全局位置更新處引入收斂因子，能夠提高算法的收斂精度；GSABOA的結(jié)果也是明顯優(yōu)于對比算法SSA、WOA、BOA，表明本文采用的黃金正弦指引機制能夠促進種群個體之間的信息交流，避免算法陷入局部最優(yōu)值，能夠有效減少BOA算法存在的部分無效迭代，提高了算法的尋優(yōu)速度。

在表2中，本文算法還與文獻[4]中的LABOA、文獻[6]中的IBOA中幾組測試函數(shù)的實驗結(jié)果進行對比，實驗結(jié)果均出自參考文獻之中，因為本文選取測試的函數(shù)與文獻[4]和文獻[6]不完全相同，所以參考文獻中未涉及的測試函數(shù)，在本文表2的對比結(jié)果中未列出。從實驗結(jié)果可以看出，本文的AGSABOA算法在部分測試函數(shù)上面的尋優(yōu)性能是要優(yōu)于LABOA和IBOA的。根據(jù)無免費午餐定理，沒有任何一種算法或者改進策略能夠達到最優(yōu)，但是可以不斷探索更優(yōu)的尋優(yōu)策略，因此AGSABOA算法存在的誤差是可以接受的。

為了進一步驗證本文改進算法的有效性，本文將給出部分測試函數(shù)的收斂曲線，如圖2所示。

從圖2收斂迭代曲線可以直觀看出改進的AGSABOA對陷入局部最優(yōu)值的性能是要優(yōu)于SSA、WOA和BOA算法的。函數(shù)f3、f5、f9的收斂迭代曲線如圖2(b)、圖2(c)和圖2(f)所示能夠快速收斂到最優(yōu)值，其曲線上存在多個拐點，表明改進策略能夠促使算法較快的跳出局部最優(yōu)值；函數(shù)f1和f7的收斂迭代曲線如圖2(a)和圖2(e)所示在300代左右開始迅速下降，并且隨著迭代次數(shù)的增加持續(xù)下降，未出現(xiàn)停滯現(xiàn)象，表明改進算法能夠彌補基本的蝴蝶優(yōu)化算法在迭代后期收斂速度慢的缺陷。函數(shù)f6收斂迭代曲線如圖2(d)所示，表明AGSABOA算法能夠快速收斂到8.88E-16這一精度，驗證本文改進策略的優(yōu)化效果良好。

圖2 測試函數(shù)的收斂迭代曲線

4 結(jié)束語

本文提出了一種融合收斂因子和黃金正弦指引機制的蝴蝶優(yōu)化算法，受到鯨魚優(yōu)化算法的啟發(fā)，將收斂因子融入基本BOA算法的全局位置更新處之中，能夠有效地提升算法的收斂精度，將黃金正弦算法作為一種局部算子融入基本的蝴蝶優(yōu)化算法之中，能夠有效地加快算法跳出局部最優(yōu)，減小BOA算法出現(xiàn)早熟的可能性。下一步的研究內(nèi)容是將AGSABOA應(yīng)用于約束優(yōu)化問題、多目標優(yōu)化和實際工程問題中，提高蝴蝶優(yōu)化算法在實際問題中的應(yīng)用，解決更多的NP-hard問題。