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

張 潼，朱曉斌

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

0 引言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2分離階段：

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

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

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

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

令max f(X)，Xπ{0,1}n表示一個(gè)最大優(yōu)化問(wèn)題。記B=[b1,b2,…,bn]π{0,1}n是種群P中最好個(gè)體對(duì)應(yīng)的解，MaxGen是算法BEHO的迭代次數(shù)?；谝陨厦枋鼋o出BEHO的偽代碼：

算法1 BEHO

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

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

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

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

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

3 利用BEHO求解0-1KP

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

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

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

3.2 不可行解的解決方法

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

3.3 算法流程圖

利用BEHO求解0-1KP的步驟如下：將物品集中的n個(gè)物品的下標(biāo)按照價(jià)值密度比pj/wj由大到小依次存入數(shù)組H[1…n]中，即H滿足pH[1]/wH[1]≥pH[2]/wH[2]≥,…,≥pH[n]/wH[n]，然后，隨機(jī)初始化種群，利用轉(zhuǎn)換函數(shù)將個(gè)體實(shí)向量轉(zhuǎn)化為0-1向量，利用GROA對(duì)種群中所有個(gè)體進(jìn)行修復(fù)優(yōu)化，并對(duì)種群進(jìn)行排序。然后，重復(fù)以下過(guò)程直到滿足終止條件：更新個(gè)體位置，利用轉(zhuǎn)換函數(shù)將個(gè)體實(shí)向量轉(zhuǎn)化為 0-1向量，對(duì)個(gè)體進(jìn)行修復(fù)優(yōu)化；找到適應(yīng)度最差的個(gè)體，隨機(jī)更新其位置，將其實(shí)向量轉(zhuǎn)化為0-1向量，對(duì)其進(jìn)行修復(fù)優(yōu)化，對(duì)種群進(jìn)行排序。最后，輸出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 計(jì)算結(jié)果與分析

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

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

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

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

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

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

圖2 代表實(shí)例的盒圖Fig.2 Box graphs representing instances

4.2 BEHO與其他算法的比較

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

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

續(xù)表

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

從表2可以看出：對(duì)于20個(gè)實(shí)例，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計(jì)算結(jié)果最差，只能25%求得最優(yōu)值。

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

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

5 總結(jié)與展望

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

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