基于Tent混沌映射的可復制的鯨魚算法

馬曉寧，李笑含

(中國民航大學計算機科學與技術學院，天津 300300)

1 引言

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

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

本文為提升鯨魚優化算法收斂性能和搜索能力，解決其易出現早熟現象、求解精度低等問題，提出了一種新的基于Tent混沌映射的可復制的鯨魚優化算法(TRWOA)。首先，利用Tent混沌映射生成的隨機混沌序列，提升初始解的質量。然后，為了加快算法的收斂速度，增強其全局搜索能力，引入細菌覓食優化算法的復制操作，協調全局搜索和局部搜索。與以往鯨魚算法改進方法不同，本文首次引入細菌覓食算法的復制操作來提高鯨魚算法的性能，結合Tent映射產生的隨機初始化序列，使得改進后的鯨魚算法性能更優。

2 鯨魚算法

在鯨魚算法中，每只鯨魚的位置代表一個優化問題的可行解[10]。在鯨魚群的捕獵過程中，鯨魚有兩種捕食行為：一種是包圍獵物，所有的鯨魚游向其它鯨魚；另一種是氣泡網捕食，鯨魚螺旋形游動并噴出氣泡來驅趕獵物。

2.1 包圍獵物

首先獲得鯨魚個體位置與最佳鯨魚位置之間的距離

(1)

2.2 氣泡網捕食

氣泡網捕食法可描述為如下兩種行為：

1) 搖擺包圍捕食

鯨魚個體位置由式(2)更新

(2)

2) 螺旋氣泡網捕食

鯨魚螺旋上游，同時吐出氣泡形成起泡網進行捕食。數學模型如下

(3)

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

式中，p是[0，1]范圍內的隨機數。

2.3 隨機捕食獵物

(5)

3 基于Tent混沌映射的可復制的鯨魚算法

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

3.1 Tent混沌映射初始化種群

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

基本的鯨魚優化算法初始化種群采用的是隨機產生的方法，該方法不僅隨機性大，而且不能保證初始解的質量。為提升初始解的質量，利用Tent混沌映射生成的隨機混沌序列產生初代鯨魚群。

Tent映射初始化鯨魚群步驟如下：

步驟1：確定參數α的值；

步驟2：根據優化問題的目標函數設置初值x0序列的取值范圍，隨機生成此范圍內的X個值；

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

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

0<α<1

(6)

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

步驟5：保存x序列，進入TRWOA算法主循環。

3.2 復制操作階段

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

在本文的算法中，鯨魚經過一次捕食迭代后，每只鯨魚均在自己相應的位置上，此時鯨魚個體位置對應細菌個體位置。鯨魚復制階段步驟如下：

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

WSkilli=∑fitnessi

(7)

步驟2：對鯨魚個體捕食能力值(適應度值)進行降序排序

步驟3：令Xr=X/2表示被淘汰鯨魚數。淘汰掉排在后50%的Xr只鯨魚，剩下的鯨魚進行自我復制。

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

(8)

步驟5：保存各鯨魚位置，進入TRWOA算法循環。

3.3 TRWOA算法步驟流程

算法主要步驟如下：

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

2)Tent映射生成分布均勻的初始鯨魚個體，執行3.1節中步驟1到步驟5。

3)算法主循環，計算并比較每只鯨魚的適應度值，比較得出當前適應度值最佳的鯨魚位置，記為X*。

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

5)復制操作階段：執行3.2節中步驟1到步驟5；

6)判斷是否滿足算法的終止條件，滿足則結束循環；否則轉到步驟2)。

7)輸出全局最優解X*。

算法流程如圖1所示。

圖1 TRWOA流程圖

4 實驗結果與分析

4.1 實驗設計

為了驗證TRWOA算法的性能，選取9個基準測試函數進行測試。這9個函數可以有效地評測算法的尋優能力。基準測試函數詳情如表1所示。函數F1、F2、F3、F4、F5是單峰函數，可用于檢測算法的收斂速度和搜索精度，其中函數F3是一種病態凹函數，具有局部極值點，主要用以檢測算法的收斂速度和全局尋優能力。函數F6是具有許多局部極值點的、復雜的、非線性多模態函數，主要用于評價算法的跳出局部最優的能力。

實驗在主頻 2.2 G，內存12 G，Windows 10操作系統，Matlab2014b的計算機上實現。實驗中算法最大迭代是500次，鯨魚種群規模是30，各算法獨立運行30次。

表1 標準測試函數表

4.2 性能分析

為了驗證TRWOA算法的性能，將其分別與基本WOA、Tent混沌鯨魚算法(Tent Chaotic Mapping-BasedWhale Optimization Algorithm，TWOA)以及可復制的鯨魚算法(ReproducibleWhale Optimization Algorithm，RWOA)進行尋優測試。每種算法對每個函數單獨運行30次，通過比較實驗結果的均值和標準差來評價算法的性能。實驗結果如表2所示。

表2 實驗結果對比表

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

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

圖2 算法收斂曲線圖

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

4.3 TRWOA在TSP問題上的應用

在有n個城市的 TSP 問題中，每只鯨魚的搜索路線對應一條路徑，以求得最短路徑為目標，即以式 (9) 作為目標函數，求得f(x)的最小值為最優路徑長度。

(9)

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

為了驗證TRWOA算法解決實際優化問題的能力，從TSPLIB 標準庫中選取6個不同類型的TSP實例進行實驗，并對比不同算法的求解結果。分別以burma14、att48、eil50、st70、pr226、gil262為實驗對象對TRWOA以及遺傳算法(GA)、螞蟻群算法(ACO)、模擬退火算法(SA)進行實驗，每個算法獨立運行10次，每次實驗迭代1000次。TRWOA對不同的TSP實例優化所得實驗結果如表3所示。不同算法實驗結果對比如表4所示，其中偏差率計算公式如下

(10)

表3 TRWOA對各TSP問題10次實驗優化結果

表4 不同算法結果對比表

從表3可以發現，TRWOA在城市數量較少的小規模TSP問題中能夠收斂到已知最優解，在城市數量較多的TSP問題中該算法也取得了較好的結果。對于burma14問題，每次實驗都可以收斂到已知最優解；對于att48問題，每一次實驗結果都接近最優解，沒有陷入局部最優，能夠隨迭代次數增多而越接近最優解；對于eil51問題和st70問題，每次實驗都盡可能收斂于已知最優解；對于pr226問題和gil262問題，隨著TSP問題城市規模的增大，TRWOA也取得了較好的結果。從表4數據可以看出，與GA、ACO和SA相比，TRWOA的搜索能力更有優勢。

5 結論

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

本文對具有不同特性的測試函數分別進行了實驗。測驗結果表明TRWOA較WOA算法性能得到了明顯增強，并且TRWOA對優化的函數類型要求不嚴格，對于有較多局部極值點的、非線性的、多模態的函數仍然具有良好的優化效果，在尋優過程中，能保證整個鯨魚群的全局搜索能力。最后將改進的鯨魚算法應用于TSP問題中，與其它各算法對比后更加驗證了TRWOA的尋優能力。下一步工作將繼續完善TRWOA算法并將其應用到更多的實際組合優化問題中。