基于拉馬克進(jìn)化的差分進(jìn)化算法求解KPC問(wèn)題

楊新花，周昱帆，沈愛(ài)玲，林 娟，鐘一文

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

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

其中，X=[x1,x2,…,x n],x j=1表示第j個(gè)物品放入背包內(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背包問(wèn)題和偽背包問(wèn)題（pseudoknapsack problem，PKP），并調(diào)用新型的動(dòng)態(tài)規(guī)劃算法[8]求解標(biāo)準(zhǔn)0-1背包問(wèn)題，采用新型的分支定界算法[9]求解PKP，提出了求解KPC的精確算法。由于算法中使用動(dòng)態(tài)規(guī)劃算法并需要對(duì)PKP進(jìn)行可行性檢查，導(dǎo)致算法實(shí)現(xiàn)繁瑣且復(fù)雜性高。賀毅朝等[3]利用放縮法對(duì)KPC進(jìn)行等價(jià)變換，基于動(dòng)態(tài)規(guī)劃算法提出了求解KPC的精確算法。Buther和Briskorn[10]將KPC的物品集劃分為三個(gè)子集，并利用啟發(fā)式策略并對(duì)變量的上下界變形，將KPC轉(zhuǎn)化為標(biāo)準(zhǔn)0-1背包問(wèn)題再進(jìn)行求解，但是該方法只能求出KPC的近似結(jié)果。Zhao和Li[4]將單連續(xù)變量S的取值區(qū)間劃分為兩部分，把KPC拆分成兩個(gè)具有標(biāo)準(zhǔn)0-1背包問(wèn)題形式的子問(wèn)題，提出了時(shí)間復(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ū)間劃分為兩個(gè)子區(qū)間，將KPC劃分為兩個(gè)子問(wèn)題，提出了求解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í)數(shù)向量映射為KPC的解，提出一個(gè)新的二進(jìn)制粒子群優(yōu)化（new binary particle swarm optimization，NBPSO）算法求解KPC。精確算法求解KPC時(shí)間復(fù)雜性高，且實(shí)現(xiàn)較為繁瑣；近似算法雖然算法簡(jiǎn)單，求解速度快，但是求解精度不夠；已有的差分進(jìn)化算法在低維實(shí)例上表現(xiàn)良好，但在高維實(shí)例上表現(xiàn)欠佳。NBPSO雖然在大部分實(shí)例上表現(xiàn)良好，但算法時(shí)間復(fù)雜性高。KPC是一個(gè)NP完全問(wèn)題[5]，不存在多項(xiàng)式時(shí)間精確算法，因此研究時(shí)間復(fù)雜性低且在高維實(shí)例上表現(xiàn)良好、穩(wěn)定的智能優(yōu)化算法是很有意義的。

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

1 相關(guān)工作

1.1 DE算法

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

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

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

（3）交叉操作。按照式（9）生成實(shí)驗(yàn)個(gè)體u i：

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

（4）選擇操作。個(gè)體x i和實(shí)驗(yàn)個(gè)體u i之間的競(jìng)爭(zhēng)，通過(guò)貪婪法選擇適應(yīng)性更好的個(gè)體，對(duì)于一個(gè)最小化問(wèn)題，選擇策略如下：

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

1.2 求解KPC的DE算法

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

其中，每個(gè)個(gè)體x i含n+1個(gè)元素，前n個(gè)元素的值域?yàn)閇-A,A]，第n+1個(gè)元素的值域?yàn)閇l,u]，它們分別由式（12）和式（13）生成。

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

其中，i=1,2,…,N,j=1,2,…,n+1,A為一個(gè)正整數(shù)。

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

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

算法1GROA

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

2.1 拉馬克進(jìn)化

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

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

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

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

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

算法2IGROA

2.3 算法描述

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

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

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

在算法時(shí)間復(fù)雜性上，第1行為快速排序，時(shí)間復(fù)雜性為O(n×lbn)，第2行的時(shí)間復(fù)雜性O(shè)(N×n)，IGOA的時(shí)間復(fù)雜性為O(n)，因此第3~5行的時(shí)間復(fù)雜性為O(N×n)。第6行的時(shí)間復(fù)雜性為O(N)，第7~25行的時(shí)間復(fù)雜性為O(MAX_G×N×n)，因此LEDE算法的時(shí)間復(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í)驗(yàn)設(shè)計(jì)和結(jié)果分析

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

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

表1 4類(lèi)實(shí)例的OPTTable 1 OPT of 4 classes of KPC instances

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

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

表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符號(hào)秩檢驗(yàn)(α=0.05)比較LEDE算法與其他4個(gè)算法的EM值，對(duì)于LEDE和NBPSO，計(jì)算得到的R+、R-和p值分別為515、265和4.13E-01；對(duì)于LEDE和S-HBDE，計(jì)算得到的R+、R-和p值分別為720、60和4.12E-06；對(duì)于LEDE和B-HBDE，計(jì)算得到的R+、R-和p值分別為740、40和6.58E-07；對(duì)于LEDE和ETDE，計(jì)算得到的R+、R-和p值分別為774、6和5.63E-08。這說(shuō)明在獲得平均解方面，LEDE明顯優(yōu)于S-HBDE、B-HBDE和ETDE，略?xún)?yōu)于NBPSO，且LEDE的時(shí)間復(fù)雜性?xún)?yōu)于NBPSO的時(shí)間復(fù)雜性，由于NBPSO的修復(fù)和優(yōu)化算子需要反復(fù)計(jì)算目標(biāo)函數(shù)，導(dǎo)致其時(shí)間復(fù)雜性為O(MAX_G×N×n2),而LEDE時(shí)間復(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

觀(guān)察圖1，LEDE在所有實(shí)例上表現(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 實(shí)例ukpc100~ukpc1000上的EM曲線(xiàn)Fig.1 Curve of EM on ukpc100~ukpc1000 instances

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

圖2 實(shí)例wkpc100~wkpc1000上的EM曲線(xiàn)Fig.2 Curve of EM on wkpc100~wkpc1000 instances

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

圖3 實(shí)例skpc100~skpc1000上的EM曲線(xiàn)Fig.3 Curve of EM on skpc100~skpc1000 instances

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

圖4 實(shí)例ikpc100~ikpc1000上的EM曲線(xiàn)Fig.4 Curve of EM on ikpc100~ikpc1000 instances

4 算法行為分析

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

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

表4 4類(lèi)KPC實(shí)例的ER值Table 4 ER values of 4 classes of KPC instances

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

表5 基于價(jià)值引導(dǎo)和基于價(jià)值密度引導(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)值，觀(guān)察兩種算法的收斂速度及收斂精度。

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

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

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

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

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

5 結(jié)束語(yǔ)

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