新穎的離散差分演化算法求解D{0-1}KP 問題

張發(fā)展，賀毅朝，劉雪靜，王澤昆

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

背包問題（knapsack problems，KP）是一類經(jīng)典的NP 完全問題，也是重要的組合優(yōu)化問題。KP 在資源分配、投資決策、經(jīng)濟金融和信息安全等諸多領域都具有重要的理論意義和實用價值。KP 有許多不同的擴展形式，例如：集合聯(lián)盟背包問題（set-union knapsack problem，SUKP）、多維背包問題（multidimensional knapsack problem，MKP）、具有單連續(xù)變量背包問題（knapsack problem with a single continuous variable，KPC）和折扣{0-1}背包問題（discounted{0-1}knapsack problem，D{0-1}KP）等。

D{0-1}KP 是由Guldan于2007 年首次提出的0-1KP 的一種更復雜的擴展形式。由于D{0-1}KP 對項目（物品）的選擇更加多樣化，使得D{0-1}KP 比0-1背包問題（0-1 knapsack problem，0-1KP）具有更大的挑戰(zhàn)性。目前，許多國內外學者對D{0-1}KP 問題的求解算法進行了研究，例如Guldan討論了如何使用啟發(fā)式和精確算法求解D{0-1}KP，并給出了一種求解D{0-1}KP 的動態(tài)規(guī)劃法；Rong 等人于2012 年通過核問題將D{0-1}KP 劃分為若干較容易的子問題，并給出了一種動態(tài)規(guī)劃與核相結合求解D{0-1}KP的精確算法；2016 年，He 等人設計了一種新的基于動態(tài)規(guī)劃的精確算法，并在此基礎上提出了三種近似算法求解D{0-1}KP；賀毅朝等人于2016 年首先建立了D{0-1}KP 的兩個新的數(shù)學模型，在提出了兩種貪心修復與優(yōu)化算法的基礎上，給出了兩種利用基于杰出者保留策略遺傳算法（genetic algorithm with elitist reservation strategy，EGA）求解D{0-1}KP 的方法；吳聰聰?shù)热耸紫炔捎秒p重編碼解決D{0-1}KP的編碼問題，在此基礎上提出了一種變異的蝙蝠算法（mutated double binary bat algorithm，MDBBA）求解D{0-1}KP；2018 年，劉雪靜等人針對D{0-1}KP 的兩種數(shù)學模型，提出了自適應細菌覓食算法（adaptive bacterial foraging algorithm，ABFO）求解D{0-1}KP的兩種算法，并比較了兩種算法的優(yōu)劣；隨后，He等人先后提出了基于群論的優(yōu)化算法（group theorybased optimization algorithm，GTOA）和基于環(huán)理論的演化算法（ring theory-based evolutionary algorithm，RTEA），并分別用于求解D{0-1}KP，取得了較好的效果；2020 年，Wu等人提出了一種離散混合教學優(yōu)化算法（hybrid teaching-learning-based optimization algorithm，HTLBO），并利用它給出了一種求解D{0-1}KP的方法；Li等人在提出一種新V 型傳遞函數(shù)的基礎上，提出了一種新的二進制鯨魚優(yōu)化算法（discrete whale optimization algorithm，DWOA），并應用于求解D{0-1}KP 問題。顯然，目前求解D{0-1}KP 的算法主要分為兩類：精確算法和非精確算法。精確算法具有偽多項式時間復雜度，不適用于求解大規(guī)模D{0-1}KP 實例。非精確算法特別是演化算法不僅求解速度快，而且計算結果能夠滿足實際應用的需求，因此探討利用演化算法求解D{0-1}KP 的高效方法是一個值得研究與探討的問題。

差分演化（differential evolution，DE）最初是由Storn 和Price提出的一種基于隨機種群的元啟發(fā)式算法，雖然在求解數(shù)值優(yōu)化和電力系統(tǒng)等問題時表現(xiàn)出優(yōu)異的性能，但是由于差分演化是基于實數(shù)運算實現(xiàn)的，不能直接應用于求解組合優(yōu)化問題。為此，研究人員先后提出了不同版本的二進制差分演化算法，例如Engelbrecht等人于2007 年利用S 型轉換函數(shù)提出了一種二進制差分演化算法（binary differential evolution，BinDE）。He 等人基于混合編碼機制提出了一個二進制差分演化算法（binary differential evolution algorithm with hybrid encoding，HBDE），利用滿射映射由個體的實向量得到一個0-1向量，從而使HBDE 適于求解以0-1 向量為可行解的組合優(yōu)化問題。但是從相關文獻中不難看出，BinDE利用S 型轉換函數(shù)將DE 中個體的實向量編碼轉換為0-1 向量編碼的概率與一個隨機數(shù)進行比較，容易造成可行解中0 和1 分布的不確定性。與BinDE恰恰相反，HBDE 利用滿射映射的方法容易造成可行解中0 和1 分布過于均勻。在大量實驗的基礎上發(fā)現(xiàn)，上述已有的二進制差分演化算法求解D{0-1}KP的實驗結果較差，并不能令人滿意。為此，本文給出了一種新V 型轉換函數(shù)（novel V-shape transfer function，NV），并在此基礎上提出了一種基于新V型轉換函數(shù)的新離散差分演化算法（novel discrete differential evolution algorithm，NDDE），給出了求解D{0-1}KP的一個新的高效方法。

1 D{0-1}KP 的定義和模型

D{0-1}KP 問題是經(jīng)典0-1KP 的一個更復雜的變體，它在0-1KP問題的基礎上加入了“折扣”思想，當同時選擇兩個物品時就會得到折扣。這種思想來源于商業(yè)領域，商場和企業(yè)通常會通過“折扣”的方式吸引更多的消費者。D{0-1}KP問題在項目決策、資源投資和資本預算等諸多領域具有重要的應用理論意義。

下面給出D{0-1}KP問題的定義和已有數(shù)學模型。

D{0-1}KP 的定義一般描述為：給定個含有3個物品的物品集，物品集(0 ≤≤-1)中含有的3 個物品分別表示為3，3+1 和3+2，其中前兩個物品3和3+1 的價值系數(shù)分別記為和，重量系數(shù)分別記為和；第三個物品3+2 為前兩個物品的合并，它的價值系數(shù)為=+，它的折扣重量系數(shù)為，滿足＜+，并且＜、＜。對于每一個物品集(0 ≤≤-1)，物品3、3+1 和3+2 中至多有一個可以被選擇裝入背包中。D{0-1}KP 問題的目的是如何選擇物品裝入背包，使得裝入背包的所有物品的重量系數(shù)之和在不超過背包載重的前提下價值系數(shù)之和達到最大。

根據(jù)上述定義，Guldan給出了D{0-1}KP 的第一個數(shù)學模型，其描述如下：

其中，=[,,…,]∈{0,1}為一個3維二進制向量。僅僅表示D{0-1}KP 的一個潛在解，只有當它同時滿足約束條件（2）和（3）時才是一個可行解；二元變量x(0 ≤≤3-1）表示物品是否裝入背包，x=0 表示物品沒有被裝入背包，反之x=1 表示物品裝入背包中。

He等人根據(jù)D{0-1}KP的定義，建立了D{0-1}KP的兩個新的數(shù)學模型：模型二和模型三。本文僅研究如何基于D{0-1}KP 的第一數(shù)學模型進行高效求解，其他兩個模型不再贅述，請參考有關文獻[12]。

2 利用NDDE 求解D{0-1}KP

本章首先介紹了四種S 型轉換函數(shù)和四種V 型轉換函數(shù)，然后提出了一個新V 型轉換函數(shù)（NV），接著基于NV 提出了一個新的離散差分演化算法（NDDE），并給出其算法原理和偽代碼描述。最后，給出了利用NDDE 求解D{0-1}KP 的具體方法。

2.1 新V 型轉換函數(shù)

目前，已有的演化算法多數(shù)都是基于實數(shù)運算實現(xiàn)進化的，因此不能直接用于求解二元優(yōu)化問題。為此，相關研究人員提出一種映射的方法，通過轉換函數(shù)將個體的實向量編碼映射為一個0-1 向量編碼，以適合直接用于求解二元優(yōu)化問題。近年來，轉換函數(shù)成為二進制演化算法研究的一個熱點問題，已有的轉換函數(shù)可以分為兩類，即S 型轉換函數(shù)和V 型轉換函數(shù)。其中S 型轉換函數(shù)分別命名為S1～S4，V 型轉換函數(shù)分別命名為V1～V4。表1 給出了4 個S 型轉換函數(shù)和4 個V 型轉換函數(shù)。

表1 S 型轉換函數(shù)和V 型轉換函數(shù)Table 1 S-shaped and V-shaped families of transfer functions

本文受V 型函數(shù)的啟發(fā)，在保留V 型轉換函數(shù)特性的基礎上，提出了一個計算簡單的新V 型轉換函數(shù)，命名為NV。轉換函數(shù)NV 的計算公式如式（5）所示，其函數(shù)曲線如圖1 所示。

圖1 NVA 的函數(shù)曲線Fig.1 Function curve of NVA

從表1、圖1 和式（5）可以看出：NV 型傳遞函數(shù)與S 型傳遞函數(shù)相比，兩者之間差別巨大，它們明顯具有不同的性質。且不難看出，由于S 型函數(shù)中涉及指數(shù)運算，NV 型傳遞函數(shù)的計算量遠遠小于S 型傳遞函數(shù)。NV 型傳遞函數(shù)與V 型傳遞函數(shù)相比，雖然兩者的函數(shù)圖像相似，都是關于軸對稱的，但是兩者之間依然存在較大差異：首先，NV 型傳遞函數(shù)為初等函數(shù)，而V 型傳遞函數(shù)中的V1 不是初等函數(shù)。其次，NV 型傳遞函數(shù)的計算復雜度明顯比V 型傳遞函數(shù)的低。

2.2 NDDE

下面利用新V 型轉換函數(shù)給出一個新的離散差分演化算法（NDDE）。在保持DE 原有進化模式不變的基礎上，利用轉換函數(shù)NV 將DE 中個體的實向量轉化為0-1 向量，實現(xiàn)對D{0-1}KP 問題的求解。

設Y=[y,y,…,y]表示NDDE的當前種群中第個個體，其中y∈[-,]，=1,2,…,,=0,1,…,3-1，為種群規(guī)模，3為物品個數(shù)。NDDE利用轉換函數(shù)NV將3維實向量Y=[y,y,…,y]轉換為一個3維0-1向量X=[x,x,…,x]∈{0,1}，X為D{0-1}KP問題的一個可行解或潛在解。

在NDDE 的一次迭代中，首先對種群的每個個體Y依次進行DE 中的變異操作和交叉操作得到中間個體Z=[z,z,…,z]∈[-,]；然后利用式（6）求得中間個體Z對應的0-1向量U=[u,u,…,u]∈{0,1}；最后利用式（7）選擇X和Z中適應度最好的個體作為新一代種群中的第個個體（仍記為Y）。重復上述過程，直到種群的所有個體都完成以上操作為止。

其中，NV(z)表示利用轉換函數(shù)NV 將z∈[-,]轉換為0 到1 之間的一個實數(shù)?！?0,1)是一個預先設定的閾值，本文設為0.2。

2.3 利用NDDE 求解D{0-1}KP

記“[0,1,…,3-1]←（{p/w|p∈,w∈,0 ≤≤3-1}）”表示將3個物品的價值重量系數(shù)比p/w(0 ≤≤3-1)由大到小依次存入數(shù)組[0,1,…,3-1]中。記=(,,…,)∈{0,1}是種群()中最好個體對應的最好解，是算法NDDE 的迭代次數(shù)，為種群規(guī)模；∈(0,1) 為DE 交叉因子；∈(0,1)為DE 縮放因子；()是[1,]上的一個隨機正整數(shù)。則基于NDDE 求解D{0-1}KP 的算法偽代碼描述如算法1 所示。

NDDE for D{0-1}KP

輸入：D{0-1}KP的一個實例；參數(shù)、、、、和。

輸出：D{0-1}KP實例的最好解和最好值()。

1.[0,1,…,3-1]←QuickSort({p/w|p∈,w∈,0 ≤

≤3-1})；

2.隨機產生初始種群(0)={Y=[y,y,…,y]|y∈[-,],1 ≤≤,0 ≤≤3-1}；

3.for←1 todo

4.for←0 to 3-1 do

5.if≤(y) then x←1 else x←0；

6.end for

7.(X(0),(X(0)))←GROA(X(0),[0,1,…,3-1])；

8.end for

9.根據(jù)(X(0))(1 ≤≤)確定種群(0)中當前最好解

10.for←1 todo

11.for←1 todo

12. for←0 to 3-1 do

13. if(＜or=())then z←y+*(y-y)else z←y；

14. if≤(z) then u←1 else u←0；

15. end for

16. (U,(U))←GROA(U(),[0,1,…,3-1])；

17. if(U)＜(X) then Y←Zand X←U；18.end for

19.根據(jù)(X)(1 ≤≤)確定當前最好解；

20.end for

21.return (,()).

在算法1 中，步驟1 利用快速排序QuickSort實現(xiàn)，其時間復雜度為(lb)；步驟2 的時間復雜度為(×(3-1))；步驟3～8的時間復雜度為(×(3-1))；步驟10～20 的時間復雜度為××(3-1)，因此NDDE求解D{0-1}KP的時間復雜度為(lb)+(×(3-1))+××(3-1)，當、是關于的多項式時，算法1為具有多項式時間復雜度的演化算法。

3 計算結果與分析

所有的計算均在配置為AMD Ryzen 3 2200G @3.50 GHz 和8 GB RAM 的微型計算機上進行。操作系統(tǒng)為Microsoft Windows 10（企業(yè)版）。利用C 語言進行編程，編譯環(huán)境為Code:Blocks。使用Python 在編譯環(huán)境JetBrains PyCharm 下繪制曲線圖、折線圖和直方圖。

3.1 4 類D{0-1}KP 實例

所使用的4類D{0-1}KP實例分別為：第一類不相關D{0-1}KP 實例（uncorrelated instances of D{0-1}KP，UDKP），編號為UDKP1～UDKP10；第二類為弱相關D{0-1}KP 實例（weakly correlated instances of D{0-1}KP，WDKP），編號為WDKP1～WDKP10；第三類為強相關D{0-1}KP實例（strongly correlated instances ofD{0-1}KP，SDKP），編號為SDKP1～SDKP10；第四類為逆相關D{0-1}KP實例（inverse correlated instances of D{0-1}KP，IDKP），編號為IDKP1～IDKP10。所有D{0-1}KP實例的詳細信息都可以在DOI獲得（https://doi.org/10.11897/SP.J1016.02614）。

3.2 參數(shù)檢驗

在NDDE 中，∈(0,1)為一個預先設定的閾值，它與傳遞函數(shù)將算法中實向量個體轉換為0 或1 的概率有關。為交叉因子，為縮放因子，[-,]為個體對應的實向量的取值空間。為了使算法NDDE 求解D{0-1}KP 問題的性能達到最佳，本文利用Kruskal-Wallis 秩和檢驗確定NDDE 中參數(shù)、和的合理取值。下面以參數(shù)為例，分別設置=0.1,0.2,0.3,0.4 和0.5，本文選擇了40 個D{0-1}KP實例中=500（為項目個數(shù)）的4 個不同類型的代表實例UDKP5、WDKP5、SDKP5 和IDKP5。在秩和檢驗過程中對每個實例在取5 個不同值時獨立計算30 次，種群大小設=50，迭代次數(shù)=3。

表2 中列出了Kruskal-Wallis 檢驗的結果，指標表示取值對計算結果的影響情況，當≥0.05 時表示取值對實驗結果影響較小，否則表示取值對實驗結果影響較大。秩和檢驗對應的盒圖見圖2，其中橫坐標表示參數(shù)的五種不同取值，縱坐標表示NDDE 求得的最好值。

表2 秩和檢驗結果Table 2 Results of Kruskal-Wallis test

從表2 中可以看出：在利用NDDE 求解4 個實例時，的值遠遠小于0.05，這說明參數(shù)取值對于求解結果影響非常明顯。從圖2 中可以看出，當參數(shù)取值為0.2 時，NDDE 求解=500 的D{0-1}KP 實例的求解性能最好。

圖2 UDKP5、WDKP5、SDKP5 和IDKP5 實例的盒圖Fig.2 Boxplots of instances UDKP5,WDKP5,SDKP5 and IDKP5

綜上，通過利用NDDE 求解D{0-1}KP 問題中4個不同類型的實例，根據(jù)Kruskal-Wallis 秩和檢驗結果可以確定，NDDE 中=0.5 是最佳的。NDDE 中交叉因子和縮放因子均類似于上述方法確定其最優(yōu)取值。

3.3 計算結果與分析

本節(jié)中，對NDDE、GTOA、RTEA、HTLBO2、FirEGA和SecEGA求解D{0-1}KP 的計算結果進行比較和分析，在表3 中給出了上述7 個算法的具體參數(shù)設置。其中為種群規(guī)模；為迭代次數(shù)；為各算法對每個D{0-1}KP 實例獨立計算次數(shù)。在NDDE 中，為交叉因子，為縮放因子，[-,]為個體對應的實向量的取值空間。在GTOA 和RTEA 中，為變異概率。在DWOA 中，是一個定義螺旋形狀的常數(shù)。在HTLBO2 中，為保留因子，為影響因子。在FirEGA 和SecEGA 中，為交叉概率，為變異概率。

表3 算法的參數(shù)設置Table 3 Setting of algorithm parameters

記、、和分別為各算法在30次獨立計算中得到的結果的最好值、最差值、平均值和標準差；表示實例可以求到的最優(yōu)值。在表4～表7 中給出了各算法求解4 類D{0-1}KP 實例的計算結果，其中表現(xiàn)最好的算法用加粗標示，并根據(jù)表4～表7 中的計算結果比較了NDDE、GTOA、RTEA、HTLBO2、DWOA、FirEGA 和SecEGA 7 個算法求解D{0-1}KP 性能的優(yōu)劣。

從表4 中可以看出：對于UDKP 類實例，NDDE對于6 個實例UDKP1～UDKP6 均能求得最優(yōu)值，對于4 個大規(guī)模實例UDKP7～UDKP10 盡管不能求得最優(yōu)值，但、和3 個指標均優(yōu)于其他6 個算法。GTOA 和RTEA 的求解性能僅次于NDDE，可以求得3 個小規(guī)模實例UDKP1～UDKP3 的最優(yōu)值，但是對于大規(guī)模實例的計算結果不盡人意。其他4 個算法對于UDKP 實例的計算結果較差，均不能求解任一實例的最優(yōu)值。

表4 NDDE 和其他算法求解UDKP 類實例的計算結果Table 4 Calculation results by NDDE and other algorithms for UDKP instances

從表5 中可以看出：對于WDKP 類實例，除實例WDKP8 以外，對于其他9 個實例均能求得最優(yōu)值，求精精度遠遠高于其他6 個算法。GTOA 可以求得5 個實例的最優(yōu)值，其求解性能僅次于NDDE。RTEA 對于小規(guī)模實例的計算結果較好，對于大規(guī)模實例的求解精度變差。4 個算法HTLBO2、DWOA、FirEGA和SecEGA 的求解性能依然和其他算法有一定差距。

表5 NDDE 和其他算法求解WDKP 類實例的計算結果Table 5 Calculation results by NDDE and other algorithms for WDKP instances

表5 （續(xù)）

從表6 中可以看出：對于SDKP 類實例，NDDE 對于實例SDKP1 和SDKP4 的計算結果較差，對于其他實例而言，等指標均優(yōu)于其他算法。GTOA 對于小規(guī)模實例的計算結果具有一定競爭力，但是對于大規(guī)模實例的計算結果較差。RTEA、HTLBO2 和DWOA 等5 個算法對于SDKP 類實例的求解性能不能令人滿意。

表6 NDDE 和其他算法求解SDKP 類實例的計算結果Table 6 Calculation results by NDDE and other algorithms for SDKP instances

從表7 中可以看出：對于IDKP 類實例，NDDE 不僅可以求得所有實例的最優(yōu)值，而且其值遠遠高于其他算法，魯棒性更佳。其次求解性能較好的是HTLBO2 和GTOA，分別有6 個和5 個實例可以求得最優(yōu)值。RTEA 和DWOA 在求解小規(guī)模實例時也獲得了較好的計算結果。FirEGA 和SecEGA 的總體求解性能最差。

表7 NDDE 和其他算法求解IDKP 類實例的計算結果Table 7 Calculation results by NDDE and other algorithms for IDKP instances

總體來說，對于40 個D{0-1}KP 實例，NDDE 有28 個實例可以求得最優(yōu)值，求得最優(yōu)值數(shù)量至少為其他算法的兩倍。從來看，除SDKP1 實例外，NDDE 對于其他39 個D{0-1}KP 實例求得的均優(yōu)于其他算法；從來看，除SDKP1 和SDKP4 實例外，NDDE求得的值更優(yōu)。綜上所述，從、和3 個指標可以說明，對于D{0-1}KP 問題，NDDE遠比GTOA、RTEA、HTLBO2、DWOA、FirEGA 和SecEGA 的求解性能優(yōu)，不僅求解精度更高，且穩(wěn)定性更佳。

為了更直觀地比較各算法的平均性能和穩(wěn)定性，在圖3 中給出了NDDE、GTOA、RTEA 和HTLBO2 的擬合曲線。在圖4中給出了NDDE、GTOA、RTEA和HTLBO2 的對應的直方圖。由于DWOA、FirEGA 和SecEGA 計算結果較差，在圖3 和圖4 中沒有給出三種算法的擬合曲線和對應的直方圖。其中為最優(yōu)值與平均值之間的相對差值，見式（8）。擬合曲線越接近橫軸，算法的平均性能越好。根據(jù)擬合曲線和直方圖對NDDE、GTOA、RTEA 和HTLBO2 進一步進行比較。

圖4 4 類D{0-1}KP 實例的Std 直方圖Fig.4 Std histogram of 4 types of D{0-1}KP instances

從圖3（a）可以看出：對于第一類UDKP 實例，NDDE 的擬合曲線始終是與軸趨于重合的，且不大于0.050，明顯優(yōu)于其他3 個算法。GTOA 在求解實例UDKP8、UDKP9 的結果較差，對于其他實例的計算結果優(yōu)于RTEA 和HTLBO2；RTEA 在求解實例UDKP1，UDKP7～UDKP9 的結果較差，對其他實例的計算結果較好；HTLBO2 在求解實例UDKP1，UDKP7～UDKP9的結果較好，而對于其他實例的計算結果要差于其他算法。

從圖3（b）可以看出：對于第二類WDKP 實例，NDDE 的值除實例WDKP1 的計算結果大于0.010 外，對于其他實例的值均小于0.005，明顯優(yōu)于其他3 個算法；其次是GTOA 和RTEA，對于第二類WDKP 實例的值均小于0.020；HTLBO2 的計算結果最差，除實例WDKP1 外，對于其他實例的值均大于0.020。

圖3 4 類D{0-1}KP 實例的Gap 曲線Fig.3 Gap curves of 4 types of D{0-1}KP instances

從圖3（c）可以看出：對于第三類SDKP 實例，NDDE 在求解實例SDKP1 和SDKP4 的結果較差，對于其他實例的計算結果均優(yōu)于其他3個算法。GTOA在求解實例SDKP7～SDKP10 的結果較差，對于其他實例的計算結果均優(yōu)于RTEA 和HTLBO2，由此可見，GTOA 不適合求解SDKP 類實例中的大規(guī)模實例。HTLBO2 求解實例SDKP1 的結果較好，而對于其他實例的計算結果較差。

從圖3（d）可以看出：對于第四類IDKP實例，NDDE的擬合曲線始終是與軸趨于重合的，明顯優(yōu)于其他3 個算法。其次是HTLBO2，與前三類實例不同，HTLBO2 的計算結果較好，優(yōu)于GTOA 和RTEA。RTEA在求解第四類IDKP實例的計算結果最差。

從圖4 中可以看出，對于4 類D{0-1}KP 實例，NDDE 的算法穩(wěn)定性總體來說比GTOA、RTEA、HTLBO2、FirEGA 和SecEGA 的均優(yōu)；雖然對于實例SDKP1、SDKP2、SDKP4 和IDKP6，NDDE 的穩(wěn)定性較差，但是對于其他36 個實例，NDDE 的穩(wěn)定性明顯要比其他算法的優(yōu)。

綜上所述，對于D{0-1}KP問題，NDDE比GTOA、RTEA、HTLBO2、FirEGA 和SecEGA 的求解結果更優(yōu)，算法的穩(wěn)定性更佳。因此，NDDE 是一種非常適于求解D{0-1}KP 的高效演化算法。

4 結束語

本文首先介紹了四種S 型轉換函數(shù)和四種V 型轉換函數(shù)，然后提出了一種新V 型轉換函數(shù)（NV）。在此基礎上，提出了一種基于NV 的離散差分演化算法（NDDE）。為了驗證NDDE 的求解性能，本文通過求解4 類大規(guī)模D{0-1}KP 實例來證明算法的探索能力和開發(fā)能力，通過與已有算法的計算結果比較表明：NDDE 比GTOA、RTEA、HTLBO2、FirEGA 和SecEGA的求解結果更優(yōu)，算法的穩(wěn)定性更佳，是求解D{0-1}KP 的一個高效算法。

顯而易見，本文提出的基于新V 型轉換函數(shù)的離散差分演化算法求解D{0-1}KP 是非常成功的。因此在未來研究中，將探索新V 型轉換函數(shù)對其他算法的影響，如灰狼優(yōu)化算法（grey wolf optimizer，GWO）和鯨魚優(yōu)化算法（whale optimization algorithm，WOA）等。此外，由于設施選址問題（facility location problem，F(xiàn)LP）和集合覆蓋問題（set coverage problem，SCP）等類似于D{0-1}KP，它們可行解中0 和1 概率分布也是不均勻的，因此將進一步考慮利用NDDE 求解FLP和SCP。