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

1.福建農(nóng)林大學(xué) 計算機(jī)與信息學(xué)院，福州 350002 2.智慧農(nóng)林福建省高等學(xué)校重點實驗室（福建農(nóng)林大學(xué)），福州 350002

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

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

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

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

1 相關(guān)工作

1.1 DE算法

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

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

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

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

其中，CR∈[0,1]為交叉概率，jrand為[1,D]的隨機(jī)整數(shù)。

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

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

1.2 求解KPC的DE算法

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

其中，每個個體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為一個正整數(shù)。

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

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

算法1GROA

2 基于拉馬克進(jìn)化的DE算法

2.1 拉馬克進(jìn)化

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

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

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

2.2 改進(jìn)的貪婪修復(fù)優(yōu)化算子

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

算法2IGROA

2.3 算法描述

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

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

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

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

算法3LEDE

3 實驗設(shè)計和結(jié)果分析

3.1 實驗數(shù)據(jù)與環(huán)境

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

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

3.2 實驗參數(shù)設(shè)置

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

3.3 實驗結(jié)果分析

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

從表2可以看出，在40個實例中，LEDE的EB均值為0.01最小，排名均值為1.125最靠前，性能最佳。其次為S-HBDE，雖然NBPSO的EB均值小于B-HBDE，但是由于其在部分實例上較差，導(dǎo)致其排名低于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。這說明在獲得最優(yōu)解方面，LEDE明顯優(yōu)于其他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明顯優(yōu)于S-HBDE、B-HBDE和ETDE，略優(yōu)于NBPSO，且LEDE的時間復(fù)雜性優(yōu)于NBPSO的時間復(fù)雜性，由于NBPSO的修復(fù)和優(yōu)化算子需要反復(fù)計算目標(biāo)函數(shù)，導(dǎo)致其時間復(fù)雜性為O(MAX_G×N×n2),而LEDE時間復(fù)雜性為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在所有實例上表現(xiàn)良好，尤其是在高維數(shù)據(jù)上，LEDE更顯優(yōu)越性。而NBPSO在ukpc100、ukpc300、ukpc700-900都表現(xiàn)不好，S-HBDE、B-HBDE和ETDE只在ukpc100、ukpc200、ukpc400、ukpc600表現(xiàn)良好。

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

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

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

觀察圖3，ETDE算法在這類數(shù)據(jù)上表現(xiàn)欠佳，LEDE、NBPSO、S-HBDE和B-HBDE在大部分實例上表現(xiàn)良好，其中在skpc800上LEDE和NBPSO明顯優(yōu)于其他3個算法。

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

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

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

4 算法行為分析

4.1 基于價值引導(dǎo)優(yōu)化分析

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

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

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

表5 基于價值引導(dǎo)和基于價值密度引導(dǎo)優(yōu)化的性能比較Table 5 Performance comparison between profit guided and profit weight ratio guided optimization

4.2 拉馬克進(jìn)化及收斂性分析

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

圖6 wkpc800上拉馬克進(jìn)化和鮑德溫效應(yīng)的收斂曲線圖Fig.6 Convergence curve of Lamarckian evolution and Baldwin effect on wkpc800

圖7 skpc800上拉馬克進(jìn)化和鮑德溫效應(yīng)的收斂曲線圖Fig.7 Convergence curve of Lamarckian evolution and Baldwin effect on skpc800

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

圖5 ukpc800上拉馬克進(jìn)化和鮑德溫效應(yīng)的收斂曲線圖Fig.5 Convergence curve of Lamarckian evolution and Baldwin effect on ukpc800

圖8 ikpc800上拉馬克進(jìn)化和鮑德溫效應(yīng)的收斂曲線圖Fig.8 Convergence curve of Lamarckian evolution and Baldwin effect on ikpc800

5 結(jié)束語

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