基于模運算的新穎離散差分演化算法求解多背包問題

摘 要：多背包問題（MKP）是一個求解難度極大的背包問題。為了基于差分演化（DE）求解MKP，首先建立了MKP的整數規劃模型，在利用模運算構造簡單且有效的新型傳遞函數基礎上，提出了一個新穎離散差分演化算法MODDE；基于貪心策略提出了消除MKP不可行解的一個有效算法GROA，由此利用MODDE給出了求解MKP的一種新方法。最后，利用MODDE求解30個國際通用的MKP實例，通過與四個代表性演化算法的比較表明，MODDE不僅計算結果優，而且算法的穩定性強，是求解MKP的一個高效算法。

關鍵詞：演化算法；差分演化；多背包問題；模運算

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001-3695（2023）08-014-2334-06

doi： 10.19734/j.issn.1001-3695.2023.01.0004

Novel discrete differential evolution algorithm based on modulo operation for

solving multiple knapsack problem

Wang Lina Zhang Hansong Sun Fei Gao Zexian He Yichao

（a. School of Information Engineering， b. Laboratory of Big Data amp; Computing Intelligence， Hebei GEO University， Shijiazhuang 050031， China）

Abstract：The multiple knapsack problem （MKP） is a special knapsack problem with great difficulty. In order to solve MKP by differential evolution （DE）， this paper firstly established the integer programming model of MKP. Based on a simple and efficient new transfer function based on modulo operation， it proposed a novel discrete differential evolution algorithm MODDE. Then， the method used an efficient algorithm GROA to eliminate the unfeasible solution of MKP by greedy strategy. Therefore， this paper proposed a new method for solving MKP based on MODDE. Finally， it used MODDE to solve 30 international instances of MKP. Comparing with 4 representative evolution algorithms show that MODDE not only has better calculation results， but also has stronger stability. It is indeed an efficient algorithm for solving MKP.

Key words：evolutionary algorithm; differential evolution; multiple knapsack problem; modulo operation

0 引言

背包問題［1，2］是一類經典的NP-難問題，也是一類著名的組合優化問題，在資源分配、車輛裝載、資金預算以及整數規劃和財務管理等領域［3］具有廣泛應用。多背包問題（multiple knapsack problem，MKP）是一種典型的背包問題，因求解難度極大，求解算法主要有精確算法和啟發式算法。精確算法雖然能夠求得MKP的最優解，但時間復雜度是指數階的，當問題的規模增大時會出現“組合爆炸”，導致算法消耗過多的時間而不適用于實時性要求較高的應用。啟發式算法雖然不能保證求得最優解，但在較短的時間內可以得到一個很好的近似解，而且能夠滿足實際應用中對求解時間的嚴格限制。

求解MKP的精確算法主要包括分支定界法和動態規劃法。例如， Martello等人［4］提出了基于“bound and bound”的樹搜索技術，利用該技術確定決策樹中的分支，從而提出了求解MKP的精確算法MTM。Pisinger［5］提出了一種新的可分離動態規劃算法MULKNAP，該算法不僅比MTM快，而且穩定性高。Fukunaga等人［6］基于物品分配到背包之間的支配性標準來修剪樹的節點，提出了求解MKP的一個新的分支定界算法。Fukunaga［7］利用優勢標準和對稱性破環策略與文獻［4］提出的邊界和邊界法技術相結合，提出了一種改進的分支定界算法。Sitarz［8］基于多準則動態規劃策略開發了求解MKP的一個動態規劃算法。

求解MKP的啟發式算法主要是演化算法（evolutionary algorithm，EA）［9］。例如，Khuri等人［10］提出了利用遺傳算法求解MKP的可行方法；Fukunaga［11］改進了文獻［10］的工作，提出了利用遺傳算法求解 MKP 的一種新方法，但該方法能提高物品價值與重量高度相關的 MKP 實例的求解效果。Ren等人［12］重新設計了粒子群優化的速度和位置更新方程，提出了利用離散粒子群優化求解 MKP的一個可行方法。Liu等人［13］基于整數編碼方法表示個體，探討了利用人工魚群算法（artificial fish swarm，AFS）求解 MKP 的可行性和有效性。李迎等人［14］在AFS算法中引入了動態視野與步長調整策略提高算法的精度，給出了利用AFS求解MKP的一種可行方法。 EA是一種基于自然選擇和遺傳變異等生物進化機制的全局搜索算法，具有自組織、自適應、自學習的特點，在不要求目標函數連續、可微與單峰的情況下能較快地求得問題的一個極好的近似解。常見的EA有遺傳算法（genetic algorithm，GA）［15］、差分演化算法（differential evolution，DE）［16］、粒子群優化算法（particle swarm optimization，PSO）［17］等，它們已被成功應用于求解背包問題［18～20］、可滿足性問題［21］和旅行商問題［22］等組合優化問題。

目前，利用EA求解 MKP 的研究成果不僅匱乏，而且已有方法存在穩定性差、求解效果不佳甚至是極差的缺陷。導致這些問題的原因主要有兩點：a）EA大多是針對連續優化問題提出的，雖然存在可行的離散化方法，但對于以整型向量為可行解的組合優化問題，現有離散化方法的效果不佳；b）在利用EA求解MKP的已有方法中，缺少對MKP不可行解進行處理的有效方法，甚至有些從未考慮過處理MKP的不可行解。因此，利用EA高效求解MKP是一個值得深入研究的課題，本文首先基于模運算提出一個新的離散DE，然后提出處理MKP不可行解的有效算法GROA，最后基于離散DE與GROA相結合給出求解MKP的一個新的高效方法。

1 背景知識

1.1 MKP定義與數學模型

1.2 差分演化算法

2 基于模運算的離散差分演化算法

2.1 新型傳遞函數

2.2 種群初始化

2.3 MODDE的進化原理

2.4 MODDE的算法偽代碼

3 利用MODDE求解MKP

4 計算結果和比較

4.1 實驗環境

4.2 三類MKP的實例

4.3 算法參數設置

4.4 計算結果與比較

記best、mean和stD分別為算法20次獨立計算得到結果的最好值、平均值和標準差。在表3～5中列出了各算法求解三類MKP實例的結果，其中的黑色加粗部分代表計算結果最好。

由表3可以看出，對于10個umkp類實例，在best方面，MODDE有8個實例的結果最好，DisPSO和RTEA有7個實例的結果最好，GA和GTOA只有6個實例的結果最好；在mean方面，MODDE有8個實例的結果最好，DisPSO和RTEA有3個實例的結果最好，而GA和GTOA只有2個實例的結果最好。

由表4可以看出，對于10個wmkp類實例，在best方面，MODDE有8個實例的結果最好，DisPSO有7個實例的結果最好，而GA、GTOA和RTEA只有4個實例的結果最好；在mean方面，MODDE有8個實例的結果最好，DisPSO有3個實例的結果最好，而GA、GTOA和RTEA只有1個實例的結果最好。

由表5可以看出，對于10個smkp類實例，在best方面，MODDE有10個實例的結果最好，GTOA有2個實例的結果最好，而DisPSO、GA和RTEA只有1個實例的結果最好；在mean方面，MODDE有10個實例的結果最好，而DisPSO、GA、GTOA和RTEA只有1個實例的結果最好。

為了比較MODDE、DisPSO、GA、GTOA和RTEA求解三類MKP實例的平均性能，圖4～6中利用Friedman秩和檢驗［32］對它們的mean值進行比較，從中不難看出，MODDE求解MKP實例的結果明顯優于DisPSO、GA、GTOA和RTEA。

在圖7～9中，利用直方圖對MODDE、DisPSO、GA、GTOA和RTEA的stD進行了比較。從圖7可以看出，對于10個umkp類實例，MODDE有6個實例的stD值為0，而DisPSO、GA、GTOA和RTEA只有2個實例的stD值為0，雖然對編號u4的實例MODDE的穩定性較差，但是對于其他9個實例，MODDE的stD值均比其他算法小，所以MODDE穩定性明顯要比其他算法的優。

從圖8不難看出，對于wmkp類的10個實例，MODDE有4個實例的stD值為0，而DisPSO、GA、GTOA和RTEA只有1個實例的stD值為0;雖然對編號w9的實例，MODDE的穩定性不是最好的，但是對于其他9個實例，MODDE的stD值均比其他算法小，穩定性明顯要比其他算法更優。

從圖9可以看出，對于smkp類的10個實例，MODDE的StD值都是最小的，所以MODDE的算法穩定性比DisPSO、GA、GTOA和RTEA的均優。

綜上所述，對于MKP，MODDE比DisPSO、GA、GTOA和RTEA的求解結果更優，算法的穩定性更佳。因此，MODDE是一種非常適于求解MKP的高效演化算法。

5 結束語

本文基于模運算提出了求解{0，1，2，…，m}n上組合優化問題的一種新型離散差分演化算法MODDE，在建立了MKP的整數規劃模型基礎上，提出了一種消除不可行解的貪心修復優化算法GROA，由此給出了利用MODDE求解MKP的一個新方法。通過與DisPSO、GA、GTOA和RTEA等離散演化算法對三類MKP實例的計算結果比較表明，MODDE是一個適用于求解MKP的高效演化算法。

注意到折扣{0-1}背包問題［19，20］是一個建模在{0，1，2，3}n上的組合優化問題，適合利用MODDE求解，因此如何基于MODDE高效求解折扣{0-1}背包問題是一個值得今后研究的問題。此外，由于MODDE可用于求解{0，1}n上的優化問題，自然可用于求解具有單連續變量的背包問題［28，33］和集合覆蓋問題［34］等二元優化問題。如何利用MODDE高效求解這兩個問題也是一個值得今后研究與探討的問題。

參考文獻：

［1］Kellerer H，Pferschy U，Pisinger D. Knapsack problems ［M］. Berlin： Springer-Verlag，2004.

［2］Martello S，Toth P. Knapsack problems： algorithms and computer implementations ［M］. New York：Wiley，1990.

［3］王熙照，賀毅朝. 求解背包問題的演化算法 ［J］. 軟件學報，2017，28（1）： 1-16. （Wang Xizhao，He Yichao. Evolutionary algorithms for knapsack problems ［J］. Journal of Software，2017，28（1）： 1-16.）

［4］Martello S，Toth P. A bound and bound algorithm for the zero-one multiple knapsack problem ［J］. Discrete Applied Mathematics，1981，3（4）： 275-288.

［5］Pisinger D. An exact algorithm for large multiple knapsack problems ［J］. European Journal of Operational Research，1999，114（3）： 528-541.

［6］Fukunaga A S，Korf R E. Bin completion algorithms for multicontainer packing，knapsack，and covering problems ［J］. Journal of Artificial Intelligence Research，2007，28（1）： 393-429.

［7］Fukunaga A S. A branch-and-bound algorithm for hard multiple knapsack problems ［J］. Annals of Operations Research，2011，184（1）： 97-119.

［8］Sitarz S. Multiple criteria dynamic programming and multiple knapsack problem ［J］. Applied Mathematics and Computation，2014，228（2）： 598-605.

［9］Leung K S，Duan Qihong，Xu Zongben，et al. A new model of simulated evolutionary computation-convergence analysis and specifications ［J］.IEEE Trans on Evolutionary Computation，2001，5（1）：3-16.

［10］Khuri S，Bck T，Heitktter J. The zero/one multiple knapsack problem and genetic algorithms ［C］// Proc of ACM Symposium on Applied Computing. New York： ACM Press，1994： 188-193.

［11］Fukunaga A S. A new grouping genetic algorithm for the multiple knapsack problem ［C］// Proc of IEEE Congress on Evolutionary Computation. Piscataway，NJ： IEEE Press，2008： 2225-2232.

［12］Ren Zihui，Wang Jian. A discrete particle swarm optimization for solving multiple knapsack problems ［C］// Proc of the 5th International Conference on Natural Computation. Piscataway，NJ： IEEE Press，2009： 166-170.

［13］Liu Qing，Odaka T，Kuroiwa J，et al. A new artificial fish swarm algorithm for the multiple knapsack problem ［J］. IEICE Trans on Information and Systems，2014，97（3）： 455-468.

［14］李迎，張璟，劉慶，等. 求解大規模多背包問題的高級人工魚群算法 ［J］. 系統工程與電子技術，2018，40（3）： 710-716. （Li Ying，Zhang Jing，Liu Qing，et al. Advanced artificial fish swarm algorithm for large scale multiple knapsack problem ［J］. Systems Enginee-ring and Electronics，2018，40（3）： 710-716.）

［15］陳國良，王熙法，莊鎮泉，等. 遺傳算法及其應用 ［M］. 北京： 人民郵電出版社，2003. （Chen Guoliang，Wang Xifa，Zhuang Zhen-quan，et al. Genetic algorithm and its application ［M］. Beijing： Posts amp; Telecom Press，2003. ）

［16］Storn R，Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces ［J］. Journal of Global Optimization，1997，11（4）： 341-359.

［17］Kennedy J，Eberhart R. Particle swarm optimization ［C］// Proc of International Conference on Neural Networks. Piscataway，NJ： IEEE Press，1995： 1942-1948.

［18］Gilmore P C，Gomory R E. The theory and computation of knapsack functions ［J］. Operations Research，1966，14（6）： 1045-1074.

［19］賀毅朝，王熙照，李文斌，等. 基于遺傳算法求解折扣{0-1}背包問題的研究 ［J］. 計算機學報，2016，39（12）： 2614-2630. （He Yichao，Wang Xizhao，Li Wenbin，et al. Research on genetic algorithms for the discounted {0-1} knapsack problem ［J］. Chinese Journal of Computers，2016，39（12）： 2614-2630.）

［20］張發展，賀毅朝，劉雪靜，等. 新穎的離散差分演化算法求解D{0-1}KP問題 ［J］. 計算機科學與探索，2022，16（2）： 468-479. （Zhang Fazhan，He Yichao，Liu Xuejing，et al. Novel discrete diffe-rential evolution algorithm for solving D{0-1} KP problem［J］. Journal of Frontiers of Computer Science amp; Technology，2022，16（2）： 468-479.）

［21］Gottlieb J，Marchiori E，Rossi C. Evolutionary algorithms for the satisfiability problem ［J］. Evolutionary Computation，2002，10（1）： 35-50.

［22］Maity S，Roy A，Maiti M. A modified genetic algorithm for solving uncertain constrained solid travelling salesman problems ［J］. Compu-ters amp; Industrial Engineering，2015，83（5）： 273-296.

［23］Dell’Amico M，Delorme M，Iori M，et al. Mathematical models and decomposition methods for the multiple knapsack problem ［J］. European Journal of Operational Research，2019，274（3）： 886-899.

［24］Tian Mengnan，Gao Xingbao. An improved differential evolution with information intercrossing and sharing mechanism for numerical optimization ［J］. Swarm and Evolutionary Computation，2019，50（11）： 100341.

［25］Joshi R，Sanderson A C. Minimal representation multisensor fusion using differential evolution ［J］. IEEE Trans on Systems，Man，and Cybernetics，Part A： Systems and Humans，1999，29（1）： 63-76.

［26］Ajithapriyadarsini S，Mary P M，Iruthayarajan M W. Automatic genera-tion control of a multi-area power system with renewable energy source under deregulated environment： adaptive fuzzy logic-based differential evolution （DE） algorithm ［J］. Soft Computing，2019，23（22）： 12087-12101.

［27］Abbass H A. An evolutionary artificial neural networks approach for breast cancer diagnosis ［J］. Artificial intelligence in Medicine，2002，25（3）： 265-281.

［28］He Yichao，Hao Xiang，Li Wenbin，et al. Binary team game algorithm based on modulo operation for knapsack problem with a single conti-nuous variable ［J］. Applied Soft Computing，2021，103（5）： 107180.

［29］賀毅朝，王熙照，趙書良，等. 基于編碼轉換的離散演化算法設計與應用 ［J］. 軟件學報，2018，29（9）： 2580-2594. （He Yichao，Wang Xizhao，Zhao Shuliang，et al. Design and applications of discrete evolutionary algorithm based on encoding transformation ［J］. Journal of Software，2018，29（9）： 2580-2594.）

［30］He Yichao，Wang Xizhao. Group theory-based optimization algorithm for solving knapsack problems ［J］. Knowledge-Based Systems，2021，219（5）： 104445.

［31］He Yichao，Wang Xizhao，Gao Suogang. Ring theory-based evolutio-nary algorithm and its application to D{0-1} KP ［J］. Applied Soft Computing，2019，77（4）： 714-722.

［32］Derrac J，García S，Molina D，et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms ［J］. Swarm and Evolutionary Computation，2011，1（1）： 3-18.

［33］王澤昆，賀毅朝，李煥哲，等. 基于新穎S型轉換函數的二進制粒子群優化算法求解具有單連續變量的背包問題 ［J］. 計算機應用，2021，41（2）： 461-469. （Wang Zekun，He Yichao，Li Huanzhe，et al. Binary particle swarm optimization algorithm based on novel S-shape transfer function for knapsack problem with a single continuous variable ［J］. Journal of Computer Applications，2021，41（2）： 461-469.）

［34］Bergantios G，Gómez-Rúa M，Llorca N，et al. Allocating costs in set covering problems ［J］. European Journal of Operational Research，2020，284（3）： 1074-1087.