基于離散哈里斯鷹優(yōu)化算法求解具有單連續(xù)變量的背包問題

摘 要：為了將哈里斯鷹優(yōu)化（HHO）算法用于求解具有單連續(xù)變量的背包問題（KPC），基于0-1向量表示個體的編碼，利用位運算重構(gòu)了HHO的進化方程，并采用一種自適應(yīng)變異機制改善搜索結(jié)果，由此提出了一個新的離散哈里斯鷹優(yōu)化算法（DisHHO）。為了驗證DisHHO求解KPC的性能，利用它求解四類大規(guī)模KPC實例，通過與已有二進制HHO以及求解KPC的最新算法比較表明：DisHHO不僅平均計算結(jié)果優(yōu)，而且計算速度快，因此DisHHO是求解KPC的一個新的高效算法。

關(guān)鍵詞：演化算法； 哈里斯鷹優(yōu)化； 具有單連續(xù)變量的背包問題； 位運算

中圖分類號：TP301.6 文獻標(biāo)志碼：A

文章編號：1001-3695（2022）07-011-1992-08

doi：10.19734/j.issn.1001-3695.2021.11.0668

基金項目：河北省自然科學(xué)基金資助項目（F2020403013）；河北省高等學(xué)校科學(xué)技術(shù)研究計劃資助項目（ZD2021016）

作者簡介：孫海祿（1994-），男（滿族），河北承德人，碩士研究生，主要研究方向為大數(shù)據(jù)與計算智能；王原（1997-），男，河北張家口人，碩士研究生，主要研究方向為大數(shù)據(jù)與計算智能；王麗娜（1999-），女，河北唐山人，碩士研究生，主要研究方向為人工智能理論與技術(shù)；賀毅朝（1969-），男（通信作者），河北晉州人，教授，碩士，主要研究方向為演化算法及其應(yīng)用、組合優(yōu)化、強化學(xué)習(xí)（heyichao119@163.com）.

Solving knapsack problem with single continuous variable by discrete Harris hawks optimization algorithm

Sun Hailu^a，b， Wang Yuan^a，b， Wang Lina^a，b， He Yichao^a，b?

（a.College of Information Technology， b.College of Big Data amp; Computing Intelligence Lab， Hebei GEO University， Shijiazhuang 050031， China）

Abstract：In order to use Harris hawks optimization （HHO） to solve KPC， this paper proposed a new discrete Harris hawks optimization （DisHHO） algorithm. DisHHO encoded individual based on 0-1 vector and established the discrete evolution equations by bitwise operation. Furthermore， it used an adaptive mutation mechanism to improve the search performance. For verifying the performance of DisHHO in solving KPC， it was used to solve four kinds of large-scale KPC instances. The comparison with the existing binary HHO and state-of-the-art algorithms for solving KPC show that DisHHO not only has excellent average calculation results， but also has fast calculation speed. Hence， DisHHO is a new and efficient algorithm for solving KPC.

Key words：evolutionary algorithm（EA）; Harris hawks optimization（HHO）; knapsack problem with a single continuous va-riable（KPC）; bitwise operation

0 引言

演化算法（EA） ^［1］是一類群智能優(yōu)化算法。與傳統(tǒng)優(yōu)化算法相比，EA具有自組織、自適應(yīng)、自學(xué)習(xí)等特點，因此被廣泛應(yīng)用于眾多領(lǐng)域的復(fù)雜優(yōu)化問題。哈里斯鷹優(yōu)化（HHO）是Heidari等人^［2］于2019年提出的一種新穎演化算法，它具有參數(shù)少、結(jié)構(gòu)簡單和適應(yīng)性強的優(yōu)點，已被應(yīng)用于諸多數(shù)值優(yōu)化問題。例如Bui等人^［3］將HHO應(yīng)用于伊朗西部滑坡敏感性分析，提高了分析的準確性。Houssein等人^［4］將HHO應(yīng)用于化學(xué)描述符的選擇和化學(xué)復(fù)合活動。Abbasi等人^［5］利用HHO提高了微通道散熱器的性能。學(xué)者們對HHO易早熟收斂、易陷入局部最優(yōu)和收斂速度慢等不足進行了深入研究，提出了HHO的多個不同改進版本。例如Fan等人^［6］基于擬反射機制，提出了擬反射哈里斯鷹優(yōu)化算法（QRHHO），很好地提高了算法的收斂速度與求解精度。Hussain等人^［7］提出了一種具有記憶概念的HHO算法（LMHHO），該算法具有較好的尋優(yōu)性。Gupta等人^［8］將貪婪選擇機制和反向?qū)W習(xí)策略引入HHO，大大提高了算法的搜索效率。Jiao等人^［9］基于正交學(xué)習(xí)和反向?qū)W習(xí)提出了一種改進的HHO算法（OLHHO），提高了算法的局部搜索能力。Qu等人^［10］提出了一種基于信息交換的HHO算法（IEHHO），提高了算法的魯棒性。Ewees等人^［11］基于混沌理論提出了一種混沌多體哈里斯鷹優(yōu)化算法（CMVHHO），提升了算法的全局搜索能力。Li等人^［12］基于對數(shù)螺線和對立學(xué)習(xí)提出了一種改進的HHO算法（RLHHO），有效地提升了算法的收斂性能。Kamboj等人^［13］將HHO與正余弦算法進行結(jié)合，提出了哈里斯鷹—正余弦算法（hHHO-SCA），在提升了搜索能力的同時，能夠有效避免算法陷入局部最優(yōu)。雖然HHO在連續(xù)優(yōu)化問題上表現(xiàn)出了強勁的潛力與優(yōu)勢，但在求解離散優(yōu)化問題方面的研究還很薄弱，目前只有Too等人^［14］提出了HHO的二進制版本BHHO和QBHHO，并利用它們求解分類任務(wù)中的特征選擇問題。為了更好地將HHO用于求解組合優(yōu)化問題，本文提出了一個新的離散哈里斯鷹優(yōu)化（discrete Harris hawks optimization，DisHHO），并基于DisHHO提出求解具有單連續(xù)變量的背包問題（knapsack problem with a single continuous variable，KPC）^［15］的一個高效新方法。

背包問題^{［16，17］}是一類經(jīng)典的組合優(yōu)化問題，在資源分配、資金預(yù)算、投資決策、貨物裝載等^［18］領(lǐng)域具有廣泛的應(yīng)用。具有單連續(xù)變量的背包問題（KPC）是Marchand等人^［15］在1999年提出的一個擴展形式的背包問題，由于其中含有一個連續(xù)變量，與標(biāo)準0-1背包問題相比，求解難度更大。由于KPC是一個NP完全問題^［19］，不存在多項式時間精確算法，所以目前對KPC的研究主要集中在非確定性算法方面。例如賀毅朝等人^［19］基于降維法建立了兩個新的KPC數(shù)學(xué)模型，然后基于混合編碼二進制差分演化算法（HBDE）給出了求解KPC的兩個高效離散演化算法S-HBDE和B-HBDE。He等人^［20］利用編碼轉(zhuǎn)換技術(shù)提出了基于編碼變換的差分進化算法（ETDE）求解 KPC。王澤昆等人^［21］在給出了一個新S-型傳遞函數(shù)的基礎(chǔ)上，提出了一個新的二進制粒子群優(yōu)化（NBPSO）算法用于求解KPC。最近，He等人^［22］基于模運算提出了一個新穎的二進制團隊博弈算法（MOBTGA）用于求解KPC。演化算法不僅求解KPC的速度快，而且計算結(jié)果能夠滿足實際需求，因此探討基于演化算法求解KPC的高效方法是一個值得研究的課題。

1 HHO的原理與進化方程

哈里斯鷹優(yōu)化（HHO）^［2］是Heidari等人在對哈里斯鷹捕食過程的觀察基礎(chǔ)上提出的。在HHO中，鷹的位置相應(yīng)于問題的解；鷹群捕食過程分為搜索階段與開發(fā)階段，它們分別實現(xiàn)算法的全局搜索與局部搜索；在這兩個階段中，鷹群根據(jù)獵物的逃逸能量E，確定選擇執(zhí)行搜索階段還是執(zhí)行開發(fā)階段。下面針對優(yōu)化問題max f（X）（X∈［lb， ub］n）介紹HHO的原理。

在HHO中，獵物的逃逸能量記為E，其計算公式為

其中：E0為（-1，1）的隨機實數(shù)，表示獵物初始逃逸能量;t是HHO的當(dāng)前迭代次數(shù);T為總的迭代次數(shù)。易知，E的取值范圍為（-2，2）。當(dāng)|E|≥1時，HHO處于搜索階段；當(dāng)|E|lt;1時，HHO處于開發(fā)階段。下面分別對這兩個階段進行介紹。

在搜索階段，HHO采用兩種策略對解空間進行搜索。令R為（0，1）的隨機實數(shù)。當(dāng)R≥0.5時，哈里斯鷹會隨機棲息在種群活動范圍內(nèi)的某一位置；當(dāng)Rlt;0.5時，每只鷹會根據(jù)種群其他成員和獵物的位置進行移動。令P（t）={Xi（t）|1≤i≤N}為HHO的第t代種群，Xi（t）=［xi1（t），xi2（t），…，xin（t）］∈［lb，ub］n表示其中的第i個個體（即哈里斯鷹的位置向量），N為種群規(guī)模。ub與lb分別為實數(shù)，表示位置向量Xi（t）中各分量的上界和下界。則HHO搜索過程為

其中：Xrand（t）表示在第t代種群中隨機選取的個體;XB（t）=［xB1（t），xB2（t），…，xBn（t）］∈［lb，ub］n表示到t代為止的全局最好個體;R和ri（i=1，2，3，4）均為（0，1）上服從均勻分布的隨機數(shù);Xm（t）表示P（t）中所有個體位置的平均值，即Xm（t）=（1/N）∑Ni=1Xi（t）。

在開發(fā)階段，為了更快獲取獵物，HHO采用軟包圍、硬包圍、帶有快速俯沖的軟包圍和帶有快速俯沖的硬包圍四種機制更新個體位置。在此階段，HHO根據(jù)逃逸能量E以及（0，1）上的隨機數(shù)r的不同取值來決定采用哪種機制。

a）軟包圍。當(dāng)r≥0.5，0.5lt;|E|≤1時，獵物還具有一定的逃逸能量，鷹群會慢慢的包圍獵物，直至獵物變得疲勞，其進化方程為

其中：J=2（1-r5）（r5∈（0，1））為獵物的隨機跳躍強度。

b）硬包圍。當(dāng)r≥0.5，|E|lt;0.5時，獵物的逃逸能量較低，易被捕食，此時的進化方程為

c）帶有快速俯沖的軟包圍。當(dāng)rlt;0.5，0.5lt;|E|≤1時，獵物仍具有逃跑的能量，此時鷹群會產(chǎn)生一個環(huán)繞式軟包圍來捕食獵物，相應(yīng)的進化方程為

其中：f （·）為個體的適應(yīng)度值;Y1和Z1的定義為

其中：D為問題的維數(shù)；S表示（0，1）D上的隨機向量；LF（·）為服從Lévy-flight分布的向量。LF（·）根據(jù)式（8）計算，其中μ和v為（0，1）的隨機數(shù)，β為1.5，σ根據(jù)式（9）計算。

d）帶有快速俯沖的硬包圍。當(dāng)rlt;0.5，|E|≤0.5時，獵物已不具備逃跑的能量，此時鷹群會產(chǎn)生一個環(huán)繞式硬包圍來捕食獵物，進化方程為

其中：Y2和Z2的定義為

基于以上描述，HHO的算法原理描述為：首先，隨機初始化種群P（0）與獵物初始逃逸能量E0，計算個體適應(yīng)度，確定最好個體。在第t（t≥1）次迭代中，HHO根據(jù)獵物逃逸能量E的取值選擇執(zhí)行搜索階段或開發(fā)階段來由P（t）產(chǎn)生新一代種群中P（t+1）的個體，并根據(jù)它們的適應(yīng)度確定當(dāng)前最好個體。重復(fù)執(zhí)行上述迭代過程直至tgt;T（T為迭代次數(shù)）為止，輸出最好解，結(jié)束算法。記O（f）是f（·）的計算時間復(fù)雜度，則由HHO的原理易知，它的時間復(fù)雜度為O（T×N×（n+O（f）））。

2 DisHHO

由于HHO是針對連續(xù)優(yōu)化問題提出的，不能直接用于求解二元優(yōu)化問題。為此，本文基于位運算提出了一種離散HHO算法，并將其用于求解KPC問題。

位運算^［23］也稱布爾運算，是計算機底層實現(xiàn)運算的基礎(chǔ)，可以直接對內(nèi)存中的二進制位進行操作，因此速度非常快且易實現(xiàn)。基本位運算包括按位與（∧）、按位或（∨）和按位取反（～），它們是定義在{0，1}上的運算，其運算規(guī)則如下：

a）按位與。參與運算的兩個值都為1時，結(jié)果為1，否則為0。即1∧1=1，1∧0=0，0∧1=0，0∧0=0。

b）按位或。參與運算的兩個值都為0時，結(jié)果為0，否則為1。即0∨0=0，1∨0=1，0∨1=1，1∨1=1。

c）按位取反。參與運算的值為1時，結(jié)果為0；參與運算的值為0時，結(jié)果為1。即～1=0，～0=1。

基于按位與、按位或與按位取反三種基本位運算的復(fù)合，可以定義一些更復(fù)雜的位運算，如按位與非、按位或非、按位與或非、按位異或等。其中，按位異或（⊕）運算最常用，它的運算規(guī)則為：參與運算的兩個值相同時，結(jié)果為0，否則為1，即1⊕1=0，0⊕0=0，1⊕0=1，0⊕1=1。

由于位運算是定義在{0，1}上的，它與二元優(yōu)化問題中二元變量的取值相同，所以適用于演化算法的離散化來求解二元優(yōu)化問題。下面，利用位運算提出一個適于求解二元優(yōu)化問題max f（X）（X∈{0，1}n）的新穎的離散HHO（記為DisHHO）。

令P（t）={Xi（t）|1≤i≤N}為DisHHO的第t（t≥0）代種群，Xi（t）=［xi1（t），xi2（t），…，xin（t）］∈{0，1}n是其中的第i個個體，N表示種群規(guī)模，XB（t）=［xB1（t），xB2（t），…，xBn（t）］∈{0，1}n表示到t代時DisHHO獲得的最好個體，則DisHHO的算法實現(xiàn)描述如下。

2.1 種群初始化

在DisHHO中，由于個體（哈里斯鷹）表示為0-1向量，因此利用式（13）隨機產(chǎn)生DisHHO的初始種群P（0）中的N個個體Xi（0）=［xi1（0），xi2（0），…，xin（0）］∈{0，1}n，1≤i≤N。

其中：rand（0，1）表示（0，1）中的一個隨機數(shù)。

在產(chǎn)生Xi（0）（1≤i≤N）之后，計算它們的適應(yīng)度，由此確定當(dāng)前最好個體XB（0）。初始化獵物的初始逃逸能量E0∈（-1，1）。

2.2 逃逸能量E

DisHHO仍使用式（1）確定獵物的逃逸能量E，并根據(jù)E的取值決定當(dāng)前算法處于搜索階段還是開發(fā)階段，即當(dāng)|E|≥1時，DisHHO處于搜索階段；當(dāng)|E|lt;1時，DisHHO處于開發(fā)階段。

2.3 搜索階段

在搜索階段，DisHHO借助于（0，1）上的隨機實數(shù)r，基于兩種策略產(chǎn)生新個體Xi（t+1）=［xi1（t+1），xi2（t+1），…，xin（t+1）］∈{0，1}n（1≤i≤N）中的位置分量xij（t+1）（1≤j≤n），即當(dāng)rlt;0.5時，由當(dāng)前個體Xi（t）的位置分量xij（t）與在當(dāng)前種群中隨機選取的個體Xp1（t）的位置分量xp1j（t）進行按位與運算產(chǎn)生xij（t+1）；當(dāng)r≥0.5時，由種群中兩個隨機選取的個體Xp2（t）與Xp3（t）的位置分量xp2j（t）與xp3j（t）進行按位與運算產(chǎn)生xij（t+1）。此過程的進化方程表示為

容易看出，在利用式（14）產(chǎn)生xij（t+1）時，xij（t+1）=1的概率為25%，xij（t+1）=0的概率為75%，j=1，2，…，n。

2.4 開發(fā)階段

設(shè)E為獵物的逃逸能量，r為（0，1）上的一個隨機實數(shù)，XB（t）為P（t）中的最優(yōu)個體，則DisHHO在開發(fā)階段更新個體位置的四種機制分別為

a）軟包圍。當(dāng)r≥0.5，0.5lt;|E|≤1時，將當(dāng)前個體與種群中的一個隨機個體的位置分量進行按位異或運算，其進化方程為

b）硬包圍。當(dāng)r≥0.5，|E|lt;0.5時，將當(dāng)前個體與種群中的最優(yōu)個體的位置分量進行按位異或運算，此時的進化方程為

c）帶有快速俯沖的軟包圍。當(dāng)rlt;0.5，0.5lt;|E|≤1時，將當(dāng)前個體與種群中的隨機個體的位置分量進行按位或運算，進化方程為

d）帶有快速俯沖的硬包圍。當(dāng)rlt;0.5，|E|lt;0.5時，將當(dāng)前個體與種群中的最優(yōu)個體的位置分量進行按位或運算，此時的進化方程為

易知，按位或運算結(jié)果為1的概率為75%，為0的概率為25%；按位異或運算的結(jié)果為0或1的概率均為50%。所以，利用式（15）（16）確定xij（t+1）=1或0的概率均為50%，利用式（17）（18）確定xij（t+1）=1的概率為75%，xij（t+1）=0的概率為25%。因此，DisHHO在搜索階段和開發(fā)階段產(chǎn)生每一維分量xij（t+1）時，總體保持了1和0的平衡。

2.5 自適應(yīng)單向變異

HHO中的萊維飛行機制雖然適用于實數(shù)域上的計算，但是不能直接用于離散域；而且，其計算量較大，不利于算法的快速實現(xiàn)。為了彌補這一缺陷，在DisHHO中不再使用萊維飛行機制，取而代之的是一種自適應(yīng)單向變異操作（adaptive one-way mutation operation，AOMO），以便于改善DisHHO新產(chǎn)生的哈里斯鷹位置向量的質(zhì)量。

記flag為一個臨時變量，flag=0代表搜索階段，flag=1代表開發(fā)階段。Rand1與Rand2分別是（0，1）上的兩個隨機實數(shù)。Pm∈（0，1）是一個預(yù)設(shè)的閾值，稱之為自適應(yīng)單向變異概率。則AOMO的算法偽代碼描述如算法1所示。

算法1 AOMO

輸入：個體X=［x1，x2，…，xn］∈{0，1}n;參數(shù)Pm和flag。

輸出：對X自適應(yīng)單向變異后的結(jié)果。

1 if flag=0 then temp←0.3 else temp←0.7

2 if Rand1lt;temp

3 for i←1 to n do

4 if （xi=1 and Rand2lt;Pm） then xi←0

5 end for

6 end if

7 return X

由于搜索階段新產(chǎn)生個體的位置向量中的0較多，所以AOMO在搜索階段的單向變異程度不宜過高；而在開發(fā)階段，新產(chǎn)生個體的位置向量中的1較多，此時單向變異的程度應(yīng)適當(dāng)提高。不難看出，AOMO的時間復(fù)雜度為O（n）。

2.6 DisHHO的算法偽代碼

DisHHO首先利用式（13）產(chǎn)生初始種群P（0），確定最好個體XB（0），并隨機產(chǎn)生獵物的初始逃逸能量E0。在第t（t≥1）次迭代中，根據(jù)獵物逃逸能量E確定處于搜索階段或開發(fā)階段，當(dāng)|E|≥1時，DisHHO利用式（14）進行搜索，產(chǎn)生Xi（t+1）；當(dāng)|E|lt;1時，DisHHO利用式（14）～（18）進行搜索，產(chǎn)生Xi（t+1）。隨后，DisHHO利用自適應(yīng)單向變異操作提升Xi（t+1）的質(zhì)量，計算Xi（t+1）的適應(yīng)度，確定當(dāng)前最好個體XB（t+1）。至此，DisHHO完成第t次迭代進化。重復(fù)執(zhí)行上述迭代過程，直至滿足終止條件為止，輸出最好個體XB并結(jié)束算法。

設(shè)種群規(guī)模為N，迭代次數(shù)為T，自適應(yīng)單向變異概率為Pm，則DisHHO的算法偽代碼描述如算法2所示。

算法2 DisHHO

輸入：二元優(yōu)化問題max f（X），X∈{0，1}n的實例；參數(shù)N、T和Pm。

輸出：XB（T）∈{0，1}n和f（XB（T））。

1 利用式（13）產(chǎn)生N個個體構(gòu)成初始種群P（0），隨機產(chǎn)生E0；

2 計算P（0）中所有個體適應(yīng)度，確定最好個體XB（0）；

3 for t←0 to T-1 do

4 利用式（1）更新獵物逃逸能量E;

5 for i←1 to N do

6 if |E|≥1 then 利用式（14）產(chǎn)生Xi（t+1），并令flag←0;

7 else

8 if r≥0.5amp;|E|≥0.5 then 利用式（15）產(chǎn)生Xi（t+1）;

9 if r≥0.5amp;|E|lt;0.5 then 利用式（16）產(chǎn)生Xi（t+1）;

10 if rlt;0.5amp;|E|≥0.5 then 利用式（17）產(chǎn)生Xi（t+1）;

11 if rlt;0.5amp;|E|lt;0.5 then 利用式（18）產(chǎn)生Xi（t+1）;

12 令flag←1;

13 end if-else

14 對Xi（t+1）執(zhí)行AOMO，計算Xi（t+1）適應(yīng)度，確定XB（t+1）;

15 end for

18 end for

19 return （XB（T）， f（XB（T）））

在算法2中，行1的時間復(fù)雜度為O（N×n）；行2的時間復(fù)雜度為O（N×O（f）），O（f）是計算f（·）的復(fù)雜度；行3～18的時間復(fù)雜度為O（T×N×（n+O（f）））。因此DisHHO時間復(fù)雜度為O（N×n）+O（N×O（f））+O（T×N×（n+O（f）））=O（T×N×（n+O（f））），與HHO具有相同的時間復(fù)雜度。當(dāng)T、N和O（f）都是n的一次多項式時，O（T×N×（n+O（f）））=O（n³）。

3 利用DisHHO求解KPC

KPC^［15］的一般描述為：給定n個物品和一個基本容量為C的背包。物品j的價值和重量分別是pj和wj；背包的可變?nèi)萘渴且粋€連續(xù)變量S∈［l， u］，因此背包的實際容量為C-S。令c代表懲罰系數(shù)或者獎勵系數(shù)，則KPC的目標(biāo)是確定S的值使得選擇裝入背包中的物品重量之和在不超過背包實際容量的情況下，價值之和減去cS最大。

為了便于演化算法求解，賀毅朝等人^［19］基于降維思想建立了KPC的一個數(shù)學(xué)模型KPCM2。KPCM2的描述如下：

其中：X=［x1， x 2，…， xn］∈{0，1}n，xj=1表示將物品j裝入背包，否則不裝入；u和l分別為S的上、下界。可以看出，KPCM2模型中不再涉及單連續(xù)變量S，在求得0-1向量X后，單連續(xù)變量S由S=［∑nj=1xj－g（x）］/c確定。

在利用DisHHO基于模型KPCM2求解KPC時，個體X∈{0，1}n均為n維0-1向量，利用式（19）計算個體的適應(yīng)度。由此，產(chǎn)生一個不容忽視的問題：由于DisHHO的搜索階段與開發(fā)階段均具有隨機性，所產(chǎn)生的新個體不一定不滿足式（20）的約束，即新個體往往是非正常編碼個體，不能直接利用式（19）計算個體的適應(yīng)度。為了解決這一問題，本文利用文獻［19］提出的M2-GROA算法對所有新產(chǎn)生個體進行處理。

在M2-GROA中，當(dāng)輸入X∈{0，1}n是一個不可行解時，依次將價值密度小的物品從背包中取出，直到滿足式（20）為止；當(dāng)X是可行解時，按照價值密度由大到小依次檢查還沒有裝入背包的物品能否裝入，若能則裝入，否則檢查下一個物品。算法M2-GROA的偽代碼不再贅述，請參考文獻［19］。

4 實驗結(jié)果與分析

4.1 計算環(huán)境與實例

所有仿真計算在配置為AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz和16 GB RAM（15.9 GB可用）的筆記本電腦上進行。利用C語言編程，編譯環(huán)境為Visual C++ 6.0。使用Python在編譯環(huán)境JetBrains PyCharm下繪圖。

仿真計算使用的40個規(guī)模為100≤n≤1 000的KPC實例來自文獻［19］，它們分為不相關(guān)實例ukpc100～ukpc1000、弱相關(guān)實例wkpc100～wkpc1000、強相關(guān)實例skpc100～skpc1000與逆強相關(guān)實例ikpc100～ikpc1000四類。具體數(shù)據(jù)見https：//www.researchgate.net/publication/33592 9189_The_KPC_Instances。

4.2 參數(shù)Pm的取值

為了確定DisHHO中變異概率Pm的合理取值，下面利用DisHHO分別求解實例ukpc500、wkpc500、skpc500、ikpc500，Pm取值分別為0.25、0.3、0.35、0.4、0.45。在圖1～4中基于Kruskal-Wallis秩和檢驗^［24］給出了獨立計算這些實例20次所得結(jié)果的小提琴圖。根據(jù)小提琴圖的分布和概率密度可以看出：在求解實例wkpc500時，Pm取0.35和0.45時，實驗結(jié)果的最優(yōu)值更佳；在求解實例ukpc500和ikpc500時，Pm取值對于算法影響不大，大部分實驗結(jié)果為最優(yōu)值；在求解實例skpc500時，當(dāng)Pm在0.25～0.35上取值時，實驗結(jié)果更多的分布于最優(yōu)值附近。綜上可以得出結(jié)論，當(dāng)Pm=0.35時，DisHHO求解n=500實例時的平均性能最好。因此，在以下的計算中DisHHO總是設(shè)置Pm=0.35。

4.3 與其他二進制HHO的比較

為了說明基于位運算的DisHHO是HHO的一種有效的離散化實現(xiàn)，下面將其與BHHO-S1和QBHHO-Q4這兩種已有二進制HHO算法計算KPC實例的結(jié)果進行比較。三個算法均基于模型KPCM2求解KPC實例，均利用M2-GROA對潛在解進行修復(fù)優(yōu)化。在BHHO-S1和QBHHO-Q4中，哈里斯鷹的位置向量中每一維分量取值范圍為［LB，UB］，LB與UB均為實數(shù)。記N為種群規(guī)模，T為迭代次數(shù)，n為實例規(guī)模，DisHHO、BHHO-S1和QBHHO-Q4算法的參數(shù)取值如表1所示。

在求解KPC實例時，DisHHO、BHHO-S1和QBHHO-Q4均獨立計算每個實例20次，在表2～5中給出了它們的計算結(jié)果。其中，OPT是實例的最優(yōu)值，best為20次計算結(jié)果的最好值，mean為20次計算結(jié)果的平均值，std為標(biāo)準差，time（單位：s）是每個算法的平均耗費時間。此外，表2～5中的黑色加粗部分代表計算結(jié)果等于opt。

由表2～5可以看出，在best方面，DisHHO有35個實例的best等于opt，QBHHO-Q4僅有三個實例，而BHHO-S1不能求得opt。從mean來看，DisHHO有21個mean等于opt；QBHHO-Q4僅有兩個實例的mean等于opt；BHHO-S1沒有任何實例的mean等于opt。使用Friedman秩和檢驗^［25］對DisHHO、BHHO-S1和QBHHO-Q4求解四類實例所得的mean值進行比較，比較結(jié)果如圖5～8所示。從中不難看出，DisHHO求解KPC實例的結(jié)果明顯優(yōu)于BHHO-S1與QBHHO-Q4。

通過以上比較得出結(jié)論，DisHHO在求解KPC時明顯優(yōu)于QBHHO-Q4與BHHO-S1等已有的二進制HHO算法，說明基于位運算的DisHHO是HHO的一種有效的離散化實現(xiàn)。

4.4 與求解KPC的已有算法比較

為了說明DisHHO求解KPC的高效性能，在本節(jié)將其與 S-HBDE^［19］、ETDE^［20］和NBPSO^［21］進行比較。記N為種群規(guī)模，T為迭代次數(shù)，n為實例規(guī)模。由文獻［19～21］易知，當(dāng)T和N是n的一次多項式時，四個算法的時間復(fù)雜度均為O（n3）。在S-HBDE和ETDE中，F(xiàn)S是比例因子，CR是交叉概率，個體分量的取值范圍為［-A，A］，A是正實數(shù)；在NBPSO中，C1和C2是加速度常數(shù)，W是慣性權(quán)重，粒子速度分量的取值范圍為［-A，A］，A為正實數(shù)。四個算法的參數(shù)取值如表6所示。

在表7～10中列出了以上四個算法獨立計算每一個KPC實例20次的求解結(jié)果。其中，opt、best、mean、std與time的含義與4.3節(jié)中的定義相同，而且表中黑色加粗部分仍然表示計算結(jié)果等于opt。

由表7～10可以看出，在best方面，DisHHO、NBPSO和S-HBDE最好，均有半數(shù)以上實例的best達到opt。ETDE表現(xiàn)較差，僅能在10個實例上取得opt。從各算法的mean來看，DisHHO表現(xiàn)最好，40個實例中有21個mean達到opt。NBPSO次之，有19個實例的mean達到opt。S-HBDE表現(xiàn)較差，有9個mean達到最優(yōu)。ETDE表現(xiàn)最差，僅有1個實例的mean是最優(yōu)的。在圖9～12給出了DisHHO、NBPSO、ETDE和S-HBDE關(guān)于指標(biāo)mean的Friedman 秩和檢驗^［24］結(jié)果，從中可以看出DisHHO在四類實例上的表現(xiàn)均優(yōu)于其他算法。

4.5 計算速度比較

由于DisHHO、QBHHO-Q4與NBPSO在求解效果方面明顯優(yōu)于其他算法，所以在圖13～16僅對DisHHO、QBHHO-Q4與NBPSO的time指標(biāo)進行比較。其中，下標(biāo)i（1≤i≤10）代表問題規(guī)模為i×100。

由圖13～16的結(jié)果不難看出，DisHHO求解所有KPC實例的平均耗費時間遠比QBHHO-Q4與NBPSO的少，說明DisHHO的求解速度遠比QBHHO-Q4與NBPSO更快。

根據(jù)以上比較不難看出，DisHHO是一個比已有求解KPC的算法更優(yōu)的且更具有競爭力的新穎離散演化算法。

5 結(jié)束語

本文提出了一種基于位運算和自適應(yīng)單向變異的離散哈里斯鷹優(yōu)化算法DisHHO，該算法適用于求解各類二元優(yōu)化問題。為了驗證DisHHO求解KPC的性能，利用DisHHO對KPC四類大規(guī)模實例進行了求解，計算結(jié)果表明，DisHHO在求解速度、尋優(yōu)能力和魯棒性方面比已有算法均具有明顯的優(yōu)勢，因此是一個求解KPC的高效新方法。雖然位運算對HHO的離散化是成功的，但是對于其他演化算法（如鯨魚優(yōu)化算法^［25］和蟻群優(yōu)化^［26］）是否適用是一個值得今后研究的問題。此外，利用DisHHO求解其他組合優(yōu)化問題（如集合覆蓋）也是一個值得繼續(xù)探討的問題。

參考文獻：

[1]Adil B.Evolutionary computation for modeling and optimization［J］.The Computer Journal，2008，51（6）：743.

［2]Heidari A A，Mirjalili S，F(xiàn)aris H，et al.Harris hawks optimization：algorithm and applications［J］.Future Generation Computer Systems，2019，97（8）：849-872.

［3]Bui D T，Moayedi H，Kalantar B，et al.Harris hawks optimization：a novel swarm intelligence technique for spatial assessment of landslide susceptibility［J］.Sensors，2019，19（16）：3590.

［4]Houssein E H，Hosney M E，Oliva D，et al.A novel hybrid Harris hawks optimization and support vector machines for drug design and discovery［J］.Computers amp; Chemical Engineering，2020，133（2）：106656.

［5]Abbasi A，F(xiàn)irouzi B，Sendur P.On the application of Harris hawks optimization（HHO） algorithm to the design of microchannel heat sinks［J］.Engineering with Computers，2021，37（2）：1409-1428.

［6]Fan Qian，Chen Zhenjian，Xia Zhanghua.A novel quasi-reflected Harris hawks optimization algorithm for global optimization problems［J］.Soft Computing，2020，24：14825-14843.

［7]Hussain K，Zhu W，Salleh M N M.Long-term memory Harris’ hawk optimization for high dimensional and optimal power flow problems［J］.IEEE Access，2019，7：147596-147616.

［8]Gupta S，Deep K，Heidari A A，et al.Opposition-based learning Harris hawks optimization with advanced transition rules：principles and analy-sis［J］.Expert Systems with Applications，2020，158：113510.

［9]Jiao Shan，Chong Guoshuang，Huang Changcheng，et al.Orthogonally adapted Harris hawk optimization for parameter estimation of photovoltaic models［J］.Energy，2020，203：117804.

［10]Qu Chiwen，He Wei，Peng Xiangni，et al.Harris hawks optimization with information exchange［J］.Applied Mathematical Modelling，2020，84：52-75.

［11]Ewees A A，Elaziz M A.Performance analysis of chaotic multi-verse Harris hawks optimization：a case study on solving engineering pro-blems［J］.Engineering Applications of Artificial Intelligence，2020，88：103370.

［12]Li Chenyang，Li Jun，Chen Huiling，et al.Enhanced Harris hawks optimization with multi-strategy for global optimization tasks［J］.Expert Systems with Applications，2021，185：115499.

［13]Kamboj V K，Nandi A，Bhadoria A，et al.An intensify Harris hawks optimizer for numerical and engineering optimization problems［J］.Applied Soft Computing，2020，89：106018.

［14]Too J W，Abdullah A R，Saad N M.A new quadratic binary Harris hawk optimization for feature selection［J］.Electronics，2019，8（10）：1130.

［15]Marchand H，Wolsey L A.The 0-1 knapsack problem with a single continuous variable［J］.Mathematical Programming，1999，85：15-33.

［16]Kellerer H，Pferschy U，Pisinger D.Knapsack problems［M］ Berlin：Springer-Verlag，2004.

［17]Karp R M.Reducibility among combinatorial problems［M］//Miller R E，Thatcher J W，Bohlinger J D.Complexity of Computer Computations.Boston，MA：Springer，1972：85-103.

［18]王熙照，賀毅朝.求解背包問題的演化算法［J］.軟件學(xué)報，2017，28（1）：1-16.（Wang Xizhao，He Yichao.Evolutionary algorithms for knapsack problems［J］.Journal of Software，2017，28（1）：1-16.）

［19]賀毅朝，王熙照，張新祿，等.基于離散差分演化的KPC問題降維建模與求解［J］.計算機學(xué)報，2019，42（10）：2267-2280.（He Yichao，Wang Xizhao，Zhang Xinlu，et al.Modeling and solving by dimensionality reduction of KPC problem based on discrete differential evolution［J］.Chinese Journal of Computers，2019，42（10）：2267-2280.）

［20]He Yichao，Wang Jinghong，Zhang Xinlu，et al.Encoding transformation-based differential evolution algorithm for solving knapsack pro-blem with single continuous variable［J］.Swarm and Evolutionary Computation，2019，50：100507.

［21]王澤昆，賀毅朝，李煥哲，等.基于新穎S型轉(zhuǎn)換函數(shù)的二進制粒子群優(yōu)化算法求解具有單連續(xù)變量的背包問題［J］.計算機應(yīng)用，2021，41（2）：461-469.（Wang Zekun，He Yichao，Li Huanzhe，et al.Binary particle swarm optimization algorithm based on novel S-shape transfer function for knapsack problem with a single continuous variable［J］.Journal of Computer Applications，2021，41（2）：461-469.）

［22]He Yichao，Hao Xiang，Li Wenbin，et al.Binary team game algorithm based on modulo operation for knapsack problem with a single conti-nuous variable［J］.Applied Soft Computing，2021，103：107180.

［23]Jaeger R C，Blalock T N.Microelectronic circuit design［M］.New York：McGraw-Hill Education，1997.

［24]Derrac J，García S，Molina D，et al.A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms［J］.Swarm and Evolutionary Computation，2011，1（1）：3-18.

［25]Mirjalili S，Lewis A.The whale optimization algorithm［J］.Advances in Engineering Software，2016，95：51-67.

［26]Dorigo M，Birattari M，Stutzle T.Ant colony optimization［J］.IEEE Computational Intelligence Magazine，2006，1（4）：28-39.

［27]賀毅朝，張新祿，曲文龍，等.求解具有單連續(xù)變量背包問題的精確算法［J］.數(shù)學(xué)的實踐與認識，2018，48（13）：216-223.（He Yichao，Zhang Xinlu，Qu Wenlong，et al.Exact algorithm for solving knapsack problem with a single continuous variable［J］.Journal of Mathematics in Practice and Theory，2018，48（13）：216-223.）