基于動(dòng)態(tài)壓力控制算子的磷蝦群算法

沈瑩 黃樟燦 談慶 劉寧

摘 要：針對基礎(chǔ)磷蝦群（KH）算法在求解復(fù)雜函數(shù)優(yōu)化問題時(shí)局部搜索能力差、求解精度低、收斂速度慢、容易陷入局部最優(yōu)等問題，提出一種基于動(dòng)態(tài)壓力控制算子的磷蝦群算法（DPCKH）。該算法將一種新的動(dòng)態(tài)壓力控制算子加入了標(biāo)準(zhǔn)磷蝦群算法，使其處理復(fù)雜函數(shù)優(yōu)化問題更有效。動(dòng)態(tài)壓力控制算子通過歐氏距離量化了多個(gè)不同優(yōu)秀個(gè)體對目標(biāo)個(gè)體的誘導(dǎo)效應(yīng)，進(jìn)而在優(yōu)秀個(gè)體附近加速產(chǎn)生新磷蝦個(gè)體，提高了磷蝦個(gè)體的局部探索能力。通過比較蟻群算法（ACO）、差分進(jìn)化算法（DE）、磷蝦群算法 （KH）、改進(jìn)的磷蝦群算法（KHLD）和粒子群算法（PSO），DPCKH算法在7個(gè)測試函數(shù)上的結(jié)果表明，DPCKH算法與ACO算法、DE算法、KH算法、KHLD算法和PSO算法相比有著更強(qiáng)的局部勘測能力，其開采能力更強(qiáng)。

關(guān)鍵詞：磷蝦群算法;動(dòng)態(tài)壓力控制算子;函數(shù)優(yōu)化;開采能力;探索能力

中圖分類號： TP18

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-9081（2019）03-0663-05

Abstract： Aiming at the problem that basic Krill Herd （KH） algorithm has poor local search ability and insufficient exploitation capacity on complex function optimization problems， a Krill Herd algorithm based on Dynamic Pressure Control operator （DPCKH） was proposed. A new dynamic pressure control operator was added to the basic krill herd algorithm， which made it more effective on complex function optimization problems. The dynamic pressure control operator quantified the induction effects of several different outstanding individuals on the target individual through Euclidean distance， accelerating the production of new krill individuals near the excellent individuals and improving the local exploration ability of krill individuals. Compared to ACO （Ant Colony Optimization） algorithm， DE algorithm， KH algorithm， KHLD （Krill Herd with Linear Decreasing step） algorithm and PSO （Particle Swarm Optimization） algorithm on 7 benchmark functions， DPCKH algorithm has stronger local exporatioin and exploitation ability.

Key words： Krill Herd （KH） algorithm; dynamic pressure control operator; function optimization; exploitation capacity; exploration capacity

0 引言

群智能優(yōu)化算法[1-2]是求解復(fù)雜的實(shí)際優(yōu)化問題的一種計(jì)算方法。該類算法從仿生學(xué)的角度，模擬自然界中生物生活習(xí)性在定義域中快速尋找目標(biāo)問題的最優(yōu)解，具有可擴(kuò)展性、自適應(yīng)性和并行性[3]等多種優(yōu)點(diǎn)。目前，群智能優(yōu)化算法被廣泛地應(yīng)用于求解復(fù)雜的優(yōu)化問題中，包括有：蟻群優(yōu)化（Ant Colony Optimization， ACO）算法[4]、粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法[5]、人工蜂群（Artificial Bee Colony， ABC）算法[6]、遺傳算法（Genetic Algorithm， GA）[7]、差分進(jìn)化（Differential Evolution， DE）算法[8]等。

Gandomi等[9]通過對南極磷蝦群（Krill Herd， KH）的生活習(xí)性的觀察和研究，并于2012年提出了磷蝦群（KH）算法，該群智能優(yōu)化算法[10]通過模仿磷蝦的活動(dòng)方式，能夠在算法演化的初期快速收斂，找到表現(xiàn)優(yōu)秀的可行解。該算法的缺點(diǎn)是磷蝦個(gè)體隨著演化的發(fā)展，缺乏全局搜索能力，算法容易陷入局部最優(yōu)解。針對該問題，相關(guān)研究工作者通過優(yōu)化算法參數(shù)和演化策略，改進(jìn)算法的搜索能力。文獻(xiàn)[11]引入差分演化算子，提出了改進(jìn)的磷蝦群算法 （hybrid Differential Evolution Krill Herd， DEKH）;文獻(xiàn)[12]中提出的改進(jìn)算法通過線性遞減步長對因子進(jìn)行縮放，設(shè)計(jì)完成改進(jìn)的磷蝦群算法（Krill Herd with Linear Decreasing step， KHLD）;文獻(xiàn)[13]中設(shè)計(jì)了一種基于混沌映射的動(dòng)態(tài)參數(shù)優(yōu)化方法對當(dāng)前種群中的最優(yōu)值進(jìn)行更新，從而實(shí)現(xiàn)對磷蝦群算法的改進(jìn);文獻(xiàn)[14]中的改進(jìn)算法對粒子群與磷蝦群兩種不同類型的群智能優(yōu)化算法進(jìn)行了融合，對兩種群智能算法規(guī)則下進(jìn)行個(gè)體的演化，并分別保留其中的優(yōu)秀個(gè)體。上述對于傳統(tǒng)的KH算法的改進(jìn)主要從參數(shù)優(yōu)化和演化規(guī)則兩個(gè)方面展開研究，均一定程度上改進(jìn)了算法的性能。然而，已有的改進(jìn)算法僅僅從適應(yīng)度函數(shù)的角度出發(fā)，通過改進(jìn)參數(shù)和適應(yīng)度評價(jià)規(guī)則來實(shí)現(xiàn)對傳統(tǒng)算法的改進(jìn)，并沒有考慮中其中優(yōu)秀個(gè)體周圍環(huán)境中優(yōu)秀個(gè)體對種群演化的影響，有一定的局限性。

為了進(jìn)一步提升KH算法的搜索能力和收斂性能，本文設(shè)計(jì)了一種動(dòng)態(tài)壓力控制算子對演化規(guī)則進(jìn)行控制，實(shí)現(xiàn)對磷蝦群算法的改進(jìn)。本文提出的基于動(dòng)態(tài)壓力控制算子的磷蝦群算法（Krill Herd algorithm based on Dynamic Pressure Control operator， DPCKH），首先利用傳統(tǒng)KH算法進(jìn)行全局搜索，評價(jià)并保留潛在的優(yōu)秀個(gè)體;然后，通過本文設(shè)計(jì)的動(dòng)態(tài)壓力控制算子在種群中產(chǎn)生的新個(gè)體與舊個(gè)體之間進(jìn)行評價(jià)選擇，保留優(yōu)秀的磷蝦個(gè)體。其中，動(dòng)態(tài)壓力控制算子通過在當(dāng)前種群優(yōu)秀個(gè)體的鄰域內(nèi)尋找相似個(gè)體，來形成潛在優(yōu)秀個(gè)體種群，從而增強(qiáng)算法的搜索能力，提高算法的收斂速度。最后，本文中通過7個(gè)測試函數(shù)對提出的改進(jìn)算法進(jìn)行了驗(yàn)證，并選取了2種算法進(jìn)行了對比。實(shí)驗(yàn)結(jié)果充分證明了本文設(shè)計(jì)的改進(jìn)算法的有效性和高精度。

1 KH算法

磷蝦群（KH）算法是由Gandomi和Alavi在2012年提出的一種模仿南極磷蝦群生存活動(dòng)的新型群智能算法。磷蝦個(gè)體的位置移動(dòng)主要受到三個(gè)因素影響：1）其他磷蝦個(gè)體的誘導(dǎo)運(yùn)動(dòng);2）覓食活動(dòng);3）隨機(jī)擴(kuò)散活動(dòng)。

磷蝦個(gè)體的移動(dòng)方向用拉格朗日模型建模：

2 基于動(dòng)態(tài)壓力控制算子的磷蝦算法（DPCKH）本文算法

在通常的KH算法中，由式（5）可知，磷蝦個(gè)體誘導(dǎo)方向αi由附近磷蝦的誘導(dǎo)方向αlocali和最優(yōu)個(gè)體的誘導(dǎo)方向αtargeti組合構(gòu)成。這里的αtargeti指代種群中最優(yōu)秀的一個(gè)磷蝦個(gè)體對當(dāng)前研究的目標(biāo)磷蝦個(gè)體產(chǎn)生的誘導(dǎo)方向。對于當(dāng)前研究的目標(biāo)磷蝦個(gè)體而言，比自身優(yōu)秀的磷蝦個(gè)體可能有多個(gè)，由于沒有考慮全局優(yōu)秀方向的多樣性，所以僅由一個(gè)優(yōu)秀個(gè)體全局感知方向是存在缺陷的。為了改善克服多樣性的不足，提高標(biāo)準(zhǔn)KH算法的開采能力，動(dòng)態(tài)壓力控制算子被加入了KH算法。動(dòng)態(tài)壓力控制算子從多個(gè)優(yōu)秀個(gè)體與目標(biāo)個(gè)體之間的距離入手，更加側(cè)重于全局搜索，這使算法可以避免早熟。

DPCKH算法中，動(dòng)態(tài)壓力控制算子主要分為篩選操作和動(dòng)態(tài)壓力控制操作兩部分。首先對磷蝦群體中所有個(gè)體進(jìn)行編號，磷蝦種群S定義如下：

動(dòng)態(tài)壓力控制算子在DPCKH算法演化初期主要起到局部搜索的作用，此時(shí)距離較近的優(yōu)秀個(gè)體權(quán)值較大，其誘導(dǎo)作用較強(qiáng)，對算法本身起到加速作用。當(dāng)DPCKH算法演化到中后期時(shí)，距離較遠(yuǎn)的優(yōu)秀個(gè)體權(quán)值較大，其誘導(dǎo)作用更強(qiáng)，由于新個(gè)體產(chǎn)生的搜索區(qū)域更大，因此跳出局部最優(yōu)的能力更強(qiáng)，所以增強(qiáng)了算法的全局尋優(yōu)能力。

動(dòng)態(tài)壓力控制算子的詳細(xì)計(jì)算方法見算法1。

其中：popsize指的是種群里磷蝦個(gè)體的數(shù)目，rand表示[0，1]中的偽隨機(jī)數(shù)，X是原始種群中的磷蝦個(gè)體，K是通過近鄰套索算子新產(chǎn)生的磷蝦個(gè)體。

在動(dòng)態(tài)壓力控制算子中，對于函數(shù)值最小化問題，如果新產(chǎn)生的磷蝦個(gè)體適應(yīng)度值比較差，舊的個(gè)體將被保留;如果新產(chǎn)生的個(gè)體適應(yīng)度值比較好，則新的個(gè)體將被保留下來。然后DPCKH算法進(jìn)入下一次演化。

在DPCKH算法中，標(biāo)準(zhǔn)的KH算法被用于全局搜索，其目的在于提供優(yōu)秀個(gè)體的目標(biāo)區(qū)域。在對可行域進(jìn)行初步篩選之后，動(dòng)態(tài)壓力控制算子作為一個(gè)局部算子被引入。在算法演化初期，動(dòng)態(tài)壓力控制算子主要體現(xiàn)了目標(biāo)個(gè)體近距離優(yōu)秀個(gè)體的誘導(dǎo)作用，這種性質(zhì)能夠提高算法初期的收斂速度。進(jìn)一步的，在算法演化的中后期，動(dòng)態(tài)壓力控制算子主要體現(xiàn)了目標(biāo)個(gè)體遠(yuǎn)距離優(yōu)秀個(gè)體的誘導(dǎo)作用，這種性質(zhì)能夠提高算法跳出局部最優(yōu)的能力，使得算法具備更強(qiáng)的全局尋優(yōu)能力。簡而言之，DPCKH算法平衡了磷蝦個(gè)體在演化過程中開采與探索的矛盾。

將動(dòng)態(tài)壓力控制算子加入KH算法之中，得到DPCKH算法。該算法的流程如圖1所示。

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 測試函數(shù)與實(shí)驗(yàn)參數(shù)

為了詳細(xì)檢驗(yàn)分析DPCKH算法在函數(shù)優(yōu)化問題下的性能，本文選取標(biāo)準(zhǔn)KH算法、DPCKH算法、KHLD算法以及文獻(xiàn)[5]中提到的PSO算法進(jìn)行比較。實(shí)驗(yàn)選取了7個(gè)典型的標(biāo)準(zhǔn)測試函數(shù)（見表1），其中： f1、 f2是高維單峰函數(shù)， f3是高維多峰函數(shù)， f4～f7是低維函數(shù)并且僅有少數(shù)幾個(gè)局部極小值。

實(shí)驗(yàn)參數(shù)設(shè)置：KH算法與DPCKH算法采用文獻(xiàn)[14]中的參數(shù)進(jìn)行設(shè)置，其中最大誘導(dǎo)速度Nmax=0.01，最大覓食速度Vf=0.02，最大隨機(jī)擴(kuò)散速度Dmax=0.005，KH和DPCKH算法中Ct=1，DPCKH算法中k=10， C=0.2。對于PSO算法，所有的參數(shù)設(shè)置按照文獻(xiàn)[5]中設(shè)置，對于KHLD算法，其參數(shù)按照文獻(xiàn)[12]中進(jìn)行設(shè)置。

3.2 實(shí)驗(yàn)結(jié)果

所有的算法均在Matlab 2016a軟件上進(jìn)行實(shí)現(xiàn)。其中種群規(guī)模設(shè)置為50，最大迭代次數(shù)設(shè)置為1000，每種算法在對應(yīng)的測試函數(shù)上運(yùn)行獨(dú)立重復(fù)運(yùn)行10次，計(jì)算其平均最優(yōu)適應(yīng)度（Mean）、標(biāo)準(zhǔn)差（Std）以及最差的最優(yōu)適應(yīng)度（Worst）。關(guān)于測試函數(shù)的維度詳見表1，對應(yīng)各種算法的運(yùn)行結(jié)果如表2所示。

從表2中不難發(fā)現(xiàn)，DPCKH算法相比標(biāo)準(zhǔn)KH算法、標(biāo)準(zhǔn)PSO算法、ACO算法和DE算法而言在最大迭代次數(shù)內(nèi)擁有更高的精度，其跳出局部最優(yōu)的能力更強(qiáng)。對比Mean、Std、Worst三個(gè)指標(biāo)發(fā)現(xiàn)，DPCKH算法在這三個(gè)方面均領(lǐng)先于其他三個(gè)算法，說明DPCKH算法不僅在優(yōu)化精度上領(lǐng)先其他算法，而且在算法的魯棒性上也具備一定優(yōu)勢。Mean和Std的優(yōu)秀表現(xiàn)說明了在有限迭代次數(shù)內(nèi)，DPCKH算法的全局尋優(yōu)能力優(yōu)于其他算法，而Std的優(yōu)秀表現(xiàn)則說明了DPCKH算法更加穩(wěn)定。

為進(jìn)一步探討DPCKH算法的全局搜索能力與局部開采能力，針對高維單峰函數(shù)、高維多峰、低維少局部極值三類測試函數(shù)，分別提取DPCKH算法、KH算法、KHLD算法、PSO算法的平均誤差演化對比結(jié)果如圖2所示。

高維度單峰函數(shù)Generalized Rosenbrock's Function和Generalized Schwefel's Problem 2.26測試結(jié)果如圖2（a）和（b）所示。PSO算法的收斂速度最快，但是也容易陷入局部最優(yōu)，導(dǎo)致其尋優(yōu)精度有限。DPCKH算法不僅收斂速度優(yōu)于標(biāo)準(zhǔn)KH算法和KHLD算法，而且尋優(yōu)精度也高于后兩者。說明DPCKH算法具有較強(qiáng)的全局探索能力，能夠有效地跳出局部最優(yōu)。高維多峰函數(shù)Kowalik's Function的測試結(jié)果如圖2（c）所示，PSO算法依舊是很快陷入了局部最優(yōu)，標(biāo)準(zhǔn)KH算法與KHLD算法則一定程度上改善了PSO算法容易陷入局部最優(yōu)的問題，但是兩者無論是收斂速度還是優(yōu)化精度都劣于DPCKH算法。低維少極值函數(shù)Six-Hump Camel-Back Function、Branin Function和Hartman's Function 2的測試結(jié)果如圖2（d）～圖2（f）所示。PSO算法很快地陷入了局部最優(yōu)，而DPCKH算法無論是在收斂速度還是收斂精度上都優(yōu)于標(biāo)準(zhǔn)KH算法和KHLD算法。仔細(xì)對比（a）、（d）與（e），可以發(fā)現(xiàn)DPCKH算法的演化過程中，前期由于較近優(yōu)秀個(gè)體的誘導(dǎo)作用主導(dǎo)，存在一個(gè)較快的收斂速度，能夠高效地找到潛在優(yōu)秀個(gè)體所在的區(qū)域，而中后期由于較遠(yuǎn)優(yōu)秀個(gè)體的誘導(dǎo)作用主導(dǎo)，提高了算法跳出局部最優(yōu)的能力，加強(qiáng)了算法全局探索的作用?？偟膩碚f，基于動(dòng)態(tài)壓力控制算子的DPCKH算法在整個(gè)演化過程中，跳出局部最優(yōu)的能力強(qiáng)于PSO算法、KH算法與KHLD算法。動(dòng)態(tài)壓力控制算子改善克服了標(biāo)準(zhǔn)KH算法局部尋優(yōu)能力不足的缺點(diǎn)，提高了算法的開采能力。

4 結(jié)語

本文針對KH算法在處理復(fù)雜函數(shù)優(yōu)化問題上局部搜索能力差、開采能力不足導(dǎo)致的收斂速度慢、收斂精度有限的現(xiàn)象，提出了基于動(dòng)態(tài)壓力控制算子的磷蝦群算法（DPCKH）。DPCKH算法從優(yōu)秀磷蝦個(gè)體的誘導(dǎo)效應(yīng)入手，通過不同距離下的動(dòng)態(tài)壓力權(quán)重控制，在優(yōu)秀個(gè)體附近加速產(chǎn)生新的優(yōu)秀個(gè)體，充分考察了優(yōu)秀磷蝦個(gè)體對目標(biāo)磷蝦個(gè)體的影響。進(jìn)而改善克服了標(biāo)準(zhǔn)KH算法中局部搜索能力不足、開采能力弱的問題?；?個(gè)測試函數(shù)在多個(gè)維度的測試結(jié)果表明，DPCKH算法相比標(biāo)準(zhǔn)KH算法、KHLD算法、PSO算法不僅有著更強(qiáng)的全局搜索能力，尋優(yōu)精度更高，而且收斂速度更快，穩(wěn)定性更好。動(dòng)態(tài)壓力控制算子讓DPCKH算法相較與普通KH算法有著更強(qiáng)的局部勘測能力。下一步的研究目標(biāo)是繼續(xù)探討磷蝦群算法在不同參數(shù)、不同壓力控制下優(yōu)化效果。

參考文獻(xiàn) （References）

[1] 林詩潔，董晨，陳明志，等.新型群智能優(yōu)化算法綜述[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（12）：1-9.（LIN S J， DONG C， CHEN M Z， et al. Summary of new group intelligent optimization algorithms [J]. Computer Engineering and Applications， 2018， 54（12）： 1-9.）

[2] 程述立，汪烈軍，秦繼偉，等.群智能算法優(yōu)化的結(jié)合熵的最大類間方差法與脈沖耦合神經(jīng)網(wǎng)絡(luò)融合的圖像分割算法[J].計(jì)算機(jī)應(yīng)用，2017，37（12）：3528-3535.（CHENG S L， WANG L J， QIN J W， et al. Image segmentation algorithm based on fusion of group intelligent algorithm optimized OTSU-entropy and pulse coupled neural network [J]. Journal of Computer Applications， 2017， 37（12）： 3528-3535.）

[3] SALEEM M， di CARO G A， FAROOQ M. Swarm intelligence based routing protocol for wireless sensor networks： survey and future directions [J]. Information Sciences， 2010， 181（20）： 4597-4624.

[4] QU M. Lunar soft-landing trajectory of mechanics optimization based on the improved ant colony algorithm [J]. Applied Mechanics and Materials， 2015， 3748（721）： 446-449.

[5] FAYCAL H， ANIS L， ANIS S， et al. A new images segmentation method based on modified particle swarm optimization algorithm [J]. International Journal of Imaging Systems and Technology， 2013， 23（3）： 265-271.

[6] PAN Q-K. An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling [J]. European Journal of Operational Research， 2016， 250（3）： 702-714.

[7] 肖振久，孫健，王永濱，等.基于果蠅優(yōu)化算法的小波域數(shù)字水印算法[J].計(jì)算機(jī)應(yīng)用，2015，35（9）：2527-2530.（XIAO Z J， SUN J， WANG Y B， et al. Wavelet domain digital watermarking method based on fruit fly optimization algorithm [J]. Journal of Computer Applications， 2015， 35（9）： 2527-2530.）

[8] 劉寶，董明剛，敬超.改進(jìn)的排序變異多目標(biāo)差分進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用，2018，38（8）：2157-2163.（LIU B， DONG M G， JING C. Multi-objective differential evolution algorithm with improved ranking-based mutation [J]. Journal of Computer Applications， 2018， 38（8）： 2157-2163.）

[9] GANDOMI A H， ALAVI A H. Krill herd： a new bio-inspired optimization algorithm [J]. Communications in Nonlinear Science and Numerical Simulation， 2012， 17（12）： 4831-4845.

[10] HOFMANN E E， HASKELL A G E， KLINCK J M， et al. Lagrangian modelling studies of Antarctic krill （euphausia superba） swarm formation [J]. ICES Journal of Marine Science， 2004， 61（4）： 617-631.

[11] WANG G-G， GANDOMI A H， ALAVI A H， et al. Hybrid krill herd algorithm with differential evolution for global numerical optimization [J]. Neural Computing and Applications， 2014， 25（2）： 297-308.

[12] LI J， TANG Y， HUA C， et al. An improved krill herd algorithm： krill herd with linear decreasing step [J]. Applied Mathematics and Computation， 2014， 234（10）： 356-367.

[13] WANG G-G， GUO L， GANDOMI A H， et al. Chaotic krill herd algorithm [J]. Information Sciences， 2014， 274： 17-34.

[14] WANG G-G， GANDOMI A H， ALAVI A H， et al. A hybrid method based on krill herd and quantum-behaved particle swarm optimization [J]. Neural Computing and Applications， 2016， 27（4）： 989-1006.

[15] 劉沛，高岳林，郭偉.基于自然選擇和隨機(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.）