混合猴群算法求解折扣｛0-1｝背包問(wèn)題?

肖 顏 潘大志，2 馮世強(qiáng)

（1.西華師范大學(xué)數(shù)學(xué)與信息學(xué)院 南充 637009）（2.西華師范大學(xué)計(jì)算方法與應(yīng)用研究所 南充 637009）

1 引言

背包問(wèn)題（Knapsack Problem，KP）［1］是組合優(yōu)化問(wèn)題中一種典型的優(yōu)化難題，在整數(shù)規(guī)劃領(lǐng)域、資源調(diào)度問(wèn)題、材料切割問(wèn)題等有著非常重要的理論意義和廣泛的應(yīng)用價(jià)值。背包問(wèn)題的擴(kuò)展形式有很多，折扣｛0-1｝背包問(wèn)題（Discount｛0-1｝Knap?sack Problem，D｛0-1｝KP）［2～7］就是其中的一種，在超市促銷活動(dòng)、項(xiàng)目決策投資和預(yù)算控制等方面具有廣闊應(yīng)用［5～6］。2005 年Guder 最早提出了單目標(biāo)D｛0-1｝KP 問(wèn)題［2］；2007 年Guldan 在單目標(biāo)折扣背包問(wèn)題的基礎(chǔ)上提出了一種多目標(biāo)D｛0-1｝KP 問(wèn)題［4］，并利用動(dòng)態(tài)規(guī)劃進(jìn)行求解；Rong［8］等針對(duì)D｛0-1｝KP問(wèn)題，提出了一種基于核問(wèn)題動(dòng)態(tài)規(guī)劃的求解算法；Aiying Rong 等結(jié)合動(dòng)態(tài)規(guī)劃對(duì)D｛0-1｝KP 的核（coer）問(wèn)題進(jìn)行研究［5］；He 等［7］針對(duì)D｛0-1｝KP 問(wèn)題提出了幾種不同的算法進(jìn)行求解，如：精確算法、近似算法和二進(jìn)制粒子群算法等，賀毅朝等［6］利用精英保留策略對(duì)D｛0-1｝KP 進(jìn)行求解，同時(shí)提出了第一遺傳算法（FirEGA）和第二遺傳算法（SecEGA）；劉雪靜等［9］為求解D｛0-1｝KP，提出了兩種該背包問(wèn)題的數(shù)學(xué)模型，并利用細(xì)菌覓食的方法進(jìn)行求解；楊洋等［10］通過(guò)對(duì)D｛0-1｝KP 建立簡(jiǎn)化新模型，并給出求解算法。

猴群算法（MA）［11］主要是通過(guò)模擬自然界猴子爬山過(guò)程設(shè)計(jì)的，由Zhao 和Tang 于2008 年首次提出。該算法是一種新興的群智能優(yōu)化算法，可用于求解大規(guī)模、多維多峰優(yōu)化問(wèn)題，其突出優(yōu)點(diǎn)在于能夠有效的求解多種優(yōu)化問(wèn)題，如：線性問(wèn)題、非線性問(wèn)題、非凸問(wèn)題、高維問(wèn)題等，同時(shí)不需要考慮函數(shù)是否存在可微或可導(dǎo)現(xiàn)象，只需通過(guò)對(duì)當(dāng)前位置的偽梯度的計(jì)算，利用兩個(gè)臨近的位置即可確定猴子在爬過(guò)程中需要搜索的方向。MA的另一個(gè)優(yōu)點(diǎn)就是其結(jié)構(gòu)簡(jiǎn)單，參數(shù)少，因而在許多領(lǐng)域得到了廣大研究者的關(guān)注。目前，該算法在加氣站項(xiàng)目進(jìn)度問(wèn)題［12］、入侵檢測(cè)技術(shù)領(lǐng)域［13］、多目標(biāo)混合動(dòng)力優(yōu)化問(wèn)題［14］、模糊規(guī)則分類器［15］、云計(jì)算資源分配問(wèn)題［16］、輸電網(wǎng)擴(kuò)展規(guī)劃問(wèn)題［17］等領(lǐng)域也被廣泛應(yīng)用。研究期間，發(fā)現(xiàn)MA 雖然能夠在某種程度上解決一些問(wèn)題，但是在計(jì)算的過(guò)程中容易陷入局部最優(yōu)，從而導(dǎo)致算法的求解精度不高，因此為提高M(jìn)A的求解質(zhì)量就需要進(jìn)一步進(jìn)行研究。本文為能夠充分利用猴群算法的優(yōu)化性能和提高算法的尋優(yōu)能力，提出了一種混合猴群算法（MMA），即將貪心核加速算子與猴群算法進(jìn)行結(jié)合，并在猴群算法的爬過(guò)程中引入誘導(dǎo)因子，將其應(yīng)用到D｛0-1｝KP 的求解中。最后，利用該算法對(duì)四類大規(guī)模的D｛0-1｝KP 實(shí)例進(jìn)行求解，通過(guò)對(duì)計(jì)算結(jié)果進(jìn)行分析，表明本文提出的MMA是有效的。

2 D｛0-1｝KP的數(shù)學(xué)模型

D｛0-1｝KP 可簡(jiǎn)單描述為給定n 個(gè)項(xiàng)集，其中每個(gè)項(xiàng)集均含有3 個(gè)物品。從n 個(gè)項(xiàng)集中任取一個(gè)項(xiàng)集j(0 ≤j ≤n-1)，所包含的三個(gè)物品的下標(biāo)編號(hào)可分別記為3i,3i+1 和3i+2，前兩個(gè)物品對(duì)應(yīng)的價(jià)值系數(shù)和重量系數(shù)分別為p3i,p3i+1和w3i,w3i+1，物品3i+2 則看作是前兩項(xiàng)物品的一個(gè)組合，其價(jià)值系數(shù)為p3i+2=p3i+p3i+1，重量系數(shù)滿足w3i+2＜w3i+w3i+1，且w3i+2＞w3i，w3i+2＞w3i+1。對(duì)于任意一個(gè)項(xiàng)集，至多有一個(gè)物品被裝入載重為C的背包中。D｛0-1｝KP問(wèn)題是指在不超過(guò)背包載重C 的容量前提下，如何選擇項(xiàng)集中的物品，才能使得這些物品的價(jià)值系數(shù)之和盡可能達(dá)到最大。

假定D｛0-1｝KP 的規(guī)模總數(shù)為3n ，一個(gè)D｛0-1｝KP 實(shí)例由三部分構(gòu)成，即：物品價(jià)值系數(shù)集P={(p3i,p3i+1,p3i+2)|0 ≤i ≤n-1}，物品重量系數(shù)集W={(w3i,w3i+1,w3i+2)|0 ≤i ≤n-1}，背包最大載重量C(C ≥0)，且滿足具體描述如下：

其中：決策變量xj(0 ≤j ≤3n-1)為二進(jìn)制向量，表示第j 個(gè)項(xiàng)集的物品是否被選入背包C 中。若xj=0，則表示項(xiàng)j 沒(méi)有被選入；若xj=1，表示項(xiàng)j被選入。顯然，任意的二進(jìn)制向量X=[x0,x1,…,x3n-1]∈{0,1}3n表示D｛0-1｝KP 的一個(gè)潛在解，當(dāng)它滿足式（2）時(shí)，X 就是一個(gè)可行解。

3 基本猴群算法

基本猴群算法（MA）的思想主要是模仿猴子爬山過(guò)程，即爬、望-跳和翻幾個(gè)有特點(diǎn)的動(dòng)作，從而設(shè)計(jì)出相應(yīng)的搜索過(guò)程。算法步驟主要為解的表示、初始化、爬過(guò)程、望過(guò)程和跳過(guò)程，各過(guò)程的具體步驟參見(jiàn)文獻(xiàn)［11］。

4 求解D｛0-1｝KP 問(wèn)題的混合猴群算法（MMA）

針對(duì)猴群算法（MA）求解D｛0-1｝KP 等離散型問(wèn)題，需要利用混合編碼方式進(jìn)行求解，本文主要采用概率映射的方法將連續(xù)型轉(zhuǎn)化為離散型的二進(jìn)制進(jìn)行求解。為了能更好地解決大規(guī)模D｛0-1｝KP問(wèn)題，在猴群算法的基礎(chǔ)上，先對(duì)折扣背包問(wèn)題進(jìn)行貪心核加速預(yù)處理，對(duì)背包進(jìn)行部分填充，再利用猴群算法對(duì)剩余背包容量進(jìn)行填充，以獲得最終的填充方案。為提高算法的求解質(zhì)量，在猴群算法的爬過(guò)程中引入誘導(dǎo)因子改進(jìn)算法。實(shí)施步驟具體如下。

Step1.物品預(yù)處理：針對(duì)D｛0-1｝KP 問(wèn)題的實(shí)例，按照價(jià)值密度由高到低進(jìn)行排序，利用貪心核加速算子對(duì)背包進(jìn)行部分裝填。

貪心核加速預(yù)處理方法：1）對(duì)給定物品按照價(jià)值密度進(jìn)行降序排列；2）選取合適的核半徑值；3）將核半徑范圍之內(nèi)的物品放入背包。

Step2.種群初始化：針對(duì)背包的剩余容量，隨機(jī)生成一個(gè)二進(jìn)制向量Xi=(xi1,…,xij,…,xiD)(1 ≤i ≤M,1 ≤j ≤D)作為種群中每只猴子的初始位置，再利用編碼修復(fù)策略對(duì)非正常編碼進(jìn)行處理，其中M 表示猴群（種群）規(guī)模，D 表示猴群所在位置的空間維度。

Step3.執(zhí)行爬過(guò)程：通過(guò)偽梯度計(jì)算出新的向量 Yi=(yi1,…,yij,…,yiD) ，其 中Yi=Xi+α ?sign由于這里產(chǎn)生的Yi是實(shí)數(shù)向量，而D｛0-1｝KP 是離散域上的問(wèn)題，產(chǎn)生的解是由{0,1}構(gòu)成的二進(jìn)制向量，為解決這一問(wèn)題，本文利用Sigmoid 函數(shù)將Yi映射成離散的二進(jìn)制向量，滿足式（7）：

則Yi=(yi1,…,yij,…,yiD) 為映射后的由二進(jìn)制數(shù){0,1}構(gòu)成的一個(gè)解；若f(Yi)＞f(Xi)，則更新第i 只猴子當(dāng)前的位置，即Xi=Yi，直到達(dá)到預(yù)定的執(zhí)行次數(shù)Nc。為了能夠優(yōu)先選出單位體積內(nèi)價(jià)值較高的物品裝入背包，這里引入誘導(dǎo)因子進(jìn)行優(yōu)選并裝填。具體操作過(guò)程如下：

3）設(shè)iterg為 誘 導(dǎo) 次 數(shù)，t1,t2∈{1,2,…,D}（t1,t2為隨機(jī)選取的兩個(gè)值），若mt1＞mt2且yit1≠yit2，則更新猴子當(dāng)前位置，使得，否則，。通過(guò)計(jì)算當(dāng)前位置的目標(biāo)函數(shù)，若更新之后的目標(biāo)函數(shù)更優(yōu)，則第i 只猴子的位置更新為當(dāng)前猴子位置，直到達(dá)到誘導(dǎo)次數(shù)iterg。

Step4.執(zhí)行望過(guò)程：在視野范圍內(nèi)生成新的二進(jìn)制向量Yi=(yi1,…,yij,…,yiD) ，其中Yi∈(xij-b,xij+b)，計(jì)算f(Yi)，若滿足f(Yi)＞f(Xi)，則更新第i只猴子當(dāng)前位置，使得Yi=Xi。

Step5.執(zhí)行跳過(guò)程：通過(guò)計(jì)算yij=xij+θ(pj-xij)產(chǎn)生新的二進(jìn)制向量Yi=(yi1,…,yij,…,yiD)，計(jì)算f(Yi)，若滿足f(Yi)＞f(Xi)，則Xi←Yi。

Step6.利用貪心策略往背包中繼續(xù)添加物品，并計(jì)算目標(biāo)函數(shù)值。

Step7.通過(guò)對(duì)目標(biāo)函數(shù)值的比較，保留其中更優(yōu)者作為全局最優(yōu)解。

Step8.重復(fù)Step3～Step7，直到達(dá)到預(yù)定的最大迭代次數(shù)Nc_max，算法結(jié)束，輸出最優(yōu)個(gè)體和最優(yōu)解。

其程序框圖見(jiàn)圖1。

圖1 MMA流程圖

5 仿真實(shí)驗(yàn)結(jié)果分析

5.1 四類D｛0-1｝KP實(shí)例及實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)中所用的計(jì)算機(jī)硬件配置為Inter（R）Xeon（R）Silver 4114 CPU @ 2.20GHz 2.19GHz（2 個(gè)處理器），32.0GB 內(nèi)存（31.7GB 可用），操作系統(tǒng)為Microsoft Windows 10，利用Matlab R2018a 對(duì)問(wèn)題進(jìn)行求解并繪圖。

為了進(jìn)一步比較混合猴群算法（MMA）的求解性能，本小節(jié)中主要采用文獻(xiàn)［10］所提出的四類D｛0-1｝KP 實(shí)例數(shù)據(jù)：UDKP，WDKP，SDKP 和IDKP，每一類實(shí)例均包含10 個(gè)實(shí)例（UDKP1～UDKP10，WDKP1～WDKP10，SDKP1～SDKP10 和IDKP1～I(xiàn)D?KP10），實(shí)例規(guī)模3n ∈{3 00,600,900,…,3000} ，分別記為不相關(guān)D｛0-1｝KP 實(shí)例（Uncorrelated in?stance of D｛0-1｝KP，UDKP）、弱相關(guān)D｛0-1｝KP 實(shí)例（Weakly correlated instances of D｛0-1｝KP，WD?KP）、強(qiáng)相關(guān)D｛0-1｝KP 實(shí)例（Strongly correlated in?stances of D｛0-1｝KP，SDKP）、逆向強(qiáng)相關(guān)D｛0-1｝KP 實(shí) 例（Inverse Strongly correlated instance of D｛0-1｝KP，IDKP），其具體數(shù)據(jù)請(qǐng)參考文獻(xiàn)［5，20］。

5.2 混合猴群算法（MMA）對(duì)實(shí)例的計(jì)算與比較分析

在利用混合猴群算法（MMA）求解四類D｛0-1｝KP 實(shí)例中，相關(guān)參數(shù)設(shè)置如下：種群規(guī)模M=30，最大迭代次數(shù)Nc_max=100 ，爬過(guò)程的步長(zhǎng)a=1，爬的迭代次數(shù)Nc=20 ，誘導(dǎo)的次數(shù)iterg=5，視野長(zhǎng)度b=0.5，望過(guò)程的迭代次數(shù)Nw=3，跳區(qū)間[c,d]=[-1,1]，常量β=1.2。每個(gè)實(shí)例利用MMA 分別獨(dú)立運(yùn)行30 次并計(jì)算，所得結(jié)果見(jiàn)表1～4。其中以文獻(xiàn)［3］中動(dòng)態(tài)規(guī)劃求解四類D｛0-1｝KP問(wèn)題的結(jié)果作為精確解，同時(shí)與第二遺傳算法（Se?cEGA）［18］、第二細(xì)菌覓食算法（SecBFO）［9］、差分烏鴉算法（DECSA）［19］、差分帝王蝶優(yōu)化算法（DEM?BO）［21］、變異蝙蝠算法（MDBBA）［18］等算法求解結(jié)果進(jìn)行比較。由于文獻(xiàn)［19］中只計(jì)算了UDKP、WDKP、SDKP 三種實(shí)例，所以本文針對(duì)DEMBO 也只分析這三種實(shí)例情況。表中Opt、Best、Mean、Worse、Best/ Opt 分別表示各算法所得結(jié)果的最好值、平均值、最差值以及最好近似比。

表1 六種算法求解UDKP1-10實(shí)例的結(jié)果比較

表2 六種算法求解WDKP1-10實(shí)例的結(jié)果比較

表3 六種算法求解SDKP1-10實(shí)例的結(jié)果比較

表4 六種算法求解IDKP1-10實(shí)例的結(jié)果比較

為更直觀地分析各種算法的求解精度與求解性能，利用表1～4 所給結(jié)果將六種算法分別求解四類D｛0-1｝KP 問(wèn)題所得的最優(yōu)值與精確解作比值繪制出折線圖，如圖2～5所示。

從表1 和圖2 中可以發(fā)現(xiàn)，MMA 算法求解UD?KP1 和UDKP2 兩組數(shù)據(jù)精度較好，但求解UD?KP3-UDKP10 八組數(shù)據(jù)時(shí)效果較差。這表明MMA在對(duì)UDKP 進(jìn)行計(jì)算時(shí)，隨著背包容量的增加，其計(jì)算結(jié)果并不理想。

從表2 和圖3 中可以看出，MMA 在求解WDKP實(shí)例時(shí)，表現(xiàn)出了更好的計(jì)算結(jié)果，該算法的穩(wěn)定性優(yōu)于其他五種算法。此外，MMA 算法的最優(yōu)比值高達(dá)了0.9982，與其他五種算法相比，MMA 的求解性能更優(yōu)，所求得的結(jié)果也較為穩(wěn)定。

從表3 所給的數(shù)據(jù)和圖4 可以看出，MMA 算法求解SDKP 所得的Best/Opt 值比較穩(wěn)定，雖然SD?KP5與SDKP7這兩組數(shù)據(jù)結(jié)果不太理想，但整體穩(wěn)定性不錯(cuò)，其中SDKP1 結(jié)果最好，Best/Opt 的值達(dá)到了0.9968。

從表4 和圖5 中可以看出，MMA 算法求解ID?KP 實(shí)例所得結(jié)果是最好的，幾乎每組數(shù)據(jù)都接近精確解，其穩(wěn)定性也是最好的，Best/Opt的值幾乎全為1。可見(jiàn)對(duì)于IDKP 實(shí)例而言，MMA 的求解效果極佳。

圖2 UDKP實(shí)例Best/Opt

圖3 WDKP實(shí)例Best/Opt

圖4 UDKP實(shí)例Best/Opt

圖5 IDKP實(shí)例Best/Opt

基于以上數(shù)據(jù)及圖像比較分析可以得出以下結(jié)論。

對(duì)大范圍類隨機(jī)產(chǎn)生的四類D｛0-1｝KP 實(shí)例進(jìn)行計(jì)算時(shí)，除了UDKP 實(shí)例外，MMA 算法均能較好的計(jì)算出近似解，所得的最優(yōu)解與精確解的比值更能接近于1。可以看出MMA 算法對(duì)于求解大規(guī)模D｛0-1｝KP問(wèn)題比較適用，但對(duì)UDKP實(shí)例而言，其實(shí)用性較差。通過(guò)對(duì)WDKP、SDKP、IDKP 實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，混合猴群算法能有效求解出較好的結(jié)果。

6 結(jié)語(yǔ)

在利用MA 求解折扣｛0-1｝背包問(wèn)題時(shí)，因D｛0-1｝KP 規(guī)模較大，導(dǎo)致算法的計(jì)算速度極慢，本文主要利用混合猴群算法（MMA）求解該問(wèn)題。通過(guò)引入貪心核加速算子來(lái)減少背包的填充，以降低計(jì)算時(shí)長(zhǎng)；同時(shí)引入誘導(dǎo)因子，避免算法陷入局部最優(yōu)，從而提高算法的局部搜索能力。通過(guò)引入貪心核加速算子、誘導(dǎo)因子等，使得MA 更能有效地求解大規(guī)模的D｛0-1｝KP 問(wèn)題，通過(guò)對(duì)比其他六種算法的求解精度，MMA表現(xiàn)出較優(yōu)的結(jié)果。

由于MA 對(duì)于離散型的問(wèn)題研究較少，該算法在爬的過(guò)程中涉及偽梯度問(wèn)題，步長(zhǎng)的設(shè)定會(huì)影響到偽梯度的計(jì)算，所以如何針對(duì)這一問(wèn)題提出一個(gè)更有效的設(shè)計(jì)，是一個(gè)值得研究的問(wèn)題。