基于自然選擇和随機擾動的改進磷蝦群算法

文章目錄

• 一、理論基礎
• • 1、磷蝦群算法(KH)
  • 2、改進的磷蝦群算法(ANRKH)
  • • （1）覓食權重和運動權重的時變非線性遞減政策
    • （2）随機擾動
    • （3）自然選擇
    • （4）ANRKH算法步驟
• 二、仿真實驗與分析
• 三、參考文獻

一、理論基礎

1、磷蝦群算法(KH)

磷蝦群(Krill herd algorithm, KH)算法是一種新的啟發式智能優化算法，該算法主要是基于對南極磷蝦群在海洋環境中的生存運動過程的仿真研究。對于每個磷蝦個體，它的位置更新主要受到3個因素的影響：

1）誘導運動(周圍磷蝦的誘導)

2）覓食活動

3）随機擴散

磷蝦個體的速度更新公式采用了下面的拉格朗日模型： d x i d t = N i + F i + D i (1) \frac{dx_i}{dt}=N_i+F_i+D_i\tag{1} dtdxi​​=Ni​+Fi​+Di​(1)其中， N i , F i , D i N_i,F_i,D_i Ni​,Fi​,Di​分别代表誘導運動、覓食活動和随機擴散。

3個因素的公式構造如下： N i = N m a x α i + w n N i o l d (2) N_i=N^{max}\alpha_i+w_nN_i^{old}\tag{2} Ni​=Nmaxαi​+wn​Niold​(2) F i = V f β i + w f F i o l d (3) F_i=V_f\beta_i+w_fF_i^{old}\tag{3} Fi​=Vf​βi​+wf​Fiold​(3) D i = D m a x ( 1 − t t m a x ) δ (4) D_i=D^{max}(1-\frac{t}{t_{max}})\delta\tag{4} Di​=Dmax(1−tmax​t​)δ(4)其中， N m a x , V f , D m a x N^{max},V_f,D^{max} Nmax,Vf​,Dmax分别代表最大誘導速度、最大覓食速度和最大擴散速度； α i , β i , δ \alpha_i,\beta_i,\delta αi​,βi​,δ分别代表誘導方向、覓食方向和擴散方向； w n , w f w_n,w_f wn​,wf​分别代表誘導權重和覓食權重； t , t m a x t,t_{max} t,tmax​分别為目前疊代次數和最大疊代次數。

磷蝦個體在 t t t到 t + Δ t t+\Delta t t+Δt區間的位置更新公式如下： x i ( t + Δ t ) = x i ( t ) + ( d x i d t ) ( Δ t ) (5) x_i(t+\Delta t)=x_i(t)+(\frac{dx_i}{dt})(\Delta t)\tag{5} xi​(t+Δt)=xi​(t)+(dtdxi​​)(Δt)(5) Δ t = C t ∑ j = 1 N V ( U B j − L B j ) (6) \Delta t=C_t\sum_{j=1}^{NV}(UB_j-LB_j)\tag{6} Δt=Ct​j=1∑NV​(UBj​−LBj​)(6)其中， Δ t \Delta t Δt為速度向量的縮放因子， C t C_t Ct​為步長縮放因子，取介于 [ 0 , 2 ] [0,2] [0,2]的常數， N V NV NV代表變量數， U B j , L B j UB_j,LB_j UBj​,LBj​分别為第 j j j個變量的上界和下界。

為了進一步提升算法的性能，在算法中執行遺傳算子(交叉或變異)，經測試，交叉算子更為有效。 x i , m = { x r , m r a n d i , m < C r x i , m e l s e (7) x_{i,m}=\begin{dcases}x_{r,m}\quad rand_{i,m}<Cr\\x_{i,m}\quad else\end{dcases}\tag{7} xi,m​={xr,m​randi,m​<Crxi,m​else​(7) x i , m = { x g b e s t , m + μ ( x p , m − x q , m ) r a n d i , m < M u   x i , m      e l s e (8) x_{i,m}=\begin{dcases}x_{gbest,m}+\mu(x_{p,m}-x_{q,m})\quad rand_{i,m}<Mu\\\ x_{i,m}\quad\quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\, else\end{dcases}\tag{8} xi,m​={xgbest,m​+μ(xp,m​−xq,m​)randi,m​<Mu xi,m​else​(8)其中， C r Cr Cr為交叉算子， M n Mn Mn為遺傳算子， r a n d rand rand為 [ 0 , 1 ] [0,1] [0,1]上均勻分布的随機數， μ \mu μ為 [ 0 , 1 ] [0,1] [0,1]内的常數。

2、改進的磷蝦群算法(ANRKH)

（1）覓食權重和運動權重的時變非線性遞減政策

較大的 w n w_n wn​和 w f w_f wf​有利于跳出局部極小點，算法有很強的全局搜尋能力；較小的 w n w_n wn​和 w f w_f wf​有利于對目前區域進行精确的局部搜尋，提高算法的局部搜尋能力；是以，合理的調節誘導權重 w n w_n wn​和覓食權重 w f w_f wf​是算法高效搜尋且避免陷入局部最優的關鍵，本文在這裡提出了一種基于時變的非線性遞減政策，即： w n = w f = w m a x − w m i n t m a x ⋅ ( t m a x − t ) + w m i n ⋅ r a n d (9) w_n=w_f=\frac{w_{max}-w_{min}}{t_{max}}\cdot(t_{max}-t)+w_{min}\cdot rand\tag{9} wn​=wf​=tmax​wmax​−wmin​​⋅(tmax​−t)+wmin​⋅rand(9)其中， t t t和 t m a x t_{max} tmax​分别為目前疊代次數和最大疊代次數， w m a x w_{max} wmax​和 w m i n w_{min} wmin​分别代表誘導權重和覓食權重的最大值和最小值。這種政策使得算法的 w n w_n wn​和 w f w_f wf​總體在逐漸減小，随機數 r a n d rand rand的引入改變了其線性遞減的單調模式，使得算法在整個疊代過程

中都可以很好的适應目前的搜尋情況，進而更加有效的調節算法的全局搜尋和局部勘探能力。

（2）随機擾動

在新一代種群生成時加入随機擾動，更新公式如下： x i ( t + Δ t ) = x i ( t ) + ( d x i d t ) ⋅ ( Δ t ) ⋅ r a n d (10) x_i(t+\Delta t)=x_i(t)+(\frac{dx_i}{dt})\cdot(\Delta t)\cdot rand\tag{10} xi​(t+Δt)=xi​(t)+(dtdxi​​)⋅(Δt)⋅rand(10)通過上述更新方式的随機擾動，可以增加新一代磷蝦群個體中包含的資訊量，使得陷入局部最優的磷蝦個體跳出局部最優點，朝着全局最優方向前進，在算法後期，可以明顯的增強算法的局部勘探能力，提升求解精度。

（3）自然選擇

自然選擇的基本思想是：在對新一代磷蝦群個體生成時進行随機擾動過後，我們将對生成的新一代磷蝦群個體進行評估，即按照目标函數值進行排序，用新種群中目标函數值好的前 1 / K 1/K 1/K替換目标函數值差的後 1 / K 1/K 1/K，在此基礎上保留原來每個磷蝦個體所記憶的曆史最優值，提高新種群中優秀粒子的比重，以此來確定每次疊代的磷蝦個體都具有很好的性能，這樣也會加快收斂速度。在本文中，為了保持磷蝦個體的多樣性以及全局性，防止磷蝦個體陷入局部最優，我們取 K K K為10，即用前10%的磷蝦個體來替換後10%的磷蝦個體。

（4）ANRKH算法步驟

請參考文獻[1]。

二、仿真實驗與分析

為了驗證ANRKH算法的性能，本文将ANRKH算法與兩種相關算法—KH 算法和KHLD算法進行比較。以文獻[1]中的f2、f3、f5為例。為了保證測試算法的公平性，3種算法中共同的參數設定如下：磷蝦個體數目 N P = 100 NP=100 NP=100，最大疊代次數 t m a x = 1000 t_{max}=1000 tmax​=1000，最大誘導速度 N m a x = 0.001 N^{max}=0.001 Nmax=0.001，最大覓食速度 V f = 0.02 V_f=0.02 Vf​=0.02，最大随機擴散速度 D m a x = 0.005 D^{max}=0.005 Dmax=0.005；3種算法中不同的參數取值見表1；每個函數進行30次獨立數值實驗。

表1 KH、KHLD和ANRKH中的參數取值

結果顯示如下：

函數：F2
KH：最大值: 124.3161,最小值:28.6977,平均值:43.0134,标準差:29.4007
KHLD：最大值: 101.6416,最小值:26.2886,平均值:30.2278,标準差:13.5046
ANRKH：最大值: 81.6635,最小值:24.9959,平均值:28.6219,标準差:12.2347
函數：F3
KH：最大值: 0.91102,最小值:0.37651,平均值:0.60851,标準差:0.12396
KHLD：最大值: 0.024535,最小值:0.0063132,平均值:0.013014,标準差:0.0046107
ANRKH：最大值: 9.4045e-07,最小值:1.4627e-07,平均值:5.5261e-07,标準差:1.9059e-07
函數：F5
KH：最大值: 0.27584,最小值:0.18773,平均值:0.22487,标準差:0.024735
KHLD：最大值: 0.038433,最小值:0.019181,平均值:0.027884,标準差:0.0054838
ANRKH：最大值: 0.00044475,最小值:0.00026492,平均值:0.00033714,标準差:4.5962e-05
           

由此可以看出，ANRKH算法能夠有效地避免陷入局部最優，在全局搜尋和局部勘探能力上有着顯著優勢。

三、參考文獻

[1] 劉沛, 高嶽林, 郭偉. 基于自然選擇和随機擾動的改進磷蝦群算法[J]. 小型微型計算機系統, 2017, 38(8): 1845-1849.

[2] Li J , Tang Y , Hua C , et al. An improved krill herd algorithm: Krill herd with linear decreasing step[J]. Applied Mathematics & Computation, 2014, 234:356-367.

[3] Gandomi A H, Alavi A H. Krill Herd:a new bio- inspired optimization algorithm[J]. Commun Nonlinear Sci Numer Simul, 2012, 17(12) : 4831-4845.