基于互利共生和優(yōu)勝劣汰的改進(jìn)磷蝦群算法

王 滔，高岳林，曹 凱

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

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

1 KH算法

KH算法是一種新的啟發(fā)式智能優(yōu)化算法，該算法主要是基于對(duì)南極磷蝦群在海洋環(huán)境中的生存運(yùn)動(dòng)過程的仿真研究。對(duì)于每個(gè)磷蝦粒子，它的位置更新主要受到3個(gè)因素的影響：

1) 誘導(dǎo)運(yùn)動(dòng)(周圍磷蝦的誘導(dǎo))；

2) 覓食活動(dòng)；

3) 隨即擴(kuò)散。

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

(1)

其中，Ni，F(xiàn)i，Di分別代表誘導(dǎo)運(yùn)動(dòng)、覓食運(yùn)動(dòng)和隨機(jī)擴(kuò)散。

3個(gè)因素的公式構(gòu)造如下：

Ni=Nmaxαi+wnNold,i.

(2)

Fi=vfβi+wfFold,i.

(3)

(4)

式中：Nmax，vf，Dmax分別代表最大誘導(dǎo)速度、最大覓食速度和最大擴(kuò)散速度；αi，βi，δ分別代表誘導(dǎo)方向、覓食方向和擴(kuò)散方向；wn，wf分別代表誘導(dǎo)權(quán)重和覓食權(quán)重；t，tmax分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。其中Nmax=0.01，vf=0.02，Dmax=0.005[1].

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

(5)

(6)

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

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

(7)

(8)

式中：Cr為交叉算子；Mu為遺傳算子；a為[0,1]上均勻分布的隨機(jī)數(shù)；μ為[0,1]內(nèi)的常數(shù)。

2 MASFKH算法

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

2.1 磷蝦群互利共生策略

自然界中的生物生活在一起，構(gòu)成了一個(gè)穩(wěn)定的生態(tài)系統(tǒng)，不同物種之間不斷地發(fā)生直接或間接的某種關(guān)系。這種關(guān)系大致可以分成3類：互利共生，即對(duì)雙方都相互有利；共棲，只對(duì)其中一方有利，但對(duì)另一方無害；寄生，對(duì)其中一方有利，但對(duì)另一方有害。互利共生歸納總結(jié)為：不同物種的個(gè)體生活在一起，雙方都收益的相互關(guān)系，也可指即使相互離開但仍可正常生存的生物，它們既相互依存又相互獨(dú)立，構(gòu)成了物種間的合作關(guān)系。

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

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

(9)

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

(10)

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

此時(shí)，收到全局預(yù)警危險(xiǎn)信號(hào)后，磷蝦群之間會(huì)相互傳遞危險(xiǎn)信號(hào)，所以隨機(jī)地選擇兩個(gè)磷蝦p和q，且Xp≠Xq.這一策略的互利共生現(xiàn)象由下式表示：

(11)

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

2.2 優(yōu)勝劣汰策略

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

優(yōu)勝劣汰的基本思想是為了維護(hù)種群中粒子的多樣性?！皟?yōu)勝劣汰”策略具體操作辦法為：在對(duì)新一代種群生成過后，將對(duì)新生成的種群進(jìn)行適應(yīng)度值的評(píng)估，即按照適應(yīng)度值進(jìn)行排序，在算法中將最差的R個(gè)粒子舍去，同時(shí)在搜索空間隨機(jī)產(chǎn)生R個(gè)新粒子。若R取值越大，則產(chǎn)生的新粒子越多，有利于保持種群的多樣性，避免算法陷入局部最優(yōu)。但如果R的取值很大，則會(huì)使算法趨于隨機(jī)搜索；若R取值越小，則不利于算法維持粒子的個(gè)體多樣性，算法的全部搜索能力變?nèi)酢Ｒ虼?，這里的R取NP/10，其中NP為種群規(guī)模。

3 MASFKH算法具體流程

Step 1：確定種群規(guī)模并初始化種群及相關(guān)參數(shù)的設(shè)置；

Step 2：將目標(biāo)函數(shù)值作為適應(yīng)度值，評(píng)價(jià)種群中每個(gè)粒子的適應(yīng)度，并將當(dāng)前的磷蝦群個(gè)體的位置和適應(yīng)度值存儲(chǔ)在各個(gè)體的Pbest，將所有的Pbest中最優(yōu)的存儲(chǔ)在Gbest中；

Step 3：采用式(2)—(4)計(jì)算磷蝦個(gè)體的運(yùn)動(dòng)速度分量；

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

Step 5：對(duì)于各個(gè)體，將其所經(jīng)歷的位置和目標(biāo)函數(shù)進(jìn)行比較，更新Pbest和Gbest；

Step 6：將新的種群按適應(yīng)度值排序，進(jìn)行“優(yōu)勝劣汰”策略；并保持Pbest和Gbest不變；

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

4 實(shí)驗(yàn)及結(jié)果分析

4.1 數(shù)值實(shí)驗(yàn)

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

4.2 結(jié)果分析

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

表1 測(cè)試函數(shù)Table 1 Test functions

表2 MASFKH、KH和KHLD等3種算法的數(shù)值實(shí)驗(yàn)結(jié)果Table 2 Numerical results of MASFKH、KH and KHLD algorithm

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

圖1 部分函數(shù)的運(yùn)行結(jié)果Fig.1 Results of function

5 結(jié)論

針對(duì)磷蝦群算法搜索能力較差的缺點(diǎn)，提出了一種基于互利共生和優(yōu)勝劣汰的改進(jìn)磷蝦群算法(MASFKH).通過數(shù)值實(shí)驗(yàn)可知，MASFKH算法、KH算法和KHLD算法相比較，MASFKH算法增強(qiáng)了每次迭代粒子間的信息交流，有效地利用了局部最優(yōu)解信息，避免所有磷蝦陷入較差的局部最優(yōu)區(qū)域?？偟膩碚f，在解決單峰和多峰優(yōu)化問題上，MASFKH算法在探索能力和求解精度上都有著顯著的優(yōu)勢(shì)。

[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] 郭偉,高岳林,劉沛.一種自適應(yīng)慣性權(quán)重的改進(jìn)磷蝦群算法[J].太原理工大學(xué)學(xué)報(bào),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ī)擾動(dòng)的改進(jìn)磷蝦群算法[J].小型微型計(jì)算機(jī)系統(tǒng),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.