基于離散混合多宇宙算法求解折扣{0-1}背包問題

郝 翔，賀毅朝，朱曉斌，翟慶雷

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

2.石家莊文化傳媒學(xué)校，石家莊050000

0-1背包問題（0-1 Knapsack Problem，0-1 KP）[1-2]既是一個典型的組合優(yōu)化問題，也是一個NP-hard問題[3-4]，在資源分配、項目組合和整數(shù)規(guī)劃等領(lǐng)域具有廣泛的應(yīng)用。折扣{0-1}背包問題（Discounted{0-1}Knapsack Problem，D{0-1}KP）[5]是由Guldan首次提出的一個0-1KP擴展形式，在商業(yè)領(lǐng)域有著重要的應(yīng)用背景。2007年，Guldan[5]建立了D{0-1}KP的基本數(shù)學(xué)模型，并給出了求解它的動態(tài)規(guī)劃算法；隨后，Rong等人[6]基于D{0-1}KP的核問題和動態(tài)規(guī)劃法研究了D{0-1}KP的求解算法。以上兩算法均為精確算法，存在求解速度慢的缺點。賀毅朝等人[7]基于整數(shù)編碼和集合編碼分別給出了D{0-1}KP的第二數(shù)學(xué)模型和第三數(shù)學(xué)模型，首先提出了基于演化算法求解D{0-1}KP問題的新思路，并給出了利用遺傳算法求解的新方法。隨后，吳聰聰?shù)热薣8]利用變異蝙蝠算法（MDBBA）提出了求解D{0-1}KP的方法，劉雪靜等人[9]利用自適應(yīng)細(xì)菌覓食算法（ABFO）求解D{0-1}KP問題，馮艷紅等人[10]利用差分進化帝王蝶優(yōu)化算法（DEMBO）求解D{0-1}KP問題，Li等人[11]提出了利用離散鯨魚優(yōu)化算法（DWOA）求解D{0-1}KP問題。這四種算法的求解效果較遺傳算法有了進一步提高。2017年，Zhu等人[12]基于離散差分進化算法HBDE提出了求解D{0-1}KP問題的新方法，并與基于整數(shù)編碼的兩種差分進化算法FDDE和SDDE進行比較，證明了HBDE算法的優(yōu)越性。最近，He等人[13]提出了基于群論的優(yōu)化算法（GTOA），并利用GTOA求解D{0-1}KP問題，隨后He等人[14]又提出了基于環(huán)論的優(yōu)化算法（RTEA）求解折扣背包問題的新方法，取得了更好的求解效果。2020年，Wu等人[15]針對D{0-1}KP問題提出了一類離散混合教學(xué)優(yōu)化算法（HTLBO），并指出采用差分進化交叉策略的HTLBO2算法具有更好的求解性能。

不難發(fā)現(xiàn)，由于精確算法在求解大規(guī)模D{0-1}KP實例時存在時間復(fù)雜度高，執(zhí)行速度慢，時效性差等缺點，人們往往采用非精確算法求解。演化算法是一類具有隨機近似性的非精確算法，具有算法簡單、通用性強和易于實現(xiàn)等優(yōu)點，已被廣泛用于求解具有較大難度的連續(xù)型與離散型優(yōu)化問題（組合優(yōu)化問題）[2，16-17]。多宇宙算法（Multi-verse Optimization Algorithm，MVO）是Mirjalili等人[18]于2016年提出的一個新穎演化算法，目前已被成功應(yīng)用于工程優(yōu)化和機器學(xué)習(xí)領(lǐng)域[19-23]。如Abasi等人[24]提出了一個基于鏈接的改進多宇宙算法LBMVO來求解文本文檔聚類問題，通過與原始MVO算法以及其他經(jīng)典的聚類算法在求解文檔聚類標(biāo)準(zhǔn)數(shù)據(jù)集的結(jié)果對比，證明了LBMVO算法的高效性。Abdel-Basset等人[25]提出了一個帶有重疊探測的改進多宙算法求解無線傳感器網(wǎng)絡(luò)部署問題。除此之外，多宇宙算法還被成功地用在石油消耗預(yù)測[26]，圖像處理[27]等問題中。由于原始MVO算法只適用于求解連續(xù)型優(yōu)化問題，不能直接求解組合優(yōu)化問題，因此不能用于求解D{0-1}KP問題。為此，本文提出MVO的一個離散版本，使之能夠用于組合優(yōu)化問題的求解。

借鑒文獻[13-14]中設(shè)計算法的思路，本文采用模運算直接離散化MVO算法，利用局部搜索策略和精英策略提高算法的局部搜索性能，提出一個離散混合多宇宙優(yōu)化算法（Discrete Hybrid Multi-verse Optimization Algorithm，DHMVO）。為了利用DHMVO求解D{0-1}KP問題，基于D{0-1}KP的第二數(shù)學(xué)模型對個體采用整型向量編碼，并利用文獻[7]中提出的算法NROA處理不可行解，提出了求解D{0-1}KP問題的一個新方法。最后，將算法DHMVO與FirEGA[7]、SecEGA[7]、DEMBO[10]、DWOA[11]、HBDE[12]、GPSO[13]、GTOA[13]、RTEA[14]和HTLBO2[15]等已有求解D{0-1}KP算法的計算結(jié)果進行對比，驗證了DHMVO的高效性與魯棒性。

1 MVO算法

多宇宙算法（MVO）是由Mirjalili等人[18]于2016年提出的一個新穎演化算法，并且已經(jīng)在數(shù)值優(yōu)化、復(fù)雜工程問題和機器學(xué)習(xí)方面有了成功的應(yīng)用[19-23]。MVO算法啟發(fā)于宇宙學(xué)中的三個基本概念：白洞、黑洞和蟲洞，通過建立白洞和黑洞間的隧道模型去提高算法的探索性能，然后通過蟲洞模型去模擬開發(fā)性能，保持了算法在探索和開發(fā)方面的平衡。在多宇宙算法中，每一個個體被稱為宇宙，個體的適應(yīng)度被稱為宇宙的膨脹率，膨脹率高的宇宙被稱為白洞，膨脹率低的宇宙被稱為黑洞。

為了便于闡述如何利用MVO求解連續(xù)型優(yōu)化問題，不失一般性，設(shè)maxg(X),X=[x1,x2,…,xn]∈Ω是一個最大優(yōu)化問題和ubj是個體X中的每一維分量的上界和下界。下面分別介紹MVO的隧道模型和蟲洞模型。

（1）隧道模型

隧道模型建立在白洞和黑洞之間，膨脹率較高的白洞通過隧道發(fā)送自身宇宙的某一個維度的物品給膨脹率較低的黑洞個體，并由黑洞接收。隧道模型的基本步驟如下：首先基于宇宙的膨脹率對宇宙進行排序并執(zhí)行標(biāo)準(zhǔn)化操作，然后根據(jù)宇宙標(biāo)準(zhǔn)膨脹率的大小對宇宙的每一個維度作如下操作：

（2）蟲洞模型

蟲洞模型建立在當(dāng)前宇宙與到目前為止的最好宇宙之間，該模型是在不考慮宇宙的膨脹率的前提下改變當(dāng)前宇宙的每一個維度的值，具體的公式如下：

其中，l是指當(dāng)前迭代次數(shù)，L是最大的迭代次數(shù)，min和max是WEP的最小和最大值。p是探索系數(shù)，更大的p值，會有更快和更精確的開發(fā)和局部搜索性能。也可以看出，WEP隨著迭代次數(shù)的增大而增大，TDR隨著迭代次數(shù)的增大而減小。

原始MVO通過順序的執(zhí)行式（1）、（2）生成下一代N個體的每一個維度的值，然后通過記錄到目前為止的最好的個體來獲得目標(biāo)函數(shù)的最優(yōu)解和最優(yōu)值。即由MVO進化算子產(chǎn)生的新個體Xi(t+1),(1≤i≤N)可能不一定比上一代的個體更好，這種策略雖然提高了算法的探索性能，但是有可能會導(dǎo)致算法的收斂性較差。同時原始MVO算法不能直接求解組合優(yōu)化問題。

由文獻[18]知，當(dāng)種群規(guī)模N，迭代次數(shù)MIT以及g(X)的時間復(fù)雜度O(g(X))均是n的線性函數(shù)時，MVO的時間復(fù)雜度為O(n3)。因為篇幅限制，不再給出MVO的算法偽代碼，具體請見文獻[18]。

2離散混合MVO算法

為了利用MVO求解組合優(yōu)化問題，下面基于文獻[13-14]中利用模運算設(shè)計離散進化算子的方法，借鑒差分進化算法[28-29]的變異策略提出離散型隧道模型和蟲洞模型，在引入局部搜索策略和精英策略[14]的基礎(chǔ)上，提出一個離散型混合多宇宙算法（DHMVO）。

不失一般性，令maxh(X),X=[x1,x2,…,xn]∈{0,1,2,3}n是一個最大優(yōu)化問題。下面依次給出DHMVO的算法原理與算法偽代碼描述。

2.1 新隧道模型

在DHMVO中，采用差分進化算法的突變策略“DE/rand/1”和模運算來對原始MVO算法的隧道模型進行修改，具體如式（5）所示：

通過式（5）與式（1）的對比可以看出，新隧道模型不再需要通過輪盤賭機制獲得第j個維度的值，而是利用差分進化算法的突變策略“DE/rand/1”來獲得。在輪盤賭機制中，適應(yīng)值更好個體通過自身占有的權(quán)重獲得更多輸出個體信息的機會，加速了收斂。而“DE/rand/1”策略則通過三個個體間的組合運算來獲得維度值，盡可能地利用了種群中每個個體，增加了算法的探索性能。

2.2 新蟲洞模型

在DHMVO中，則采用突變策略“DE/best/1”和模運算來對原始MVO算法的蟲洞模型進行修改，具體如式（6）所示：

在本文中，WEP的取值范圍由0.2線性增大為0.6，TDR的取值范圍由0.5線性減小為0。

通過式（6）可以看出，DHMVO的下一代種群在算法迭代的早期趨向于臨時個體Y(t)，在迭代中期趨向于在最好個體XB(t)的周圍進行局部搜索后得到的個體，在迭代后期則趨向于最好個體XB(t)。

通過式（6）與式（2）的對比可以看出，新蟲洞模型本質(zhì)上是原蟲洞模型的一種通過模運算直接離散化的版本。在原蟲洞模型中，當(dāng)r2

2.3 DHMVO的算法偽代碼

為了提高算法的收斂速度與求解效率，在DHMVO中引入局部搜索策略（Ring-based Local Development Operator，R-LDO）[14]，該策略融合了反向搜索策略和突變策略，具體的操作算子如公式（8）所示：

其中，MX為一個固定常數(shù)，本文MX=4,r4和r5是[0，1]的隨機數(shù)，rand({0,1,2,3})表示隨機選取{0，1，2，3}中的一個整數(shù)，pl表示局部搜索概率。

順序的執(zhí)行新隧道模型、新蟲洞模型以及R-LDO構(gòu)成了離散的混合多宇宙算法DHMVO。設(shè)N為DHMVO的種群規(guī)模，MIT為最大迭代次數(shù)，P(t)={Xi(t)|1≤i≤N}表示DHMVO的第t代種群，pl為局部搜索概率。表示P(MIT)最好個體對應(yīng)的解，Y(t)=(y1(t),y2(t),…,yn(t))為由式（5）、（6）和（8）產(chǎn)生的臨時個體。則對于最大優(yōu)化問題maxh(X)，在算法1和圖1中分別給出算法DHMVO的偽代碼和流程圖。

圖1算法DHMVO的流程圖Fig.1 Flow chart of algorithm DHMVO

算法1 DHMVO

記O(h)為計算h(Xi(t))的時間復(fù)雜度，則DHMVO的時間復(fù)雜度為O(h)+O(MIT×N×(n+O(h)))。顯然，當(dāng)N、MIT和O(h)都是關(guān)于n的線性函數(shù)時，DHMVO的時間復(fù)雜度為O(n3)，與原MVO算法的時間復(fù)雜度相同，但是新算法DHMVO較原MVO算法有以下幾處優(yōu)點：一是新隧道模型利用差分進化算法的突變策略“DE/rand/1”提高了算法的探索性能，并使之可以直接求解組合優(yōu)化問題；二是通過模運算和突變策略“DE/best/1”直接離散化原蟲洞模型，獲得與原模型相同含義的新模型；三是采用局部搜索策略R-LDO來提高算法的探索性能；四是算法采用精英策略，確保進化產(chǎn)生的下一代個體總是比原個體更好，使收斂速度進一步提高。

3 基于DHMVO求解D{0-1}KP問題

3.1 D{0-1}KP的第二數(shù)學(xué)模型

D{0-1}KP的定義[5，7]：給定n個項集，每一個項集i∈{0,1,…,n-1}均含3項3i、3i+1和3i+2；其中項3i的價值和重量分別為p3i和w3i，項3i+1的價值和重量分別為p3i+1和w3i+1，項3i+2的價值和重量分別為p3i+2和w3i+2，其中p3i+2是p3i和p3i+1的和，w3i+2分別大于w3i和w3i+1，但小于w3i和w3i+1的和；同時每一項集中至多有一項可以被裝入背包。D{0-1}KP問題的目的是如何選擇物品裝入背包，使得裝入背包的所有物品的重量之和在不超過背包載重C的前提下價值之和最大。

本文基于D{0-1}KP的第二數(shù)學(xué)模型[7]進行求解，其數(shù)學(xué)模型如下：其中，X=[x0,x1,…,xn-1]∈{0,1,2,3}n為一個n維整型向量，[x]為頂函數(shù)，整型變量xi(0≤i≤n-1)的取值表示項集i中是否存在項被裝入背包，xi=0表示項集i中沒有項被裝入了背包，xi=1和xi=2分別表示項3i和項3i+1被裝入了背包，xi=3表示項3i+2被裝入了背包。需要注意的是整型向量X僅為D{0-1}KP的一個潛在解，只有當(dāng)它滿足約束條件（10）時才是一個可行解。

3.2 基于DHMVO求解D{0-1}KP的方法

在利用演化算法求解D{0-1}KP問題中不可避免地會產(chǎn)生不可行解，為了提高算法求解效率，本文采用文獻[7]中提出的基于貪心策略的修復(fù)與優(yōu)化算法NROA來處理不可行解，下面首先介紹NROA的基本原理，然后在算法2中給出基于DHMVO求解D{0-1}KP的算法偽代碼。

在NROA中，首先根據(jù)價值密度pj/wj(0≤j≤3n-1)由大到小將3n個項排序，并存儲到數(shù)組H[0,1,…,3n-1]中；然后計算當(dāng)前個體X中已裝入背包的項的重量和，并判斷其是否超過背包載重C。當(dāng)不滿足載重C（即約束條件式（10））時對個體X進行修復(fù)操作，即嘗試從背包中依次取出價值密度最小的項，直到滿足式（10）的約束條件為止；然后嘗試對個體X進行優(yōu)化處理，即當(dāng)背包中還有剩余的容量時，嘗試向背包中加入還未裝入背包且價值密度最大的物品項，直到所有物品項均被嘗試完畢為止。算法NROA的偽代碼請參考文獻[7]，不再贅述。

算法2 DHMVO for D{0-1}KP

由文獻[7]知，NROA的時間復(fù)雜度為O(n)。在算法2中，步驟1由快速排序算法實現(xiàn)，時間復(fù)雜度為O(nlbn)；步驟2、3的時間復(fù)雜度分別為O(Nn)和O(n)；步驟7的時間復(fù)雜度為O(N)；步驟9~13的時間復(fù)雜度均為O(n)；步驟5~20的時間復(fù)雜度為O(MIT×N×n)。因此，當(dāng)MIT和N都是n的一次多項式時，算法DHMVO的時間復(fù)雜度為O(n3)。

4 實驗結(jié)果與分析

4.1 實驗環(huán)境和D{0-1}KP實例

本文采用具有Intel?CoreTMi5-8300H CPU@2.3 GHz和8 GB的RAM的微型計算機，編程語言為C，編譯環(huán)境為Codeblocks 17.12，使用Python在編譯環(huán)境JetBrains PyCharm 2018.3上繪圖。

D{0-1}KP實例來自于文獻[14]中提供的公開數(shù)據(jù)集，其中四類實例分別是不相關(guān)D{0-1}KP實例（UDKP）、弱相關(guān)D{0-1}KP實例（WDKP）、強相關(guān)D{0-1}KP實例（SDKP）和逆強相關(guān)D{0-1}KP實例（IDKP），每一類實例都包含10個實例，實例規(guī)模3n∈{300,600,…,3 000},所有實例數(shù)據(jù)見網(wǎng)址https：//www.researchgate.net/project/Four-kinds-ofD0-1-KP-instances。

4.2 參數(shù)設(shè)置

為了與已有求解D{0-1}KP的算法DWOA[11]、HBDE[12]、GPSO[13]、GTOA[13]、RTEA[14]和HTLBO2[15]的計算結(jié)果進行公平比較（由于FirEGA[7]、SecEGA[7]和DEMBO[10]的求解性能太差，不再與之進行比較），在DHMVO算法中，設(shè)置DHMVO的種群大小為20，迭代次數(shù)為12×n，其中n為項集的個數(shù)。由算法2知，參數(shù)WEP和TDR均由迭代次數(shù)自適應(yīng)計算得出，所以僅有局部搜索概率pl影響算法DHMVO的性能。因此本節(jié)將通過分析算法DHMVO求解n=500的四個D{0-1}KP實例的計算結(jié)果來確定參數(shù)pl的合理取值，其中每一個實例獨立計算50次，pl分別取0.001、0.003、0.005、0.007、0.009。利用Kruskal-Wallis檢驗[30]比較數(shù)據(jù)的優(yōu)劣。表1給出了算法DHMVO在不同參數(shù)下求解4個D{0-1}KP實例的秩和檢驗表，圖2為DHMVO在不同pl值下求解4個D{0-1}KP實例的性能比較圖。

從表1中可以看出，在利用DHMVO求解n=500的實例SDKP5和UDKP5時，p_value值遠(yuǎn)小于0.05，即參數(shù)pl的取值對求解性能有明顯的影響，而在求解WDKP5和IDKP時則影響不大。通過圖2也可以看出，在pl=0.005時，算法DHMVO求解n=500實例的平均性能最好，所以在求解其他規(guī)模的D{0-1}KP實例時均設(shè)置局部搜索概率為pl=0.005。

表1 DHMVO在不同pl值下求解n=500四個實例的秩和檢驗表Table 1 Rank and test table of DHMVO for four instances with n=500 under different pl

圖2 DHMVO求解n=500的四個D{0-1}KP實例的性能比較Fig.2 Performance comparison of DHMVO for four instances with n=500

算法DHMVO和其他算法的參數(shù)設(shè)置在表2中給出。N為種群大小，MIT為最大迭代次數(shù)。其他各算法參數(shù)含義見文獻[7-15]。

表2 參數(shù)設(shè)置Table 2 Parameter settings

4.3 DHMVO與已有算法的比較

本節(jié)將利用算法DHMVO求解四類大規(guī)模D{0-1}KP實例，每個實例獨立計算50次，并與HBDE[12]、DWOA[11]、GPSO[13]、GTOA[13]、RTEA[14]和HTLBO2[15]等算法的計算結(jié)果進行比較，在表3~表6中分別給出上述算法求解UDKP類實例、WDKP類實例、SDKP類實例以及IDKP類實例的結(jié)果。其中OPT是該實例的最好值，Best、Mean、Worst、Std分別是上述算法在運行50次中得到的最優(yōu)值、平均值、最差值以及標(biāo)準(zhǔn)差，Gap由OPT和Mean計算得到，其計算方法見式（12）：

表6 DHMVO和其他算法求解IDKP類實例的計算結(jié)果Table 6 Experimental results by DHMVO and other algorithms for IDKP instances

顯然Gap≥0,Gap越接近0，表明算法的求解性能越好。此外，為了方便比較，將同一個統(tǒng)計量中最好的值用黑體加粗表示，將無數(shù)據(jù)的部分用“—”表示。

從表3~6中可以看出以下兩點：

表3 DHMVO和其他算法求解UDKP類實例的計算結(jié)果Table 3 Experimental results by DHMVO and other algorithms for UDKP instances

（1）對UDKP類、WDKP類和SDKP類的30個實例，除了實例UDKP3、UDKP4、UDKP5、WDKP6、WDKP7、WDKP8和SDKP1外，DHMVO求解其他的23個D{0-1}KP實例時，5個統(tǒng)計量均是最好的。下面給出算法DHMVO求解上述7個實例的求解結(jié)果。在求解實例UDKP3、UDKP4、UDKP5時，DHMVO的Gap<0.04，與求解性能最好的GTOA的Gap差值最大不超過0.006，在7個算法中，對這三個實例的求解性能僅次于GTOA。在求解實例WDKP6、WDKP7、WDKP8和SDKP1時，DHMVO的Gap在7個算法中最小，只有最優(yōu)值未到達(dá)最好值，但與實例最好值OPT的差值最大不超過10。

（2）在求解IDKP類實例時，HTLBO2的求解性能最好，除實例IDKP外，共有9個實例的Gap值取得最小。算法DHMVO和GPSO的求解性能相當(dāng)，僅次于HTLBO2。在算法DHMVO中，除實例IDKP1的Gap值小于0.015外，DHMVO求解其他9個實例的Gap均不超過0.005，同時10個IDKP實例中除了實例IDKP7和IDKP8的最優(yōu)值未到達(dá)最好值外，其余的均已達(dá)到。總體而言，DHMVO在7個算法中的求解精度最佳，穩(wěn)定度最好，非常適合求解D{0-1}KP問題。

為了更直觀地比較計算結(jié)果，通過Gap圖和Std直方圖比較DHMVO、HBDE、HTLBO2、GPSO、GTOA和RTEA的求解性能（由于DWOA的計算結(jié)果明顯比其他算法的差，因此不再與其對比）。6個算法求解D{0-1}KP的Gap曲線圖和Std直方圖如圖3和圖4所示。

圖3 Gap擬合曲線Fig.3 Fitting curves of Gap

圖4 Std直方圖Fig.4 Std histograms

表4 DHMVO和其他算法求解WDKP類實例的計算結(jié)果Table 4 Experimental results by DHMVO and other algorithms for WDKP instances

表5 DHMVO和其他算法求解SDKP類實例的計算結(jié)果Table 5 Experimental results by DHMVO and other algorithms for SDKP instances

從圖3和圖4中可以看出，在利用6個算法求解D{0-1}KP實例時，DHMVO的Gap值和Std值總體上看均是最好的。

（1）在求解UDKP、WDKP和SDKP時，GTOA和RTEA的求解性能相當(dāng)，但GTOA略好，兩者性能僅次于DHMVO，算法HTLBO2的性能居于第四名，GPSO和HBDE最差。

（2）在求解IDKP時，HTLBO2最好，其次為DHMVO，GPSO性能居于第三名，之后求解性能好的算法依次為GTOA、RTEA和HBDE。

綜上所述，DHMVO是一個在10個算法中的求解性能最好，穩(wěn)定度最強，非常適合求解D{0-1}KP問題的高效算法。

5 結(jié)束語

本文提出了求解D{0-1}KP問題的一個離散混合多宇宙算法DHMVO。首先，基于模運算提出了新的隧道模型和蟲洞模型，并基于局部搜索策略和精英策略來平衡算法的探索與開發(fā)能力。然后，采用基于貪心策略的修復(fù)與優(yōu)化算法NROA處理D{0-1}KP的不可行解，基于DHMVO提出了求解D{0-1}KP的一種新方法。最后，將DHMVO求解四類大規(guī)模D{0-1}KP實例的計算結(jié)果與已有的求解算法FirEGA、SecEGA、DEMBO、HBDE、DWOA、HTLBO2、GPSO、GTOA和RTEA等的計算結(jié)果進行對比，驗證了DHMVO在求解D{0-1}KP問題時的高效性，并指出DHMVO不僅求解精度更高，而且穩(wěn)定性更強，是比其他算法更適合求解大規(guī)模D{0-1}KP實例的一種新的高效方法。