一種求解KPC問題的帶有編碼復用離散混合差分進化算法

郝 翔，李香軍

(河北地質大學 信息工程學院，河北 石家莊 050031)

0 引言

0-1背包問題（0-1 Knapsack problem, 0-1KP）[1-2]既是一個 NP-complete問題，也是一個典型的組合優化問題，在資源分配、項目組合和整數規劃等[3]領域有廣泛的應用。0-1KP衍化出了多種擴展形式，其中具有單連續變量的背包問題（knapsack problem with a single continuous variable, KPC）[4]是一個在物品生產、組織協調、分配管理以及其他經濟問題中具有重要的應用價值的0-1KP問題擴展形式之一，由 Marchand和 Wolsey于 1999年提出。KPC問題帶有一個連續變量S，S的連續變化會導致背包容量發生擴大或者縮小，從而導致問題求解難度增大。由于0-1KP是KPC的一個特例，因此KPC也是一個NP-complete問題，如何對其進行快速、高效求解是一個重要的問題。

2011年，Lin等人[5]給出了KPC問題的混合整型規劃公式，并通過將KPC問題轉化為0-1KP和 pseudo-KP的方法，分別利用動態規劃算法COMBO和分支定界算法EXPKNAP進行求解，顯然算法具有很高的時間復雜度。2012年，Buther和Briskorn[6]提出了等價構造法和啟發式策略，將KPC轉化為0-1KP問題，最后通過COMBO方法對轉化后的KP問題進行求解，執行速度仍較慢。2018年，He等人[7]首先利用放縮法將KPC中的連續變量離散化，并基于動態規劃法提出了求解KPC的精確算法DP-KPC。上述算法均采用了動態規劃等精確算法，時間復雜度都較高，在求解大規模KPC實例時存在速度慢、在限定時間內不能獲得精確解的缺點，不能滿足實際應用中時效性要求。為此，He等人[8]于 2018年提出了基于演化算法求解KPC問題的新思路，在利用降維法消除連續變量的基礎上，基于離散差分演化算法給出了求解KPC的算法S-HBDE和B-HBDE，求解效果有了很大的提高。He等人[9]將 KPC的單連續變量與物品的裝填方案（0-1向量）一起作為個體編碼，基于編碼轉換技術提出了求解KPC問題的一個具有混合編碼的差分進化算法 ETDE，該算法不需要進行放縮或者等價變換等操作，較文獻[8]中的算法更加容易實現。

為了滿足現實生產中對計算結果與時效性的要求，本文提出了一個具有編碼復用的離散混合差分進化算法（Discrete hybrid differential evolution algorithm with code reuse, DHDE）來求解KPC問題。在算法DHDE單個種群的一次進化中，通過自適應的選擇編碼維度為n的 S-HBDE算法或者選擇編碼維度為(n+1)的 ETDE來進化個體，并最終獲得KPC實例的最優解。

1 KPC 問題

KPC的定義：給定n個物品的集合N={ 1 ,2,…,n}和一個基本載重為C的背包，其中物品j∈N具有價值pj和重量wj，背包的可變載重S是區間[l,u]的一個連續變量，pj、wj和C是正有理數，S，l和u為有理數，且l＜0＜u.給定一個懲罰系數c＞0,如何確定S的取值以及在S確定的情況下如何選擇物品裝入背包，使得物品的重量之和在不超過載重C+S的前提下價值之和減去cS最大。

KPC問題的基本數學模型KPCM1如下：

其中，X= ［x1,x2,… ,xn］∈{0,1}n，xj=1(1≤j≤n)表示物品j被裝入了背包，xj= 0 (1 ≤j≤n)表示物品j沒有被裝入背包。從KPCM1中不難看出，KPC的背包載重不再固定不變，而是由連續變量S進行連續調整，當S＞0時背包載重增加，當S＜ 0 時背包載重減少; 同時，目標函數也不只是裝入背包物品的價值之和，而是要加上了一個關于S的增量（–cS）。

為了方便離散演化算法求解KPC問題，He等人在文獻[8]中基于降維法“消去”連續變量S，提出了KPC的一個新數學模型KPCM2，其描述如下：

2 S-HBDE和ETDE求解KPC

2.1 S-HBDE for KPC

從上述步驟中不難看出，S-HBDE算法的個體編碼維度為n。由于篇幅緣故，S-HBDE算法的進化操作以及M2-GROA算法偽代碼請見參考文獻[8]，以下不再贅述。

2.2 ETDE for KPC

由于篇幅緣故，ETDE算法的進化操作以及KPC-GROA算法偽代碼請見參考文獻[9]，以下不再贅述。

3 DHDE求解KPC

為了高效的求解KPC問題，本文提出了一個具有編碼復用的離散混合差分進化算法 DHDE。算法 DHDE僅有一個種群且個體編碼維度為(n+1)，采用與ETDE算法相同方式進行初始化。在算法的每一次進化中，采用公式（7）自適應的隨機選擇S-HBDE或者ETDE算法進化個體。在利用算法 S-HBDE時僅僅利用前n個編碼位置，第(n+1)個位置的數值通過計算獲得。在利用算法 ETDE時則利用全部的(n+1)個編碼位置，操作方式與原先算法相同。當滿足終止條件時，此時f(Ybest,Sbest)即為利用算法DHDE求解KPC問題的最優解。

其中，bn表示利用前一次算法進化個體時適應度改進的數目，Pbn∈ [ 0,1]表示其對應的適應度改進概率，NP表示種群數目。Pbn越接近1表示前一次選取的算法的改進效果越好。所以，利用隨機數rand∈ [ 0,1]是否小于Pbn來決定是否繼續選擇前一次所采用的進化算法，若小于，則仍采用前一次的進化算法；否則，采用另一個進化算法。

假設NP表示種群數目，n為 KPC實例中物品個數，MIT為迭代次數，A表示DHDE上一次進化種群選擇的算法，可以選擇 S-HBDE或者ETDE，bn表示前一次利用算法A進化個體時適應度改進的數目，Pbn∈ [ 0,1]表示其對應的適應度改進概率，rand是在[0,1]上的隨機數。P(t)={(Xi(t),S(t) ) |1 ≤i≤N}表示 MOBTGA的第t代種 群 ， (Xt(t),St) = (xt1(t),xt2(t) , … ,xtn(t),St)表 示臨時實數向量元組， (Yt(t),S(t) ) =(yt1(t),yt2(t),…,ytn(t),St)表示與(Xt(t),St)對應的個體向量元組。(Ybest,Sbest)表示由算法ETDE得到的最優解。則DHDE的偽代碼如下:

算法1 DHDE

輸入：一個KPC實例，S-HBDE和ETDE進化算子參數，NP，n和MIT。

輸出：最優解 (Ybest,Sbest)以及目標函數值f(Ybest,Sbest)

Step.1按照價值密度pj/wj(1 ≤j≤n)由大到小的次序依次將物品對應下標存入的數組H[1 …n]中。

Step.2初始化種群P(t)，獲得個體對應的元組向量(Yi(t) ,Si(t) ) ,1≤i≤NP,利用 KPC-GROA 對(Yi(t) ,Si(t))進行修復與優化操作并由f(Yi(t) ,Si(t))的大小獲得 (Ybest,Sbest)。

Step.3t←0，bn←0和隨機選擇算法A

Step.4當t≤MIT，執行Step.5，否則執行Step.9

Step.5根據算法A的操作算子進化種群個體，并由與算法A對應的修復與優化操作修復個體向量

Step.6更新bn和Pbn值

Step.7由rand與Pbn的大小判定是否保持上一次的算法A，獲得下一次進化個體的算法A

Step.8更新 (Ybest,Sbest)，t←t+1，轉到Step.4

Step.9輸出 ( (Ybest,Sbest),f(Ybest,Sbest))

由文獻[8][9]知，KPC-GROA的時間復雜度為O(n)，M2-GROA的時間復雜度為O(n2)。在算法 DHDE中，step1由快速排序[10]實現，時間復雜度為O(nlogn)，Step.2的時間復雜度為O(NP*n)，Step.3-Step 8的時間復雜度為O(MIT*NP*n2)，因此DHDE的時間復雜度為O(nl ogn) +O(NP*n)+O(MIT*NP*n2) =O(MIT*NP*n2)。

4 實驗結果與分析

4.1 KPC 實例

本文實驗環境在配置為 Intel(R) CoreTM i5-8300H CPU@2.3 GHz和8 GB的RAM的微型計算機上進行，編程語言為 C，編譯環境為Codeblocks 17.12，使用Python在編譯環境JetBrains PyCharm2018上繪圖。

KPC實例來自于文獻[5]中提供的公開數據集，KPC的四類大規模實例分別是不相關實例ukpc、弱相關實例wkpc、強相關實例skpc和逆強相關實例ikpc，其中每一類都包含10個不同規模的實例，實例規模n∈ { 100,200,… ,1 000}。所有實例的具體數據可以在網址：https://www.researchgate.net/project/KPC-problem-and-Its-algorithms中獲得。

4.2 DHDE 與其它算法的比較

在本節中，首先利用DHDE算法對四類KPC實例獨立運行50次，然后將得到的計算結果與利用DP-KPC ETDE、S-HBDE和B-HBDE的已有結果進行比較，DHDE中使用的S-HBDE和ETDE算法的設置參數與文獻[8][9]相同，具體參數見參考文獻。在表 1-表 4中給出上述算法分別求解ukpc類實例、wkpc類實例、skpc類實例以及ikpc類實例的計算結果。其中，OPT是利用DP-KPC算法求解KPC實例獲得的最好值，Best，Mean和Std分別表示上述算法獨立計算實例50次的計算結果的最優值，平均值以及標準差 （由于上述算法求解 kpc實例的運行時間差別不大，在表 1-4中便不再列出）。

表1 ukpc 實例結果Tab.1 The result of ukpc instances

表2 w kpc實例結果Tab.2 The result of wkpc instances

在表1-4中，通過統計 4個演化算法求解四類 KPC實例獲得的Best總數不難發現，算法DHDE的尋優性能最強，共31個實例可以找到實例最好值，而ETDE，S-HBDE和B-HBDE找到Best的實例個數分別為 12，30和 27。為了更加直觀的比較算法的求解性能，在圖 1-2中給出 4個演化算法求解四類KPC實例的AR=|OPT-Mean|的曲線圖和Std直方圖。

表3 skpc 實例結果Tab.3 The result of skpc instances

表4 ikpc 實例結果Tab.4 The result of ikpc instances

從圖 1-2中不難看出，DHDE算法充分繼承了S-HBDE和ETDE的優點，能自適應的選擇性能良好的算法進化個體，AR和Std值均得到了很大的改善，在ukpc9,wkpc5,skpc8,ikpc7等實例中尤為明顯。同時，DHDE算法的穩定性也有了進一步的增強，40個實例中，有11個實例Std值達到最小，有37個Std值排名第二。

圖 1 AR 曲線圖(a) ukpc1–ukpc10, (b) wkpc1–wkpc10, (c) skpc1–skpc10, (d) ikpc1–ikpc10

圖 2 Std 曲線圖(a) ukpc1–ukpc10, (b) wkpc1–wkpc10, (c) skpc1–skpc10, (d) ikpc1–ikpc10

綜上所述，DHDE是一個求解性能良好，穩定性很強的，很適合求解KPC問題的高效算法。

5 結論

本文提出了求解KPC問題的一個具有編碼復用的離散混合差分進化算法 DHDE。算法在單種群中通過編碼復用的方式混合了算法S-HBDE和ETDE兩種進化算子，同時通過記錄算法 DHDE在前一次進化模式中種群個體改善數目，自適應的選擇下一次的進化算子。最后，通過將 DHDE求解四類KPC實例的計算結果與ETDE、S-HBDE和B-HBDE的計算結果對比，證明了DHDE在求解 KPC問題中的有效性，是一個適合高效求解KPC實例的新方法。