沈瑩 黃樟燦 談慶 劉寧

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

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

中圖分類號： TP18

文獻標志碼：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]是求解復雜的實際優(yōu)化問題的一種計算方法。該類算法從仿生學的角度，模擬自然界中生物生活習性在定義域中快速尋找目標問題的最優(yōu)解，具有可擴展性、自適應性和并行性[3]等多種優(yōu)點。目前，群智能優(yōu)化算法被廣泛地應用于求解復雜的優(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]、差分進化（Differential Evolution， DE）算法[8]等。

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

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

1 KH算法

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

磷蝦個體的移動方向用拉格朗日模型建模：

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

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

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

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

動態(tài)壓力控制算子的詳細計算方法見算法1。

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

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

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

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

3 仿真實驗與結果分析

3.1 測試函數(shù)與實驗參數(shù)

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

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

3.2 實驗結果

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

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

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

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

4 結語

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

參考文獻 （References）

[1] 林詩潔，董晨，陳明志，等.新型群智能優(yōu)化算法綜述[J].計算機工程與應用，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)化的結合熵的最大類間方差法與脈沖耦合神經(jīng)網(wǎng)絡融合的圖像分割算法[J].計算機應用，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].計算機應用，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].計算機應用，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].小型微型計算機系統(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.）