基于二進制象群優(yōu)化算法求解0-1背包問題

張 潼，朱曉斌

(1. 河北地質(zhì)大學 信息工程學院，河北 石家莊 050031；2. 石家莊文化傳媒學校，河北 石家莊 050000)

0 引言

背包問題（Knapsack Problems，KPs）[1]是一類著名的NP-Complete問題，在決策投資、資源分配、預算控制、物流、材料學等領(lǐng)域[2-3]具有重要的理論與應(yīng)用價值。求解0-1KP的傳統(tǒng)方法是精確算法[4]，如分支定界法、動態(tài)規(guī)劃法、割平面法等。精確算法雖然可求得精確解，但它們的時間復雜度都是偽多項式時間的，隨著0-1KP問題規(guī)模的增大，求解效率迅速降低，不適于求解大規(guī)模0-1KP實例。演化算法作為一類特殊的隨機近似算法,既不需要計算目標函數(shù)的導數(shù)和梯度,也不要求目標函數(shù)具有連續(xù)性,而且具有內(nèi)在的隱含并行性和全局尋優(yōu)能力，已成求解 0-1KP問題的最重要方法[1]。

除了經(jīng)典的遺傳算法（Genetic algorithm，GA）[5]、粒子群優(yōu)化（Particle swarm optimization，PSO）[6]、差分演化（Differential evolution，DE）[7]等算法以外，近年來一系列新的演化算法被提出，如正弦余弦算法（Sine cosine algorithm，SCA）[8]、藤壺交配優(yōu)化（Barnacles mating optimizer，BMO）[9]、象群優(yōu)化算法（Elephant herding optimization，EHO）[10]等，已被用于求解工程管理、金融、醫(yī)藥、制造、化學等的優(yōu)化問題。

EHO是Wang等人[10]根據(jù)大象放牧行為，提出的一種新演化算法，用于求解連續(xù)優(yōu)化問題，有高效的全局搜索能力，較少的控制參數(shù)和結(jié)構(gòu)簡單易于實現(xiàn)的優(yōu)點。本文基于EHO提出一種針對 0-1KP設(shè)計的二進制象群優(yōu)化算法（Binary elephant herding optimization，BEHO），在 EHO基礎(chǔ)算法框架內(nèi)，利用傳遞函數(shù)將操作算子轉(zhuǎn)化為適合于離散問題的算法求解步驟，擴展EHO在組合優(yōu)化問題上的應(yīng)用，為大規(guī)模的0-1KP提供了高效簡潔的解決方案，并通過與6個算法的比較驗證了算法的有效性。

本文其余內(nèi)容組織如下：在第 1節(jié)中，給出了0-1KP的定義與數(shù)學模型，以及相關(guān)算法概述，介紹了原始象群優(yōu)化算法；在第2節(jié)中，介紹二進制象群優(yōu)化算法；在第 3節(jié)中，給出了利用BEHO求解0-1KP的具體方法；在第4節(jié)中，將BEHO與其他求解0-1KP的算法進行比較并分析結(jié)果；在第5節(jié)中，對本文進行總結(jié)。

1 相關(guān)工作

1.1 KP的定義與數(shù)學模型

X=(x1,x2,…,xn)π{0,1}n是 0-1KP 問題的一個潛在解，只有滿足約束條件時才是一個可行解。

1.2 相關(guān)算法概述

Peng等人[3]提出了采用二分變異和二分交叉的二元差分進化(DBDE)。 Hota等人[11]將具有自適應(yīng)參數(shù)控制的微分算子的概念推廣到量子范式中，提出了自適應(yīng)量子啟發(fā)的差分進化算法（AQDE）。Gong等人[12]研究了 DE如何適應(yīng)二進制編碼（BinDE），并在二進制水平上研究其行為。Chen等人[13]提出了一種二進制學習差分進化（BLDE）算法，該算法可以通過從最后一個種群中學習，來有效的定位全局最優(yōu)解。Kennedy[14]對離散二元變量運算的改進提出了新的二進制粒子群優(yōu)化（BPSO）算法，該算法中種群個體不是潛在的解決方案，而是代表概率。Bansal等人[15]提出了一種改進的二進制粒子群算法（MBPSO）并求解0-1KP問題，該算法引入了一種新的概率函數(shù)，保持了種群的多樣性。這些算法只在一定程度上解決了傳統(tǒng)算法的不足，仍存在一些問題，如粒子群的提出主要是針對連續(xù)空間優(yōu)化問題，其解決離散空間優(yōu)化問題優(yōu)勢不明顯；其他算法僅適用于小型實例的求解，對于大規(guī)模實例求解精度不夠且其求解時間較長。

1.3 象群優(yōu)化算法

象群優(yōu)化算法是一種基于群體行為的演化算法，該算法模擬象群的放牧行為。在模擬過程中主要遵循以下三條規(guī)則[10]：

規(guī)則 1：大象以族群的形式生活，由許多氏族組成。

規(guī)則 2：每個氏族有一個女性首領(lǐng)命名為女族長。

規(guī)則 3：雄性大象成年之后，離開自己所在氏族，獨自生活。

在大象的社會生活中，每個氏族中的大象根據(jù)女族長的位置來更新自己的位置，因此每個氏族之間沒有相互作用。根據(jù)規(guī)則 1和 2，這個過程被命名為更新算子。雄性大象離開氏族，他們的位置在搜索空間內(nèi)隨機生成。這個過程被命名為分離算子。

基于以上規(guī)則描述，下面給出更新和分離階段涉及到的數(shù)學公式：

1氏族更新階段，如下所示：

其中，Xcenter,ci表示ci氏族的平均位置，β是[0,1]內(nèi)生成的隨機數(shù)。Xcenter,ci被計算如下：

其中1≤d≤D，d是第d維，D為個體總的維度，nci是ci氏族中大象的個數(shù)，Xdcenter,ci是ci氏族中平均位置的第d維。

2分離階段：

Xmax和Xmin是搜索空間的上下界，rand是[0,1]內(nèi)生成的隨機數(shù)，Xworst,ci是ci氏族中適應(yīng)度最差的大象。

2 二進制象群優(yōu)化算法

在原始EHO算法中，大象個體的位置向量在每一次進化之后是實向量，然后利用適應(yīng)度函數(shù)對進化后的實向量進行計算，對可行解的優(yōu)劣進行評價。在本章，基于轉(zhuǎn)換函數(shù)V4（如公式（8）所示），我們給出二進制象群優(yōu)化算法（BEHO）。

V(yijt)表示利用V4將yijt轉(zhuǎn)換為0到1之間的一個實數(shù)。Pvπ(0,1)是一個預先設(shè)定的閾值，απ[0,1]，βπ[0,1]，γ是在[0,1]之間均勻分布的一個隨機值,rand是 [0,1]之間的隨機值。

令max f(X)，Xπ{0,1}n表示一個最大優(yōu)化問題。記B=[b1,b2,…,bn]π{0,1}n是種群P中最好個體對應(yīng)的解，MaxGen是算法BEHO的迭代次數(shù)。基于以上描述給出BEHO的偽代碼：

算法1 BEHO

輸入：一個max f(X)實例，參數(shù)Pv，nClan，c，n，α，βandMaxGen；

輸出：最好解B，最好值f(B)。

(1)隨機初始化種群P={Yij=[yij1,yij2,…,yijn]

(9)根據(jù)f(Xij)對種群P由小到大排序；

容易看出，當f(Xij)的計算時間復雜度為O(n)時，Step1的時間復雜度為O(N*n)，Step2～8的時間復雜度為N*O(n)，Step9的時間復雜度為O(NlgN)，Step10～34的時間復雜度為MaxGen*((N+nClan)*O(n))，所以BEHO的時間復雜度為O(N*n)+N*O(n)+O(NlgN)+MaxGen*((N+nClan)*O(n))。

3 利用BEHO求解0-1KP

3.1 個體編碼與適應(yīng)度計算

在BEHO中，個體編碼為Yij=[yij1,yij2,…,yijn]π[-A,A]n，對Yij利用轉(zhuǎn)換函數(shù)轉(zhuǎn)換為Xij= [xij1,xij2,…,xijn]∈{0,1}n，xij1=1表示物品放入背包，反之，沒有放入背包。然后，利用 3.2節(jié)提到的修復優(yōu)化方法將Xij轉(zhuǎn)換為可行解。

令max f(Xij)表示求解0-1KP的目標函數(shù)，用來計算個體的適應(yīng)度評判個體的優(yōu)劣。0-1KP是一個最大優(yōu)化問題，所以求得f(Xij)越大，解的質(zhì)量越高。

3.2 不可行解的解決方法

由于0-1KP是約束優(yōu)化問題，利用BEHO求解0-1KP時會不可避免地產(chǎn)生不可行解，這會導致不能直接使用目標函數(shù)值評判個體適應(yīng)度的好壞。因此我們要找到合適的方法處理不可行解。目前處理不可行解一般有兩種方法：罰函數(shù)法、修復法和修復與優(yōu)化操作。本文采用了文獻[1]提出的貪心修復優(yōu)化方法（GROA）來處理不可行解。

3.3 算法流程圖

利用BEHO求解0-1KP的步驟如下：將物品集中的n個物品的下標按照價值密度比pj/wj由大到小依次存入數(shù)組H[1…n]中，即H滿足pH[1]/wH[1]≥pH[2]/wH[2]≥,…,≥pH[n]/wH[n]，然后，隨機初始化種群，利用轉(zhuǎn)換函數(shù)將個體實向量轉(zhuǎn)化為0-1向量，利用GROA對種群中所有個體進行修復優(yōu)化，并對種群進行排序。然后，重復以下過程直到滿足終止條件：更新個體位置，利用轉(zhuǎn)換函數(shù)將個體實向量轉(zhuǎn)化為 0-1向量，對個體進行修復優(yōu)化；找到適應(yīng)度最差的個體，隨機更新其位置，將其實向量轉(zhuǎn)化為0-1向量，對其進行修復優(yōu)化，對種群進行排序。最后，輸出0-1KP的最優(yōu)解B和最優(yōu)值f(B)。BEHO求解0-1KP的流程圖如圖1所示。

圖1 算法BEHO求解0-1KP的流程圖Fig.1 Flow chart of algorithm BEHO for 0-1KP

4 計算結(jié)果與分析

本文所有計算在配置為 Intel Core(TM)i7-3770 CPU @ 3.40 GHzhe 8GB RAM的微型計算機上進行，操作系統(tǒng)為Microsoft Windows10。利用C語言進行編程，編譯環(huán)境為Code:Blocks。利用Python在編譯環(huán)境JetBrains PyCharm下繪制盒圖。

4.1 0-1KP實例與算法參數(shù)

實例可從https://github.com/whuph/KP_data獲取，該實例根據(jù)物品價值和重量的相關(guān)性又可分為四類，1）不相關(guān)實例；2）弱相關(guān)實例；3）強相關(guān)實例；4）子集和實例。為驗證 BEHO的性能，利用上述實例對BEHO、DBDE[3]、AQDE[11]、BinDE[12]、BLDE[13]、BPSO[14]和 MBPSP[15]進行比較。為了使算法BEHO求解0-1KP實例的性能達到最佳，本文利用 Kruskal-Wallis秩和檢驗[16]確定BEHO中參數(shù)Pv、α和β的合理取值。選取20個 0-1KP實例中 2個代表實例 kp_uc_500和kp_wc_1000。下面以Pv為例，分別設(shè)置Pv=0.1，0.2，0.3，0.4，0.5，對每個實例在Pv取5個不同值時獨立計算50次，并對50次計算結(jié)果進行分析。在利用BEHO求解0-1KP實例的仿真試驗中，種群大小均設(shè)N=25，迭代次數(shù)MaxGen=100，α=0.5，β=0.1。

表1中列出了Kruskal-Wallis檢驗的結(jié)果，指標Res表示Pv取值對計算結(jié)果的影響情況，其中的“Y”表示Pv取值對計算結(jié)果有影響，“NAN”表示Pv取值對計算結(jié)果沒有影響；當P≥0.05時表示Pv取值對實驗結(jié)果影響較小，否則表示Pv取值對實驗結(jié)果影響較大。求解實例的 Kruskal-Wallis秩和檢驗對應(yīng)的盒圖見圖2，其中橫坐標表示參數(shù)Pv的 5種不同取值，縱坐標表示 BEHO求得的最好值。

表1 Kruskal-Wallis檢驗結(jié)果Tab.1 Kruskal-Wallis test results

從表1可以看出，Pv的取值對求解結(jié)果影響較大，從圖2可以看出當Pv取0.2時，計算結(jié)果更穩(wěn)定。類似上述測試Pv的方法測試α和β，可根據(jù)秩和檢驗結(jié)果確定當Pv=0.2，α=0.5,β=0.1時BEHO的求解性能最佳。其他6個算法的參數(shù)設(shè)置詳見相關(guān)文獻。

圖2 代表實例的盒圖Fig.2 Box graphs representing instances

4.2 BEHO與其他算法的比較

本節(jié)中，分別對BEHO與其他6個算法求解0-1KP的計算結(jié)果進行比較和分析。在表2中給出各算法的求解結(jié)果，其中Best是50次計算結(jié)果的最好值；Time是各算法求解每個實例的平均出各算法的求解結(jié)果，其中Best是 50次計算結(jié)?時間（單位是秒）；其中表現(xiàn)最好的算法利用加粗標示，能夠求得最優(yōu)值的用*標示。

表2 BEHO和其他算法求解實例的實驗結(jié)果Tab.2 The Results of BEHO and other algorithms for solving the cases

續(xù)表

表2給出了BEHO與6個不同算法求解規(guī)模分別為100、200、300、500和1 000的四類不同實例的最好值和求解問題需要的時間，其中0-1KP實例統(tǒng)一表示為“kp_aa_$$$”， “$$$”表示實例的規(guī)模。當aa=“sc”時，表示一個強相關(guān)實例，當aa=“ss”時，表示一個子集和實例，當 aa=“wc”時，表示一個弱相關(guān)實例，當 aa=“uc”時，表示一個不相關(guān)實例。例如，kp_sc_100表示它是一個規(guī)模為100的強相關(guān)實例。

從表2可以看出：對于20個實例，BEHO可以 100%求得最優(yōu)值，DBDE可以 75%求得最優(yōu)值，BPSO可以 50%求得最優(yōu)值，MBPSO可以40%求得最優(yōu)值，AQDE可以 35%求的最優(yōu)值，BLDE可以30%求得最優(yōu)值，BinDE計算結(jié)果最差，只能25%求得最優(yōu)值。

從求解20個實例的平均時間上來看，BEHO速度最快，僅需0.1412s, 其次，DBDE需20.97s，BinDE需 18.19s，BLDE需 53.86s，MBPSO 需61.29s，BPSO需 63.014s，AQDE速度最慢，平均需要65.624s。

從上述計算結(jié)果的比較可以看出：BEHO不僅求解0-1KP的結(jié)果好，而且速度快，因此BEHO比其他6個算法有更強的競爭力。

5 總結(jié)與展望

本文基于V型傳遞函數(shù)提出了一種二進制象群優(yōu)化算法 BEHO，并結(jié)合修復與優(yōu)化法提出了求解0-1KP的新方法。為驗證BEHO求解0-1KP的性能，對20個大規(guī)模0-1KP實例，與6個求解0-1KP的已有算法的計算結(jié)果進行比較，比較結(jié)果表明BEHO不僅在求解結(jié)果上有更好的效果，而且在求解速度上明顯具有較大的優(yōu)勢，因此，利用BEHO求解0-1KP不僅是可行的，而且是高效的。

由于EHO的提出時間較晚，利用它求解組合優(yōu)化問題的研究還相對較少。為此，我們今后將繼續(xù)探討EHO的離散化方法，以及利用離散EHO求解集合覆蓋問題、可滿足性問題和設(shè)施選址問題等其他組合優(yōu)化問題的可行性與有效性。