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

肖 顏 潘大志，2 馮世強

（1.西華師范大學數學與信息學院 南充 637009）（2.西華師范大學計算方法與應用研究所 南充 637009）

1 引言

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

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

2 D｛0-1｝KP的數學模型

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

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

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

3 基本猴群算法

基本猴群算法（MA）的思想主要是模仿猴子爬山過程，即爬、望-跳和翻幾個有特點的動作，從而設計出相應的搜索過程。算法步驟主要為解的表示、初始化、爬過程、望過程和跳過程，各過程的具體步驟參見文獻［11］。

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

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

Step1.物品預處理：針對D｛0-1｝KP 問題的實例，按照價值密度由高到低進行排序，利用貪心核加速算子對背包進行部分裝填。

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

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

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

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

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

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

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

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

Step7.通過對目標函數值的比較，保留其中更優(yōu)者作為全局最優(yōu)解。

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

其程序框圖見圖1。

圖1 MMA流程圖

5 仿真實驗結果分析

5.1 四類D｛0-1｝KP實例及實驗設置

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

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

5.2 混合猴群算法（MMA）對實例的計算與比較分析

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

表1 六種算法求解UDKP1-10實例的結果比較

表2 六種算法求解WDKP1-10實例的結果比較

表3 六種算法求解SDKP1-10實例的結果比較

表4 六種算法求解IDKP1-10實例的結果比較

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

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

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

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

從表4 和圖5 中可以看出，MMA 算法求解ID?KP 實例所得結果是最好的，幾乎每組數據都接近精確解，其穩(wěn)定性也是最好的，Best/Opt的值幾乎全為1?？梢妼τ贗DKP 實例而言，MMA 的求解效果極佳。

圖2 UDKP實例Best/Opt

圖3 WDKP實例Best/Opt

圖4 UDKP實例Best/Opt

圖5 IDKP實例Best/Opt

基于以上數據及圖像比較分析可以得出以下結論。

對大范圍類隨機產生的四類D｛0-1｝KP 實例進行計算時，除了UDKP 實例外，MMA 算法均能較好的計算出近似解，所得的最優(yōu)解與精確解的比值更能接近于1?？梢钥闯鯩MA 算法對于求解大規(guī)模D｛0-1｝KP問題比較適用，但對UDKP實例而言，其實用性較差。通過對WDKP、SDKP、IDKP 實驗數據進行分析，混合猴群算法能有效求解出較好的結果。

6 結語

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

由于MA 對于離散型的問題研究較少，該算法在爬的過程中涉及偽梯度問題，步長的設定會影響到偽梯度的計算，所以如何針對這一問題提出一個更有效的設計，是一個值得研究的問題。