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

南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，南京210023

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

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

1 被囊體種群優(yōu)化算法

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

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

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

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

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

其中，F(xiàn)S為最佳搜索個體的位置（即食物源的位置或是最優(yōu)解），向量Pp(t)表示普通搜索個體的位置，t為迭代次數(shù)，rand是區(qū)間[0，1]的隨機(jī)數(shù)。

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

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

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

2 改進(jìn)后的被囊體種群優(yōu)化算法

2.1 余弦自適應(yīng)

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

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

其中，l為當(dāng)前迭代次數(shù)，Max_iter為最大迭代次數(shù)，在本實(shí)驗(yàn)中，Max_iter=250。

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

2.2 混沌搜索

混沌向量搜索是在非線性動力系統(tǒng)中發(fā)現(xiàn)的一種確定性的、隨機(jī)的方法?；煦缦蛄績?yōu)化算法的主要思想是利用混沌運(yùn)動的隨機(jī)性和遍歷性等特點(diǎn)，將待優(yōu)化的變量映射到混沌變量空間的取值區(qū)間內(nèi)，再將得到的解線性地轉(zhuǎn)換到優(yōu)化變量空間[11-12]。常見的映射方式有

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

表1 混沌映射表Table 1 Chaotic maps

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

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

其中，gl+1為混沌映射的輸出。經(jīng)過多次實(shí)驗(yàn)對比，在選取的16個測試函數(shù)中，篩選出了12個效果差異比較大的函數(shù)(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），實(shí)驗(yàn)最終迭代次數(shù)為250次，為了展現(xiàn)出明顯的收斂速度區(qū)別，本文保留了迭代后期，即220～250代的實(shí)驗(yàn)結(jié)果，其中，由于F9收斂速度較快，保留了40～80代的結(jié)果。據(jù)實(shí)驗(yàn)表明，Gauss/mouse map的結(jié)果較優(yōu)。因此本文最后在表1中選取

圖1 函數(shù)F1混沌結(jié)果Fig.1 Chaotic results of F1

圖5 函數(shù)F5混沌結(jié)果Fig.5 Chaotic results of F5

圖6 函數(shù)F6混沌結(jié)果Fig.6 Chaotic results of F6

圖7 函數(shù)F7混沌結(jié)果Fig.7 Chaotic results of F7

圖8 函數(shù)F8混沌結(jié)果Fig.8 Chaotic results of F8

圖12 函數(shù)F15混沌結(jié)果Fig.12 Chaotic results of F15

圖9 函數(shù)F9混沌結(jié)果Fig.9 Chaotic results of F9

圖10 函數(shù)F10混沌結(jié)果Fig.10 Chaotic results of F10

圖11 函數(shù)F13混沌結(jié)果Fig.11 Chaotic results of F13

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

這里的rand與公式（5）中的rand相同。在后面3.2節(jié)中給出了相關(guān)的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果表明CTSA中采用的混沌搜索方式可以提高算法的尋優(yōu)性能。

2.3 算法的流程

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

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

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

3.1 實(shí)驗(yàn)基本設(shè)置

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

圖2 函數(shù)F2混沌結(jié)果Fig.2 Chaotic results of F2

圖4 函數(shù)F4混沌結(jié)果Fig.4 Chaotic results of F4

圖13 函數(shù)F1圖像Fig.13 Image of F1

圖28 函數(shù)F16圖像Fig.28 Image of F16

圖42 函數(shù)F15迭代曲線Fig.42 Iterative curve of F15

表2 16個函數(shù)極值優(yōu)化測試函數(shù)Table 2 Sixteen test functions

圖14 函數(shù)F2圖像Fig.14 Image of F2

圖15 函數(shù)F3圖像Fig.15 Image of F3

圖16 函數(shù)F4圖像Fig.16 Image of F4

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

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

圖29 函數(shù)F1迭代曲線Fig.29 Iterative curve of F1

表3 測試函數(shù)F1的結(jié)果Table 3 Results of F1

圖17 函數(shù)F5圖像Fig.17 Image of F5

圖18 函數(shù)F6圖像Fig.18 Image of F6

圖19 函數(shù)F7圖像Fig.19 Image of F7

圖20 函數(shù)F8圖像Fig.20 Image of F8

圖21 函數(shù)F9圖像Fig.21 Image of F9

圖22 函數(shù)F10圖像Fig.22 Image of F10

圖23 函數(shù)F11圖像Fig.23 Image of F11

圖24 函數(shù)F12圖像Fig.24 Image of F12

圖25 函數(shù)F13圖像Fig.25 Image of F13

圖26 函數(shù)F14圖像Fig.26 Image of F14

圖27 函數(shù)F15圖像Fig.27 Image of F15

表4 測試函數(shù)F2的結(jié)果Table 4 Results of F2

表9 測試函數(shù)F7的結(jié)果Table 9 Results of F7

表11 測試函數(shù)F9的結(jié)果Table 11 Results of F9

表13 測試函數(shù)F11的結(jié)果Table 13 Results of F11

表14 測試函數(shù)F12的結(jié)果Table 14 Results of F12

表15 測試函數(shù)F13的結(jié)果Table 15 Results of F13

表17 測試函數(shù)F15的結(jié)果Table 17 Results of F15

圖30 函數(shù)F2迭代曲線Fig.30 Iterative curve of F2

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

圖3 函數(shù)F3混沌結(jié)果Fig.3 Chaotic results of F3

表5 測試函數(shù)F3的結(jié)果Table 5 Results of F3

表7 測試函數(shù)F5的結(jié)果Table 7 Results of F5

表8 測試函數(shù)F6的結(jié)果Table 8 Results of F6

表10 測試函數(shù)F8的結(jié)果Table 10 Results of F8

表12 測試函數(shù)F10的結(jié)果Table 12 Results of F10

圖31 函數(shù)F3迭代曲線Fig.31 Iterative curve of F3

圖32 函數(shù)F4迭代曲線Fig.32 Iterative curve of F4

圖33 函數(shù)F5迭代曲線Fig.33 Iterative curve of F5

圖34 函數(shù)F6迭代曲線Fig.34 Iterative curve of F6

圖35 函數(shù)F7迭代曲線Fig.35 Iterative curve of F7

圖36 函數(shù)F8迭代曲線Fig.36 Iterative curve of F8

圖38 函數(shù)F10迭代曲線Fig.38 Iterative curve of F10

圖40 函數(shù)F12迭代曲線Fig.40 Iterative curve of F12

圖41 函數(shù)F13迭代曲線Fig.41 Iterative curve of F13

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

表6 測試函數(shù)F4的結(jié)果Table 6 Results of F4

表16 測試函數(shù)F14的結(jié)果Table 16 Results of F14

表18 測試函數(shù)F16的結(jié)果Table 18 Results of F16

圖37 函數(shù)F9迭代曲線Fig.37 Iterative curve of F9

圖39 函數(shù)F11迭代曲線Fig.39 Iterative curve of F11

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

3.3 算法運(yùn)行時間比較

本文的實(shí)驗(yàn)環(huán)境為：Windows10操作系統(tǒng)，Intel?CoreTMi5-8300U的CPU，8 GB內(nèi)存，開發(fā)工具為MATLAB R2019b。

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

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

表19 運(yùn)行時間的對比Table 19 Comparisons of running time

4 結(jié)束語

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