基于混沌搜索與精英交叉算子的磷蝦覓食算法

王 磊,張漢鵬

(西南財經大學a.經濟信息工程學院;b.工商管理學院,成都610074)

基于混沌搜索與精英交叉算子的磷蝦覓食算法

王 磊a,張漢鵬b

(西南財經大學a.經濟信息工程學院;b.工商管理學院,成都610074)

為解決磷蝦覓食(KH)優化算法在處理高維多模態函數優化問題時存在局部搜索能力不強、收斂速度慢等問題,利用一種貪婪的精英交叉算子加速其收斂速度,使用基于邏輯自映射函數的混沌搜索算子避免局部極值的吸引,采用對立搜索算子提高初始種群的質量。結合上述3種算子提出一種改進的磷蝦覓食算法。在7個標準測試函數上的仿真實驗結果表明,與KH及其改進算法相比,該算法在尋優精度和收斂速度方面均得到明顯增強。

磷蝦覓食算法;局部搜索能力;對立策略;精英交叉算子;混沌搜索;收斂速度

1 概述

仿生群體智能算法在優化過程中具有易于實現、適于并行處理、不受搜索空間條件的限制、魯棒性強等優點,在科學計算和工程技術領域日益受到廣泛的應用。近些年來,人們在研究生物群體智能行為和自然規律過程中受到啟發,相繼提出了一些新穎的仿生群體智能算法。例如蟻群算法(ACO)［1］、蝙蝠算法(BA)［2］、生物地理優化算法(BBO)［3］、和聲搜索算法(HS)［4］、布谷鳥搜索算法(CS)［5］等。

2012年,Gandomi等人在研究磷蝦覓食過程中蝦群結構的形成規律時,發現個體的運動行為明顯受到它所估計的食物位置和附近群體(傾向于形成高密度蝦群)的吸引。這樣每個磷蝦個體結合自身估算的全局食物信息和個體之間交換的局部位置信息,不斷向全局最優(食物)位置移動。他們使用一種Lagrangian模型來描述這種行為,并在此基礎上

提出了一種新穎的仿生群體智能算法——磷蝦覓食算法(Krill Herd,KH)［6］。

由于同時考慮全局探索和局部搜索能力,KH算法在連續空間的非線性優化性能強于目前大多數群體智能算法,并具有控制參數少、易于實現等優點。然而,最新實驗研究表明,KH算法在處理一些高維多模態優化問題時(如30維的Fletcher函數),容易出現早熟、陷入局部最優、后期收斂速度慢等不足,即算法的局部搜索能力不強。針對這些問題,文獻［7］利用混合DE算子增強種群多樣性和局部搜索能力;文獻［8］采用基于和聲搜索的變異算子提高了算法的逃離極值的能力,取得了一定的效果;類似的工作還包括文獻［9］。文獻［10］受SGA算法的啟發提出一種SSC交叉算子,以貪婪地方式與當前最優解進行交叉,提出的SKH算法在收斂速度和局部搜索能力有明顯提升。

作為最新的仿真群體智能算法之一,KH算法的理論和應用研究剛剛起步。本文將從增強KH算法的局部搜索性能和收斂速度的視角出發,設計和聯合使用精英交叉、混沌搜索和對立搜索3種算子,提出一種新穎的改進KH算法,并在多個標準測試函數上驗證其性能。

2 磷蝦覓食算法

2.1 基本的磷蝦覓食算法原理

研究發現［11］,磷蝦通常形成一定的群體結構進行覓食,蝦群密度和食物吸引是群體形成的2個主要因素。磷蝦個體的移動位置可以用Lagrangian模型進行建模:

在文獻［6］給出的KH算法中,認為每個個體不僅受到周圍磷蝦個體的局部吸引(以便維持高的蝦群密度),也受到當前全局最優個體的吸引。因此,模型中的運動向量Ni定義為:

其中,Nmax是最大移動步長;ωn是慣性權重;代表受周圍鄰居吸引的運動向量;代表受當前最優個體吸引的運動向量。

覓食運動向量Fi受到當前估計的食物位置和前一次覓食活動及位置的影響,因此,Fi可以由式(3)描述:

物理擴散運動向量Di表示磷蝦個體的隨機搜索行為,可以由下式估計:

其中,Dmax代表最大擴散速度值;δ表示隨機擴散方向向量;r和rmax分別表示當前迭代次數和最大迭代次數。

此后,磷蝦個體的位置更新公式為:

其中,Δt是具體應用相關的時間間隔常量。更具體的KH算法步驟及參數取值方法參見文獻［6］。值得注意的是,磷蝦覓食行為的Lagrangian模型已經有深入的實驗研究,KH算法的大多數參數都可以根據模型和大量實驗觀測結果經驗地選?。?,11］,而Δt是算法唯一需要結合具體應用確定的參數。

2.2 KH算法分析

通過對上述3種運動分析,磷蝦個體在搜索食物位置時,不僅具有全局探索能力(與和食物吸引度值有關),而且具有局部搜索能力(與和有關)。在這些因素的共同作用下,個體經過多次迭代不斷向適應度最優的位置移動。

然而近期的研究表明,基本的KH算法在處理一些高維多模態優化問題時(如30維的Fletcher函數),容易出現早熟、陷入局部最優、后期收斂速度慢等不足［7-9］,算法的局部搜索能力不強。經過分析,歸納的主要原因如下:

(1)KH算法一旦在迭代后期陷入局部極值,磷蝦個體周圍的鄰居由于已經聚集在極值點附近(形成高密度蝦群),對個體的影響力趨于同質(群體多樣性降低)。因而運動向量Ni更主要地受到局部極值點的影響,不具備強的局部搜索能力。

(2)食物的位置(代表全局最優值)實際是由所有磷蝦的當前位置估計出的。當蝦群被局部極值吸引時,覓食運動向量Fi難以擺脫其影響,因而個體的局部搜索能力變差。

(3)出于算法收斂的考慮,擴散運動向量Di在算法迭代的后期影響逐漸衰減,因而也不具備強的局部搜索能力。

在文獻［6］給出的KH變體算法中,通過增加自適應交叉算子和變異算子來增強KH的局部搜索能力及群體多樣性,然而,采用的交叉和變異行為具有

明顯隨機性特點,且當種群聚集在局部極值點附近時,交叉和變異概率非常低,使得這些算子難以發揮有效作用。

為有效提高KH算法局部搜索能力和收斂速度,本文聯合使用精英交叉、基于邏輯自映射函數的混沌局部搜索和對立搜索3種算子對KH算法進行改進,大幅增強其處理復雜優化問題的能力。

3 改進的KH算法

3.1 精英交叉算子

在KH變體算法中,磷蝦個體以一定交叉概率同隨機挑選的個體進行交叉操作,這種方式顯然效率十分低下,不僅收斂速度慢而且局部探索能力弱。受SGA算法采用的貪婪搜索的策略啟發［12］,本文提出一種新的精英交叉算子SEL,在KH算法利用式(5)更新位置后,進一步對個體的適應度進行優化,以達到快速收斂的目的,如式(6)所示:

其中,f(·)是適應度函數;crossover(·,·)表示任意交叉操作,如單點交叉、雙點交叉等;向量Xe表示當前迭代中的精英集合中的任意一個精英個體。精英集合{Xelitst}由當前適應度最低的前a%磷蝦個體向量組成,本文取值為a=10。

顯然,與KH變體算法采用的隨機交叉算子相比,SEL交叉算子使得個體貪婪地朝當前精英所在的位置靠近,搜索方向更具目的性,有利于加快算法的全局尋優速度。文獻［10］采用的SSC交叉算子僅選用當前最優個體進行交叉操作。與之相比, SEL算子與精英集合的任意個體進行交叉操作,該方式有利于保持蝦群的多樣性,一定程度避免算法陷入局部極值。

3.2 基于邏輯自映射的混沌局部搜索算子

在KH的變體算法中,采用自適應的變異算子進行局部搜索,效率很低［6］。

混沌是非線性系統特有的一種非周期運動現象,具有隨機性和遍歷性的特點。實驗研究結果表明,用混沌序列替代元啟發式智能算法中的隨機搜索,能夠有效提高算法的局部搜索性能［13］。在本文研究中,將采用邏輯自映射函數來產生混沌序列。該函數產生的混沌序列的遍歷性通常優于常用的Logistic映射, Circle映射,Tent映射等函數［9,13］,如下所示:

文獻［9］通過混沌序列調整KH的模型參數來增強局部搜索能力。文基于邏輯自映射函數設計出一種新的混沌局部搜索算子CHS,如下所示:

CHS算子:

(4)除當前最優個體X?外,所有磷蝦個體按式(8)進行混沌局部搜索并更新位置。其中,符號/和?表示向量的點除和點乘運算;向量L是搜索空間的位置下限,即L=(l1,l2,…,ln),向量U為相應的位置上限。

其中,rand是區間(0,1)之間的隨機數;Cchaos是局部搜索系數,在(0,1)區間內取值,用于控制個體進行局部搜索的活躍度。它的值越小,個體的局部搜索行為越活躍。本文取值為Cchaos=0.2。

顯然,利用混沌搜索的軌道遍歷性,使得群體容易擺脫局部極值的束縛,從而具備良好的局部搜索能力。

3.3 基于對立搜索算子的種群初始化

任意的n維空間中的點Xi,它的對立點唯一存在且定義為:

KH算法在搜索空間中隨機確定初始蝦群的位置。然而,文獻［14］已經從理論上證明了利用對立點能比隨機選擇更快地找到最優位置,相關實驗也表明對立搜索比隨機搜索更為有效。因此,為了加快KH算法的收斂速度,本文借鑒文獻［15］的方法,采用一種簡單的對立搜索算子OPP用于磷蝦種群的初始化,如式(10)所示:

顯然,對立搜索算子將使得隨機選取的磷蝦個體具有更好適應度值,無疑有利于算法的收斂。

3.4 基于3種算子的CO-KH算法

為了提高KH算法的局部搜索能力和收斂速度,本文基于前文提出的3種算子給出了一種新的改進算法——CO-KH,主要步驟描述如下:

CO-KH算法:

初始化:確定算法參數;隨機產生P個磷蝦個體,并利用OPP算子完成初始化;

(1)r=1,計算磷蝦個體的適應度值,并確定當

前最優的磷蝦位置X?;

(2)針對每個個體按式(2)～式(4)計算其運動向量;并按式(5)更新其位置;

(3)更新個體的適應度值并排序,選取前a%作為精英集合,執行SEL算子;

(4)執行CHS算子;

(5)r=r+1,更新體的適應度值,確定當前最優磷蝦位置X?;

(6)如果r小于最大迭代次數rmax,返回步驟(2);

(7)輸出最優位置X?及對應的適應度值。算法的參數包括時間間隔Δt,最大移動步長Nmax,最大覓食速度Vf,最大擴散速度Dmax,慣性權重ωn和ωf。其中,Δt可以按式(11)確定,它與具體應用問題相關。其他參數可以依據磷蝦群體的Lagrangian行為模型,經驗地取常量值(具體取值情況參見文獻［11］的表1)。

其中,時間常量Ct∈(0,2］,控制了磷蝦群體的覓食活動的運動幅度。

此外,假設評價個體適應度值1次的時間復雜度為O(f),則CO-KH算法執行1次迭代的時間復雜度為2P·O(f)+O(PlogP)+O(nP),與原始KH算法在同一數量級。其中,為了計算本文算法步驟(3)、步驟(4)中的SEL算子和CHS算子,相對于KH算法需要增加的時間開銷為P·O(f)+O(PlogP)+O(nP)。但考慮到達到相同收斂精度時CO-KH算法所需的迭代次數更少(參見實驗結果),它具有非?？斓倪\行速度。

4 仿真實驗與結果分析

為了檢驗本文提出的CO-KH算法的優化性能,實驗選取了7個標準測試函數進行仿真測試,并與原始KH算法［6］以及最近的改進算法SKH［10］進行性能對比。

4.1 標準測試函數及算法參數設置

標準測試函數如表1所示,其中函數f1～f5是復雜的非線性多模態連續優化函數,存在大量局部極值,常用于測試算法的全局尋優能力、擺脫局部極值的能力及收斂性能,f6-f7是復雜的單模連續優化函數,極難收斂到全局最優點,常用于測試算法的收斂速度。

表1 標準測試函數

實驗參數設置如下:對于CO-KH,KH和SKH算法,依據文獻［11］的模型研究,設置最大移動步長Nmax為0.01,最大覓食速度Vf為0.02,最大擴散速度Dmax為0.005,慣性權重ωn和ωf的值隨著迭代次數從0.9線性變化到0.1,時間常量Ct參照文獻［6］的實驗取值為0.5。另外,對于CO-KH算法,經反復實驗比較,SEL算子中的參數比率a取10,采用單點交叉操作;局部搜索系數Cchaos取值為0.2。對于SKH算法,SSC算子同樣采用單點交叉操作。

4.2 實驗結果

所有算法在Matlab2011上編碼實現,種群規模設置為50,個體采用實數編碼,最大迭代次數固定設置為1 500次。每種算法在函數上獨立運行30次,并統計平均最優適應度值(Mean)和標準差(Std)。表2給出了相應的實驗統計結果。

表2 不同算法的實驗結果比較

從表2的實驗可以看出,固定迭代次數情況下, CO-KH算法的尋優精度在多模態函數和單多模態函數上均顯著優于KH算法,其中,在3個測試函數上的尋優誤差低于10-4。這表明本文采用的3種算子有助于增強算法的跳出局部極值的能力,具有非常強的全局尋優性能。原始的KH算法由于局部搜索能力不足,基本上在除f1外上的所有函數上的尋優結果均明顯偏離最優值(例如,在Fletcher函數上的平均適應度值達0.624×104),表明KH算法在復雜多模態優化問題上存在容易陷入局部極值而發生收斂停滯的缺陷。相比較,SKH改進算法的尋優精度稍好于KH算法,在f6和f7上獲得的尋優精度與CO-KH算法基本在同一個數量級,但在其他函數上的結果仍明顯比后者差。此外,CO-KH算法在所有函數上的30次獨立實驗的統計標準差最小,表明該算法具有良好的魯棒性。

為進一步比較各算法的收斂性能,實驗度量了各算法在不同函數上的平均適應度值進化曲線。限于篇幅,圖1～圖4只給出了具有代表性的函數f1,f4,f5,f7上的測試結果?？梢杂^察到以下主要現象: (1)CO-KH算法具有最快的收斂速度和最優的精度。例如,在Schwefel2.26函數上300次迭代時的尋優精度甚至優于KH和SKH算法在1 500次迭代時的結果。(2)CO-KH算法能夠獲得較好的初始值(見圖中▼標記)。(3)SKH算法的收斂速度和精度強于原始的KH算法,但仍明顯弱于本文算法。

圖1 不同算法在函數f1上的適應度進化曲線

圖2 不同算法在函數f4上的適應度進化曲線

圖3 不同算法在函數f5上的適應度進化曲線

圖4 不同算法在函數f7上的適應度進化曲線

實驗現象(1)和現象(3)表明本文算法采用的混沌局部搜索算子顯著增強了KH算法的局部尋優和避免陷入局部極值的能力,圖中CO-KH算法的收斂曲線在中后期仍有明顯的鋸齒狀下降趨勢。同時,采用的精英交叉算子使得種群貪婪地向最優解集靠近,因而算法的收斂速度大幅加快。實驗現象(2)表明本文采用的對立搜索算子明顯提高了算法初始解的質量,有助于加快算法的收斂。

5 結束語

本文針對磷蝦覓食算法在求解一些復雜連續函數優化問題時遇到的局部搜索能力差、收斂速度慢等不足,提出一種性能優異的改進算法——CO-KH。使用一種新穎精英交叉算子加快種群的全局尋優速度,并采用一種基于邏輯自映射的混沌局部搜索算子增強其局部尋優能力。此外,利用對立搜索算子提高初始種群的質量?；?個標準測試函數的實驗結果表明,在復雜函數優化問題中,本文算法在尋優精度、收斂速度及魯棒性方面均優于原始的KH算法及最新的SKH算法,具有良好的應用前景。

［1]Yang Xinshe.Nature-inspiredMetaheuristicAlgorithms［M］.［S.1.］:Luniver Press,2008.

［2]Yang Xinshe.ANewMetaheuristicBat-inspired Algorithms［C］//ProceedingsofNatureInspired CooperativeStrategiesforOptimization.Berlin, Germany:Springer-Verlag,2010:65-74.

［3]Simon D.Biogeography-based Optimization［J］.IEEE Transactions on Evolutionary Computation,2008,12(6): 702-713.

［4]Geem Z W,Kim J H,Loganathan G V.A New Heuristic Optimization Algorithm:Harmony Search［J］.Simulation, 2001,76(2):60-68.

［5]Yang Xinshe,DebS.CuckooSearchViaLevy Flights［C］//Proceedings of World Congress on Nature &Biologically Inspired Computing.Washington D.C., USA:IEEE Press,2009:210-214.

［6]Gandomi A H,Alavi A H.Krill Herd:A New Bioinspired Optimization Algorithm［J］.Communications in Nonlinear Science and Numerical Simulation,2012, 17(12):4831-4845.

［7]Wang G G,Guo L H,Wang H Q,et al.Incorporating Mutation Scheme Into Krill Herd Algorithm for Global Numerical Optimization［J］.Neural Computing and Applications,2014,24(3-5):853-871.

［8]Mandal B,Roy P K,Mandal S.Economic Load Dispatch Using Krill Herd Algorithm［J］.International Journal of Electrical Power&Energy Systems,2014,57:1-10.

［9]Saremi S,Mirjalili S M,Mirjalili S.Chaotic Krill Herd Optimization Algorithm［J］.Procedia Technology,2014, 12(1):180-185.

［10]Wang G G,Gandomi AH,Alavi A H.Stud Krill Herd Algorithm［J］.Neurocomputing,2014,128(1):363-370.

［11]Hofmann E E,HaskellAG,KlinckGM,etal.Lagrangian Modelling Studies of Antarctic Krill Swarm Formation［J］.ICES Journal of Marine Science,2004, 61(4):617-631.

［12]Khatib W,Fleming P.The Stud GA:A Mini Revolution?［C］//Proceedings of the 5th International Conference on Parallel Problem Solving from Nature.Berlin, Gexmany:Springer,1998:683-691.

［13]劉長平,葉春明.具有混沌搜索策略的蝙蝠優化算法及性能仿真［J］.系統仿真學報,2013,25(6): 1183-1188.

［14]Rahnamayan S,Tizhoosh H R,Salama M M.Opposition Versus Randomness in Soft Computing Techniques［J］.Applied Soft Computing,2008,8(2):906-918.

［15]董明剛,牛秦洲,楊 祥.基于對立策略的螺栓遺傳算法［J］.計算機工程,2009,35(20):239-241.

編輯 索書志

Krill Herd Foraging Algorithm Based on Chaotic Searching and Elitism Crossover Operator

WANG Leia,ZHANG Hanpengb
(a.School of Economics Information Engineering;b.School of Business Administration, Southwestern University of Finance&Economic,Chengdu 610074,China)

Krill Herd(KH)foraging optimization algorithm is one of the most recent achievements in the field of bionic swarm intelligence.Despite high performance of KH,weak local searching ability and slow convergence speed are two probable deficiencies for solving some high-dimension and multi-modal function optimization.This paper proposes a greedy elitism crossover operator for accelerating convergence,utilizes one chaotic searching operator to escape some local optima based on self-logical mapping function,and employs an opposition searching operator to improve quality of initial population.A new improved KH algorithm combining such three operators is given.Simulation results on 7 benchmark functions show that the new algorithm has remarkable global optimizing ability and fast convergence speed, and outperforms the original KH algorithm and its newest variant algorithm.

Krill Herd(KH)foraging algorithm;local searching ability;opposition strategy;elitism crossover operator;chaotic searching;convergence speed

王 磊,張漢鵬.基于混沌搜索與精英交叉算子的磷蝦覓食算法［J］.計算機工程,2015,41(3):156-161.

英文引用格式:Wang Lei,Zhang Hanpeng.Krill Herd Foraging Algorithm Based on Chaotic Searching and Elitism Crossover Operator［J］.Computer Engineering,2015,41(3):156-161.

1000-3428(2015)03-0156-06

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.030

中央高?；究蒲袠I務費專項基金資助項目(JBK130503);四川省教育廳基金資助項目(14ZB0046);教育部人文社會科學研究基金資助項目(10YJCZH153)。

王 磊(1978-),男,副教授、博士,主研方向:機器學習,數據挖掘,計算智能;張漢鵬,副教授、博士。

2014-03-20

:2014-05-30E-mail:wanglei_t@swufe.edu.cn