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

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

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

2.石家莊文化傳媒學校，石家莊050000

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

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

借鑒文獻[13-14]中設計算法的思路，本文采用模運算直接離散化MVO算法，利用局部搜索策略和精英策略提高算法的局部搜索性能，提出一個離散混合多宇宙優化算法（Discrete Hybrid Multi-verse Optimization Algorithm，DHMVO）。為了利用DHMVO求解D{0-1}KP問題，基于D{0-1}KP的第二數學模型對個體采用整型向量編碼，并利用文獻[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算法的計算結果進行對比，驗證了DHMVO的高效性與魯棒性。

1 MVO算法

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

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

（1）隧道模型

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

（2）蟲洞模型

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

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

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

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

2離散混合MVO算法

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

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

2.1 新隧道模型

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

通過式（5）與式（1）的對比可以看出，新隧道模型不再需要通過輪盤賭機制獲得第j個維度的值，而是利用差分進化算法的突變策略“DE/rand/1”來獲得。在輪盤賭機制中，適應值更好個體通過自身占有的權重獲得更多輸出個體信息的機會，加速了收斂。而“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）的對比可以看出，新蟲洞模型本質上是原蟲洞模型的一種通過模運算直接離散化的版本。在原蟲洞模型中，當r2

2.3 DHMVO的算法偽代碼

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

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

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

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

算法1 DHMVO

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

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

3.1 D{0-1}KP的第二數學模型

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的第二數學模型[7]進行求解，其數學模型如下：其中，X=[x0,x1,…,xn-1]∈{0,1,2,3}n為一個n維整型向量，[x]為頂函數，整型變量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的一個潛在解，只有當它滿足約束條件（10）時才是一個可行解。

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

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

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

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

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

4 實驗結果與分析

4.1 實驗環境和D{0-1}KP實例

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

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

4.2 參數設置

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

從表1中可以看出，在利用DHMVO求解n=500的實例SDKP5和UDKP5時，p_value值遠小于0.05，即參數pl的取值對求解性能有明顯的影響，而在求解WDKP5和IDKP時則影響不大。通過圖2也可以看出，在pl=0.005時，算法DHMVO求解n=500實例的平均性能最好，所以在求解其他規模的D{0-1}KP實例時均設置局部搜索概率為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和其他算法的參數設置在表2中給出。N為種群大小，MIT為最大迭代次數。其他各算法參數含義見文獻[7-15]。

表2 參數設置Table 2 Parameter settings

4.3 DHMVO與已有算法的比較

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

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

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

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

表3 DHMVO和其他算法求解UDKP類實例的計算結果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個統計量均是最好的。下面給出算法DHMVO求解上述7個實例的求解結果。在求解實例UDKP3、UDKP4、UDKP5時，DHMVO的Gap<0.04，與求解性能最好的GTOA的Gap差值最大不超過0.006，在7個算法中，對這三個實例的求解性能僅次于GTOA。在求解實例WDKP6、WDKP7、WDKP8和SDKP1時，DHMVO的Gap在7個算法中最小，只有最優值未到達最好值，但與實例最好值OPT的差值最大不超過10。

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

為了更直觀地比較計算結果，通過Gap圖和Std直方圖比較DHMVO、HBDE、HTLBO2、GPSO、GTOA和RTEA的求解性能（由于DWOA的計算結果明顯比其他算法的差，因此不再與其對比）。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類實例的計算結果Table 4 Experimental results by DHMVO and other algorithms for WDKP instances

表5 DHMVO和其他算法求解SDKP類實例的計算結果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的求解性能相當，但GTOA略好，兩者性能僅次于DHMVO，算法HTLBO2的性能居于第四名，GPSO和HBDE最差。

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

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

5 結束語

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