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

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

0 引 言

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

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

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

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

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

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

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

(2)所有的蝴蝶個(gè)體都會(huì)隨機(jī)或向發(fā)出最多香味的最優(yōu)蝴蝶移動(dòng)[10]。

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

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

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

fi=cIa

(1)

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

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

(2)

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

(3)

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

2.1 收斂因子

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

a=2-t/tmax

(4)

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

改進(jìn)后全局位置更新公式如下

(5)

2.2 黃金正弦指引機(jī)制

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

(6)

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

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

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

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

步驟4 如果概率p

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

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

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

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

圖1 AGSABOA算法的流程

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

3.1 仿真實(shí)驗(yàn)環(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í)驗(yàn)參數(shù)設(shè)置

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

3.3 測(cè)試函數(shù)

為驗(yàn)證改進(jìn)算法的有效性，本文選取9個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)。表1給出本文選取測(cè)試函數(shù)的基本信息。

表1 測(cè)試函數(shù)

3.4 實(shí)驗(yàn)結(jié)果分析

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

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

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

表2(續(xù))

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

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

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

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

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

4 結(jié)束語(yǔ)

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