基于Tent混沌映射的可復(fù)制的鯨魚(yú)算法

馬曉寧，李笑含

(中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

1 引言

Mirjalili S[1]等人在2016年提出了一種仿生優(yōu)化算法—鯨魚(yú)優(yōu)化算法(Whale Optimizat-ion Algorithm，WOA)。WOA所需參數(shù)少，算法結(jié)構(gòu)及操作簡(jiǎn)單，然而，算法本身存在易陷入局部最優(yōu)、收斂速度較慢、求解精度低等缺點(diǎn)，因此備受廣大學(xué)者的關(guān)注，并衍生出很多改進(jìn)的算法和應(yīng)用。例如，凌穎[2]為了提高鯨魚(yú)優(yōu)化算法的全局搜索能力，在鯨魚(yú)個(gè)體位置進(jìn)行所有的位置更新后引入Lévy飛行軌跡策略。M. Huang[3]在傳統(tǒng)鯨魚(yú)算法中增加了自適應(yīng)慣性權(quán)重和非線性收斂因子，引入了鯨魚(yú)位置更新中的量子旋轉(zhuǎn)門(mén)的概念。E.Emary[4]基于每個(gè)搜索代理的隨機(jī)游動(dòng)的自適應(yīng)切換，提出了一種最新引入的鯨魚(yú)優(yōu)化算法的變體。黃輝先等人[5]提出基于混沌權(quán)重和精英引導(dǎo)的先進(jìn)鯨魚(yú)優(yōu)化算法(AWOA)。褚鼎立等人[6]通過(guò)改進(jìn)的自適應(yīng)權(quán)重策略來(lái)調(diào)整算法的收斂速度，通過(guò)模擬退火增強(qiáng)鯨魚(yú)優(yōu)化算法的全局尋優(yōu)能力。

混沌優(yōu)化被眾多學(xué)者應(yīng)用于算法中，以提高算法的性能。目前文獻(xiàn)中引用較多的混沌映射是Logistic映射，例如王濤[7]使用改進(jìn)后的Logistic混沌映射來(lái)初始化種群，增加種群多樣性。但單梁等人[8]研究了Tent映射的結(jié)構(gòu)和混沌特性，指出該映射結(jié)構(gòu)簡(jiǎn)單，且迭代過(guò)程適合計(jì)算機(jī)運(yùn)行。并且相對(duì)一些問(wèn)題而言，其運(yùn)算效率要遠(yuǎn)遠(yuǎn)高于 Logistic 映射。趙欣[9]也對(duì)幾種常見(jiàn)混沌映射進(jìn)行了優(yōu)化性能比較，指出Tent映射混沌序列的均勻分布性質(zhì)，可以有效提高算法搜索效率。

本文為提升鯨魚(yú)優(yōu)化算法收斂性能和搜索能力，解決其易出現(xiàn)早熟現(xiàn)象、求解精度低等問(wèn)題，提出了一種新的基于Tent混沌映射的可復(fù)制的鯨魚(yú)優(yōu)化算法(TRWOA)。首先，利用Tent混沌映射生成的隨機(jī)混沌序列，提升初始解的質(zhì)量。然后，為了加快算法的收斂速度，增強(qiáng)其全局搜索能力，引入細(xì)菌覓食優(yōu)化算法的復(fù)制操作，協(xié)調(diào)全局搜索和局部搜索。與以往鯨魚(yú)算法改進(jìn)方法不同，本文首次引入細(xì)菌覓食算法的復(fù)制操作來(lái)提高鯨魚(yú)算法的性能，結(jié)合Tent映射產(chǎn)生的隨機(jī)初始化序列，使得改進(jìn)后的鯨魚(yú)算法性能更優(yōu)。

2 鯨魚(yú)算法

在鯨魚(yú)算法中，每只鯨魚(yú)的位置代表一個(gè)優(yōu)化問(wèn)題的可行解[10]。在鯨魚(yú)群的捕獵過(guò)程中，鯨魚(yú)有兩種捕食行為：一種是包圍獵物，所有的鯨魚(yú)游向其它鯨魚(yú)；另一種是氣泡網(wǎng)捕食，鯨魚(yú)螺旋形游動(dòng)并噴出氣泡來(lái)驅(qū)趕獵物。

2.1 包圍獵物

首先獲得鯨魚(yú)個(gè)體位置與最佳鯨魚(yú)位置之間的距離

(1)

2.2 氣泡網(wǎng)捕食

氣泡網(wǎng)捕食法可描述為如下兩種行為：

1) 搖擺包圍捕食

鯨魚(yú)個(gè)體位置由式(2)更新

(2)

2) 螺旋氣泡網(wǎng)捕食

鯨魚(yú)螺旋上游，同時(shí)吐出氣泡形成起泡網(wǎng)進(jìn)行捕食。數(shù)學(xué)模型如下

(3)

設(shè)鯨魚(yú)用式(2)或式(3)更新位置的概率各為50%。數(shù)學(xué)模型如下

式中，p是[0，1]范圍內(nèi)的隨機(jī)數(shù)。

2.3 隨機(jī)捕食獵物

(5)

3 基于Tent混沌映射的可復(fù)制的鯨魚(yú)算法

為提升WOA的算法性能，有效增強(qiáng)其搜索能力和收斂性能，本文提出了基于Tent 混沌映射的可復(fù)制的鯨魚(yú)優(yōu)化算法(TRWOA)。該算法是利用Tent映射產(chǎn)生初始種群，保證初代鯨魚(yú)群個(gè)體的隨機(jī)性，提升其分布均勻性和多樣性，從而提高初始解的質(zhì)量和求解精度。并在每一次迭代后期，引入細(xì)菌覓食優(yōu)化算法的復(fù)制操作，首先，對(duì)鯨魚(yú)個(gè)體進(jìn)行適應(yīng)度值降序排序，然后淘汰掉適應(yīng)度值差的二分之一鯨魚(yú)，優(yōu)秀的二分之一鯨魚(yú)進(jìn)行復(fù)制，來(lái)增強(qiáng)算法的全局搜索能力。

3.1 Tent混沌映射初始化種群

混沌映射特別適用于優(yōu)化算法的初始化種群，用混沌映射代替隨機(jī)參數(shù)使得算法能夠在搜索空間中生成具有良好多樣性的初始解。高質(zhì)量的初始種群對(duì)算法的收斂速度和求解精度等性能有很大的幫助[11]。

基本的鯨魚(yú)優(yōu)化算法初始化種群采用的是隨機(jī)產(chǎn)生的方法，該方法不僅隨機(jī)性大，而且不能保證初始解的質(zhì)量。為提升初始解的質(zhì)量，利用Tent混沌映射生成的隨機(jī)混沌序列產(chǎn)生初代鯨魚(yú)群。

Tent映射初始化鯨魚(yú)群步驟如下：

步驟1：確定參數(shù)α的值；

步驟2：根據(jù)優(yōu)化問(wèn)題的目標(biāo)函數(shù)設(shè)置初值x0序列的取值范圍，隨機(jī)生成此范圍內(nèi)的X個(gè)值；

步驟3：令X0=x0(n)，n=1，2，…，X；

步驟4：令x(1)=X0，x(n+1)由式(6)計(jì)算獲得

0<α<1

(6)

為保證Tent混沌映射生成的序列有效，α≠0.5，且初值x0和參數(shù)α不能相等。

步驟5：保存x序列，進(jìn)入TRWOA算法主循環(huán)。

3.2 復(fù)制操作階段

細(xì)菌覓食優(yōu)化算法主要包括三層循環(huán)，最外層的遷徙操作，中間層的復(fù)制操作，最內(nèi)層的趨向性操作[12]。復(fù)制操作遵循的是優(yōu)勝劣汰的規(guī)則。在細(xì)菌覓食優(yōu)化算法中，復(fù)制操作后種群規(guī)模不變。覓食一段時(shí)間后，對(duì)細(xì)菌種群的適應(yīng)度進(jìn)行降序排列，把排在后50%細(xì)菌淘汰掉，剩余的一半細(xì)菌進(jìn)行自我復(fù)制，各自生成一個(gè)與自己完全相同的新個(gè)體，即生成的新個(gè)體與原個(gè)體有相同的位置，也就說(shuō)具有相同的覓食能力[13]。

在本文的算法中，鯨魚(yú)經(jīng)過(guò)一次捕食迭代后，每只鯨魚(yú)均在自己相應(yīng)的位置上，此時(shí)鯨魚(yú)個(gè)體位置對(duì)應(yīng)細(xì)菌個(gè)體位置。鯨魚(yú)復(fù)制階段步驟如下：

步驟1：計(jì)算得出上一次迭代完成后第i只鯨魚(yú)個(gè)體位置的適應(yīng)度值之和，即為該鯨魚(yú)的捕食能力值。對(duì)于每只鯨魚(yú)i=1，2，..，X，捕食能力值如下

WSkilli=∑fitnessi

(7)

步驟2：對(duì)鯨魚(yú)個(gè)體捕食能力值(適應(yīng)度值)進(jìn)行降序排序

步驟3：令Xr=X/2表示被淘汰鯨魚(yú)數(shù)。淘汰掉排在后50%的Xr只鯨魚(yú)，剩下的鯨魚(yú)進(jìn)行自我復(fù)制。

步驟4：計(jì)算得出復(fù)制生成的Xr只鯨魚(yú)的位置。復(fù)制生成的Xr只新鯨魚(yú)與原鯨魚(yú)個(gè)體有同等位置，且具有相同的捕食能力。第t次迭代復(fù)制生成的Xr只鯨魚(yú)位置如下：

(8)

步驟5：保存各鯨魚(yú)位置，進(jìn)入TRWOA算法循環(huán)。

3.3 TRWOA算法步驟流程

算法主要步驟如下：

1)鯨魚(yú)群規(guī)模為X。初始化a，A，C，l，p等參數(shù)以及迭代次數(shù)Iteration。

2)Tent映射生成分布均勻的初始鯨魚(yú)個(gè)體，執(zhí)行3.1節(jié)中步驟1到步驟5。

3)算法主循環(huán)，計(jì)算并比較每只鯨魚(yú)的適應(yīng)度值，比較得出當(dāng)前適應(yīng)度值最佳的鯨魚(yú)位置，記為X*。

4)如果p<0.5且|A|<1，每只鯨魚(yú)個(gè)體按照式(2)更新當(dāng)前位置，|A|≥1則按照式(5)更新鯨魚(yú)個(gè)體位置。如果p≥0.5，則每只鯨魚(yú)個(gè)體依據(jù)式(3)更新位置。

5)復(fù)制操作階段：執(zhí)行3.2節(jié)中步驟1到步驟5；

6)判斷是否滿足算法的終止條件，滿足則結(jié)束循環(huán)；否則轉(zhuǎn)到步驟2)。

7)輸出全局最優(yōu)解X*。

算法流程如圖1所示。

圖1 TRWOA流程圖

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證TRWOA算法的性能，選取9個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試。這9個(gè)函數(shù)可以有效地評(píng)測(cè)算法的尋優(yōu)能力?；鶞?zhǔn)測(cè)試函數(shù)詳情如表1所示。函數(shù)F1、F2、F3、F4、F5是單峰函數(shù)，可用于檢測(cè)算法的收斂速度和搜索精度，其中函數(shù)F3是一種病態(tài)凹函數(shù)，具有局部極值點(diǎn)，主要用以檢測(cè)算法的收斂速度和全局尋優(yōu)能力。函數(shù)F6是具有許多局部極值點(diǎn)的、復(fù)雜的、非線性多模態(tài)函數(shù)，主要用于評(píng)價(jià)算法的跳出局部最優(yōu)的能力。

實(shí)驗(yàn)在主頻 2.2 G，內(nèi)存12 G，Windows 10操作系統(tǒng)，Matlab2014b的計(jì)算機(jī)上實(shí)現(xiàn)。實(shí)驗(yàn)中算法最大迭代是500次，鯨魚(yú)種群規(guī)模是30，各算法獨(dú)立運(yùn)行30次。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)表

4.2 性能分析

為了驗(yàn)證TRWOA算法的性能，將其分別與基本W(wǎng)OA、Tent混沌鯨魚(yú)算法(Tent Chaotic Mapping-BasedWhale Optimization Algorithm，TWOA)以及可復(fù)制的鯨魚(yú)算法(ReproducibleWhale Optimization Algorithm，RWOA)進(jìn)行尋優(yōu)測(cè)試。每種算法對(duì)每個(gè)函數(shù)單獨(dú)運(yùn)行30次，通過(guò)比較實(shí)驗(yàn)結(jié)果的均值和標(biāo)準(zhǔn)差來(lái)評(píng)價(jià)算法的性能。實(shí)驗(yàn)結(jié)果如表2所示。

表2 實(shí)驗(yàn)結(jié)果對(duì)比表

表2中實(shí)驗(yàn)結(jié)果的均值反映的是算法的收斂特性，均值小說(shuō)明算法性能好，從表中可以看出TRWOA的收斂性更好、收斂精度更高。這里的標(biāo)準(zhǔn)差則反映的是算法進(jìn)行30次實(shí)驗(yàn)所得實(shí)驗(yàn)結(jié)果相對(duì)于均值的偏離程度，小的標(biāo)準(zhǔn)差說(shuō)明實(shí)驗(yàn)結(jié)果都集中在更小范圍之內(nèi)，算法的穩(wěn)定性更好。從表中可以看出，基于Tent混沌映射的可復(fù)制的鯨魚(yú)算法(TRWOA)與基本的鯨魚(yú)算法(WOA)相比，算法性能得到了很大的提升。對(duì)于函數(shù)F6、F7、F8，RWOA和TRWOA的實(shí)驗(yàn)結(jié)果均值和標(biāo)準(zhǔn)差相同，且較WOA更小，對(duì)復(fù)雜的、非線性多峰函數(shù)F6尋優(yōu)，TWOA也達(dá)到了與RWOA和TRWOA相同的結(jié)果。實(shí)驗(yàn)數(shù)據(jù)表明，Tent混沌映射和復(fù)制操作均可以在一定程度上提高算法的收斂性、收斂精度以及穩(wěn)定性，將兩者相結(jié)合的TRWOA性能更優(yōu)。

為了更好地驗(yàn)證TRWOA的有效性和收斂性，將其與引入Lévy飛行軌跡策略的鯨魚(yú)算法[2](Lévy Flight Trajectory-Based Whale Opt-imizationAlgorithm，LWOA)以及自適應(yīng)權(quán)重改進(jìn)的鯨魚(yú)算法[6](Improved Whale Optimizat-ion Algorithm，IWOA)進(jìn)行對(duì)比，通過(guò)觀察收斂曲線來(lái)比較各算法的性能。各算法對(duì)每個(gè)測(cè)試函數(shù)尋優(yōu)的優(yōu)化收斂曲線如圖2所示。

圖2 算法收斂曲線圖

觀察圖2中的圖(g)和(h)發(fā)現(xiàn)，迭代初期IWOA收斂速度較WOA和TWOA快，但迭代后期較TWOA慢，且RWOA和TRWOA收斂性均明顯優(yōu)于IWOA。觀察圖(a)、(f)、(g)和(h)發(fā)現(xiàn)，算法LWOA和TRWOA收斂性能難分伯仲，圖(b)和(g)顯示，在迭代初期算法LWOA的收斂性能優(yōu)于TRWOA，但觀察圖(c)、(d)、(e)和(i)發(fā)現(xiàn)，TRWOA收斂速度明顯優(yōu)于LWOA，而且LWOA在對(duì)函數(shù)F3、F4、F5、F9尋優(yōu)過(guò)程中出現(xiàn)了明顯的早熟現(xiàn)象，其中函數(shù)F3作為病態(tài)、單峰、凹函數(shù)，其對(duì)于全局搜索能力要求更高，說(shuō)明TRWOA的全局搜索能力較LWOA更強(qiáng)，所以TRWOA算法優(yōu)化性能比LWOA算法性能更好。綜上所述，TRWOA算法穩(wěn)定性更好，搜索能力更強(qiáng)，收斂性更優(yōu)。

4.3 TRWOA在TSP問(wèn)題上的應(yīng)用

在有n個(gè)城市的 TSP 問(wèn)題中，每只鯨魚(yú)的搜索路線對(duì)應(yīng)一條路徑，以求得最短路徑為目標(biāo)，即以式 (9) 作為目標(biāo)函數(shù)，求得f(x)的最小值為最優(yōu)路徑長(zhǎng)度。

(9)

其中，d(i，j)為任意兩城市間的距離，n為城市數(shù)。

為了驗(yàn)證TRWOA算法解決實(shí)際優(yōu)化問(wèn)題的能力，從TSPLIB 標(biāo)準(zhǔn)庫(kù)中選取6個(gè)不同類型的TSP實(shí)例進(jìn)行實(shí)驗(yàn)，并對(duì)比不同算法的求解結(jié)果。分別以burma14、att48、eil50、st70、pr226、gil262為實(shí)驗(yàn)對(duì)象對(duì)TRWOA以及遺傳算法(GA)、螞蟻群算法(ACO)、模擬退火算法(SA)進(jìn)行實(shí)驗(yàn)，每個(gè)算法獨(dú)立運(yùn)行10次，每次實(shí)驗(yàn)迭代1000次。TRWOA對(duì)不同的TSP實(shí)例優(yōu)化所得實(shí)驗(yàn)結(jié)果如表3所示。不同算法實(shí)驗(yàn)結(jié)果對(duì)比如表4所示，其中偏差率計(jì)算公式如下

(10)

表3 TRWOA對(duì)各TSP問(wèn)題10次實(shí)驗(yàn)優(yōu)化結(jié)果

表4 不同算法結(jié)果對(duì)比表

從表3可以發(fā)現(xiàn)，TRWOA在城市數(shù)量較少的小規(guī)模TSP問(wèn)題中能夠收斂到已知最優(yōu)解，在城市數(shù)量較多的TSP問(wèn)題中該算法也取得了較好的結(jié)果。對(duì)于burma14問(wèn)題，每次實(shí)驗(yàn)都可以收斂到已知最優(yōu)解；對(duì)于att48問(wèn)題，每一次實(shí)驗(yàn)結(jié)果都接近最優(yōu)解，沒(méi)有陷入局部最優(yōu)，能夠隨迭代次數(shù)增多而越接近最優(yōu)解；對(duì)于eil51問(wèn)題和st70問(wèn)題，每次實(shí)驗(yàn)都盡可能收斂于已知最優(yōu)解；對(duì)于pr226問(wèn)題和gil262問(wèn)題，隨著TSP問(wèn)題城市規(guī)模的增大，TRWOA也取得了較好的結(jié)果。從表4數(shù)據(jù)可以看出，與GA、ACO和SA相比，TRWOA的搜索能力更有優(yōu)勢(shì)。

5 結(jié)論

針對(duì)WOA的優(yōu)缺點(diǎn)，本文提出了基于Tent 混沌映射的可復(fù)制的鯨魚(yú)算法(TRWOA)，該算法具有如下主要特點(diǎn)：1)利用Tent混沌映射生成的隨機(jī)混沌序列，提升初始解的質(zhì)量，從而提高算法的求解精度。2)引入細(xì)菌覓食優(yōu)化算法的復(fù)制操作，不但能有效避免其收斂于局部極值點(diǎn)，而且能加快其收斂速度。

本文對(duì)具有不同特性的測(cè)試函數(shù)分別進(jìn)行了實(shí)驗(yàn)。測(cè)驗(yàn)結(jié)果表明TRWOA較WOA算法性能得到了明顯增強(qiáng)，并且TRWOA對(duì)優(yōu)化的函數(shù)類型要求不嚴(yán)格，對(duì)于有較多局部極值點(diǎn)的、非線性的、多模態(tài)的函數(shù)仍然具有良好的優(yōu)化效果，在尋優(yōu)過(guò)程中，能保證整個(gè)鯨魚(yú)群的全局搜索能力。最后將改進(jìn)的鯨魚(yú)算法應(yīng)用于TSP問(wèn)題中，與其它各算法對(duì)比后更加驗(yàn)證了TRWOA的尋優(yōu)能力。下一步工作將繼續(xù)完善TRWOA算法并將其應(yīng)用到更多的實(shí)際組合優(yōu)化問(wèn)題中。