梁建明，何 慶

1(貴州大學 大數(shù)據(jù)與信息工程學院，貴陽 550025) 2(貴州省公共大數(shù)據(jù)重點實驗室，貴陽 550025)

1 引 言

近年來元啟發(fā)算法引得越來越多的學者關注和研究，在不斷的探索和研究的過程中，也誕生了許多群體智能優(yōu)化算法.如鯨魚優(yōu)化算法(WOA)[1]、蝗蟲優(yōu)化算法(GOA)[2]、蝴蝶優(yōu)化算法(BOA)[3]、黏菌優(yōu)化算法(SMA)[4]、正余弦優(yōu)化算法(SCA)[5]等.

被囊群算法(Tunicate Swarm Algorithm，TSA)[6]是Satnam Kaur等在2020年9月提出的一種新型元啟發(fā)優(yōu)化算法，它的靈感來自以海洋被囊動物在導航和覓食過程中的噴射推進及其群體行為.其優(yōu)點在于操作簡單，調(diào)整的參數(shù)少以及跳出局部最優(yōu)的能力強.在文獻[6]中仿真結(jié)果表明，與其他群智能算法相比，TSA算法能較快地找到最優(yōu)解.使用該算法可以解決具有未知搜索點的實際案例研究，Abhishek Sharma等[7]采用TSA來估計標準溫度條件下光伏電池組件未知參數(shù)的最優(yōu)值，有效的證實了TAS運用在光伏電池中提取最優(yōu)參數(shù)的優(yōu)越性；Tamer Fetouh等[8]將TSA運用到配電系統(tǒng)中尋找最優(yōu)解以提供定量和定性的電力服務，降低能耗；D.Anand Joseph Daniel等[9]將TSA算法運用到特征選擇中，解決了由于特征集較大而引起的可擴展性問題.

雖然TSA的局部開發(fā)能力強，但是對于全局探索能力卻不足，從而導致尋優(yōu)精度不高，收斂速度慢[10].為此，針對這些問題.Li等[11]使用混沌初始化、全局搜索向量和萊維飛行對TSA算法改進，并運用于解決動態(tài)經(jīng)濟排放調(diào)度問題.

為了提高算法的收斂速度，文獻[12]利用群體協(xié)同機制，增強蝴蝶算法逃離局部最優(yōu)的能力；文獻[13]通過引入控制概率Pc決定算法進入前半段還是后半段探索.所以這有助于算法前期需進行大范圍全局探索，后期需進行小范圍的局部開發(fā)并避免算法過早收斂.文獻[14]通過使用混沌映射初始化種群位置，加快鯨魚算法的收斂速度.

上述策略對于改進算法全局探索能力不足、尋優(yōu)精度不高和收斂速度慢具有一定的效果，但是在TSA中卻達不到很好的預期，為此本文將改進的策略融入標準的TSA算法中，提出萊維飛行和反饋策略的自適應被囊群算法.首先通過分析和實驗確定萊維飛行參數(shù)，使之適應TSA算法；反饋策略改進種群位置更新公式，增強算法逃離局部最優(yōu)的能力和加快算法收斂的速度；受文獻[13]的啟發(fā)，我們舍棄原有的等式，采用分段式的概率分配，實現(xiàn)在位置更新處權重自適應，提高算法對全局搜索和局部搜索能力，避免算法早熟.

2 被囊群優(yōu)化算法

被囊群算法是對海洋中被囊動物的覓食行為進行建模.被囊動物是利用其自身的兩種行為來尋找食物來源，即尋找最佳.覓食行為包括噴射推進和群體智能.為了對噴射推進行為進行數(shù)學建模，被囊動物應滿足3個條件，即避免搜索種群之間的沖突、向最佳搜索個體的位置移動以及保持與最佳搜索個體的距離.最后，群體會根據(jù)個體的最優(yōu)解更新位置.

(1)

PD=|Fbest-rand-P(x)|

(2)

(3)

其中，式(1)表示避免搜索種群之間的沖突行為.rand、c1、c2、c3是[0，1]上服從均勻分布的隨機數(shù)，Vmin、Vmax分別是表示初始的相互作用速度范圍，一般設定Vmin=1、Vmax=4.式(2)計算個體與食物之間的位置，其中Fbest為食物位置，P(x)為個體當前位置.式(3)表示個體向最優(yōu)位置收斂，其個體的位置更新為P(x).

被囊群是由被囊動物所構成，是群體性的動物.所以在完成個體運動行為建模之后，接下來就是對群體行為的建模.

群體行為：

(4)

式(4)表示保存前一個最優(yōu)解和當前最優(yōu)解，通過這兩個解完成對當前位置的更新.

由上述分析可知TSA算法的基本實現(xiàn)步驟如下：

Step1.初始化種群P;

Step2.初始化種群參數(shù)，邊界條件;

Step3.計算每個個體的適應度值；

Step4.搜索最佳個體的位置;

Step5.根據(jù)群體行為更新每個個體位置；

Step6.調(diào)整超出給定搜索空間邊界的個體位置；

Step7.計算更新后的群體每個個體的適應度值，如果適應度優(yōu)于之前，則更新；

Step8.如果滿足停止條件，則停止算法，否則重復步驟如果滿足停止條件，則停止算法，否則重復步驟Step 5-Step 8；

Step9.返回最優(yōu)值；

3 LSATSA算法

3.1 融入反饋策略位置更新

本文在搜索種群空間中隨機選出一只被囊動物，得到隨機被囊動物的反饋信息，然后再結(jié)合最佳位置去更新個體位置.通過不斷地迭代，最終找到食物.如果選擇的隨機被囊動物離食物近，那么它反饋給其他被囊動物的信息是有利于個體位置更新的，則在更新位置時加入反饋的信息；反之，如果隨機被囊動物離食物遠，那么反饋回來的信息對當前位置更新沒有幫助.

建立的數(shù)學模型如下：

(5)

b=Fmax+rand(Fmax-Fmin)

(6)

(7)

式用β是共享系數(shù)，平衡位置更新時反饋信息的大小.γ為反饋數(shù)，隨著迭代次數(shù)的增加，呈現(xiàn)遞增趨勢，能夠加快被囊動物之間的信息交流；R(x)為隨機被囊動物個體；F為計算被囊個體適應度；t表示當前迭代次數(shù).

反饋策略可以借助隨機個體的信息幫助自身更快的完成最佳位置的探索，有效的避免了算法陷入局部最優(yōu)的風險.而且在迭代的初期，這樣的反饋策略，使得算法增強了探索開發(fā)能力，可以避免算法早熟現(xiàn)象.

3.2 萊維飛行策略

萊維飛行是服從萊維分布的隨機搜索的，是一種短距離的搜索與隨機較長距離的行走相間的行走方式，模擬自然界動物和昆蟲覓食的一個隨機游走過程.萊維分布是由法國數(shù)學家萊維提出的一種概率分布，在自然界中很多動物的運動軌跡均服從萊維分布[15].

由于萊維飛行機制，使得個體位置的變化更加靈動，所以可以避免算法陷入停滯狀態(tài).其使用引入萊維飛行的位置更行如下：

(8)

式(8)中L(β)的數(shù)學式如式(9)所示：

(9)

式(9)中μ和v是[0，1]上的隨機數(shù)，均服從正態(tài)隨機分布.相較于原L(β)，式(9)簡化了參數(shù)，但是能達到與原L(β)相同的效果.

改進后的L(β)以及α的選取的萊維飛行算法更適用于運用到被囊群算法中.不僅增強了算法的全局開發(fā)能力，同時也減小了算法陷入局部最優(yōu)的風險.

3.3 自適應權重

在標準的被囊群算法中，可以看出被囊動物的位置更新公式主要受個體當前位置、上一代個體位置和一個[0，1]之間的隨機參數(shù)決定的.這個參數(shù)的大小影響著算法的探索能力和開發(fā)能力.因為當這個隨機數(shù)越大，個體位置更新的步長越小，越有利于對種群空間的探索能力；當這個隨機數(shù)越小，個體位置更新的步長越大，越有利于算法的開發(fā)能力.由于原被囊群算法使用的是隨機數(shù)，這就使得算法在計算被囊動物的位置的時候會產(chǎn)生盲目性.正因為這種盲目性，使得算法在迭代的初期和后期不能很好的完成探索和開發(fā).

針對以上問題，本文在被囊群算法的群體行為中加入自適應權重值.在更新個體位置時，使用自適應權重代替原被囊群算法中的隨機數(shù).具體的數(shù)學表達見式(10)：

(10)

在被囊群算法的群體行為中引入自適應權重值的個體位置更新公式為：

(11)

算法迭代中前期，自適應權重值隨時間逐漸減小，位置更新權重整體增大，更新步長增大，算法在前期具有較強的探索能力；算法迭代中后期，自適應權重值隨時間逐漸增大，位置更新權重整體減小，更新步長減小，算法在后期具有較強的開發(fā)能力.

3.4 LFATS算法流程

本文將萊維飛行、反饋策略和自適應函數(shù)融入到標準的被囊群算法中，使得算法具有較強的全局搜索能力和局部開發(fā)能力，而且有效的降低了算法的盲目性.當陷入局部最優(yōu)的時候，改進的算法還具有跳出局部最優(yōu)的能力.較標準的被囊群算法來說，改進后的被囊群算法整體上效果更優(yōu).算法的流程圖如圖1所示.

圖1 算法流程圖Fig.1 Algorithm flow chart

Step1.初始化種群P;

Step2.初始化種群參數(shù)，邊界條件;

Step3.計算每個個體的適應度值；

Step4.根據(jù)式(7)加入反饋策略更新個體位置；

Step5.根據(jù)式(10)計算自適應權重值c；

Step6.在原位置更新處融入式(8)萊維飛行機制和自適應權重共同更新個體位置；

Step7.根據(jù)群體行為更新每個個體位置；

Step8.調(diào)整超出給定搜索空間邊界的個體位置；

Step9.計算更新后的群體每個個體的適應度值，如果適應度優(yōu)于之前，則更新；

Step10.如果滿足停止條件，則停止算法，否則重復步驟如果滿足停止條件，則停止算法，否則重復步驟Step 6-Step 10；

Step11.返回最優(yōu)值.

3.5 算法時間復雜度分析

在TSA算法迭代初期，假設種群規(guī)模為n，空間維度為d.則算法初始化的時間復雜度為O(n×d)，計算適應度的時間復雜度為O(Tmax×n×d)，算法在迭代過程之中的時間復雜度為O(N)，N為被囊動物噴射推進行為的次數(shù)，最終TSA算法的時間復雜度為O(Tmax×n×d×N).

LFATS算法在原算法中添加了反饋策略、萊維飛行和自適應權重.LFATS算法初始化的時間復雜度為O(n×d)，加入反饋策略的時間復雜度O(n×d)，加入萊維飛行和自適應權重模擬被囊動物的噴射推進時間復雜度為O(N)，所以最終O(Tmax×n×d×N)的時間復雜度為O(Tmax×n×d×N)，與原算法的時間復雜度相同，那么添加的這些策略機制不會對算法帶來負面影響.

3.6 算法空間復雜度分析

TSA算法的空間復雜度被定義為初始化過程中的最大空間量，即O(n×d).同理LFATS算法的空間復雜度為O(n×d).

4 實驗仿真與分析

本文采用MATLAB R2018b進行試驗，運行環(huán)境為64位Windows 10操作系統(tǒng)，處理器類型為 Intel(R)Pentium(R)CPU G4560.仿真程序中算法參數(shù)設置：種群規(guī)模N=30，最大迭代次數(shù)Tmax=500，空間維度D=30.

實驗采用6個基準測試函數(shù)，這6個基準函數(shù)有單峰函數(shù)也有多峰函數(shù).如表1所示.函數(shù)1-4為單峰函數(shù)，最優(yōu)解就是局部最優(yōu)值.函數(shù)5-6為多峰函數(shù)，最優(yōu)解能夠驗證算法是否具有跳出局部最優(yōu)能力.

表1 基準測試函數(shù)Table 1 Benchmark function

實驗1.為了驗證算法的有效性和魯棒性，使用如表1所示的6個基準測試函數(shù)作為算法的目標函數(shù)，將本文算法與標準TSA、WOA、ITAS[11]、蟻獅優(yōu)化算法(ALO)[16]和SCA做比較.此外，為了直觀地觀察引入策略的可行性，將3種策略引入到對比實驗中.為了實驗的公平性，對比算法的參數(shù)與原文獻中保持一致，本文算法參數(shù)設定如2、3節(jié)所示.

表2 不同算法尋優(yōu)結(jié)果對比Table 2 Comparison of results of algorithms

實驗中種群設置為30，最大迭代次數(shù)為500，每個算法獨立運行30次.

實驗通過表2中的最優(yōu)值、最差值、平均值、方標準、平均收斂時間差5個性能指標來評估各算法性能.

表2中的平均值和最優(yōu)值反映了算法的收斂速度和尋優(yōu)精度.不管是在單峰函數(shù)還是多峰函數(shù)上，可以明顯看到，改進的被囊群算法的平均值和最優(yōu)值優(yōu)于WOA、ALO和SCA，說明改進的被囊群算法在收斂速度和尋優(yōu)精度上優(yōu)于其他的優(yōu)化算法.F1-F4單峰函數(shù)上，LFATSA有很強的尋優(yōu)精度和收斂速度.在F1和F3上找到了理論最優(yōu)值，在F3和F4上找到的最優(yōu)值在數(shù)量級上已經(jīng)非常接近理論最優(yōu)值.由于F5和F6是多峰函數(shù)，在求解時會有一定的困難，所以LFATSA效果在多峰函數(shù)上的效果沒有單峰函數(shù)的好，但是收斂速度和尋優(yōu)精度卻是優(yōu)于WOA、ALO和SCA.LFATSA在F6上的最優(yōu)值與WOA的最優(yōu)值相等，但是LFATSA的平均值要優(yōu)于WOA，所以LFATSA的收斂速度要比WOA、ALO和SCA快.F2到F3維度上增加，WOA、ALO和SCA收斂速度和尋優(yōu)精度表現(xiàn)得很差，從負數(shù)量級到正數(shù)量級的跳躍.而LFATSA卻能在F4上尋找到理論最優(yōu)值，表明LFATSA算法在處理高維和低維函數(shù)上有更好的效果.為了驗證引入的機制對于TSA的收斂速度和尋優(yōu)精度是否有幫助.本文還使用LTSA、FTSA、ATSA來與TSA做比對，驗證其加入機制的效果.從表中明顯看出，在F1-F4上LTSA、FTSA、ATSA的收斂速度和尋優(yōu)精度都是優(yōu)于TSA的，甚至在F3中FTSA找到了理論最優(yōu)值.由于多峰函數(shù)的特性，使得求解最優(yōu)值有一定的難度.雖然在F5和F6上部分值與TSA相等，但是整體上LFATSA還是優(yōu)于TSA.所以說明引入的機制不同程度上對TSA性能上有較大的提升.

表2中的標準差可以衡量算法的穩(wěn)定性和跳出局部最優(yōu)的能力.從表中的數(shù)據(jù)可以看出，不管是單峰函數(shù)還是多峰函數(shù)，LFATSA算法的標準差都遠小于WOA、ALO和SCA的標準差.而且在F1、F2、F3、F4、F6上都達到了最優(yōu)值.所以在與對比算法相比，LFATSA穩(wěn)定性和跳出局部最優(yōu)的能力要更佳.同樣，LTSA、FTSA和ATSA三者的標準差都要低于TSA的標準差，所以驗證了引入三者對于改進TSA算法的穩(wěn)定性和跳出局部最優(yōu)的能力有很大的增強.值得注意的是，標準的TSA算法在F1、F3、F6上的標準差為理論值，所以TSA算法也具有跳出局部最優(yōu)的能力.但是在F2、F4、F5上表現(xiàn)得不是很明顯，說明標準的TSA算法也存在這陷入局部最優(yōu)的風險.但是從表中得知F2、F4、F5上的LTSA、FTSA和ATSA上的都要優(yōu)于TSA，所以使得LFATSA的穩(wěn)定性和跳出局部最優(yōu)的能力要強于標準的TSA.

此外，與其他改進的TSA算法ITSA相比，本文所提出的算法在各個基準函數(shù)的性能評估上優(yōu)于ITSA.

最后，從算法的平均耗時分析，所有算法中ALO平均收斂時間最長，達到幾百秒.從收斂曲線可以看出，每一個策略對于原算法性能有著不同程度的增強，引入更多策略，擴大了算法的搜索范圍以及找到更多的解，所以改進算法的平均耗時要大于標準的TSA算法.但相較于其他對比算法，本文改進算法的平均收斂時間要更小，所以算法增加的時間在可接受的范圍之內(nèi).

圖2(a)～圖2(d)上是各算法在單峰函數(shù)的平均收斂曲線.明顯觀察到TSA算法還有其改進的算法的收斂速度和尋優(yōu)精度都要優(yōu)于其他3種對比算法，尤其LFATSA性能更要遠超于WOA、ALO和SCA.LFATSA與LTSA、FTSA、ATSA和TSA相比，尋優(yōu)精度依次是LFATSA、FTSA、LTSA、ATSA，最后是TSA.其四者的收斂速度和尋優(yōu)精度都要高于標準的TSA算法，直觀的說明了3種策略提高了被囊群算法有效性.

圖2(e)和圖2(f)上是各算法在多峰函數(shù)的平均收斂曲線.在多峰函數(shù)F5上，所有的算法都未能找到最優(yōu)值，但是在算法迭代的后期LFATSA算法的尋優(yōu)效果要比其他算法好.雖然在迭代中期靠后一點WOA收斂速度要優(yōu)于LFATSA，但是在迭代的前期和迭代的后期，算法的收斂速度都要好于其3種對比算法，ALO和SCA效果最差.在多峰函數(shù)F6上所有的算法也都沒能尋找到最優(yōu)值，但是LFATSA、FTSA、LTSA和ATSA的收斂速度都要優(yōu)于TSA、WOA、ALO和SCA，尋優(yōu)精度上LFATSA和LTSA要略優(yōu)于其他算法.

從引入3種機制的角度上分析收斂曲線.在圖2(a)～圖2(f)中LFATSA、FTSA、LTSA和ATSA曲線下降速度快并且尋優(yōu)精度高說明引入的萊維飛行和反饋策略能夠增強算法跳出局部最優(yōu)的能力，致使算法能夠在迭代的前期有較快的收斂速度.在接下來迭代的過程中，LFATSA能夠繼續(xù)保持尋優(yōu)，說明了自適應權重的引入對于算法的探索能力有一定程度的提升.因為算法迭代后期，自適應權重值增大，算法整體權重值減小，更新步長減小，算法這時具有探索能力.在圖2(a)～圖2(d)上LFATSA收斂速度更快、尋優(yōu)精度更高，說明引入的萊維飛行、反饋策略和自適應權重增強了算法跳出局部最優(yōu)的能力和全局搜索能力，其他對比算法卻出現(xiàn)了停滯狀態(tài).在F5多峰函數(shù)上.LFATSA算法在迭代的后期還有尋優(yōu)能力，說明引入的自適應權重提高了算法的開發(fā)能力.

圖2 測試函數(shù)平均收斂曲線Fig.2 Average convergence curve of test function

實驗2.本文選取了CEC2014上的部分函數(shù)進行了驗證選取上的CEC2014部分函數(shù)如表3所示.參數(shù)設置如下：種群規(guī)模為30，CEC2014函數(shù)的搜索維度設為30，迭代次數(shù)500，獨立運行30次.實驗結(jié)果如表4所示.

表3 CEC2014函數(shù)(部分)Table 3 CEC2014 function(part)

表4 CEC2014 測試函數(shù)的結(jié)果對比Table 4 Comparison of CEC2014 test function results

表4記錄了LFATSA、TSA、WOA、ALO、和CSA算法的在CEC2014部分函數(shù)上測的平均值和標準差.由于CEC2014函數(shù)的復雜性，在尋找最優(yōu)值上有一定的困難.由表4可知，在CEC5、CEC6、CEC16上，LFATSA算法的平均值和標準差都要低于其他算法.在CEC16和CEC26上，LFATSA性能略低于TSA算法，但是卻優(yōu)于其他對比算法.在CEC24上，LFATSA的平均值大于TSA，但是LFATSA的標準差要比TSA的更小.綜上所述，改進后的被囊群算法的綜合性能要優(yōu)于其他算法，具有良好的魯棒性和有效性.

此外本文還運用Derrac等在文獻[17]中提出Wilcoxon秩和檢驗方法，對改進算法性能進行評估.使用Wilcoxon秩和檢驗方法來驗證本文改進算法在每個函數(shù)上獨立運行30次的結(jié)果是否在統(tǒng)計上與其他算法存在顯著性的差異.并且在5%的顯著性水平下進行.當p值>0.05時，接受H0假設，表明兩種算法沒有顯著性的差異；當p值>0.05時，拒絕H0假設，表明兩種算法具有顯著性的差異.

表5給出了LFATSA與TSA、LTSA、FTSA、ATSA、SCA、WOA、ALO的秩和檢驗中計算的p值，由于算法不能和本身作比較，所以在表中“Na”表示不適用，為了更明顯觀察判定結(jié)果，“+”、“-”，“-”表示LFATSA算法性能優(yōu)于，劣于和相當于對比算法.

從表5看來，LFATSA算法在函數(shù)F5上性能低于FTSA和ATSA外.在其他位置上都優(yōu)于其他算法，總體上LFATSA算法的性能與其他算法有著顯著性的差異.

表5 基準函數(shù) Wilcoxon 秩和檢驗的p值Table 5 p value for Wilcoxon′s rank-sum test on benchmark function

5 結(jié)束語

為了增強標準的TSA算法的收斂速度和尋優(yōu)精度已經(jīng)跳出局部最優(yōu)的能力，本文在標準的TSA算法上引入了萊維飛行機制、反饋策略和自適應權重，提出了基于萊維飛行和反饋策略的自適應被囊群算法(LFATSA).萊維飛行使得被囊動物個體位置的變化更加靈動，當算法陷入局部最優(yōu)的時，算法就具有了跳出局部最優(yōu)的能力；其次，反饋策略中引入一個隨機被囊動物，將隨機被囊動物的信息反饋給當前被囊動物.通過這種反饋方式，可以更好的引導算法朝著最優(yōu)值前進；再次，自適應權重機制使得算法在迭代前期和迭代后期的探索能力和開發(fā)能力都有增強.為了驗證改進算法的魯棒性和有效性，本文將改進算法與其他算法及單獨改進的TSA算法應用于基準測試函數(shù)和CEC2014函數(shù)上進行尋優(yōu)，通過平均值和標準差等指標對算法性能進行評估.另外，為了更好的評估改進算法的性能，本文還使用統(tǒng)計檢驗Wilcoxon對算法進行顯著性分析.試驗結(jié)果表明LFATSA算法具有很好的性能，收斂速度快和尋優(yōu)精度高，探索能力和開發(fā)能力得到增強.

在后續(xù)的研究中，可以考慮使用其他的策略更好的改進算法，使得算法在多峰函數(shù)上表現(xiàn)得更佳并能使用到實際工程運用中，解決更多工程問題.