差分?jǐn)_動(dòng)的堆優(yōu)化算法

張新明，溫少晨，劉尚旺，2

（1.河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南新鄉(xiāng) 453007；2.智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實(shí)驗(yàn)室（河南師范大學(xué)），河南新鄉(xiāng) 453007）

0 引言

隨著社會(huì)的快速發(fā)展，現(xiàn)實(shí)生活中亟待解決的優(yōu)化問題越來越多，也越來越多樣化和復(fù)雜化。傳統(tǒng)的優(yōu)化方法如牛頓法和梯度法并不能有效地解決這些問題［1］。受自然現(xiàn)象和生物進(jìn)化行為等的啟發(fā)，許多學(xué)者開發(fā)出多種元啟發(fā)式算法（Meta-heuristic Algorithm，MA）。這些MA 包括差分進(jìn)化（Differential Evolution，DE）［2］、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［3］、生物地理學(xué)優(yōu)化（Biogeography-Based Optimization，BBO）算法［4］和灰狼優(yōu)化（Grey Wolf Optimizer，GWO）［5］算法等。因簡單易實(shí)現(xiàn)等優(yōu)勢，已經(jīng)在現(xiàn)實(shí)生活中得到了非常廣泛的應(yīng)用。然而，根據(jù)無免費(fèi)午餐理論［6］，沒有一種MA 能夠解決所有的優(yōu)化問題。另外，為了處理不同的和更復(fù)雜的優(yōu)化問題，不斷有新的或改進(jìn)的MA被提出。

堆優(yōu)化（Heap-Based Optimizer，HBO）算法是Askari 等［7］在2020 年提出的一種新的MA。它利用堆結(jié)構(gòu)模擬了公司的層級(jí)結(jié)構(gòu)，采用了堆的概念形成個(gè)體之間的交互，并且構(gòu)建了三種構(gòu)造新解的數(shù)學(xué)模型。HBO 有獨(dú)特的搜索機(jī)制，且解決經(jīng)典優(yōu)化問題的性能優(yōu)于一些經(jīng)典的MA，如PSO 等。但HBO 也存在一些不足，例如高層個(gè)體和低層個(gè)體之間的信息交流不足，沒有對(duì)最優(yōu)個(gè)體的位置進(jìn)行更新，導(dǎo)致其在解決復(fù)雜優(yōu)化問題時(shí)存在搜索能力不足、效率低下等問題。另外HBO 提出的時(shí)間較短，有許多工作要做，如理論研究、改進(jìn)研究和應(yīng)用研究等。因此對(duì)HBO 的研究非常必要。

差分?jǐn)_動(dòng)策略利用兩個(gè)或多個(gè)個(gè)體之間的加權(quán)差來擾動(dòng)當(dāng)前個(gè)體，有效增強(qiáng)種群的多樣性，提高種群中的各種信息的使用程度。許多學(xué)者對(duì)差分?jǐn)_動(dòng)策略進(jìn)行了大量的研究，主要可以分為以下幾個(gè)方面：1）兩個(gè)隨機(jī)個(gè)體差分?jǐn)_動(dòng)，主要用來增強(qiáng)個(gè)體之間的信息共享能力［8］；2）最優(yōu)個(gè)體與最差個(gè)體差分?jǐn)_動(dòng)，通過最優(yōu)個(gè)體的引導(dǎo)，可以增強(qiáng)信息引導(dǎo)能力［6］；3）最優(yōu)個(gè)體、當(dāng)前個(gè)體和兩個(gè)隨機(jī)個(gè)體兩組差分?jǐn)_動(dòng)。通過兩組不同類型的差分，兼顧信息共享與信息引導(dǎo)［4］。

因此，為了解決HBO 存在的一些問題，本文采用了不同的差分?jǐn)_動(dòng)策略以改進(jìn)HBO，提出了一種差分?jǐn)_動(dòng)的HBO（Differential disturbed HBO，DDHBO）算法。本文的主要工作如下：1）由于HBO 獨(dú)特的搜索機(jī)制，無法更新最優(yōu)個(gè)體的位置和前期易產(chǎn)生無效解，本文對(duì)最優(yōu)個(gè)體采用一種隨機(jī)差分?jǐn)_動(dòng)策略，在前期采用基于維的差分?jǐn)_動(dòng)策略，從而提高搜索效率；2）對(duì)于最差個(gè)體，采用一種最優(yōu)最差差分?jǐn)_動(dòng)策略更新其位置，強(qiáng)化其搜索能力；3）對(duì)于一般個(gè)體，采用一種多層差分?jǐn)_動(dòng)策略，以強(qiáng)化高層與低層之間的信息交流，提高搜索能力。由于HBO 原始算法的優(yōu)化性能僅僅在經(jīng)典函數(shù)上進(jìn)行了驗(yàn)證，本文將HBO 及其改進(jìn)算法運(yùn)用到復(fù)雜函數(shù)集CEC2017［9］上進(jìn)行驗(yàn)證。

1 堆優(yōu)化算法

HBO 模擬公司層次結(jié)構(gòu)建立樹狀結(jié)構(gòu)，它選擇的是三元堆或者說是一個(gè)三叉樹，具體見圖1。公司等級(jí)制度的最終目標(biāo)是以最好的方式完成與業(yè)務(wù)相關(guān)的任務(wù)，主要包括三個(gè)數(shù)學(xué)模型：下屬與直接領(lǐng)導(dǎo)的交互、與同事的交互和個(gè)體的自我貢獻(xiàn)。

圖1 中X1所在的層次為最高層第一層，僅有一個(gè)個(gè)體；X2～X4所在的層次為第二層，3 個(gè)個(gè)體；X5～X13所在的層次為第三層，9 個(gè)個(gè)體；如此，第四層應(yīng)該有27 個(gè)體；所有這些個(gè)體組成一個(gè)群體，其種群大小為40。從X2開始所有的個(gè)體都是通過直接領(lǐng)導(dǎo)和同事的引導(dǎo)進(jìn)行更新。以X8為例，由于堆獨(dú)特的結(jié)構(gòu)，與X8在同一層次的個(gè)體均為其同事，為X5～X13，且只有一個(gè)直接領(lǐng)導(dǎo)X3。然而對(duì)于最高領(lǐng)導(dǎo)X1，它所在的層是最高層，沒有直接領(lǐng)導(dǎo)，并且該層只有X1一個(gè)個(gè)體，也不存在同事。

與直接領(lǐng)導(dǎo)交互的數(shù)學(xué)模型可以描述為：

其中：t是當(dāng)前迭代次數(shù)；T是最大迭代次數(shù)；j是一個(gè)解向量的第j個(gè)分量；B是當(dāng)前個(gè)體的直接領(lǐng)導(dǎo)；r是均勻分布在［0，1］中的隨機(jī)數(shù)；在迭代過程中，γ是一個(gè)三角波，它的值在1的左右波動(dòng)，從2 到0，或從0 到2。

在堆中，位于同一層的個(gè)體都是其同事，每個(gè)個(gè)體Xi根據(jù)隨機(jī)選擇的同事Sr更新位置，數(shù)學(xué)模型見式（4）：

其中：f是個(gè)體的目標(biāo)函數(shù)。對(duì)于最小極值問題，若f（Sr）＜f（Xi），個(gè)體可以探索Sr周圍的區(qū)域；若f（Sr）≥f（Xi），個(gè)體可以探索Xi周圍的區(qū)域，以保證搜索向好的方向發(fā)展。

在個(gè)體的自我貢獻(xiàn)的模型中，個(gè)體在前一次迭代中的一些位置信息會(huì)一直保留到下一次迭代。即個(gè)體Xi在下一次迭代中不會(huì)改變其第j個(gè)分量的值。

在HBO 中，p1、p2和p3決定了個(gè)體將會(huì)在這三個(gè)數(shù)學(xué)模型中選擇哪個(gè)模型進(jìn)行更新。選擇概率的計(jì)算方法如下：

HBO 通過p1選擇自我貢獻(xiàn)模型更新個(gè)體，通過p2選擇與直接領(lǐng)導(dǎo)交互的數(shù)學(xué)模型更新個(gè)體，通過p3選擇與同事交互的數(shù)學(xué)模型更新個(gè)體，其中p3=1。HBO 的偽代碼見算法1。

算法1 堆優(yōu)化算法。

其中邊界控制是：當(dāng)Xj小于Lj（下界），則Xj=Lj；當(dāng)Xj大于Uj（上界），則Xj=Uj。

從以上描述來看，HBO 具有以下特點(diǎn)：1）具有獨(dú)特的結(jié)構(gòu)和搜索機(jī)制。HBO 采用三元堆結(jié)構(gòu)，不同層次由于受到不同的直接領(lǐng)導(dǎo)的引導(dǎo)和隨機(jī)選擇同事更新個(gè)體的方式，因此產(chǎn)生的解會(huì)不同，如此會(huì)獲得一定的多樣性。2）HBO 每產(chǎn)生一個(gè)新解，就計(jì)算其適應(yīng)度值，并采用貪心選擇方法更新對(duì)應(yīng)的個(gè)體，更新后的好個(gè)體又對(duì)后續(xù)新解的產(chǎn)生發(fā)揮作用，如此的選擇稱為動(dòng)態(tài)貪心選擇，它形成一種正反饋，使算法獲得更強(qiáng)的局部搜索能力，加快收斂［1］。3）式（4）的更新方式可以保證個(gè)體向更好的方向演化，從而獲得好的收斂性能。4）堆中的個(gè)體通過直接領(lǐng)導(dǎo)和同事的引導(dǎo)進(jìn)行局部搜索，但每一次局部搜索都會(huì)影響堆的構(gòu)建，因此更新堆可以在一定程度上實(shí)現(xiàn)個(gè)體間的信息交流。

2 差分?jǐn)_動(dòng)的堆優(yōu)化算法

2.1 HBO存在的問題及改進(jìn)的動(dòng)機(jī)

雖然HBO 具有較多的優(yōu)勢，但仍存在一些不足：1）HBO獨(dú)特的堆搜索結(jié)構(gòu)決定了HBO 的最高領(lǐng)導(dǎo)不會(huì)參與搜索過程。2）雖然在不同的層次中會(huì)產(chǎn)生不同的解，從而增強(qiáng)種群的多樣性，但個(gè)體僅受到直接領(lǐng)導(dǎo)和同事的影響，尤其最差個(gè)體采用這種搜索模型導(dǎo)致搜索能力受限。3）第l層個(gè)體的更新只依賴于第l層和第l-1 層個(gè)體，與其他層（間接層）的個(gè)體之間沒有聯(lián)系，僅通過動(dòng)態(tài)更新堆實(shí)現(xiàn)信息共享，信息利用的程度較低，缺少間接層之間的信息交互，從而導(dǎo)致在解決復(fù)雜優(yōu)化問題時(shí)搜索能力不足［1］。4）在迭代前期，p1的值很大，接近1，此時(shí)通過式（5）產(chǎn)生的新解可能與原解相同，此新解是無效的，算法在迭代前期的搜索能力較差。另外，在搜索后期，若t＞T/2，則p1的值小于0.5，p2的取值范圍為［0.5，0.75］，個(gè)體所在的層次越低，產(chǎn)生新解的多樣性越強(qiáng)，雖然有利于防止算法陷于局部最優(yōu)，但會(huì)影響收斂速度。因此，本文提出了DDHBO，在保持HBO 最大優(yōu)勢的同時(shí)，克服了HBO 的一些缺陷。

2.2 最優(yōu)個(gè)體：隨機(jī)差分?jǐn)_動(dòng)策略

正如上文所述，在HBO 中，由于堆的獨(dú)特結(jié)構(gòu)，根節(jié)點(diǎn)（最優(yōu)個(gè)體）在堆中沒有直接領(lǐng)導(dǎo)和同事，因此在HBO 中并未參與搜索，導(dǎo)致了算法搜索效率低的問題。因此，本文對(duì)最優(yōu)個(gè)體采用了隨機(jī)差分?jǐn)_動(dòng)策略，突破結(jié)構(gòu)限制。通過對(duì)種群中隨機(jī)選擇的兩個(gè)個(gè)體之間的正弦加權(quán)差進(jìn)行擾動(dòng)，提高搜索效率，強(qiáng)化最優(yōu)個(gè)體，具體如式（8）所示：

其中：Xa和Xb是從種群中隨機(jī)選擇的兩個(gè)個(gè)體的位置；fr是縮放因子，采用正弦模型［10］。

由式（9）可得，fr的值在0.5 左右波動(dòng)，當(dāng)fr＞0.5 時(shí)，可以增大當(dāng)前個(gè)體的搜索范圍；當(dāng)fr≤0.5 時(shí)，個(gè)體可以進(jìn)行更精細(xì)的搜索，有助于提高局部搜索能力。由式（8）可得，最優(yōu)個(gè)體的位置更新受到了兩個(gè)隨機(jī)個(gè)體Xa和Xb的影響，因此，隨機(jī)差分?jǐn)_動(dòng)策略可以通過種群中的兩個(gè)隨機(jī)個(gè)體的擾動(dòng)，增強(qiáng)不同層次（含間接層）之間的信息共享，從而提高搜索能力。

總之，對(duì)于最優(yōu)個(gè)體采用隨機(jī)差分?jǐn)_動(dòng)策略對(duì)其位置進(jìn)行更新，不僅提高搜索效率，而且也提高了算法的搜索能力。

2.3 最差個(gè)體：最優(yōu)最差差分?jǐn)_動(dòng)策略

由木桶效應(yīng)可知，一個(gè)由多個(gè)木板組成的水桶可以裝載的水容量，取決于其中最短的一塊木板。在MA 中，也是同樣，種群中最差個(gè)體的質(zhì)量可能影響整個(gè)種群的搜索能力。因此，為了提高最差個(gè)體的質(zhì)量，采用了一種最優(yōu)最差差分?jǐn)_動(dòng)策略，其中具有兩種不同的更新方式，根據(jù)迭代次數(shù)的不同在兩種更新方式中進(jìn)行選擇。兩種更新公式都是通過最優(yōu)個(gè)體的引導(dǎo)，提升最差個(gè)體的質(zhì)量，從而強(qiáng)化最差個(gè)體的搜索能力，具體如式（10）～（12）所示：

其中：Xw為當(dāng)前種群中的最差個(gè)體位置；Xg為當(dāng)前種群中的最優(yōu)個(gè)體位置；ceil是一個(gè)向上取整函數(shù)；?表示兩向量間各個(gè)對(duì)應(yīng)的分量相乘；rt是一個(gè)隨迭代次數(shù)隨機(jī)變化的量。

最優(yōu)最差差分?jǐn)_動(dòng)策略根據(jù)rt的不同在兩種更新方式中進(jìn)行選擇，若當(dāng)前迭代次數(shù)t＜rt，則執(zhí)行式（11）；若t≥rt，則執(zhí)行式（12），以此實(shí)現(xiàn)在兩種更新方式中的動(dòng)態(tài)和隨機(jī)選擇。由式（11）可知，縮放因子為2(rand-0.5)，rand是一個(gè)隨機(jī)向量，其中每一個(gè)分量在［0，1］中均勻分布，則該縮放因子中每一個(gè)分量均勻分布在［-1，1］，Xg與Xw差分結(jié)果的每一個(gè)分量都通過不同的隨機(jī)數(shù)進(jìn)行加權(quán)，可以更好地提升解的多樣性。由于在每次迭代過程中，rt的值在不斷變化，因此，式（11）和式（12）在整個(gè)迭代過程中執(zhí)行的次數(shù)不一定相同，并且，在迭代前期執(zhí)行式（11），最優(yōu)個(gè)體Xg與最差個(gè)體Xw之間的差異較大，可以使個(gè)體在更大的范圍內(nèi)進(jìn)行搜索，強(qiáng)化了探索能力；在迭代后期執(zhí)行式（12），隨著種群的進(jìn)化，最優(yōu)個(gè)體Xg與最差個(gè)體Xw之間的差異逐漸縮小，有利于個(gè)體更精細(xì)的搜索，增強(qiáng)開采能力。

2.4 一般個(gè)體：多層差分?jǐn)_動(dòng)策略

在HBO 中當(dāng)前個(gè)體僅與直接領(lǐng)導(dǎo)和同事有信息交換，與其他層次的個(gè)體之間沒有信息共享導(dǎo)致搜索能力不足。因此，對(duì)一般個(gè)體采用了多層差分?jǐn)_動(dòng)策略，最優(yōu)個(gè)體與當(dāng)前個(gè)體差分，高層隨機(jī)選擇個(gè)體與低層隨機(jī)選擇個(gè)體進(jìn)行差分的方法對(duì)一般個(gè)體的位置進(jìn)行更新，以強(qiáng)化多層之間的信息交流，提高搜索能力，具體如式（13）所示：

其中：Xc是從高層個(gè)體中隨機(jī)選擇個(gè)體的位置；Xd是低層個(gè)體中隨機(jī)選擇個(gè)體的位置。這里的一般個(gè)體是指從除最優(yōu)個(gè)體和最差個(gè)體外余下個(gè)體中隨機(jī)選擇的一個(gè)個(gè)體。

由式（13）可知，當(dāng)前個(gè)體的位置更新受到了4 個(gè)不同個(gè)體的影響：最優(yōu)個(gè)體、當(dāng)前個(gè)體本身、隨機(jī)選擇的高層個(gè)體和隨機(jī)選擇的低層個(gè)體。這4 個(gè)個(gè)體幾乎分別來自不同的層次，最優(yōu)個(gè)體位于堆的最高層，當(dāng)前個(gè)體與最優(yōu)個(gè)體一定處于不同層次上，故兩組差分?jǐn)_動(dòng)形成多層差分?jǐn)_動(dòng)。另外，個(gè)體在進(jìn)化的過程中不僅受到了最優(yōu)個(gè)體的引導(dǎo)，還受到高層個(gè)體的引導(dǎo)，可以向著更好的方向進(jìn)化，加快收斂速度；同時(shí)，也受到了不同層次中個(gè)體的相互影響，從而增強(qiáng)種群的多樣性，實(shí)現(xiàn)不同層次之間信息共享，提升搜索能力。

2.5 搜索前期：基于維的差分?jǐn)_動(dòng)策略

正如前文所述，HBO 通過隨機(jī)數(shù)p在個(gè)體的自我貢獻(xiàn)模型，與直接領(lǐng)導(dǎo)的交互、與同事的交互三種不同的更新方式中進(jìn)行選擇，根據(jù)式（6），在搜索前期p1的值很大，接近1。依據(jù)式（5），每次迭代，在個(gè)體的自我貢獻(xiàn)模型中，將前一次迭代得到的解直接賦值給當(dāng)前的新解，有可能產(chǎn)生的新解與原解相同，如此的新解是無效解，故前期全局搜索能力不足。因此，本文采用了基于維的差分?jǐn)_動(dòng)策略，在搜索前期增強(qiáng)全局搜索能力，改進(jìn)后的更新公式如下所示：

其中：Xm和Xn是從當(dāng)前種群中隨機(jī)選擇的兩個(gè)個(gè)體。

由式（14）可知，為了增強(qiáng)全局搜索能力，對(duì)HBO 的自我貢獻(xiàn)模型進(jìn)行改變，當(dāng)t＜0.05T時(shí)，采用了對(duì)兩個(gè)隨機(jī)個(gè)體位置進(jìn)行正弦差分的方式，替代HBO 中的直接賦值。兩個(gè)隨機(jī)個(gè)體在迭代前期的差異較大，并且與最優(yōu)個(gè)體的隨機(jī)差分?jǐn)_動(dòng)不同，每一維都隨機(jī)選擇兩個(gè)不同的個(gè)體，即，在迭代前期，個(gè)體有很大的概率會(huì)采用前期基于維的差分?jǐn)_動(dòng)策略更新，從而在迭代前期避免產(chǎn)生無效解，增強(qiáng)全局搜索能力。

2.6 本文算法的總流程

雖然HBO 采用動(dòng)態(tài)貪心選擇能夠加快收斂速度，但存在一些不足，如易陷于局部最優(yōu)，導(dǎo)致算法不穩(wěn)定和目標(biāo)函數(shù)難以進(jìn)行并行計(jì)算等。為了克服這些不足，本文采用了靜態(tài)貪心選擇，即每次迭代，在所有的個(gè)體產(chǎn)生新解之后，并行處理每個(gè)新解的邊界，并行計(jì)算所有個(gè)體的適應(yīng)度值，然后采用貪心選擇更新種群，如此貪心選擇被稱為靜態(tài)貪心選擇。更新種群后再對(duì)堆進(jìn)行更新。因此靜態(tài)貪心選擇雖然降低了收斂性能，但提高了穩(wěn)定性，并且靜態(tài)貪心選擇使并行計(jì)算可行，可以有效地減少算法的運(yùn)行時(shí)間。

將各種差分?jǐn)_動(dòng)策略嵌入到HBO 中，并采用靜態(tài)貪心算法，構(gòu)建DDHBO。流程如圖2 所示。其中隨機(jī)差分?jǐn)_動(dòng)、最優(yōu)最差差分?jǐn)_動(dòng)和多層差分?jǐn)_動(dòng)是三種基于個(gè)體的更新策略。

圖2 DDHBO流程Fig.2 Flowchart of DDHBO

與HBO 相比，DDHBO 具有如下的不同之處：1）HBO 中最優(yōu)個(gè)體并未參與搜索過程，沒能發(fā)揮最優(yōu)個(gè)體的作用；而DDHBO 中最優(yōu)個(gè)體采用隨機(jī)差分?jǐn)_動(dòng)策略，突破了HBO 更新模型的限制，提高搜索效率和搜索能力。2）在DDHBO 中，最差個(gè)體放棄原更新方式，采用了兩種不同的方式進(jìn)行位置更新，不僅增強(qiáng)了算法的全局搜索能力，也在一定程度上增強(qiáng)了算法的局部搜索能力。3）HBO 個(gè)體都是通過與直接領(lǐng)導(dǎo)和同事交互進(jìn)行更新，而DDHBO 對(duì)一般個(gè)體采用了多層差分?jǐn)_動(dòng)策略，突破了僅與直接層個(gè)體有信息交流的限制，提升了不同層次間個(gè)體的交流。4）HBO 采用式（1）～（5）對(duì)個(gè)體進(jìn)行位置更新，在搜索前期易產(chǎn)生無效解；而DDHBO 在搜索前期采用了基于維的差分?jǐn)_動(dòng)策略，從而避免產(chǎn)生無效解，增強(qiáng)搜索能力，即對(duì)于其他個(gè)體采用改進(jìn)后的式（14）進(jìn)行位置更新。5）HBO 采用動(dòng)態(tài)貪心選擇可加快收斂速度，但穩(wěn)定性不強(qiáng)；DDHBO 采用了靜態(tài)貪心選擇，可采用并行計(jì)算，這種計(jì)算方式有效地減少了算法的運(yùn)行時(shí)間，增強(qiáng)了穩(wěn)定性。

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

3.1 實(shí)驗(yàn)環(huán)境配置及參數(shù)設(shè)置

為了驗(yàn)證DDHBO 的優(yōu)化性能，選擇公開的復(fù)雜優(yōu)化問題benchmark：CEC2017 測試集［9］進(jìn)行大量實(shí)驗(yàn)。CEC2017 包括30 個(gè)不同類型的復(fù)雜基準(zhǔn)函數(shù)。其中，F(xiàn)1～F3為單峰函數(shù)、F4～F10為多峰函數(shù)、F11～F20為混合函數(shù)，F(xiàn)21～F30為復(fù)合函數(shù)。所有實(shí)驗(yàn)都是在Windows 7 操作系統(tǒng)下，CPU 為3.1 GHz，內(nèi)存為4 GB 的PC 上實(shí)現(xiàn)的。編程語言采用Matlab2014a。為了公平比較，所有算法的公共參數(shù)設(shè)置相同，即維度D為30，依據(jù)文獻(xiàn)［9］的最佳推薦設(shè)置，最大目標(biāo)函數(shù)評(píng)價(jià)次數(shù)為D×10 000，獨(dú)立運(yùn)行次數(shù)為51。為了更好地驗(yàn)證DDHBO 的優(yōu)化性能，本文選擇了8 個(gè)具有代表性的優(yōu)秀算法進(jìn)行對(duì)比實(shí)驗(yàn)。這些算法既有最經(jīng)典MA 的代表如DE 和PSO 的改進(jìn)算法，也有最近提出的MA 的代表如BBO和GWO 的改進(jìn)算法。分別是HBO、SaDE（DE with Strategy adaptation）［11］、SE04（Spherical Evolution）［12］、WRBBO（Worst opposition learning and Random-scaled differential mutation BBO）［13］、DEBBO（Differential Evolution and BBO）［2］、HGWOP（Hybrid PSO and GWO）［3］、MEGWO（Multi-strategy Ensemble GWO）［14］和MPSO（Motion-encoded PSO）［15］，其中DEBBO 和SaDE均為DE 的變體，HGWOP 和MPSO均為PSO 的變體，WRBBO 和MEGWO 分別為BBO 和GWO 的改進(jìn)算法，HGWOP、MPSO 和SE04 是最新提出的算法，因此，本文中所選擇的對(duì)比算法有較強(qiáng)的代表性和可比性。每個(gè)對(duì)比算法的參數(shù)設(shè)置均為對(duì)應(yīng)文獻(xiàn)中的最佳推薦，具體如表1 所示，其中SaDE 和SE04 的具體的參數(shù)設(shè)置見文獻(xiàn)［12］。本文采用均值（Mean）、標(biāo)準(zhǔn)差（Std）和排名（Rank）［3］評(píng)價(jià)算法的性能好壞。對(duì)于最小值問題，均值越小性能越好，方差越小，算法的穩(wěn)定性越強(qiáng)。

表1 不同算法的參數(shù)設(shè)置Tab.1 Parameter setting of different algorithms

3.2 與不完全算法的對(duì)比分析

為了驗(yàn)證本文所提出的每種差分?jǐn)_動(dòng)策略的有效性，將DDHBO 與它的3 個(gè)不完全算法（ESHBO、EBHBO 和WEHBO）和HBO 進(jìn)行對(duì)比實(shí)驗(yàn)。其中，ESHBO 為在HBO 的基礎(chǔ)上采用了靜態(tài)貪心和基于維的差分?jǐn)_動(dòng)策略（HBO with static greedy and dimension-based differential disturbance strategy），EBHBO 為在ESHBO 的基礎(chǔ)上添加了對(duì)最優(yōu)個(gè)體的隨機(jī)差分?jǐn)_動(dòng)策略（ESHBO with the random difference disturbance strategy for the best individual），WEHBO為在EBHBO 的基礎(chǔ)上添加了對(duì)最差個(gè)體的最優(yōu)最差差分?jǐn)_動(dòng)策略（EBHBO with the best worst differential disturbance strategy for the worst individual），DDHBO 為在WEHBO 的基礎(chǔ)上添加了對(duì)一般個(gè)體執(zhí)行的多層差分?jǐn)_動(dòng)策略。3 個(gè)不完全算法與DDHBO 的參數(shù)設(shè)置相同。DDHBO 與其3 個(gè)不完全算法及HBO 在30 維CEC2017 復(fù)雜函數(shù)上進(jìn)行實(shí)驗(yàn)，對(duì)比算法的平均排名如表2 所示。將結(jié)果進(jìn)行Wilcoxon 符號(hào)秩檢驗(yàn)［3］，顯著性水平為0.05，其檢驗(yàn)結(jié)果見表3。表3 中：“n”表示30個(gè)CEC2017 的復(fù)雜函數(shù)；“+”表示優(yōu)于對(duì)比算法；“≈”表示兩種算法獲得近似的優(yōu)化結(jié)果；“-”表示劣于對(duì)比算法；最后一行為“n/+/≈/-”的統(tǒng)計(jì)結(jié)果。

表2 不完全算法平均排名結(jié)果Tab.2 Average ranking results of incomplete algorithms

表3 不完全算法的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果Tab.3 Wilcoxon signed rank test results of incomplete algorithms

由表3 可得，ESHBO 優(yōu)于HBO 的函數(shù)個(gè)數(shù)是25，僅在5個(gè)函數(shù)上的優(yōu)化結(jié)果上劣于HBO，由此可得，本文所采用的基于維的差分?jǐn)_動(dòng)策略和靜態(tài)貪心選擇可以有效地提高HBO 的優(yōu)化性能。EBHBO 優(yōu)于ESHBO 的函數(shù)個(gè)數(shù)是27，并且結(jié)合表2 可得，EBHBO 的平均排名為2.93，優(yōu)于ESHBO 的排名3.87，表明對(duì)最優(yōu)個(gè)體的隨機(jī)差分?jǐn)_動(dòng)策略有效地提高了ESHBO 的優(yōu)化性能。WEHBO 優(yōu)于EBHBO 的函數(shù)個(gè)數(shù)是27，在3 個(gè)函數(shù)上的優(yōu)化結(jié)果劣于EBHBO，WEHBO 的平均排名結(jié)果為2.13，相較于EBHBO 的平均排名又有了一定程度的提升，表明本文對(duì)最差個(gè)體的最優(yōu)最差差分?jǐn)_動(dòng)策略對(duì)算法性能的提高是有幫助的。DDHBO 在27 個(gè)函數(shù)上的優(yōu)化結(jié)果優(yōu)于WEHBO，并且DDHBO 在平均排名上優(yōu)于WEHBO，由此可見對(duì)一般個(gè)體執(zhí)行的多層差分?jǐn)_動(dòng)策略在一定程度上提升了算法的優(yōu)化性能。結(jié)合表2 可知，在5 個(gè)算法中，HBO 的平均排名為4.70，排名第5，優(yōu)化性能最差。DDHBO 的平均排名為1.37，在30 個(gè)復(fù)雜函數(shù)上的總排名為第1，說明DDHBO 具有最好的優(yōu)化性能，并且在大多數(shù)函數(shù)上均提供了最優(yōu)結(jié)果。綜上，本文所提出的每種改進(jìn)策略都不同程度地對(duì)DDHBO 整體性能有貢獻(xiàn)，每一個(gè)改進(jìn)策略都是不可或缺的。

3.3 與最先進(jìn)算法進(jìn)行比較

為了更好地驗(yàn)證DDHBO 的優(yōu)化性能，本節(jié)將其與8 個(gè)具有代表性的優(yōu)秀算法進(jìn)行對(duì)比實(shí)驗(yàn)。8 個(gè)算法見3.1 節(jié)所述。在30 維CEC2017 的復(fù)雜函數(shù)上的實(shí)驗(yàn)結(jié)果如表4 所示，其中SaDE 和SE04 的實(shí)驗(yàn)數(shù)據(jù)直接來自文獻(xiàn)［12］。

由表4 可知，在3 個(gè)單峰函數(shù)上，DDHBO 的排名均為第1，獲得了最好的結(jié)果，大幅度優(yōu)于其8 個(gè)對(duì)比算法，由此可得，在9 個(gè)算法中，DDHBO 具有最強(qiáng)的局部搜索能力和最好的優(yōu)化精度。盡管在7 個(gè)多峰函數(shù)的均值上DDHBO 略遜于不同的對(duì)比算法，但在6 個(gè)多峰函數(shù)的均值上都優(yōu)于HBO的均值，表明本文所提出的策略可以有效提高HBO 的全局搜索能力。在20 個(gè)復(fù)雜函數(shù)上（10 個(gè)混合函數(shù)和10 個(gè)復(fù)合函數(shù)），DDHBO 獲得排名第1 的次數(shù)為8，而其他8 個(gè)算法HBO、WRBBO、DEBBO、SaDE、SE04、HGWOP、MEGWO 和MPSO 獲得排名第1 的次數(shù)分別為0、1、4、0、0、4、3 和0，由此可得，與其他8 個(gè)對(duì)比算法相比，DDHBO 具有更強(qiáng)的解決復(fù)雜優(yōu)化問題的能力。總體而言，DDHBO 在29 個(gè)函數(shù)（96.67%）上具有比HBO 更好的優(yōu)化性能。所有算法的排名順序?yàn)镈DHBO、MEGWO、HGWOP、DEBBO、SE04、SaDE、WRBBO、MPSO、HBO。DDHBO 排名第1 的次數(shù)為11，總排名為第1，表明DDHBO 具有最好的優(yōu)化性能，本文所提出的改進(jìn)策略有效提高了HBO 的性能。

續(xù)表

3.4 收斂性分析

為了驗(yàn)證DDHBO 的收斂性能，本節(jié)進(jìn)行收斂性實(shí)驗(yàn)和分析。為了更簡潔描述和更能說明問題，從CEC2017 測試集的4 類函數(shù)中選擇了4 個(gè)具有代表性的函數(shù)來分析討論DDHBO 與其他3 個(gè)不完全算法、HBO，以及MEGWO 和HGWOP（在表4 中排名第2、第3）的收斂性能。這4 個(gè)函數(shù)F3、F7、F14和F30分別為單峰函數(shù)、多峰函數(shù)、混合函數(shù)和復(fù)合函數(shù)。7 種算法在30 維的收斂曲線如圖3 所示，其中縱軸表示算法獲得的實(shí)際最優(yōu)值與函數(shù)的理論最優(yōu)值之間誤差的平均值。

圖3 DDHBO及其對(duì)比算法的收斂圖Fig.3 Convergence curves of DDHBO and its comparison algorithms

由圖3 可知，DDHBO 在4 個(gè)不同函數(shù)上的收斂速度均優(yōu)于其3 個(gè)不完全算法和HBO，隨著目標(biāo)函數(shù)評(píng)價(jià)次數(shù)的增加，DDHBO 的收斂速度最快。由3.2 節(jié)可知，從ESHBO、EBHBO、WEHBO 到DDHBO，分別在HBO 中依次疊加了靜態(tài)貪心選擇和基于維的差分?jǐn)_動(dòng)策略，對(duì)最優(yōu)個(gè)體的隨機(jī)差分?jǐn)_動(dòng)策略，對(duì)最差個(gè)體的最優(yōu)最差差分?jǐn)_動(dòng)策略，對(duì)一般個(gè)體執(zhí)行的多層差分?jǐn)_動(dòng)策略。盡管DDHBO 在F7上的收斂性能略遜于HGWOP，但優(yōu)于其他5 個(gè)對(duì)比算法；并且在其他3 個(gè)函數(shù)上的收斂性能始終優(yōu)于6 個(gè)對(duì)比算法的收斂性能。以圖3（c）為例，可以看到隨著改進(jìn)策略的增加，算法的收斂性能也得到了不同程度的提升，7 個(gè)算法在函數(shù)F14的收斂性能順序?yàn)镈DHBO、MEGWO、WEHBO、EBHBO、HGWOP、ESHBO 和HBO。因此，與HBO 相比，DDHBO 不管是在單峰函數(shù)、多峰函數(shù)、混合函數(shù)還是復(fù)合函數(shù)上都具有更好的收斂性能，表明本文所提出的改進(jìn)策略不僅增強(qiáng)了探索能力和開采能力，更好地實(shí)現(xiàn)了探索與開采之間的平衡；再次驗(yàn)證了本文所提出的改進(jìn)策略在HBO 上的有效性，可以有效加快HBO 的收斂速度。

3.5 時(shí)間對(duì)比

為了測試DDHBO 的運(yùn)行速度，進(jìn)行運(yùn)行時(shí)間對(duì)比實(shí)驗(yàn)。由于DDHBO 是HBO 的改進(jìn)算法，因此，為了簡潔和更能說明問題，對(duì)比算法僅選擇了4 個(gè)算法，即DDHBO、HBO，以及MEGWO 和HGWOP（表4 中排名第2和第3），在30 維CEC2017 復(fù)雜函數(shù)上的平均運(yùn)行時(shí)間如表5 所示。

從表5 可以看出，DDHBO 的平均運(yùn)行時(shí)間（3.445 0 s）為HBO 平均運(yùn)行時(shí)間（9.500 6 s）的36.26%，DDHBO 的平均運(yùn)行時(shí)間為MEGWO（3.801 6 s）的90.62%。與HGWOP 的平均運(yùn)行時(shí)間（3.287 3 s）相比，DDHBO 的平均運(yùn)行時(shí)間稍多，這是由于HGWOP 采用了更簡潔的更新方程，而DDHBO 每次迭代需要更新堆。與HBO 相比，DDHBO 的運(yùn)行時(shí)間更少的主要原因如下：HBO 中使用了動(dòng)態(tài)貪心選擇以更新種群中個(gè)體的適應(yīng)度值。動(dòng)態(tài)貪心選擇是一種串行計(jì)算方法，在每次迭代中，每次更新個(gè)體，計(jì)算適應(yīng)度值一次，耗費(fèi)的時(shí)間更多。DDHBO 采用靜態(tài)貪心選擇，在每次迭代中，更新種群中所有個(gè)體后，并行處理邊界和計(jì)算所有個(gè)體的適應(yīng)度值，減少了運(yùn)行時(shí)間。另外，雖然在HBO 添加了4 種差分?jǐn)_動(dòng)策略，但除了隨機(jī)差分?jǐn)_動(dòng)策略外，其他3 種策略都是替換操作不增加額外的計(jì)算復(fù)雜度。

3.6 顯著性分析

Wilcoxon 符號(hào)秩檢驗(yàn)是非參數(shù)統(tǒng)計(jì)檢驗(yàn)［3］，用于檢測兩種算法之間差異的顯著性。其中R+為正秩總和，R-為負(fù)秩總和。一般顯著性水平設(shè)為0.05。如果p-value＜0.05，則兩個(gè)算法之間存在顯著性差異；如果p-value≥0.05，則在優(yōu)化性能上，DDHBO 劣于對(duì)比算法或二者幾乎相同。n/w/t/l表示在n個(gè)函數(shù)上，DDHBO 在w個(gè)函數(shù)上優(yōu)于對(duì)比算法，在t個(gè)函數(shù)上獲得了與對(duì)比算法相同的結(jié)果，在l個(gè)函數(shù)上劣于對(duì)比算法。DDHBO 與其他8 個(gè)對(duì)比算法在CEC2017 復(fù)雜函數(shù)上的Wilcoxon 符號(hào)秩檢驗(yàn)結(jié)果見表6。

表6 Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果Tab.6 Wilcoxon sign rank test results

由表6可知，DDHBO 與HBO 相比的p-value為0.000 002，遠(yuǎn)遠(yuǎn)小于0.05，表明DDHBO 顯著優(yōu)于HBO，再一次說明本文中所采用的改進(jìn)策略是有效的。與WRBBO、DEBBO、SaDE、SE04、HGWOP、MEGWO 和MPSO相比，pvalue全部小于0.05，并且DDHBO優(yōu)于HBO、WRBBO、DEBBO、SaDE、SE04、HGWOP、MEGWO 和MPSO 的函數(shù)數(shù)量分別為29、26、22、26、25、19、22、30，由此可以進(jìn)一步驗(yàn)證，本文提出的DDHBO 顯著優(yōu)于對(duì)比算法。

4 結(jié)語

針對(duì)HBO 在解決復(fù)雜優(yōu)化問題時(shí)存在的搜索能力不足和效率低的問題，本文提出了一種差分?jǐn)_動(dòng)的HBO（DDHBO）。首先，為了提高HBO 的搜索效率，對(duì)于在HBO中并未更新的最優(yōu)個(gè)體位置，提出了一種隨機(jī)差分?jǐn)_動(dòng)策略；其次，為了增強(qiáng)算法的搜索能力，強(qiáng)化最差個(gè)體從而提升整個(gè)種群質(zhì)量，提出了一種最優(yōu)最差差分?jǐn)_動(dòng)策略；然后，提出了一種多層差分?jǐn)_動(dòng)策略強(qiáng)化一般個(gè)體，增強(qiáng)不同層次之間個(gè)體的信息共享，提升搜索能力；最后，提出了一種基于維的差分?jǐn)_動(dòng)策略，從而解決HBO 在搜索初期獲得有效解的概率低的問題。采用了靜態(tài)貪心選擇替代HBO 中動(dòng)態(tài)貪心選擇，并行計(jì)算方式減少了算法的運(yùn)行時(shí)間，提高了算法的運(yùn)行速度和穩(wěn)定性。在30 維CEC2017 復(fù)雜函數(shù)上的實(shí)驗(yàn)結(jié)果表明，與HBO 和其他最先進(jìn)的優(yōu)化算法相比，DDHBO 具有更好的優(yōu)化性能；并且，DDHBO 具有比HBO 更少的平均運(yùn)行時(shí)間。綜上可得，相較于對(duì)比算法，DDHBO 具有更強(qiáng)的競爭性和解決復(fù)雜優(yōu)化問題的能力。但由于HBO 是最新提出的算法，還有許多的地方需要進(jìn)一步完善，如算法理論研究、改進(jìn)研究和應(yīng)用研究以彌補(bǔ)其不足，本文僅僅是一種改進(jìn)研究嘗試。在未來的研究中，將對(duì)HBO 上述三方面做深入的研究，并將DDHBO 應(yīng)用于解決不同類型的工程優(yōu)化問題。