余弦自適應混沌被囊體種群優化算法

李湘喆，顧 磊，馬 麗，王夢杰

南京郵電大學 計算機學院，南京210023

群智能優化算法[1]主要模擬了自然界中生物的群體行為。這些群體按照一定的方式尋找食物，群體中的個體根據所接受到的信息對自己的行為進行調整，即不斷改變搜索方向，最終表現出群體智能[1]?；谌后w智能的算法具有較強的搜索能力，易于實現，能同其他算法結合改進的性能。近年來，這類算法受到了業界和學術界極大的關注。因此，研究人員從大自然的生物種群中汲取靈感，提出了許多經典算法，包括粒子群算法[2]、蟻群算法[3]、蜂群算法[4]、魚群算法[5]、果蠅算法[6]、灰狼算法[7]、蝗蟲算法[8]等。其中粒子群算法[2]假設每個粒子在搜索空間中移動，并且不斷更新當前位置和全局位置，直到找到滿意的解空間。根據沒有免費午餐定理（no free lunch），一個特定的優化算法并不能解決所有問題，越來越多的新型優化算法正在被不斷提出。

被囊體種群優化算法（tunicate swarm algorithm，TSA）是由Kaur等人[9]在2020年提出的新型群智能算法。被囊體最有趣的地方是噴射推進和群體行為，這也是TSA的主要動機，其中噴射推進行為使得TSA具有勘測和開發的雙重能力。在迭代過程中，TSA算法可以在給定的搜索空間內朝著最優解方向收斂。與許多算法一樣，TSA也存在易陷入局部最優和后期收斂速度慢的問題。針對這些缺點，本文提出一種基于余弦自適應和混沌搜索的被囊體種群優化算法（tunicate swarm algorithm based on cosine adaptive and chaotic search，CTSA）。本文的貢獻如下：（1）提出曲線自適應計算搜索個體（search agents，即尋找食物的被囊體）間的社會作用力（social forces），優化了TSA算法位置參數的更新方式，使其動態更新，進而提高算法的收斂精度和收斂速度。（2）搜索個體位置更新時，引入混沌參數m，并采用混沌映射方式[10]，使得被囊體個體有一定的概率以混沌模型更新機制去更新位置。這種混沌搜索的引入有助于進一步緩解高維問題中陷入局部最優和收斂速度慢這兩個問題。實驗結果表明，與TSA算法相比，本文提出的CTSA在收斂速度和全局最優性方面有明顯提高。

1 被囊體種群優化算法

被囊體是唯一一種利用流體噴射式推進在海洋中移動的動物，盡管在給定的搜索空間中，被囊體并不知道食物的來源，但是噴射推進行為和群體行為可以讓被囊體在海洋中移動，使得這種動物有能力在海里找到食物來源。被囊體優化算法TSA主要是用數學的方式模擬這兩種行為，并在這兩種行為的反復迭代中尋找最優解。此外，為了對噴射推進行為進行數學建模，一個普通的搜索個體必須做到以下三點：（1）避免彼此之間位置上的沖突。（2）向最佳搜索個體（即離食物源最近的搜索個體）移動。（3）使自己的位置接近最佳搜索個體[9]。

TSA算法模擬噴射推進行為主要分三步[9]：

（1）勘探階段。在此階段中，主要是用如下公式（1）～（4）得到了向量A去更新搜索個體的位置，其目的是引入重力和深海水流因素的影響，來幫助搜索個體探尋最優解（即食物源），且避免搜索個體彼此間位置上的沖突。

其中，公式（1）里G為重力，F為深海水流平流作用力，M表示搜索個體之間的社會作用力。公式（2）是重力G的定義，C1、C2、C3為區間[0，1]的隨機數。公式（3）是深海水流平流作用力F的定義。公式（4）是搜索個體間社會作用力M的定義，其中Pmin和Pmax代表個體間進行社會互動（social interaction）初始速度的最小值和最大值。

（2）開發階段。在此階段中，主要是用如下公式（5）獲得普通搜索個體與最佳搜索個體之間的距離PD，其目的是在更新搜索個體位置時，可以讓普通搜索個體向處于最佳位置的搜索個體移動。

其中，FS為最佳搜索個體的位置（即食物源的位置或是最優解），向量Pp(t)表示普通搜索個體的位置，t為迭代次數，rand是區間[0，1]的隨機數。

（3）更新階段。在此階段中，主要是用如下公式（6）更新搜索個體的位置，讓普通搜索個體靠近最佳搜索個體。

其中，rand取值與公式（5）相同。

在TSA算法流程中模擬噴射推進行為會連續執行兩次形成兩個Pp(t)，分別令它們為P1和P2。TSA算法模擬群體行為就是利用P1和P2來進一步更新搜索個體的位置，具體公式如下：

2 改進后的被囊體種群優化算法

2.1 余弦自適應

在公式（4）中，M為搜索個體之間的社會作用力，Pmin和Pmax代表個體間進行社會互動初始速度的最小值和最大值。文獻[9]經過實驗比對確定在TSA每次迭代中取M為[1，4]區間內的隨機值時效果最優，因此本文保留了原作者對Pmin和Pmax值的選擇。隨著迭代過程的進行，M的改變使得矢量A隨機變化，從而使得搜索個體可以在搜索空間中尋找最優解。然而，隨著迭代次數的增加，TSA算法會因每次迭代重新隨機生成M，這種隨機生成不僅耗費時間，并且M的無規律性使得每一次迭代與下一次迭代之間失去了聯系，因而TSA表現出收斂速度慢和最優解精度不準的問題。

針對這個問題，本文的CTSA算法假設隨著迭代次數的增加，搜索個體間的社會作用力可以自適應地減小。引入余弦自適應來重新定義參數M，公式（4）被如下的公式（8）所取代：

其中，l為當前迭代次數，Max_iter為最大迭代次數，在本實驗中，Max_iter=250。

公式（8）中采用余弦自適應策略來更新參數M，即利用迭代次數l對M進行動態調整。參數M影響被囊體種群的搜索范圍，其遞減的過程對應于CTSA由全局搜索到局部搜索的轉變。當l增加，M的值將變小，公式（1）得到的A則會增加。這樣，隨著迭代次數的增加，利用公式（6）就可以擴大搜索個體的搜索范圍。并且余弦自適應的調整策略相比于常用的線性自適應，其在開始時和快結束時下降速率較小，過程緩慢。因此，在前期能夠加大全局搜索的范圍，在后期能夠縮小局部搜索的范圍，從而達到增強全局搜索能力和提高算法收斂精度與速度的目的。更高效且簡單的混沌映射Gauss/mouse map來產生分布更均勻的種群。

2.2 混沌搜索

混沌向量搜索是在非線性動力系統中發現的一種確定性的、隨機的方法。混沌向量優化算法的主要思想是利用混沌運動的隨機性和遍歷性等特點，將待優化的變量映射到混沌變量空間的取值區間內，再將得到的解線性地轉換到優化變量空間[11-12]。常見的映射方式有

Chebyshev map、Circle map、Gauss/mouse map、Iterative map、Logistic map、Piecewise map。本文用到的混沌映射定義如表1所示[13]。

表1 混沌映射表Table 1 Chaotic maps

在TSA算法執行中，隨著迭代次數的逐漸增加，重力、浮力和深海水流等因素會造成被囊體搜索個體在開發階段的噴射推進行為發生改變，但TSA中忽略了這些改變的影響。因此本文考慮引入混沌映射來模擬這種無條件的隨機行為，這種混沌行為有助于避免算法陷入局部最優和提高收斂速度。為了模擬該行為，本文定義了公式（9）和公式（10）。

公式（9）中引入了混沌向量m，具體如下所示：

其中，gl+1為混沌映射的輸出。經過多次實驗對比，在選取的16個測試函數中，篩選出了12個效果差異比較大的函數(F1,F2,F3,F4,F5,F6,F7,F8,F9,F10,F13,F15)，如圖1至圖12所示（所有圖中TSA采用Chebyshev map，TSA2采用Circle map，TSA3采 用Gauss/mouse map，TSA4采 用Iterative map，TSA5采 用Logistic map，TSA6采用Piecewise map），實驗最終迭代次數為250次，為了展現出明顯的收斂速度區別，本文保留了迭代后期，即220～250代的實驗結果，其中，由于F9收斂速度較快，保留了40～80代的結果。據實驗表明，Gauss/mouse map的結果較優。因此本文最后在表1中選取

圖1 函數F1混沌結果Fig.1 Chaotic results of F1

圖5 函數F5混沌結果Fig.5 Chaotic results of F5

圖6 函數F6混沌結果Fig.6 Chaotic results of F6

圖7 函數F7混沌結果Fig.7 Chaotic results of F7

圖8 函數F8混沌結果Fig.8 Chaotic results of F8

圖12 函數F15混沌結果Fig.12 Chaotic results of F15

圖9 函數F9混沌結果Fig.9 Chaotic results of F9

圖10 函數F10混沌結果Fig.10 Chaotic results of F10

圖11 函數F13混沌結果Fig.11 Chaotic results of F13

本文提出的CTSA算法在迭代過程中，通過定義值域為[0，1]的隨機變量rand1，使得被囊體搜索個體有50%的概率通過混沌模型更新位置，即利用如下公式（10）（取代原公式（5））得到其與最佳搜索個體之間的距離PD，再通過公式（6）更新位置。

這里的rand與公式（5）中的rand相同。在后面3.2節中給出了相關的實驗結果，實驗結果表明CTSA中采用的混沌搜索方式可以提高算法的尋優性能。

2.3 算法的流程

CTSA的簡要算法流程如下所示。其中，算法輸入被囊體初始種群Pp，即搜索個體初始位置，可以輸出最優適應度值FS，即最佳搜索個體的位置，也就是最優解。

算法因增加了混沌函數，時間復雜度為O(Max_iter2·dim·N)，其中N為種群個數，Max_iter為迭代次數，dim為維度。TSA時間復雜度為O(Max_iter·dim·N)，在第3章中進行對比實驗的算法時間復雜度同TSA。

3 實驗結果與分析

3.1 實驗基本設置

在本文中，被囊體種群優化算法的參數設置如下：種群個數N=25，迭代次數Max_iter=250,Pmax=1,Pmin=4,混沌向量m選擇映射3，即Guass/mouse map。為驗證算法的效果，共使用包括基準測試函數和CEC-2017部分函數在內的16個函數F1～F16進行測試，各個函數的具體情況如表2所示，其函數圖像如圖13至圖28所示。其中針對非固定維度的函數(F1～F11,F13～F15)，測試了其在10維和30維的結果。為了驗證CTSA算法的性能，本文將CTSA與TSA[9]及阿基米德算法（AOA）[14]、基于粒子群算法的混沌混合蝶形優化算法（HPSOBOA）[15]、海洋生物優化算法（MPA）[16]、灰狼優化算法（GWO）[7]、烏燕鷗優化算法（STOA）[17]、海鷗優化算法（SOA）[18]作對比。在實驗中，包括CTSA在內的每個算法都在16個測試函數上獨立運行了30次，并統計平均值、方差、最大值、最小值等相關指標，對于函數F1～F11、F13、F15（30維）和F12（2維），圖29至圖42分別給出了各個算法的收斂情況。

圖2 函數F2混沌結果Fig.2 Chaotic results of F2

圖4 函數F4混沌結果Fig.4 Chaotic results of F4

圖13 函數F1圖像Fig.13 Image of F1

圖28 函數F16圖像Fig.28 Image of F16

圖42 函數F15迭代曲線Fig.42 Iterative curve of F15

表2 16個函數極值優化測試函數Table 2 Sixteen test functions

圖14 函數F2圖像Fig.14 Image of F2

圖15 函數F3圖像Fig.15 Image of F3

圖16 函數F4圖像Fig.16 Image of F4

3.2 實驗結果對比與分析

針對表2中的16個函數，將本文所提出的CTSA與TSA、AOA、HPSOBOA、MPA、GWO、STOA、SOA等7個群智能優化算法進行了對比，主要實驗結果在表3～18及圖29～42中給出。

圖29 函數F1迭代曲線Fig.29 Iterative curve of F1

表3 測試函數F1的結果Table 3 Results of F1

圖17 函數F5圖像Fig.17 Image of F5

圖18 函數F6圖像Fig.18 Image of F6

圖19 函數F7圖像Fig.19 Image of F7

圖20 函數F8圖像Fig.20 Image of F8

圖21 函數F9圖像Fig.21 Image of F9

圖22 函數F10圖像Fig.22 Image of F10

圖23 函數F11圖像Fig.23 Image of F11

圖24 函數F12圖像Fig.24 Image of F12

圖25 函數F13圖像Fig.25 Image of F13

圖26 函數F14圖像Fig.26 Image of F14

圖27 函數F15圖像Fig.27 Image of F15

表4 測試函數F2的結果Table 4 Results of F2

表9 測試函數F7的結果Table 9 Results of F7

表11 測試函數F9的結果Table 11 Results of F9

表13 測試函數F11的結果Table 13 Results of F11

表14 測試函數F12的結果Table 14 Results of F12

表15 測試函數F13的結果Table 15 Results of F13

表17 測試函數F15的結果Table 17 Results of F15

圖30 函數F2迭代曲線Fig.30 Iterative curve of F2

（1）單峰函數F1～F3、F5～F8和F10。從圖29～圖31、圖33～圖36和圖38的迭代曲線可以看出，無論在10維還是30維下，CTSA在收斂速度上明顯優于其他算法；同時，從表3～表5，表7～表10及表12可以看出，CTSA的適應度值精度也明顯優于其他算法。且與TSA相比，CTSA在收斂速度上取得了很大的提升，因此認為CTSA在單峰函數上有很好的表現。如對于測試函數F1，10維條件下，CTSA較TSA的收斂精度提高了至少E+34個數量級，并且最小值已經達到E-173個數量級；30維條件下，CTSA較TSA的收斂精度提高了至少E+20個數量級；對于函數F5和F6，如表7和表8，CTSA在10維和30維下均有很好的表現，10維條件下，CTSA最小值已超過E-170個數量級。由迭代曲線可以看出，對于此類單峰函數，CTSA在保持了尋優過程中波動小的特點的同時，提高了收斂速度。對于函數F1～F3、F5和F6，由表中數據可以看出，CTSA的方差均已達到E-300個數量級，而TSA均未達到E-300個數量級，這說明改進后的CTSA在穩定方面也有所提升。

圖3 函數F3混沌結果Fig.3 Chaotic results of F3

表5 測試函數F3的結果Table 5 Results of F3

表7 測試函數F5的結果Table 7 Results of F5

表8 測試函數F6的結果Table 8 Results of F6

表10 測試函數F8的結果Table 10 Results of F8

表12 測試函數F10的結果Table 12 Results of F10

圖31 函數F3迭代曲線Fig.31 Iterative curve of F3

圖32 函數F4迭代曲線Fig.32 Iterative curve of F4

圖33 函數F5迭代曲線Fig.33 Iterative curve of F5

圖34 函數F6迭代曲線Fig.34 Iterative curve of F6

圖35 函數F7迭代曲線Fig.35 Iterative curve of F7

圖36 函數F8迭代曲線Fig.36 Iterative curve of F8

圖38 函數F10迭代曲線Fig.38 Iterative curve of F10

圖40 函數F12迭代曲線Fig.40 Iterative curve of F12

圖41 函數F13迭代曲線Fig.41 Iterative curve of F13

（2）多峰函數F4、F9和F11～F16。對于函數F4（簡單多峰函數），如表6，在10維的時候，CTSA表現最優，收斂精度較TSA提高了E+17個數量級，且CTSA的收斂速度明顯快于TSA；而在30維下，CTSA表現出了全局性，雖然效果較低維相比有所下降，但較于TSA仍提高了E+12個數量級，并且明顯優于其他算法。對于函數F9和F11～F16，這些多峰函數存在大量的局部最優值，主要用來測試算法的全局開發能力以及避免陷入早熟的能力。從收斂曲線（圖37、圖39～圖42）可以看出，相比TSA，改進后的CTSA算法雖然在收斂速度上和TSA算法相差不大，但在收斂精度上總體優于TSA。對于函數F12（固定維度為2）所有函數均已收斂到最小值，雖然CTSA平均值稍劣于其他對比算法，但仍稍優于TSA算法。對于函數F13，10維條件下，CTSA最優值的平均值較TSA提高了E+09個數量級，并且從其迭代曲線可以看出，改進后的CTSA尋優過程波動更小。對于函數F14～F16，如表16～表18所示，CTSA相較于TSA，最優值的平均值精度提升在E+01以內，雖略有提升，但效果不太明顯。

表6 測試函數F4的結果Table 6 Results of F4

表16 測試函數F14的結果Table 16 Results of F14

表18 測試函數F16的結果Table 18 Results of F16

圖37 函數F9迭代曲線Fig.37 Iterative curve of F9

圖39 函數F11迭代曲線Fig.39 Iterative curve of F11

從上述實驗結果可以看出：對于單峰函數，CTSA表現很好；對于復雜的多峰函數，CTSA較TSA的優化效果不顯著，但CTSA整體上比TSA收斂速度更快，收斂精度更高，因此改進結果是可以接受的。同時，實驗結果驗證了余弦自適應和混沌搜索能夠使算法更好地開發全局，在開發與勘測之間達到了平衡，不拘泥于局部最優，進而向全局最優值逼近。

3.3 算法運行時間比較

本文的實驗環境為：Windows10操作系統，Intel?CoreTMi5-8300U的CPU，8 GB內存，開發工具為MATLAB R2019b。

CTSA、TSA、AOA、HPSOBOA、MPA、GWO、STOA

和SOA的運行時間如表19所示。從表19可以看出，改進后的CTSA相比TSA以及其他對比函數增加了運行時間。結合實驗結果與分析可以得出，新算法CTSA雖然增加了時間復雜度，但是能夠獲得更好的實驗結果。

表19 運行時間的對比Table 19 Comparisons of running time

4 結束語

本文提出一種基于余弦自適應和混沌搜索的被囊體種群優化算法，對被囊體在每次迭代中的位置更新機制進行改進，在一定程度上避免算法早熟，使算法迭代后期更快速地收斂到最優值。本文所提出的算法在尋優的精度上也有所提高，實驗結果證明了該算法的有效性和可行性。不足的是，對于存在大量局部最優值的多峰函數，優化效果并不顯著，有待進一步的研究。