一種自適應慣性權重的改進磷蝦群算法

郭 偉, 高岳林, 劉 沛

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

?

一種自適應慣性權重的改進磷蝦群算法

郭 偉, 高岳林, 劉 沛

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

提出一種自適應慣性權重的磷蝦群算法(AKH)。通過理論論證，得出在采用線性遞減的磷蝦群算法求解全局優化問題的迭代過程中,出現大量無效迭代是受到慣性權重的影響；進而提出相關改進策略:在以目標函數作為適應度值的基礎上,將種群粒子動態分為適應度值變差粒子和適應度值變優粒子兩類,令適應度值變差粒子的慣性權重重置為零,從而消除慣性權重對算法當前迭代的不良影響,適應度值變優粒子的慣性權重保持不變；對算法中的步長縮放因子作非線性遞減處理,進一步提升算法的全局探索能力。通過9個具有代表性的測試函數進行實驗,將該算法與線性遞減的粒子群算法(LPSO)、標準磷蝦群算法(KH)和線性遞減的磷蝦群算法(LKH)作性能對比分析。實驗表明,該算法能夠有效地減少無效迭代次數,在全局探索性能和收斂穩定性方面有著顯著優勢。

磷蝦群算法;全局優化;自適應;慣性權重

智能優化算法是一種以數學為基礎,用于解決各種優化問題的算法。磷蝦群算法(KH)[1]是一種新的群智能優化算法,該算法是基于對南極磷蝦的生存環境及生活習性的仿真模擬[2],由GANDOMI et al在2012年首次提出。在海洋中存在著捕食者,南極磷蝦群為了更好地存活下來,在運動過程中,它們不斷地聚集以增大種群密度減少被捕食的幾率,同時探索生存區域,盡可能縮短它們與食物的距離,最終使得種群獲取食物。

一般地,與其它智能優化算法相比,標準磷蝦群具有自身良好特性,在解決一些復雜優化問題[3-5]時具有極強的收斂能力,然而,由于在算法迭代過程中粒子運動的隨機性,在算法運行時,當粒子運動到適應度值較差位置時,并未對粒子的運動狀態進行適時調整,從而出現大量的無效迭代,使得算法并非總能很好地完成全局搜索,特別是在處理一些多峰優化問題時,算法的解更易陷入局部最優,出現“早熟”現象。對此,研究人員對標準磷蝦群算法從不同方面對算法進行改進,文獻[6-8]主要通過對算法中的部分參數進行調整,從而提升算法的搜索性能。

筆者提出了一種自適應慣性權重的磷蝦群算法(AKH),在磷蝦群算法的每一輪迭代中,通過監測磷蝦群粒子的運動狀態來動態調整各粒子的慣性權重,消除迭代過程中慣性權重的不良影響,減少算法的無效迭代次數,使得磷蝦群算法能夠更好地進行全局探索,同時收斂穩定性得到明顯提升。

1 標準磷蝦群算法

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

1) 周圍磷蝦的誘導;

2) 覓食活動;

3) 隨機擴散。

磷蝦粒子的速度更新公式采用了以下的拉格朗日模型:

(1)

式中,Ni,Fi,Di分別代表第i個粒子運動速度受到上面所提三個因素的影響。

三個因素的公式構造如下:

(2)

(3)

(4)

式中:Nmax,Vf,Dmax分別代表最大誘導速度、最大覓食速度和最大擴散速度；αi,βi,δi分別代表誘導方向、覓食方向和擴散方向；wn,wf為慣性參數；t,tmax分別為當前迭代次數和最大迭代次數。

磷蝦群粒子在t到t+Δt區間的位置更新公式如下:

(5)

(6)

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

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

(7)

(8)

式(5)中，Δt是一個重要的變量,文獻[8]對式(6)中的Ct采用式(9)進行處理,將該算法記為LKH。

(9)

標準磷蝦群算法的流程:

Step 1 種群初始化及參數設置,包括當前迭代次數t=1,初始種群粒子位置xi(t),種群規模NP,最大迭代次數tmax,最大誘導速度Nmax,最大覓食速度Vf,最大隨機擴散速度Dmax,誘導慣性權重wn,覓食慣性權重wf和步長縮放因子Ct等。

Step 2 將目標函數值作為適應度值,評價每個粒子的適應度。

Step 3 利用式(2)-式(4)分別對磷蝦群粒子運動的速度分量計算:a.誘導速度Ni;b.覓食速度Fi;c.隨機擴散速度Di.

Step 5 根據式(7)或式(8)對粒子進行遺傳操作(一般采用交叉操作)以增加種群的多樣性。

Step 6 計算迭代后種群粒子的適應度值,對粒子的位置進行更新。

Step 7 令t=t+1,返回Step 3,直到滿足t達到設定的最大迭代次數tmax.

2 算法問題分析

由仿真試驗可知,在采用KH和LKH算法求解復雜的非線性全局優化問題時,算法迭代過程中存在著大量的無效迭代。圖1給出了采用KH和LKH算法對F1(D=30)的一次仿真試驗。

圖1 KH和LKH算法對F1(D=30)的仿真試驗Fig.1 The experiment of KH and LKH for F1

在問題求解的迭代前期,算法具有良好的的收斂速度,但是,隨著迭代次數的增加,出現了大量的無效迭代,使得KH和LKH算法的收斂速度和收斂精度受到嚴重影響。

(10)

(11)

將式(5)代入式(10)化簡,得

(12)

當粒子在上一輪迭代到適應度值更差位置時,即

(13)

又，Δt>0,由式(1)、式(12)和式(13)得

(14)

(15)

3 自適應慣性權重的磷蝦群算法

3.1 改進方案

基于上述分析,筆者對磷蝦群算法提出了一種簡單的改進方案。在迭代過程中,根據粒子適應度值的變化,將粒子分成兩類:適應度值變差的粒子和適應度值變優的粒子。對于適應度值變差的粒子,令其下一次迭代的慣性權重wn=0,wf=0;對于適應度值變優的粒子,令其下一次迭代的慣性權重保持不變。

(16)

(17)

同時,采式(18)處理步長縮放因子Ct,相較于式(9)的線性遞減,非線性操作可以提升Ct的下降趨勢,在算法迭代的過程中,保證了在前期可以獲得更大的探索范圍,后期加快粒子的收斂速度。

(18)

3.2 算法流程

Step 1 種群初始化及參數設置,包括當前迭代次數t=1,初始種群粒子位置xi(t),種群規模NP,最大迭代次數tmax,最大誘導速度Nmax,最大覓食速度Vf,最大隨機擴散速度Dmax,誘導慣性權重wn,覓食慣性權重wf和步長縮放因子Ct等。

Step 2 將目標函數值作為適應度值,評價每個粒子的適應度。

Step 3 利用式(2)-(4)分別對磷蝦群粒子運動的速度分量計算:a.誘導速度Ni;b.覓食速度Fi;c.隨機擴散速度Di.

Step 5 根據式(7)或式(8)對粒子進行遺傳操作(一般采用交叉操作)以增加種群的多樣性。

Step 6 計算迭代后種群粒子的適應度值,根據適應度值對粒子的位置進行更新替換。

Step 7 通過比較當前代粒子適應度值的變化,采用式(16)、式(17)動態調整粒子慣性權重;

Step 8 令t=t+1,返回Step 3,直到滿足t達到設定的最大迭代次數tmax.

具體流程圖如圖2所示。

圖2 AKH流程圖Fig.2 The flow chart of AKH

4 對比實驗

4.1 實驗說明

實驗操作環境:運行軟件—Matlab2012a;電腦配置—Intel(r)Core(TM)i5-4440CPU@3.10GHz,8.00GB.

實驗測試指標:對于搜索類算法的收斂性能評估,一般可以分為算法的求解效率和求解質量兩方面,本文從求解質量的角度來考慮算法的收斂有效性,求解質量是指在規定的迭代次數(或時間內)所獲得可行解的優劣。

當算法進化的終止目標是達到最大迭代次數時,主要有兩個評價指標:平均最優適應度值和標準方差。

1) 平均最優適應度值。達到最大迭代次數時,所得到最優解的平均值。平均適應度值越接近于全局最優解,表明算法的尋優性能越好。對于最小優化問題,解的平均適應度越小越好。

2) 標準方差。達到最大迭代次數時優化算法所得到的最優解的標準方差。該指標反映了算法的穩定性。對于穩定的算法而言,其每次優化所得結果之間差異很小。算法的質量平均最有適應度值和標準方差共同反映。

同時,在測試結果中給出了最小值和最大值,二者體現算法在規定的最大迭代次數內所能探索到的最好的可行解,二者越小,進一步表明算法的求解質量越高。對于磷蝦群算法,在文獻[1]中的測試函數在1 000次迭代結果就能達到一定的求解精度,在此,本文中的實驗每次獨立運行最大迭代次數設為1 000次。

為了驗證本文所提出算法AKH的有效性,將算法與KH(標準磷蝦群算法)、LKH(變量Ct線性遞減)分別對表1中的9個Benchmark優化問題[11]進行性能對比實驗,同時,為了進一步體現磷蝦群算法的快速收斂性,將算法與LPSO(變量w線性遞減)進行對比實驗。

表中,f1是典型的單峰函數,在解的搜索空間中僅有一個極值點;f2為病態函數,是一個經典復雜優化問題,它的全局最優點位于一個平滑、狹長的拋物形山谷內。由于函數僅僅為優化算法提供了少量信息,使得算法很難辨別搜索方向,找到全局最優點的機會微乎其微,f3在搜索空間中為不連續、不可微的單峰函數。f4-f9是典型的非線性多峰函數,在搜索空間中存在大量的局部極值點。所有實驗的種群規模均為50,每個函數獨立運行20次,最大迭代次數設定為1 000次,

對于LPSO,c1=c2=2,wmax=0.95,wmin=0.4;

對于KH,wn=0.7,wf=0.7,Ct=0.4;

對于LKH和AKH,wn=0.7,wf=0.7,Ct，max=1.9,Ct，min=0.1 .

表1 Benchmark函數

4.2 Benchmark問題對比實驗結果分析

首先,由測試函數對比試驗圖可以看出,對于同樣的測試函數,在規定的最大迭代次數內,KH、LKH和AKH比LPSO的求解結果更快地達到更小的數量級,這說明在一般情況下,磷蝦群算法比粒子群算法具有更強的收斂性和有效性。

圖3(a)和圖3(b)為單峰函數測試對比實驗圖,由圖可以看出,對于單峰函數,由于大量無效迭代的

圖3 測試函數對比實驗圖Fig.3 The contrast experiment of test functions

減少,AKH可以更加有效地探尋搜索空間,從而比KH和LKH具有更強的收斂速度和探索能力,進一步提升了解的精度。

圖3(c)是多峰函數Rastrigin的對比實驗圖,在收斂速度方面AKH介于KH和LKH之間,但是在探索能力方面,AKH強于KH和LKH。圖3(d)是Ackley函數的對比實驗圖,在探索能力方面,AKH強于KH,稍弱于LKH,同時,收斂速度弱于LKH,AKH。由圖3(e)和圖3(f)可以看出,相比于其它算法,在迭代前期,AKH具有更快的收斂速度,在迭代后期,AKH仍具有極強的探索能力,從而在求解質量方面有所提高。

表2中的各項數據顯示,對于多峰函數Ackley,AKH在求解精度方面稍弱于LKH,但是強于KH和LPSO,對于其它測試函數,AKH算法在最小值、均值和標準方差等方面明顯優于其它3種算法,對于解決復雜非線性全局優化問題,具有顯著優于其它3種算法的搜索性能,最優解的搜索精度具有顯著提高,同時,標準方差結果表明數據差異性相對較小,具有良好的魯棒性。

表2 AKH與其它算法在Benchmark問題上的數值對比

5 結論

磷蝦群算法具有極強的收斂性能,但是在求解全局優化問題中,存在大量無效迭代,而且解易陷入局部最優。對此,為了提升算法的探索能力和收斂性能,本文提出了一種自適應慣性權重的磷蝦群算法,并理論證明了算法改進的合理性,通過對粒子群體運動狀態的分析,動態調整每一輪迭代中全體粒子的慣性權重,降低了迭代過程中慣性權重的不良影響,從而減少了算法無效迭代次數。同時,對步長縮放因子進行非線性處理,進一步提升算法的探索能力,從而提升了解的精度。9個具有代表性的測試函數的數值實驗對比表明,本文提出的改進算法AKH在探索能力和收斂穩定性上顯著優于LKH,KH和LPSO。

[1]GANDOMIAH,ALAVIAH.KrillHerd:anewbio-inspiredoptimizationalgorithm,Commun[J].NonlinearSciNumerSimul,2012,17(12):4831-4845.

[2]HOFMANNEE,HASKELLAGE,KLINCKJM,etal.Lagrangianmodellingstudiesofantarctickrill(Euphasiasuperba)swarmformation[J].ICESJMarSci,2004,61:617-31.

[3]MILANT,NEBOJSAB,BRANISLAVP.Krillherd(KH)algorithmappliedtotheconstrainedportfolioselectionproblem[J].Internationaljournalofmathematicsandcomputersinsimulation.Volume,2014,8:1998-0159.

[4]LARINS,ABADEHMS.Trainingartificialneuralnetworkbykrill-herdalgorithm[J].Informationtechnologyandartificialintelligenceconference(ITAIC),2014IEEE7thJointInternational,2014,20/21:63-67.

[5]KOWALSKIPA,LUKASIKS.Tuningneuralnetworkswithkrillherdalgorithm[J].Jointconferencecomputationalintelligence,2014:119-128.

[6]WANGG,GUOL,AMIRHG,etal.Chaotickrillherdalgorithm[J].Informationsciences,2014:0020-0255.

[7]SHAHRZADS,SEYEDMM,SEYEDALIM.Chaotickrillherdoptimizationalgorithm[J].ProcediaTechnology,2014,12:180-185.

[8]LIJP,TANGYG,HUACC,etal.Animprovedkrillherdalgorithm:Krillherdwithlineardecreasingstep[J].Appliedmathematicsandcomputation,2014(234):356-367.

[9]SHIYH,EBERHEARTRC.Parameterselectioninparticleswarmoptimization[C]∥IEEE.7thInternationalConference,EvolutionaryprogrammingVII.BerlinHeidelberg:Springer,1998,1447:591-600.

[10]AOYC,SHIYB,ZHANGW,etal.Improvedparticleswarmoptimizationwithadaptiveinertiaweight[J].JournalofUniversityofElectronicScienceandTechnologyofChina,2014:874-880.

[11]LIANGJ,QUB,SUGANTHANP,etal.ProblemdefinitionsandevaluationcriteriafortheCEC2013specialsessionandcompetitiononreal-parameteroptimization:technicalreport201212[R].Singapo:NanyangTechnologyUniversity,2013.

(編輯：朱 倩)

An Improved Krill Herd Algorithm with Adaptive Inertia Weight

GUO Wei,GAO Yuelin,LIU Pei

(Institute of Information and System Science,Beifang University of Nationalities,Yinchuan 750021,China)

In this paper,an improved krill herd algorithm with adaptive inertia weight is proposed. First, the relationship between the number of invalid iteration and inertia weight in the algorithm is presented, and then the related improvement strategy is put forward.The inertia weights of the particles whose fitness become worse at the last iterations are set to zero while solving the global optimization problems.At the same time, the step length scale factor is decreased nonlinearly.The algorithm can reduce the invalid iterations and enhance global exploring ability. Nine benchmark functions are used to test the AKH, LPSO,KH and LKH. Experiments show that the proposed algorithm can effectively reduce invalid iterations and it has obvious superiority on the search performance and the convergence stability.

krill herd algorithm; global optimization; adaptive;inertia weight

1007-9432(2016)05-0651-07

2015-09-21

國家自然科學基金資助項目：基于粒子群優化的多目標智能算法及應用研究(61561001);北方民族大學重點科研項目資助(2015KJ10);北方民族大學研究生創新項目：磷蝦群算法的改進及應用研究(YCX1549)

郭偉(1990-),男,河南信陽人,碩士生,主要從事智能計算與優化新技術研究,(E-mail)864369663@qq.com

高岳林,教授,博士生導師,主要從事智能計算與智能信息處理,最優化理論方法及其應用,(E-mail)gaoyuelin@263.net

TP18

A

10.16355/j.cnki.issn1007-9432tyut.2016.05.017