一種求解KPC問(wèn)題的帶有編碼復(fù)用離散混合差分進(jìn)化算法

郝 翔，李香軍

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

0 引言

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

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

為了滿足現(xiàn)實(shí)生產(chǎn)中對(duì)計(jì)算結(jié)果與時(shí)效性的要求，本文提出了一個(gè)具有編碼復(fù)用的離散混合差分進(jìn)化算法（Discrete hybrid differential evolution algorithm with code reuse, DHDE）來(lái)求解KPC問(wèn)題。在算法DHDE單個(gè)種群的一次進(jìn)化中，通過(guò)自適應(yīng)的選擇編碼維度為n的 S-HBDE算法或者選擇編碼維度為(n+1)的 ETDE來(lái)進(jìn)化個(gè)體，并最終獲得KPC實(shí)例的最優(yōu)解。

1 KPC 問(wèn)題

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

KPC問(wèn)題的基本數(shù)學(xué)模型KPCM1如下：

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

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

2 S-HBDE和ETDE求解KPC

2.1 S-HBDE for KPC

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

2.2 ETDE for KPC

由于篇幅緣故，ETDE算法的進(jìn)化操作以及KPC-GROA算法偽代碼請(qǐng)見(jiàn)參考文獻(xiàn)[9]，以下不再贅述。

3 DHDE求解KPC

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

其中，bn表示利用前一次算法進(jìn)化個(gè)體時(shí)適應(yīng)度改進(jìn)的數(shù)目，Pbn∈ [ 0,1]表示其對(duì)應(yīng)的適應(yīng)度改進(jìn)概率，NP表示種群數(shù)目。Pbn越接近1表示前一次選取的算法的改進(jìn)效果越好。所以，利用隨機(jī)數(shù)rand∈ [ 0,1]是否小于Pbn來(lái)決定是否繼續(xù)選擇前一次所采用的進(jìn)化算法，若小于，則仍采用前一次的進(jìn)化算法；否則，采用另一個(gè)進(jìn)化算法。

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

算法1 DHDE

輸入：一個(gè)KPC實(shí)例，S-HBDE和ETDE進(jìn)化算子參數(shù)，NP，n和MIT。

輸出：最優(yōu)解 (Ybest,Sbest)以及目標(biāo)函數(shù)值f(Ybest,Sbest)

Step.1按照價(jià)值密度pj/wj(1 ≤j≤n)由大到小的次序依次將物品對(duì)應(yīng)下標(biāo)存入的數(shù)組H[1 …n]中。

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

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

Step.4當(dāng)t≤MIT，執(zhí)行Step.5，否則執(zhí)行Step.9

Step.5根據(jù)算法A的操作算子進(jìn)化種群個(gè)體，并由與算法A對(duì)應(yīng)的修復(fù)與優(yōu)化操作修復(fù)個(gè)體向量

Step.6更新bn和Pbn值

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 KPC 實(shí)例

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

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

4.2 DHDE 與其它算法的比較

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

表1 ukpc 實(shí)例結(jié)果Tab.1 The result of ukpc instances

表2 w kpc實(shí)例結(jié)果Tab.2 The result of wkpc instances

在表1-4中，通過(guò)統(tǒng)計(jì) 4個(gè)演化算法求解四類 KPC實(shí)例獲得的Best總數(shù)不難發(fā)現(xiàn)，算法DHDE的尋優(yōu)性能最強(qiáng)，共31個(gè)實(shí)例可以找到實(shí)例最好值，而ETDE，S-HBDE和B-HBDE找到Best的實(shí)例個(gè)數(shù)分別為 12，30和 27。為了更加直觀的比較算法的求解性能，在圖 1-2中給出 4個(gè)演化算法求解四類KPC實(shí)例的AR=|OPT-Mean|的曲線圖和Std直方圖。

表3 skpc 實(shí)例結(jié)果Tab.3 The result of skpc instances

表4 ikpc 實(shí)例結(jié)果Tab.4 The result of ikpc instances

從圖 1-2中不難看出，DHDE算法充分繼承了S-HBDE和ETDE的優(yōu)點(diǎn)，能自適應(yīng)的選擇性能良好的算法進(jìn)化個(gè)體，AR和Std值均得到了很大的改善，在ukpc9,wkpc5,skpc8,ikpc7等實(shí)例中尤為明顯。同時(shí)，DHDE算法的穩(wěn)定性也有了進(jìn)一步的增強(qiáng)，40個(gè)實(shí)例中，有11個(gè)實(shí)例Std值達(dá)到最小，有37個(gè)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是一個(gè)求解性能良好，穩(wěn)定性很強(qiáng)的，很適合求解KPC問(wèn)題的高效算法。

5 結(jié)論

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