基于互利共生和優勝劣汰的改進磷蝦群算法

王 滔，高岳林，曹 凱

(北方民族大學 信息與系統科學研究所，寧夏 銀川 750021)

磷蝦群(KH)算法[1]是一種用于優化全局非線性問題的群智能優化算法。該算法是基于對南極磷蝦的生存環境以及生活規律的仿真模擬[2]。磷蝦群為了更好地存活下來，既要躲避捕食者的襲擊，又要時刻搜尋食物的位置；同時，磷蝦種群會不斷淘汰生存能力較差的個體，使得種群在惡劣的環境中得以繁衍。磷蝦群算法前期收斂速度快，但后期無法跳出局部最優，求解精度較差。對此，研究人員對磷蝦群算法從不同方面進行了改進，文獻[3-5]主要是對算法的部分參數進行了調整，文獻[6-7]則是對算法采用不同的改進優化策略，提升了算法的搜索能力。本文提出了一種基于互利共生和優勝劣汰的改進磷蝦群算法(MASFKH).在磷蝦群每一次迭代過程中，磷蝦群中的個體在感知捕食者存在的情況下，會向其他磷蝦個體傳遞危險信號，磷蝦個體會不斷與其他位置的磷蝦進行比較，朝著更安全的位置游去；即適應度值較差的個體會向適應度較好的方向移動，從而達到躲避捕食者襲擊的目的，有效地增加了每次迭代過程中的信息交流。然后，通過優勝劣汰的進化策略，用目標函數適應度值好的磷蝦個體位置替換目標函數適應度值較差的磷蝦個體位置，提升了下一輪迭代的磷蝦個體的質量，以此提升算法的求解精度和局部的搜索能力。最后，用仿真實驗說明了算法的有效性。

1 KH算法

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

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

2) 覓食活動；

3) 隨即擴散。

磷蝦個體的速度更新公式采用了下面的拉格朗日模型：

(1)

其中，Ni，Fi，Di分別代表誘導運動、覓食運動和隨機擴散。

3個因素的公式構造如下：

Ni=Nmaxαi+wnNold,i.

(2)

Fi=vfβi+wfFold,i.

(3)

(4)

式中：Nmax，vf，Dmax分別代表最大誘導速度、最大覓食速度和最大擴散速度；αi，βi，δ分別代表誘導方向、覓食方向和擴散方向；wn，wf分別代表誘導權重和覓食權重；t，tmax分別為當前迭代次數和最大迭代次數。其中Nmax=0.01，vf=0.02，Dmax=0.005[1].

磷蝦個體在t到(t+Δt)區間的位置更新如下：

(5)

(6)

式中：Δt為速度向量的縮放因子；Ct為步長縮放因子，取介于[0,2]的常數；Nv代表變量數；Bu,j，BL,j分別為第j個變量的上界和下界。

為了進一步提升算法的性能，在算法中執行遺傳算子(交叉或變異)，經測試，交叉算子更為有效[1]。

(7)

(8)

式中：Cr為交叉算子；Mu為遺傳算子；a為[0,1]上均勻分布的隨機數；μ為[0,1]內的常數。

2 MASFKH算法

由標準KH算法知,由于算法在迭代過程中粒子運動具有隨機性，所以算法運動到較差位置時，即磷蝦群運動到捕食者存在的惡劣環境時，磷蝦個體之間若不能及時地進行信息傳遞做出危險預警，磷蝦群很容易被捕食掉，也就出現了大量的無效迭代，使得算法不能很好的完成局部搜索；特別是處理多峰優化問題時，算法的解更易陷入局部最優，出現“早熟”現象。基于此，提出了一種基于互利共生和優勝劣汰的改進磷蝦群算法。

2.1 磷蝦群互利共生策略

自然界中的生物生活在一起，構成了一個穩定的生態系統，不同物種之間不斷地發生直接或間接的某種關系。這種關系大致可以分成3類：互利共生，即對雙方都相互有利；共棲，只對其中一方有利，但對另一方無害；寄生，對其中一方有利，但對另一方有害。互利共生歸納總結為：不同物種的個體生活在一起，雙方都收益的相互關系，也可指即使相互離開但仍可正常生存的生物，它們既相互依存又相互獨立，構成了物種間的合作關系。

本文利用的互利共生策略就是使得磷蝦之間具有上述的合作關系。磷蝦之間通過信息交換、信息傳遞的方式為其他磷蝦個體提高生存能力。磷蝦在感知有捕食者存在的危險情況下會四處逃竄，導致整個磷蝦群會往不同的方向移動，在此過程中引入互利共生策略，使得磷蝦個體之間能夠相互交流，傳遞危險信號，為其他磷蝦預警。磷蝦個體會通過比較各自的位置優劣，即當前位置的適應度值差的磷蝦個體，會朝著適應度值好的磷蝦方向移動，從而達到躲避捕食者的目的。記當前位置安全系數水平Xk，全局最安全系數水平Xbest，全局磷蝦平均安全系數水平Xmean，用如下公式表示全局最安全的磷蝦向所有磷蝦發出的危險警告后，各磷蝦的移動方式：

X'k=Xk+ri×(Xbest-λXmean) .

(9)

λ=round[1+a(0,1)] .

(10)

其中，ri是[0,1]之間的隨機數，λ是預警因子，λ的值是1或2.如果X'k優于Xk，那么就更新Xk；如果X'k優于Xbest，則更新Xbest.

此時，收到全局預警危險信號后，磷蝦群之間會相互傳遞危險信號，所以隨機地選擇兩個磷蝦p和q，且Xp≠Xq.這一策略的互利共生現象由下式表示：

(11)

式中：ri是[0,1]之間的隨機數；X'p和X'q分別表示磷蝦p和q磷蝦在交流前的安全系數水平；X"p表示磷蝦p向磷蝦q交流后的安全系數水平。如果X"p優于X'p，則更新X'p；如果X"p優于X'q，則更新X'q.

2.2 優勝劣汰策略

在上述改進的基礎上，本文還加入了優勝劣汰的思想，最終得到了基于互利共生和優勝劣汰的改進磷蝦群算法(MASFKH).

優勝劣汰的基本思想是為了維護種群中粒子的多樣性。“優勝劣汰”策略具體操作辦法為：在對新一代種群生成過后，將對新生成的種群進行適應度值的評估，即按照適應度值進行排序，在算法中將最差的R個粒子舍去，同時在搜索空間隨機產生R個新粒子。若R取值越大，則產生的新粒子越多，有利于保持種群的多樣性，避免算法陷入局部最優。但如果R的取值很大，則會使算法趨于隨機搜索；若R取值越小，則不利于算法維持粒子的個體多樣性，算法的全部搜索能力變弱。因此，這里的R取NP/10，其中NP為種群規模。

3 MASFKH算法具體流程

Step 1：確定種群規模并初始化種群及相關參數的設置；

Step 2：將目標函數值作為適應度值，評價種群中每個粒子的適應度，并將當前的磷蝦群個體的位置和適應度值存儲在各個體的Pbest，將所有的Pbest中最優的存儲在Gbest中；

Step 3：采用式(2)—(4)計算磷蝦個體的運動速度分量；

Step 4：采用式(9)—(11)對磷蝦群實行“互利共生”策略；

Step 5：對于各個體，將其所經歷的位置和目標函數進行比較，更新Pbest和Gbest；

Step 6：將新的種群按適應度值排序，進行“優勝劣汰”策略；并保持Pbest和Gbest不變；

Step 7：判斷算法是否滿足終止條件，若滿足，輸出Pbest和Gbest；否則，返回Step 3繼續搜索。

4 實驗及結果分析

4.1 數值實驗

為了驗證MASFKH算法的性能，本文將MASFKH算法、KH算法和KHLD算法[5]進行比較。分別對10個典型的標準測試函數進行測試，每個測試函數獨立進行30次的數值實驗。其中f1—f3是典型的單峰函數，在整個搜索空間中僅有一個極值點；f4為病態函數，是一個經典復雜優化問題，它的全局最優點位于一個平滑、狹長的拋物型山谷內；f5—f10是典型的非線性多峰函數，在探索空間中存在大量的局部極值點，若算法的設計存在問題則很難跳出局部極值去全局最優。測試內容包括3種算法在10個測試函數[8-9]上最小值(Min)，最大值(Max)，平均值(Mean)，標準方差(Std)的表現，結果見表1.

4.2 結果分析

對實驗數據進行分析時，主要對最小值(Min)、最大值(Max)、平均值(Mean)和方差(Std)等4方面進行比較。從表2可以直觀看出，除了f4之外的9個函數，MASFKH算法在Min、Max和Mean方面的數值結果比KH和KHLD算法都有顯著提高；Min和Max值分別代表不同算法獨立運行30次相同測試函數所得最優值的最小值和最大值，Min值越小說明算法所能達到的最大精度越高；Std代表不同算法獨立運行30次所得最優解的方差，方差越小表明算法越穩定。在10個測試函數里MASFKH的Std均是表現最優的。由此可知：Min，Max，Mean方面的表現說明MASFKH算法相較于KH和KHLD算法來說，在絕大多數測試條件下，MASFKH算法具有很強的全局和局部搜索能力，因而在求解精度上表現優異。Std方面的表現說明了MASFKH算法每次獨立測試的結果都相差無異，具有較強的穩定性，是一種可靠的智能算法。

表1 測試函數Table 1 Test functions

表2 MASFKH、KH和KHLD等3種算法的數值實驗結果Table 2 Numerical results of MASFKH、KH and KHLD algorithm

圖1(a)—(f)為各種算法測試函數f1—f10的部分收斂圖。圖1(a)，(b)為經典單峰函數的收斂實驗圖，MASFKH算法與另外兩種算法相比，前期迅速收斂到極值點附近，在前300代都出現頻繁跳出局部最優的趨勢，且在精度上提高了4個數量級以上。由圖1(c)可以看出，MASFKH算法的最終求解精度雖與KH和KHLD算法相差無異，但MASFKH算法在前期就收斂到了穩定解。圖1(d)—(f)為3個經典多峰測試函數對比圖，MASFKH算法的收斂速度和求解精度均遠優于KH和KHLD算法，說明MASFKH算法更夠更準確地找到全局最優值。由表2函數f2、f8、f10實驗結果可以看出，在算法迭代的后期，MASFKH相較于KH和KHLD仍具有很強的局部搜索能力，使得算法避免陷入局部最優；由表2函數f2、f5、f8、f10可以看出，MASFKH的最終求解精度即尋優能力遠遠優于KH和KHLD，均提高了5個數量級以上，在其他測試函數上求解精度也有顯著提升；總之，對于大多數的單峰函數和多峰函數，MASFKH算法都能較快地找到函數的最優近似解并達到穩定，說明該算法有著穩定的全局和局部搜索能力。

圖1 部分函數的運行結果Fig.1 Results of function

5 結論

針對磷蝦群算法搜索能力較差的缺點，提出了一種基于互利共生和優勝劣汰的改進磷蝦群算法(MASFKH).通過數值實驗可知，MASFKH算法、KH算法和KHLD算法相比較，MASFKH算法增強了每次迭代粒子間的信息交流，有效地利用了局部最優解信息，避免所有磷蝦陷入較差的局部最優區域。總的來說，在解決單峰和多峰優化問題上，MASFKH算法在探索能力和求解精度上都有著顯著的優勢。

[1] GANDOMI A H,ALAVI A H.Krill herd:a new bio-inspired optimization algorithm[J].Communications in Nonlinear Science & Numerical Simulation,2012,17(12):4831-4845.

[2] HOFMANN E E,HASKELL AG E,KLINCK J M,et al.Lagrangian modelling studies of antarctic krill (Euphasia superba) swarm formation[J].ICES Journal of Marine Science,2004,61:617-631.

[3] WANG G G,GUO L,GANDOMI A H,et al.Chaotic krill herd algorithm[J].Information Sciences,2014,274(274):17-34.

[4] SAREMI S,MIRJALILI S M,MIRJALILI S.Chaotic krill herd optimization algorithm[J].Procedia Technology,2014,12(1):180-185.

[5] 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(10):356-367.

[6] 郭偉,高岳林,劉沛.一種自適應慣性權重的改進磷蝦群算法[J].太原理工大學學報,2016,47(5):651-657.

GUO W,GAO Y L,LIU P.An improved krill herd algorithm with adaptive inertia weight[J].Journal of Taiyuan University of Technology,2016,47(5):651-657.

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

LIU P,GAO Y L,GUO W.Improved krill herd algorithm based on natural selection and random disturbance[J].Journal of Chinese Computer Systems,2017,38(8):1845-1849.

[8] JAMIL M,YANG X S.A literature survey of benchmark functions for global optimization problems[J].International Journal of Mathematical Modelling & Numerical Optimisation,2013,4(2):150-194.

[9] VANARET C,GOTTELAND J B,DURAND N,et al.Certified global minima for a benchmark of difficult optimization problems[J].Applied Mathematics Computer Science & Automatics for Air Transport,2014.