基于混沌遷移的社會學習天牛群算法

鄭 源， 付曉剛， 軒艷文

(上海電機學院 電氣學院， 上海 201306)

群智能算法是模仿自然界中沒有智能的個體或智能度不高的個體，在群體的交互中學到一些簡單的規則，然后在群體層面中涌現出比較高級的智能。天牛須算法(Beetle Antennae Search Algorithm, BAS)[1-2]作為一種生物智能算法模擬了自然界中天牛利用天牛須來搜尋食物的過程。相比于粒子群算法(Particle Swarm Optimization, PSO)等群智能優化算法，BAS只需一個個體，參數少易于實現，對于低緯優化函數收斂速度快，質量高。邵良杉等[3]為了改進花朵授粉算法(Flower Pollination Algorithm, FPA)的收斂速度和精度的問題，在FPA的全局尋優階段引入BAS；陳婷婷等[4]提出基于BAS的PSO，并將其應用于包含完整費用的投資組合模型中，提高了PSO的有效性和穩定性；趙玉強等[5]提出了一種混沌天牛群算法，提高了BAS收斂性和尋優能力。上述文獻對BAS都做出了一定的運用和改進。

為了改善BAS的搜索性能，解決其精度低和易陷入局部最優的缺陷，本文將社會學習策略、拉丁超立方抽樣(Latin Hypercube Sampling, LHS)、混沌遷移策略、相似度與BAS深度融合。首先用LHS產生初始群體，其次基于相似度采用混沌遷移策略，最后根據社會學習策略更新種群。該算法改進了傳統BAS算法在高維問題上精度低、易陷入局部最優的缺點，并保留了BAS參數少、易于實現的優點，極大地提高了全局搜索的能力，降低了收斂的迭代次數。本文選取了4種測試函數，對社會學習天牛群算法(Social Learning Beetle Swarm Algorithm, SLBSA)、天牛群算法(Beetle Swarm Optimization, BSO)和PSO進行仿真測試和比較。結果表明SLBSA具有更好的效果。

1 BAS基本原理

BAS基本原理為天牛在覓食過程中并不知道食物的精確位置，但可通過判斷左右須食物味道的強弱來確定自身的飛行方向。如果右須收集到的味道強于左須，天牛下一步就往左飛，反之，天牛往右飛。BAS模型建立的方法如下：

求解D維優化問題時，天牛由質心、左須及右須3個點代替。

天牛的質心、左須和右須之間的關系為

(1)

式中：X為質心在D維度空間中的位置X=(x1,x2,…,xd)；Xr、Xl為右須和左須在空間中的位置；L為兩須到質心的距離。

(2)

式中：ranks()是隨機函數，規定將右須作為天牛的朝向。

式(2) 算法的迭代過程中，天牛判斷左右須的適應度，將適應度強的一邊作為更新的方向。

天牛位置的更新方法為

x(t+1)=

(3)

δ(t+1)=λδ(t)

(4)

式中：t為算法的當前迭代次數，即天牛當前移動次數；f(xr(t))為右須的適應度值，同理左須為f(xl(t))；δ(t)為第t次迭代的步長；sign()為符號函數，為下一次移動時候的方向；λ為步長因子，一般取0.95。若右須的適應度值大于左須，sign()取1，天牛往右須方向以步長δ(t)移動，反之，往左須方向移動。

2 改進的BSO

2.1 LHS原理

文獻[6]表明群智能算法的收斂性受初始群體分布的影響較大。LHS[7]可從決策空間中選取較均勻、合適數目、具有全區域信息的樣本點,有利于保證初始群體的多樣性,故本文采用LHS產生初始種群。具體抽樣原理如下：

設某一待求概率問題的K個隨機變量X1,X2,…,XK中的任意一個累積概率分布函數為

YK=FK(XK)

(5)

設采樣次數為N，將YK的縱軸N等分且各隨機變量相互獨立，xkn為第k個變量的第n次抽樣。選取每個區間的中點作為YK的采樣值，然后用YK=FK(XK)的反函數來計算xkn，則有

(6)

抽樣步驟如下：

(1) 確定決策空間樣本的維數為a，以及要從決策空間中抽取樣本點的個數b。

(2) 把已知的樣本中每一維劃分為b個等概率、不重復的區域，從而得到a·b個等量的小區間。

(3) 在a·b個等概率的小區域中，隨機選取b個不重復的全排列小區域即可得到對應的樣本矩陣A。

(4) 在步驟(3)中隨機選取的全排列小區域內進行隨機取樣，選取隨機的一個樣本點，從而保證b維數據中，每一維每一個區域中都能選取一個樣本，即獲得b個樣本點。

2.2 基于相似度的混沌遷移策略

本文提出的更新策略的基本思想是考慮在迭代過程中一直向最優個體靠近，但無法在種群中占據支配地位的天牛，這些天牛在算法滿足終止條件時無法達到最優值，不利于天牛群在尋優過程中維持多樣性、跳出局部最優。類比生物群體在覓食過程中，最優天牛為最先找到食物的天牛，而非最優的其他天牛，后找到資源，導致資源已經大部分被最優個體取走，所以對多次迭代后靠近最優個體的天牛根據天牛相似度[8]S(i,j)對天牛群進行混沌遷移[9]操作。

相似度S(i,j)定義如下：

S(i,j)=

(7)

式中：d(i,j)為個體j與i的歐氏距離，i為第t代適應度最大的天牛；dmin為與i相距最近個體的歐氏距離；dmax為與i相距最遠天牛的歐氏距離。

相似度函數為

(8)

式中：pj(t)為0～1的隨機數。

相似度計數為

(9)

混沌序列[10]具有內隨機性、遍歷性和規律性等特點，看似混亂卻有著精致的內在結構。本文提出了基于相似度的動態混沌遷移算法，引入進化過程中，Logistic映射混沌模型程序為

(10)

式中：d為對應的維度；δ為遷移參數，當混沌序列的長度S大于種群數N的20%左右時效果較好，所以δ取0.2；σ為控制參數，取(3.56，4)時系統進入混沌狀態。

賦D個0～1的混沌初值，根據迭代式(11)可得混沌序列G={x1,x2,…,xs}，然后對所有相似度值sh取1的天牛進行混沌遷移操作，即

xi=xi(bu-bl)+bl，i=1,2,…,s

(11)

式中：bu、bl分別為上邊界和下邊界。

2.3 社會學習策略

社會學習策略就是種群中適應度差的個體向多個適應度優于自己的個體學習。由于BAS個體搜索范圍有限，并且在處理高維、復雜問題時難以搜尋到最優解，而社會學習粒子群算法[11-13](Social Learning Particle Swarm Optimization, SLPSO)，在有限計算次數上擁有更好的性能，尤其是在解決高維、復雜問題上擁有更顯著的優勢。本文在天牛須算法基礎上提出了SLBSA，種群中個體j的t到t+1代迭代過程為

xjd(t+1)=

(12)

社會學習策略中天牛的速度更新規則為

(13)

式中：k(Pk>Pj)為個體j在大于它適應度的個體中隨機選擇的學習對象，并且個體j在每個維度上選擇的學習對象k并不是固定的，都是隨機的。天牛i可以向當前優于它的多個個體學習，使其能夠獲得更多的信息。xkd(t)為個體k在第t代的d維上的位置(1≤d≤D)；D為決策空間維數；xm(t)為天牛群位置在d維上的均值；ε為影響因子用來控制xm(t)的社會影響力，本文取0.01；r1～r3為個體j在[0,1]之間的隨機數。

概率函數為

(14)

式中：N為種群數；i為個體j在適應度排序后在種群中的排位。

社會學習策略步驟如下，流程見圖1。

(1) 對t代種群P(t)進行適應度評價，計算其大小。

(2) 由壞到好，按適應度值對種群排序。

(3) 由適應度值最壞的天牛開始，其每一個維度都獨立且隨機地向優于自身的天牛學習，通過社會學習得到第t+1代種群P(t+1)。

圖1 社會學習策略流程圖

2.4 算法步驟

SLBSA的流程如下，具體流程見圖2。

圖2 SLBSA算法流程圖

(1) 初始化算法參數，設置天牛群規模為N，質心與觸須的距離為L，學習因子為ε，迭代步長為δ(0)，控制參數為σ，遷移參數為δ，步長因子為λ，最大迭代次數為imax。

(2) 采用LHS產生規模為N的初始群體P(0)，并計算初始種群的適應度值。

(3) 計算最優天牛i與其他天牛的相似度，根據式(7)～(9)計算相似度計數。

(4) 根據式(10)判斷是否需要進行混沌遷移操作，如果需要轉步驟(5)，反之轉步驟(6)。

(5) 對相似度函數取1的天牛通過式(10)進行混沌遷移操作，計算遷移后的天牛的適應度值。

(6) 計算當前天牛群在d維上的均值xm，然后根據天牛的適應度值進行排序，通過式(12)、(13)從最壞的天牛開始隨機向由于自身的個體學習，并更新速度與位置。

(7) 對超出范圍的天牛進行越界處理，計算更新后的天牛群的適應度值。

(8) 檢驗是否滿足迭代終止條件，若是，輸出全局最優解及對應的位置，否則跳轉步驟(3)。

3 數值實驗

3.1 測試函數及參數設定

為了評估SLBSA的性能，引入了4個標準測試函數對SLBSA和BAS進行測試和對比。采用2種單模態函數f1～f2對SLBSA的收斂性進行檢驗；2種多模態函數f3～f4對算法的群體多樣性、全局搜索能力和逃離局部最優能力進行考察。天牛群的初始種群大小為300，所有函數維度為20，迭代次數為100次，所有函數的運行次數為50次，優化目標取10-3。基本測試函數的相關參數見表1。

表1 測試函數

3.2 測試結果分析

測試結果對比包括尋優成功率(Rate)、最佳適應度值(Best)、最差適應度值(Worst)、平均適應度值(Mean)，如表2所示。

表2 測試結果對比

對于測試函數f1～f4，SLBSA收斂精度都高于 PSO和BSO，說明改進策略能夠提高收斂的精度和局部搜索能力，對于Shpere、Rosenbrock和Griewank函數，SLBSA達到目標適應度值1.0×10-3的成功率分別為100%、84%和86%，都明顯高于PSO和BSO，且找到最優值的概率較大。對于相對復雜的單模態測試函數Rosenbrock，由于種群間的信息量不夠，BSO和PSO的尋優成功率只有0%和12%，但是SLBSA加入了混沌遷移策略和社會學習策略增加了種群間的信息交流，尋優成功率為84%，明顯高于BSO和PSO，所以SLBSA的尋優穩定性更好，并且尋優精度更高，每次尋優的結果相差較小。但是對于Rastigrin測試函數而言，3個算法的尋優成功率都很低，算法在Rastigrin類的測試函數上的收斂精度不佳，因為Rastigrin測試函數是一個典型的非線性多峰函數，它具有大規模的搜索區間和局部最小值，當導致優化算法尋找到滿足設定的尋優精度的全局最小值較難。但SLBSA在收斂精度和平均值上相比PSO和BSO都有提高，說明SLBSA相對而言性能更好。以上4種函數的測試結果如圖3～6所示。

由圖3和圖4的單模態函數測試結果可見，SLBSA收斂速度和收斂精度優于PSO和BSO。由于SLBSA在產生初始種群時采用了HLS，所以SLBSA具有多樣性更好的初始種群，在迭代的初期收斂速度都優于PSO和BSO。SLBSA在種群更新過程中利用基于相似度的混沌遷移策略，當相似度計數達到能產生較好混沌序列時，對相似度計數為1 的個體進行混沌遷移操作，即保證天牛群在迭代過程中既能保證產生較好的混沌個體維持種群的多樣性，也避免了每次迭代都進行混沌遷移操作，降低了一定的計算量。社會學習策略保證了天牛群在更新時充分的信息交換，隨機向優于自己的多個個體學習，使天牛群能搜索更廣闊的空間，避免陷入局部最優，隨著迭代的進行，天牛的步長逐漸減小，天牛群能進行更精細地搜索，收斂精度更高，算法的尋優性更好。

圖3 Shpere函數測試結果

圖4 Rosenbrock函數測試結果

圖5 Griewank函數測試結果

圖6 Rastigrin函數測試結果

由圖5和圖6的多模態函數測試結果可見，SLBSA在前期和后期的收斂速度以及最后的收斂精度都優于PSO和BSO，但在Rastigrin函數上，SLBSA的收斂速度要劣于PSO，由于多模態的Rastigrin函數相對復雜，采用LHS產生初始種群使天牛群相對分散，所以在中期收斂速度可能會略微弱于隨機產生初始種群的PSO和BSO，但在迭代后期體現了混沌遷移和社會學習策略在收斂精度和速度上的優勢，PSO和BSO分別在50代和40代左右才開始收斂，而SLBSA在30代左右就開始收斂。總之，SLBSA的收斂速度和跳出局部最優的能力都優于PSO和BSO。

4 結 論

針對天牛須算法尋優時收斂速度慢，容易陷入局部最優的問題，提出了SLBSA來提高算法的有效性，采用LHS保證初始種群的多樣性。在天牛群位置更新過程中加入基于相似度的混沌遷移策略，在加入擾動的同時還保留了最優個體，防止了種群的早熟也保證了收斂速度；社會學習策略增加了個體間的信息交流，保證了在尋優過程中對更廣的空間進行探索，在算法后期有更大的概率跳出局部最優。實驗結果證明了SLBSA的各方面能力都優于PSO和BSO。在以后的工作中，將會考慮到初始種群數為N的SLBSA在每次迭代過程中評價函數的使用次數至少為3N的問題，采用代理模型[14-15]的方法減少評價函數的使用次數，使算法能夠運用到評價昂貴的實際工程問題中。