基于拉馬克進化的差分進化算法求解KPC問題

楊新花，周昱帆，沈愛玲，林 娟，鐘一文

1.福建農林大學 計算機與信息學院，福州 350002 2.智慧農林福建省高等學校重點實驗室（福建農林大學），福州 350002

具有單連續變量的背包問題（knapsack problem with a single continuous variable，KPC）由Marchand和Wolsey于1999年提出[1]，是標準0-1背包問題的擴展形式。因為KPC使用連續變量S來控制背包的實際容量，其求解難度比標準0-1背包問題更大。在KPC中，給定n個物品和一個基本容量為C的背包，其中第j個物品的價值和重量分別為p j和w j。背包的實際容量不是固定的，用一個連續變量S表示背包實際容量與基本容量C的差值，系數c代表懲罰率或者獎勵率，當S＞0時，即背包的實際容量增加S，此時背包內物品的總價值將減去c×S；反之，當S＜0，背包的實際容量減少|S|，背包內物品的總價值將加上|c×S|。KPC的求解目標是通過確定S的值和選擇物品，在不超過背包實際容量允許范圍的情況下，使得裝入背包內物品的總價值最大。KPC的基本數學模型定義如下：

其中，X=[x1,x2,…,x n],x j=1表示第j個物品放入背包內，否則該物品不在背包內，u和l分別為S的上、下界。

目前求解KPC的方法主要有精確算法[2-3]、近似算法[5]和智能優化算法[5-7]等。Lin等[2]根據變量代換的方法將KPC轉化為標準0-1背包問題和偽背包問題（pseudoknapsack problem，PKP），并調用新型的動態規劃算法[8]求解標準0-1背包問題，采用新型的分支定界算法[9]求解PKP，提出了求解KPC的精確算法。由于算法中使用動態規劃算法并需要對PKP進行可行性檢查，導致算法實現繁瑣且復雜性高。賀毅朝等[3]利用放縮法對KPC進行等價變換，基于動態規劃算法提出了求解KPC的精確算法。Buther和Briskorn[10]將KPC的物品集劃分為三個子集，并利用啟發式策略并對變量的上下界變形，將KPC轉化為標準0-1背包問題再進行求解，但是該方法只能求出KPC的近似結果。Zhao和Li[4]將單連續變量S的取值區間劃分為兩部分，把KPC拆分成兩個具有標準0-1背包問題形式的子問題，提出了時間復雜度為O(n2)的2-近似算法。在智能優化算法方面，最早被用于求解KPC的是差分進化（differential evolution，DE）算法。賀毅朝等[5]利用降維法建立KPC的離散數學模型，提出了求解KPC的單種群離散演化算法（single-population binary DE with hybrid encoding，S-HBDE）；另外，將單連續變量S的取值區間劃分為兩個子區間，將KPC劃分為兩個子問題，提出了求解KPC的雙種群離散演化算法（bipopulation binary DE with hybrid encoding，B-HBDE）。He等[6]利用編碼轉換技術提出了基于編碼變換的差分進化算法（encoding transformation-based DE，ETDE）求解KPC。王澤昆等[7]利用新型的S型轉換函數將實數向量映射為KPC的解，提出一個新的二進制粒子群優化（new binary particle swarm optimization，NBPSO）算法求解KPC。精確算法求解KPC時間復雜性高，且實現較為繁瑣；近似算法雖然算法簡單，求解速度快，但是求解精度不夠；已有的差分進化算法在低維實例上表現良好，但在高維實例上表現欠佳。NBPSO雖然在大部分實例上表現良好，但算法時間復雜性高。KPC是一個NP完全問題[5]，不存在多項式時間精確算法，因此研究時間復雜性低且在高維實例上表現良好、穩定的智能優化算法是很有意義的。

本文針對KPC提出基于拉馬克進化的差分進化算法（Lamarckian evolution-based DE，LEDE），將算法在修復優化操作中得到的改進遺傳給后代，加快算法收斂速度，解決已有求解KPC的DE算法在高維實例上收斂速度慢而導致算法不穩定，收斂精度低的不足，利用變種群的策略避免算法收斂過快；同時設計基于價值引導的優化算子，提高求解精度，幫助算法跳出局部最優。實驗表明LEDE算法在所有大規模KPC實例上表現良好且穩定，性能明顯優于現有算法。

1 相關工作

1.1 DE算法

DE算法[11]是一種群體進化算法，標準的DE算法基于實數編碼在連續空間內進行搜索。設定種群大小為N，優化問題的維數為D，迭代次數為MAX_G，則初始種群X={x1,x2,…,x N}，其中x i表示問題的一個解，x i=[xi,1,xi,2,…,x i,D]，DE算法的求解步驟如下：

（2）變異操作。種群內個體的合作產生新的變異個體v i，常用的變異策略包括以下五種：

其中，F為縮放比例因子，r1、r2、r3、r4和r5為1到N之間的隨機數，且r1≠r2≠r3≠r4≠r5≠i,xbest為種群中最好的個體。

（3）交叉操作。按照式（9）生成實驗個體u i：

其中，CR∈[0,1]為交叉概率，jrand為[1,D]的隨機整數。

（4）選擇操作。個體x i和實驗個體u i之間的競爭，通過貪婪法選擇適應性更好的個體，對于一個最小化問題，選擇策略如下：

由于DE算法具有良好的性能，許多學者對DE算法的改進及其應用進行了深入的研究，主要的改進方向為控制參數、變異策略、種群設計等方面。在控制參數方面，Cui等[12]提出建立一個參數種群，將好的參數遺傳到下一代，而差的參數不斷向好參數學習更新。Leon等[13]提出一種新的參數聯合自適應方法，將F和CR所有可能的取值進行配對，并利用一個矩陣存儲選擇一對F和CR的概率，通過更新概率矩陣實現自適應的參數選擇。針對變異策略的改進，主要有將已有的變異策略進行混合以及設計新的變異策略。沈鑫等[14]提出一種雙變異策略，該策略將DE/rand/1和DE/current-to-best/1結合起來，在進化早期，DE/rand/1的權重更大，而在進化后期，DE/current-to-best/1權重增大，加速算法收斂。Li等[15]建立變異策略協作機制，將不同的變異策略結合，平衡算法的全局勘探和局部開發。Lu等[16]提出對傳統的DE/rand/1策略進行改進，使得變異個體能更接近種群目前所找到的全局最優解。Feng等[17]提出一種基于自適應群體智能的變異策略，可以有效避免算法陷入局部最優而過早收斂。在種群設計方面，Meng等[18]提出一種基于拋物線型的種群規模縮小策略。王浩等[19]將種群劃分為多個子種群，并通過種群優劣因子評價子種群的優劣，子種群在迭代過程中自適應合并與分裂。Chen等[20]將種群分為精英種群和普通種群，并分別應用不同的變異策略。

1.2 求解KPC的DE算法

以文獻[6]中的ETDE為例，KPC問題的解用一個n+1維的向量表示，其中前n個元素屬于{0，1}，表示物品是否放入背包內，第n+1個元素為實數，表示S。設種群大小為N，則初始種群X由N個實數向量表示的個體構成：

其中，每個個體x i含n+1個元素，前n個元素的值域為[-A,A]，第n+1個元素的值域為[l,u]，它們分別由式（12）和式（13）生成。

為了將個體x映射為解y，采用式（14）的映射方式，將前n個元素映射為0或者1，而第n+1個元素保留不變。

其中，i=1,2,…,N,j=1,2,…,n+1,A為一個正整數。

ETDE算法采用式（4）對個體進行變異，使用式（9）進行交叉，將變異、交叉后的個體通過式（14）映射為KPC的解，再用式（10）進行選擇操作。同時由于S是帶有約束的，變異操作可能會使得S越界，ETDE中對S越界采用式（13）的處理方法。

由于KPC是一個約束優化問題，采用啟發式方式生成的解可能是不可行解，ETDE采用貪心修復優化算子（greedy repair and optimization algorithm，GROA）對解做進一步處理，以保證解的有效性和解的質量，其貪心策略都是基于價值密度的比較方法。令HD是n個物品的編號按照價值密度p i/wi由大到小排列的數組，其中HD[i]是價值密度第i大的物品的編號，GROA偽代碼為算法1。算法第2~8行為貪心修復過程：對不可行解，從HD的尾部開始遍歷，依次將背包內價值密度小的物品從背包中取出，直到滿足式（2）約束條件，變成可行解；第9~15行為貪心優化過程：對可行解，從HD的頭部開始遍歷，在不違反式（2）的約束條件下，依次將價值密度大且不在背包內的物品放入背包中。

算法1GROA

2 基于拉馬克進化的DE算法

2.1 拉馬克進化

拉馬克進化的主要思想為“用進廢退、后天獲得性遺傳”，個體由于環境的影響導致性狀發生改變，這種改變會反饋回基因上遺傳給后代。相對的，鮑德溫效應認為個體性狀改變后，僅會導致個體的適應性改變，并不會表達在基因上。拉馬克進化被證明能加快算法的收斂速度[21-22]，Bereta[23]在文化基因算法的局部搜索過程中應用拉馬克進化、鮑德溫效應及兩者混合的策略，并對這三種策略進行分析。El-Mihoub等[24]在遺傳算法中采用拉馬克進化和鮑德溫效應的混合策略。綜上，可以把求解KPC的貪婪修復與優化算子看作是一種后天學習過程，通過該算子個體的性狀發生了變化。現有求解KPC的智能優化算法中修復優化算子是基于鮑德溫效應，修復優化操作僅使得個體的適應性改變，并沒有編碼到基因上。本文利用拉馬克進化能夠有效加快算法收斂速度的特點，設計基于拉馬克進化的修復優化算子，幫助算法在高維數據上加快收斂。即在修復操作中當背包內的第j個物品被拿出來后，個體對應位的基因通過式（15）進行改變。式（15）中rand(μ,1)的值域是[μ,1]，其中μ是一個大于0且足夠小的正數，以保證x i,j不為0。同理，優化操作中當物品被放入背包內后，個體對應位的基因通過式（16）進行改變。

拉馬克進化具有加快算法收斂的優點，但也存在急速降低種群多樣性，算法收斂過快導致陷入局部最優的缺陷。針對此不足，本文提出變種群的策略，將算法的迭代過程分為三個時期，每個時期分配不同的種群大小。種群大小N滿足式（17）。

其中，N1＞N2＞N3,g為當前迭代次數，MAX_G為最大迭代次數。在進化早期種群數量最大，種群的多樣性較好，能充分發揮算法的全局探索能力。在完成MAX_G/3次迭代后，為了增強算法的局部求精能力，使得資源更多地用在較優的個體，對個體按照適應值非升序排序，淘汰適應值較小的個體，僅保留前N2個個體。重復上述過程，直到種群大小縮減至N3。

2.2 改進的貪婪修復優化算子

在解的修復和優化過程中，基于價值密度的選擇策略使得那些單位價值大的物品優先選入，有助于提高算法的搜索質量，但是修復和優化都基于單一的選擇策略會使算法陷入局部最優。因此，提出改進的貪心修復優化算子（improved greedy repair and optimization algorithm，IGROA），在修復操作采用基于價值密度的引導策略，優化操作采用基于價值的引導策略，即優化過程中讓價值大的物品優先被選擇放入背包內，兩種不同的引導策略互相補充。令HV是物品編號按照價值p i由大到小排列的數組，其中HV[i]是價值第i大的物品的編號，IGROA的偽代碼為算法2。算法2與算法1的主要差異在于算法2使用拉馬克進化加快算法收斂，同時采用基于價值引導優化策略幫助算法跳出局部最優。第5行和第14行實現拉馬克進化。第11~18行實現價值引導的優化策略，從HV的頭部開始遍歷，在不違反式（2）的約束條件下，依次將價值大且不在背包內的物品放入背包中。IGROA的貪心修復和貪心優化過程的時間復雜性都為O(n)，因此IGROA的時間復雜性為O(n)。

算法2IGROA

2.3 算法描述

LEDE算法首先采用映射方式生成初始種群的個體集X和解集Y，在DE框架下，進行變異、交叉及選擇操作，采用拉馬克進化及基于價值密度的選擇準則對個體進行修復，并采用基于價值的選擇策略進行優化，具體步驟如算法3所示。

第2行得到初始種群個體集X和解集Y，第3~5行調用IGROA對X和Y進行修復和優化，第9~15行生成實驗個體Z和中間解V，其中iff函數包含3個參數，如果第1個參數為真，則函數值為第2個參數，否則函數值為第3個參數。第16行調用IGROA對實驗個體Z和中間解V進行修復和優化，如果中間解比父代中對應個體的解好，則中間解為下一代種群中的解。

需要說明的是，ETDE算法針對S越界處理方法為式（13），而本文采用式（18）約束S，即當S越界時以邊界值替換。同時，由式（12）可知個體集中x i的前n個元素的值域為[-A,A]，為避免某個元素過大或者過小使得該元素在變異操作中起決定性作用，降低變異操作的效果，將x i在進化過程中也限制在[-A,A]。

在算法時間復雜性上，第1行為快速排序，時間復雜性為O(n×lbn)，第2行的時間復雜性O(N×n)，IGOA的時間復雜性為O(n)，因此第3~5行的時間復雜性為O(N×n)。第6行的時間復雜性為O(N)，第7~25行的時間復雜性為O(MAX_G×N×n)，因此LEDE算法的時間復雜性為O(n×lbn)+O(N×n)+O(N×n)+O(N)+O(MAX_G×N×n)=O(MAX_G×N×n)。

算法3LEDE

3 實驗設計和結果分析

3.1 實驗數據與環境

本文將LEDE算法與NBPSO、S-HBDE、B-HBDE和ETDE算法進行對比，驗證LEDE算法的優化效率。實驗數據采用文獻[6]中的4類KPC問題實例，每類包含10個物品數從100到1 000的實例：不相關KPC實例，標記為ukpc100~ukpc1000；弱相關KPC實例，標記為wkpc100~wkpc1000；強相關KPC實例，標記為skpc100~skpc1000；逆強相關KPC實例，標記為ikpc100~ikpc1000。表1列出了這40個測試實例的最優解（OPT）[3]。實驗環境為Windows10 OS，Intel?CoreTMi5-5200U CPU@2.2 GHz，4 GB RAM，64位操作系統。

表1 4類實例的OPTTable 1 OPT of 4 classes of KPC instances

3.2 實驗參數設置

LEDE算法的參數A使用ETDE算法建議的值。縮放比例因子F和交叉概率CR采用全因子實驗來確定，實驗中F的取值范圍[0.3，0.8]，CR的取值范圍在[0.1，0.5]，步長均為0.1，實驗結果表明當F=0.3,CR=0.3時，LEDE算法的整體性能最好。算法迭代次數和種群大小保證LEDE和其他算法所生成解的數量相同。實驗參數具體設置為：迭代次數MAX_G為3n,N1=90,N2=20,N3=10，實數A為3，F為0.3，CR為0.3。

3.3 實驗結果分析

與ETDE算法相同，LEDE算法在每個測試用例上獨立運行50次，記錄獲得的最好解Best、平均解Mean，并計算Best與OPT的差(EB)、Mean與OPT的差(EM)，表2~表3列出LEDE算法的實驗結果并與NBPSO、SHBDE、B-HBDE和ETDE算法進行比較，對5種算法在每個實例上進行排名，并計算其EB和EM均值及排名均值，“+/=/-”表示LEDE優于、等于、差于與之比較算法的實例個數。其中NBPSO、S-HBDE、B-HBDE和ETDE算法的數據來源于原文獻，表中對5種算法中最好的EB和EM進行加粗顯示。為了更清晰地展示算法之間的優劣，把100~1 000維的實例標記序號為1~10，將各算法的EM值繪制成圖1~圖4進行比較。

從表2可以看出，在40個實例中，LEDE的EB均值為0.01最小，排名均值為1.125最靠前，性能最佳。其次為S-HBDE，雖然NBPSO的EB均值小于B-HBDE，但是由于其在部分實例上較差，導致其排名低于B-HBDE，B-HBDE的EB均值最差，ETDE的排名均值最差。采用Wilcoxon符號秩檢驗(α=0.05)比較LEDE算法與其他4個算法的EB值，對于LEDE和NBPSO，計算得到的R+、R-和p值分別為778、2和6.43E-04；對于LEDE和S-HBDE，計算得到的R+、R-和p值分別為777、3和4.74E-03；對于LEDE和B-HBDE，計算得到的R+、R-和p值分別為777、3和1.20E-03；對于LEDE和ETDE，計算得到的R+、R-和p值分別為780、0和5.58E-06。這說明在獲得最優解方面，LEDE明顯優于其他4個算法。

表2 LEDE、NBPSO、S-HBDE、B-HBDE和ETDE算法的EB性能比較Table 2 EB performance comparison of LEDE，NBPSO，S-HBDE，B-HBDE and ETDE algorithms

從表3可以看出，LEDE的EM均值為0.27最小，排名均值為1.45最靠前，NBPSO次之。采用Wilcoxon符號秩檢驗(α=0.05)比較LEDE算法與其他4個算法的EM值，對于LEDE和NBPSO，計算得到的R+、R-和p值分別為515、265和4.13E-01；對于LEDE和S-HBDE，計算得到的R+、R-和p值分別為720、60和4.12E-06；對于LEDE和B-HBDE，計算得到的R+、R-和p值分別為740、40和6.58E-07；對于LEDE和ETDE，計算得到的R+、R-和p值分別為774、6和5.63E-08。這說明在獲得平均解方面，LEDE明顯優于S-HBDE、B-HBDE和ETDE，略優于NBPSO，且LEDE的時間復雜性優于NBPSO的時間復雜性，由于NBPSO的修復和優化算子需要反復計算目標函數，導致其時間復雜性為O(MAX_G×N×n2),而LEDE時間復雜性為O(MAX_G×N×n)。

表3 LEDE、NBPSO、S-HBDE、B-HBDE和ETDE算法的EM性能比較Table 3 EM performance comparison of LEDE，NBPSO，S-HBDE，B-HBDE and ETDE algorithms

觀察圖1，LEDE在所有實例上表現良好，尤其是在高維數據上，LEDE更顯優越性。而NBPSO在ukpc100、ukpc300、ukpc700-900都表現不好，S-HBDE、B-HBDE和ETDE只在ukpc100、ukpc200、ukpc400、ukpc600表現良好。

圖1 實例ukpc100~ukpc1000上的EM曲線Fig.1 Curve of EM on ukpc100~ukpc1000 instances

觀察圖2，wkpc100~wkpc400前4個數據中5個算法差距不明顯，從wkpc500開始，LEDE算法明顯優于S-HBDE、B-HBDE和ETDE，且在wkpc1000數據中，另外4個算法效果很差，LEDE效果良好。

圖2 實例wkpc100~wkpc1000上的EM曲線Fig.2 Curve of EM on wkpc100~wkpc1000 instances

觀察圖3，ETDE算法在這類數據上表現欠佳，LEDE、NBPSO、S-HBDE和B-HBDE在大部分實例上表現良好，其中在skpc800上LEDE和NBPSO明顯優于其他3個算法。

圖3 實例skpc100~skpc1000上的EM曲線Fig.3 Curve of EM on skpc100~skpc1000 instances

觀察圖4，可以發現B-HBDE算法效果較差，且S-HBDE、B-HBDE、ETDE算法都存在隨著實例的維度增大求解結果變差的情況，LEDE和NPBSO在所有的實例上都表現良好。

圖4 實例ikpc100~ikpc1000上的EM曲線Fig.4 Curve of EM on ikpc100~ikpc1000 instances

4 算法行為分析

4.1 基于價值引導優化分析

為了分析在貪婪修復優化算子中使用價值引導優化策略的效果，在第3章使用的4類40個實例上進行基于價值密度和基于價值引導優化的比較實驗，Mean p和Mean p/w分別為價值引導優化和價值密度引導優化運行50次的均值。記ER=Mean p-Mean p/w，40個實例上的ER值如表4所示，正數表示價值引導優于價值密度引導，表中對價值引導不差于價值密度引導的E R值加粗顯示。

表4 4類KPC實例的ER值Table 4 ER values of 4 classes of KPC instances

觀察表4可以看出，價值引導優化在36個實例上不差于價值密度引導優化，其中23個實例更好，13個實例相等。為更準確地比較這兩種引導策略，依據文獻[2，8]給出的KPC實例生成方法，對4類100維~1 000維問題，每種類型每個維度的數據分別生成10個實例，即4×10×10個實例。每個實例運行50次取均值Mean，統計每類實例中價值引導優化優于（記為p＞p/w）、相等（記為p=p/w）、差于（記為p＜p/w）價值密度引導優化的個數。采用Wilcoxon符號秩檢驗比較兩種策略是否存在顯著性差異，統計結果如表5所示。通過表5可以看出價值引導的策略能夠在ukpc、wkpc和skpc上明顯提高算法的性能，在ikpc類實例上兩種策略無明顯差異，因為對ikpc類問題，任意兩個物品之間價值相對大小關系和價值密度相對大小關系完全相同，所以在ikpc類問題上兩種策略實際沒有區別。

表5 基于價值引導和基于價值密度引導優化的性能比較Table 5 Performance comparison between profit guided and profit weight ratio guided optimization

4.2 拉馬克進化及收斂性分析

為了分析拉馬克進化的效果及LEDE算法的收斂性，將LEDE算法和基于鮑德溫效應的DE算法在ukpc800、wkpc800、skpc800和ikpc800上進行比較，算法參數均保持一致。將種群中解的平均值作為適應值，觀察兩種算法的收斂速度及收斂精度。

圖6 wkpc800上拉馬克進化和鮑德溫效應的收斂曲線圖Fig.6 Convergence curve of Lamarckian evolution and Baldwin effect on wkpc800

圖7 skpc800上拉馬克進化和鮑德溫效應的收斂曲線圖Fig.7 Convergence curve of Lamarckian evolution and Baldwin effect on skpc800

觀察圖5~圖8可以看出，拉馬克進化比鮑德溫效應收斂速度更快，收斂精度更高。在ukpc800、wkpc800和skpc800上收斂精度明顯高于鮑德溫效應，ikpc800上兩種算法雖然在求解精度上差異不大，但是拉馬克進化在進化早期收斂速度比鮑德溫效應快。

圖5 ukpc800上拉馬克進化和鮑德溫效應的收斂曲線圖Fig.5 Convergence curve of Lamarckian evolution and Baldwin effect on ukpc800

圖8 ikpc800上拉馬克進化和鮑德溫效應的收斂曲線圖Fig.8 Convergence curve of Lamarckian evolution and Baldwin effect on ikpc800

5 結束語

本文對求解KPC的DE算法進行了研究，把貪婪修復優化算子看作一種后天學習過程，將拉馬克進化的思想引入到DE算法中，提出了基于拉馬克進化的DE算法，以加快算法的收斂速度，提高算法的求解精度和穩定性。同時將價值引導的優化策略引入到貪婪修復優化算子，進一步提高了算法的全局尋優能力，使用變種群大小的策略保證算法在前期有足夠的勘探能力。實驗分析表明采用的拉馬克進化策略和價值引導的優化策略是有效的，提出的LEDE算法性能明顯優于現有基于DE的算法，在獲取最優解方面性能顯著優于NBPSO算法，在獲取平均解方面也略優于NBPSO算法，且LEDE算法的時間復雜性優于NBPSO算法。本文提出的優化策略對求解KPC的智能優化算法具有通用性，下一步計劃將拉馬克進化策略和價值引導的優化策略引入到其他智能優化算法中，研究這些算法在KPC中的應用。