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

關(guān)鍵詞：演化算法；差分演化；多背包問題；模運(yùn)算

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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］是一類經(jīng)典的NP-難問題，也是一類著名的組合優(yōu)化問題，在資源分配、車輛裝載、資金預(yù)算以及整數(shù)規(guī)劃和財(cái)務(wù)管理等領(lǐng)域［3］具有廣泛應(yīng)用。多背包問題（multiple knapsack problem，MKP）是一種典型的背包問題，因求解難度極大，求解算法主要有精確算法和啟發(fā)式算法。精確算法雖然能夠求得MKP的最優(yōu)解，但時(shí)間復(fù)雜度是指數(shù)階的，當(dāng)問題的規(guī)模增大時(shí)會(huì)出現(xiàn)“組合爆炸”，導(dǎo)致算法消耗過多的時(shí)間而不適用于實(shí)時(shí)性要求較高的應(yīng)用。啟發(fā)式算法雖然不能保證求得最優(yōu)解，但在較短的時(shí)間內(nèi)可以得到一個(gè)很好的近似解，而且能夠滿足實(shí)際應(yīng)用中對(duì)求解時(shí)間的嚴(yán)格限制。

求解MKP的精確算法主要包括分支定界法和動(dòng)態(tài)規(guī)劃法。例如， Martello等人［4］提出了基于“bound and bound”的樹搜索技術(shù)，利用該技術(shù)確定決策樹中的分支，從而提出了求解MKP的精確算法MTM。Pisinger［5］提出了一種新的可分離動(dòng)態(tài)規(guī)劃算法MULKNAP，該算法不僅比MTM快，而且穩(wěn)定性高。Fukunaga等人［6］基于物品分配到背包之間的支配性標(biāo)準(zhǔn)來修剪樹的節(jié)點(diǎn)，提出了求解MKP的一個(gè)新的分支定界算法。Fukunaga［7］利用優(yōu)勢標(biāo)準(zhǔn)和對(duì)稱性破環(huán)策略與文獻(xiàn)［4］提出的邊界和邊界法技術(shù)相結(jié)合，提出了一種改進(jìn)的分支定界算法。Sitarz［8］基于多準(zhǔn)則動(dòng)態(tài)規(guī)劃策略開發(fā)了求解MKP的一個(gè)動(dòng)態(tài)規(guī)劃算法。

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

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

1 背景知識(shí)

1.1 MKP定義與數(shù)學(xué)模型

1.2 差分演化算法

2 基于模運(yùn)算的離散差分演化算法

2.1 新型傳遞函數(shù)

2.2 種群初始化

2.3 MODDE的進(jìn)化原理

2.4 MODDE的算法偽代碼

3 利用MODDE求解MKP

4 計(jì)算結(jié)果和比較

4.1 實(shí)驗(yàn)環(huán)境

4.2 三類MKP的實(shí)例

4.3 算法參數(shù)設(shè)置

4.4 計(jì)算結(jié)果與比較

記best、mean和stD分別為算法20次獨(dú)立計(jì)算得到結(jié)果的最好值、平均值和標(biāo)準(zhǔn)差。在表3～5中列出了各算法求解三類MKP實(shí)例的結(jié)果，其中的黑色加粗部分代表計(jì)算結(jié)果最好。

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

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

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

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

在圖7～9中，利用直方圖對(duì)MODDE、DisPSO、GA、GTOA和RTEA的stD進(jìn)行了比較。從圖7可以看出，對(duì)于10個(gè)umkp類實(shí)例，MODDE有6個(gè)實(shí)例的stD值為0，而DisPSO、GA、GTOA和RTEA只有2個(gè)實(shí)例的stD值為0，雖然對(duì)編號(hào)u4的實(shí)例MODDE的穩(wěn)定性較差，但是對(duì)于其他9個(gè)實(shí)例，MODDE的stD值均比其他算法小，所以MODDE穩(wěn)定性明顯要比其他算法的優(yōu)。

從圖8不難看出，對(duì)于wmkp類的10個(gè)實(shí)例，MODDE有4個(gè)實(shí)例的stD值為0，而DisPSO、GA、GTOA和RTEA只有1個(gè)實(shí)例的stD值為0;雖然對(duì)編號(hào)w9的實(shí)例，MODDE的穩(wěn)定性不是最好的，但是對(duì)于其他9個(gè)實(shí)例，MODDE的stD值均比其他算法小，穩(wěn)定性明顯要比其他算法更優(yōu)。

從圖9可以看出，對(duì)于smkp類的10個(gè)實(shí)例，MODDE的StD值都是最小的，所以MODDE的算法穩(wěn)定性比DisPSO、GA、GTOA和RTEA的均優(yōu)。

綜上所述，對(duì)于MKP，MODDE比DisPSO、GA、GTOA和RTEA的求解結(jié)果更優(yōu)，算法的穩(wěn)定性更佳。因此，MODDE是一種非常適于求解MKP的高效演化算法。

5 結(jié)束語

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

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

參考文獻(xiàn)：

［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］. 軟件學(xué)報(bào)，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］李迎，張璟，劉慶，等. 求解大規(guī)模多背包問題的高級(jí)人工魚群算法 ［J］. 系統(tǒng)工程與電子技術(shù)，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］陳國良，王熙法，莊鎮(zhèn)泉，等. 遺傳算法及其應(yīng)用 ［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］. 計(jì)算機(jī)學(xué)報(bào)，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］張發(fā)展，賀毅朝，劉雪靜，等. 新穎的離散差分演化算法求解D{0-1}KP問題 ［J］. 計(jì)算機(jī)科學(xué)與探索，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］賀毅朝，王熙照，趙書良，等. 基于編碼轉(zhuǎn)換的離散演化算法設(shè)計(jì)與應(yīng)用 ［J］. 軟件學(xué)報(bào)，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型轉(zhuǎn)換函數(shù)的二進(jìn)制粒子群優(yōu)化算法求解具有單連續(xù)變量的背包問題 ［J］. 計(jì)算機(jī)應(yīng)用，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.