基于Tent映射的改進(jìn)型人工蜂群算法

王賀琦，王 然，劉詩琳，唐浩桁，馬云鵬

(天津商業(yè)大學(xué)信息工程學(xué)院，天津 300134)

384410733@qq.com;kad2001628@163.com;1595996480@qq.com;tanghaoheng@163.com;mayunpeng@tjcu.edu.cn

1 引言(Introduction)

群體智能(Swarm Intelligence)是指具有簡(jiǎn)單智能的個(gè)體通過相互協(xié)作和組織表現(xiàn)出群體智能行為的特性，具有天然的分布式和自組織特征。無論外界環(huán)境如何變化，蜜蜂總能找到蜜源和巢穴，對(duì)外界環(huán)境變化具有很好的適應(yīng)性。蜜蜂屬于群居性昆蟲，其行為目標(biāo)簡(jiǎn)單明確，各司其職，可以高效快速地找到蜜源。當(dāng)外界環(huán)境變化時(shí)，蜜蜂可以靈活地調(diào)整勞動(dòng)分工，如減少或增加采蜜的工蜂。針對(duì)以上現(xiàn)象和行為，文獻(xiàn)[3]提出了ABC算法，并將其應(yīng)用于函數(shù)的數(shù)值優(yōu)化問題上，且取得良好的效果。類比自然界中的蜜蜂采蜜行為，ABC算法是將各蜜蜂的初始位置定義為搜索空間的初始點(diǎn)；把蜜蜂的進(jìn)化和覓食行為模擬為種群個(gè)體更新機(jī)制；將蜜蜂對(duì)環(huán)境的適應(yīng)性類比為解的適應(yīng)度函數(shù)值；將蜜源的質(zhì)量作為目標(biāo)函數(shù)值。根據(jù)以上分析，ABC算法屬于一種啟發(fā)式迭代優(yōu)化算法。

ABC算法具有控制參數(shù)少、全局優(yōu)化能力強(qiáng)的優(yōu)點(diǎn)，引起國內(nèi)外研究學(xué)者的廣泛關(guān)注，并將其成功應(yīng)用于各個(gè)領(lǐng)域。然而，ABC算法仍存在一些不足，如局部搜索能力差、收斂精度低、收斂速度慢等。針對(duì)上述不足，文獻(xiàn)[4]提出了分段式蜜源搜索半徑公式，提高了算法的收斂精度和收斂速度，并采用改進(jìn)的ABC算法對(duì)徑向基神經(jīng)網(wǎng)絡(luò)的初始參數(shù)進(jìn)行優(yōu)化。文獻(xiàn)[5]針對(duì)傳統(tǒng)ABC算法收斂速度慢的問題，引入自適應(yīng)參數(shù)，加快了算法的后期收斂能力，實(shí)驗(yàn)結(jié)果表明改進(jìn)的算法收斂能力更強(qiáng)，收斂速度更快。文獻(xiàn)[6]在ABC算法的跟隨蜂階段，使種群依概率進(jìn)行反向?qū)W習(xí)代替跟隨蜂搜索方式，雇傭蜂和偵察蜂階段用以保證種群的探索能力以及種群的多樣性。文獻(xiàn)[7]運(yùn)用最大最小距離積法處理初始蜜源，將K均值聚類算法與ABC算法相結(jié)合，提高了ABC算法的收斂速度，具有較好的解適應(yīng)度。ZHU等人改進(jìn)ABC算法的搜索模式來提高局部搜索能力，提出改進(jìn)的ABC算法。文獻(xiàn)[9]將交叉機(jī)制與全局最優(yōu)解信息融入ABC算法，增強(qiáng)了ABC算法的開發(fā)能力和探索能力。曾志文等人提出一種雙種群架構(gòu)ABC算法，將交叉變異操作和最優(yōu)解鄰域搜索融入不同種群，提高了算法的尋優(yōu)能力。

為進(jìn)一步提高ABC算法的性能，本文提出一種改進(jìn)的ABC算法(Modified Artificial Bee Colony，MABC)。首先，分別采用Tent混沌映射函數(shù)和反向?qū)W習(xí)機(jī)制初始化種群個(gè)體的位置，使初始解在搜索空間中的分布更加均勻，以增強(qiáng)種群的多樣性，有助于提高算法的全局搜索能力；然后，在雇傭蜂階段，將分組機(jī)制和慣性權(quán)值引入種群個(gè)體的更新機(jī)制中，以提高算法的收斂精度和平衡算法的探索能力與開發(fā)能力。

為驗(yàn)證MABC算法的有效性，本文應(yīng)用13 個(gè)基準(zhǔn)數(shù)學(xué)函數(shù)對(duì)MABC算法的收斂精度和全局搜索能力等性能進(jìn)行測(cè)試。與原始ABC算法對(duì)比，實(shí)驗(yàn)結(jié)果表明MABC算法具有良好的收斂速度和收斂精度。

2 ABC算法簡(jiǎn)介(Introduction to ABC algorithm)

在標(biāo)準(zhǔn)ABC算法中，有三種角色：引領(lǐng)蜂、跟隨蜂、偵察蜂。引領(lǐng)蜂又稱為雇傭蜂，跟隨蜂和偵查蜂被稱為非雇傭蜂。ABC算法的搜索過程簡(jiǎn)要描述如下：首先，所有蜜蜂都是偵查蜂，在整個(gè)解空間隨機(jī)搜索。當(dāng)偵查蜂搜索到蜜源后，將蜜源質(zhì)量信息帶回蜂巢與其他蜜蜂共享，對(duì)偵察蜂帶回的所有信息進(jìn)行比較。當(dāng)該蜜源的質(zhì)量排名靠前時(shí)，該偵查蜂就轉(zhuǎn)變?yōu)橐I(lǐng)蜂，蜜源和引領(lǐng)蜂一一對(duì)應(yīng)，另外招募到一些跟隨蜂到引領(lǐng)蜂所在的蜜源附近搜索新的蜜源；當(dāng)蜜源的質(zhì)量排名居中時(shí)，該偵查蜂就轉(zhuǎn)變?yōu)楦S蜂，然后根據(jù)一定的規(guī)則選擇引領(lǐng)蜂，到引領(lǐng)蜂對(duì)應(yīng)的蜜源附近進(jìn)行搜索；當(dāng)該蜜源的質(zhì)量排名靠后時(shí)，該偵查蜂就放棄已經(jīng)搜索到的蜜源，再次成為偵查蜂，在整個(gè)區(qū)域進(jìn)行新一輪的隨機(jī)搜索。

ABC算法在求解優(yōu)化問題時(shí)，蜜源的位置代表優(yōu)化問題的可行解，蜜源的質(zhì)量代表優(yōu)化問題的值，尋找蜜源的過程就是優(yōu)化問題的過程，蜜源的最大質(zhì)量即優(yōu)化問題的最優(yōu)解。在整個(gè)算法中，引領(lǐng)蜂和跟隨蜂是為了加快算法的收斂，偵察蜂主要負(fù)責(zé)跳出局部最優(yōu)解。

在該算法中，控制參數(shù)的設(shè)置能有效平衡全局搜索與局部搜索。如果引領(lǐng)蜂在其蜜源鄰域搜索次數(shù)達(dá)到最大未更新次數(shù)時(shí)，仍沒有找到適應(yīng)度值更高的新解，表明這個(gè)解為局部最優(yōu)值，就放棄該蜜源；然后，根據(jù)式(1)再次隨機(jī)初始化該引領(lǐng)蜂的位置。

3 MABC算法(MABC algorithm)

3.1 初始解產(chǎn)生方式的改進(jìn)

3.2 種群個(gè)體更新機(jī)制的改進(jìn)

在原始ABC算法中，是[-1,1]之間的一個(gè)隨機(jī)數(shù)。解更新操作對(duì)原個(gè)體的影響較小，保留了很多特征到新解，極大影響了種群收斂的速度和精度。另一方面，系數(shù)是一個(gè)隨機(jī)數(shù)，不能動(dòng)態(tài)地、自適應(yīng)地改變搜索步長(zhǎng)，造成了原始ABC算法隨機(jī)性大的缺陷。本文采用一種新雇傭蜂更新機(jī)制，其基本思想如下：每次迭代更新前，找出當(dāng)前解中最優(yōu)秀的解向量，讓較差解向最優(yōu)解學(xué)習(xí)，讓雇傭蜂根據(jù)式(7)進(jìn)行更新，以便較快地提高算法的收斂精度和收斂速度。隨著種群迭代的進(jìn)行，在算法前期，較差解向最優(yōu)解加速靠攏；在算法后期，較差解在其周圍鄰域內(nèi)搜索。此外，引入慣性權(quán)值，如式(8)所示。慣性權(quán)值是非線性收斂因子調(diào)整策略，它是逐級(jí)遞增的，前期距離控制參數(shù)較大，保證較少的特性遺留到下一代，搜索范圍較大，因此有利于全局尋優(yōu)；在迭代后期距離控制參數(shù)大，較多保留了上一代優(yōu)秀解的特性，在優(yōu)秀解附近進(jìn)行精細(xì)搜索，有利于局部尋優(yōu)，能夠有效平衡算法的全局搜索能力和局部搜索能力。三角函數(shù)權(quán)值系數(shù)也有助于提高算法的運(yùn)行速度和全局搜索能力。

4 MABC算法的性能測(cè)試(Performance test of MABC algorithm)

為驗(yàn)證MABC算法的性能，本文選用13 個(gè)經(jīng)典數(shù)學(xué)函數(shù)集測(cè)試MABC算法的收斂速度和收斂精度。表1給出13 個(gè)函數(shù)的詳細(xì)描述，包括函數(shù)表達(dá)式、解的取值范圍、最優(yōu)點(diǎn)的位置及最優(yōu)值等。在表1中，F(xiàn)1—F7為單峰函數(shù)，用于測(cè)試MABC算法的收斂精度和求解能力；F8—F13為多峰函數(shù)，用于驗(yàn)證MABC算法的全局搜索能力。本文將MABC算法與原始ABC算法進(jìn)行對(duì)比，兩種算法的相關(guān)設(shè)置參數(shù)如表2所示。為驗(yàn)證算法的穩(wěn)定性和對(duì)比公平性，每個(gè)算法獨(dú)立運(yùn)行20 次，每次迭代1,000 次，分別測(cè)試每個(gè)函數(shù)10 維、30 維、50 維的函數(shù)值，并求20 次最優(yōu)函數(shù)值的平均值和均方差，實(shí)驗(yàn)結(jié)果記錄于表3。平均值和均方差越小，說明算法的收斂精度和穩(wěn)定性越好。表3中加粗的字體表示最優(yōu)性能參數(shù)。本文采用的實(shí)驗(yàn)設(shè)備為：64 位MateBook X Pro 2019款筆記本；處理器型號(hào)為：Intel(R) Core(TM) i5-8265U CPU @1.60 GHz 1.80 GHz；運(yùn)行內(nèi)存為8.00 GB；仿真軟件為：MATLAB 2014b。由表3可知，相較于ABC算法，MABC算法在F1、F2、F3、F4、F7、F9、F10、F11、F12等9 個(gè)函數(shù)上取得更小的最優(yōu)解的平均值和均方根誤差，說明MABC算法具有良好的收斂精度和穩(wěn)定性。雖然ABC算法在F5、F6、F8及F13等4 個(gè)函數(shù)上表現(xiàn)出較好的收斂精度和穩(wěn)定性，但兩種算法在收斂精度上差距不大。

表1 經(jīng)典測(cè)試函數(shù)集Tab.1 Classic test function set

表2 初始參數(shù)設(shè)置Tab.2 Initial parameter setting

表3 測(cè)試結(jié)果Tab.3 Test results

為了更加直觀地對(duì)比MABC算法與ABC算法的收斂性，圖1—圖8分別給出部分函數(shù)在兩個(gè)算法中某個(gè)維度的仿真圖，其中MABC算法用虛線表示，ABC算法用實(shí)線表示。由8個(gè)仿真圖可知，無論是單峰函數(shù)還是多峰函數(shù)，MABC算法的收斂速度和收斂精度明顯優(yōu)于原始ABC算法。綜上所述，MABC算法具有良好的收斂速度和全局搜索能力。

圖1 F1=10適應(yīng)度值對(duì)比Fig.1 Comparison of fitness value of F1 with dim=10

圖2 F2=30適應(yīng)度值對(duì)比Fig.2 Comparison of fitness value of F2 with dim=30

圖3 F5=50適應(yīng)度值對(duì)比Fig.3 Comparison of fitness value of F5 with dim=50

圖4 F7=30適應(yīng)度值對(duì)比Fig.4 Comparison of fitness value of F7 with dim=30

圖5 F8=30適應(yīng)度值對(duì)比Fig.5 Comparison of fitness value of F8 with dim=30

圖6 F9=50適應(yīng)度值對(duì)比Fig.6 Comparison of fitness value of F9 with dim=50

圖7 F10=30適應(yīng)度值對(duì)比Fig.7 Comparison of fitness value of F10 with dim=30

圖8 F13=50適應(yīng)度值對(duì)比Fig.8 Comparison of fitness value of F13 with dim=50

5 結(jié)論(Conclusion)

為進(jìn)一步提升ABC算法的性能，分別對(duì)ABC算法的種群個(gè)體初始化方式和雇傭蜂階段的種群個(gè)體更新機(jī)制進(jìn)行改進(jìn)。應(yīng)用Tent混沌映射函數(shù)和反向?qū)W習(xí)機(jī)制對(duì)種群個(gè)體的位置進(jìn)行初始化，增強(qiáng)了初始個(gè)體在解空間的均勻分布性，提高了種群個(gè)體多樣性。在雇傭蜂階段，引入新型慣性權(quán)值和改進(jìn)種群個(gè)體更新機(jī)制，有利于提高收斂速度和平衡算法的全局探索能力及局部開發(fā)能力。通過13 個(gè)基準(zhǔn)測(cè)試函數(shù)的驗(yàn)證，實(shí)驗(yàn)結(jié)果顯示MABC算法具有良好的收斂速度和全局搜索能力。