改进帕累托算法求解超大规模多选择背包问题

doi:10.3969/j.issn.0372-2112.2020.06.023

摘要/Abstract

摘要： 实际生产生活中大量多选一的问题都可以转为多选择背包问题（MCKP），但MCKP是一个经典的NP难问题，因此对于超大规模MCKP而言，往往只能利用粒子群算法、狼群算法、鱼群算法等群智能算法对问题进行求解.对于群智能算法而言，高效快捷的贪心算法对于初始解的生成起着至关重要的作用.基于凸帕累托算法（CPA），提出一种能够快速求解线性支配子集的改进帕累托算法（IPA）.IPA首先选择各类项集的质量最小项，然后计算所有物品的价值密度，最后按照价值密度从高到低选择对物品进行贪心选择，若贪心选择项的价值大于其所在项集原有选择项，则进行迭代.仿真实验结果表明：IPA相比于CPA，求解速度平均提升98.86%.且PSO-IPA求解精度平均提升28.92%.

关键词: 多选择背包问题, 贪心算法, 大数据, 帕累托前沿, 凸优化, 群智能算法, 整数优化

Abstract: In the actual production life conditions,a large number of multiple choices can be converted into a multiple-choice knapsack problem(MCKP),but MCKP is a classic NP-hard problem.Therefore,for very large scale MCKP,it is often only possible to use the particle swarm algorithm,wolf pack algorithm,fish swarm algorithm and so on to solve the problem.For swarm intelligence algorithms,efficient and fast greedy algorithms play a key role in the generation of initial solutions.Based on the convex Pareto algorithm(CPA),an improved Pareto algorithm(IPA) that can quickly get the linear programming dominated set is proposed.IPA firstly selects the minimum weight item of each set,then computes the value density of all items,and finally chooses the greedy choice of the item according to the value density from high to low.When the value of the greedy option is greater than the original selection of the item set,then IPA is iterated.The simulation results show that compared with CPA,the speed of IPA is increased by 98.86%.The PSO-IPA solution accuracy is increased by an average of 28.92%.

Key words: multiple-choice knapsack problem(MCKP), greedy algorithm, big data, Pareto front, convex optimization, swarm intelligence algorithm, integer optimization

中图分类号:

TP18
O224

杨洋. 改进帕累托算法求解超大规模多选择背包问题[J]. 电子学报, 2020, 48(6): 1205-1212.

YANG Yang. Improved Pareto Algorithm for Solving Very Large Scale Multiple-Choice Knapsack Problem[J]. Acta Electronica Sinica, 2020, 48(6): 1205-1212.

参考文献

[1] NAUSS R M.The 0-1 knapsack problem with multiple choice constraints[J].European Journal of Operational Research,1978,2(2):125-131.
[2] BALINTFY J L,ROSS G T,SINHA P,et al.A mathematical programming system for preference and compatibility maximized menu planning and scheduling[J].Mathematical Programming,1978,15(1):63-76.
[3] SINHA P,ZOLTNERS A A.Integer programming models for sales resource allocation[J].Management Science,1980,26(3):242-260.
[4] RONG A Y,FIGUEIRA J R,KLAMORTH K.Dynamic programming based algorithms for the discounted{0-1}knapsack problem[J].Applied Mathematics and Computation,2012,218(12):6921-6933.
[5] HE Y C,WANG X Z,HE Y L,et al.Exact and approximate algorithms for discounted{0-1}knapsack problem[J].Information Sciences,2016,369:634-647.
[6] 冯艳红,杨娟,贺毅朝,王改革.差分进化帝王蝶优化算法求解折扣{0-1}背包问题[J].电子学报,2018,46(6):1343-1350. FENG Y H,YANG J,HE Y C,et al.Monarch butterfly optimization algorithm with differential evolution for the discounted{0-1}knapsack problem[J].Acta Electronica Sinica,2018,46(6):1343-1350.(in Chinese)
[7] HE Y C,XIE H,WONG T L,et al.A novel binary artificial bee colony algorithm for the set-union knapsack problem[J].Future Generation Computer Systems,2018,78(1):77-86.
[8] WEI Z Q,HAO J K.Iterated two-phase local search for the Set-Union Knapsack Problem[J].Future Generation Computer Systems,2019,101(07):1005-1017.
[9] PISINGER D.A minimal algorithm for the multiple-choice knapsack problem[J].European Journal of Operational Research,2007,83(2):394-410.
[10] MARTELLO S,TOTH P P.Dynamic programming and strong bounds for the 0-1 knapsack problem[J].Management Science,1999,45(3):414-424.
[11] DYER M E,KAYA N,WALKER J.A branch and bound algorithm for solving the multiple-choice knapsack problem[J].Journal of Computational and Applied Mathematics,1984,11(2):231-249.
[12] BALAS E,ZEMEL E.An algorithm for large zero-one knapsack problems[J].Operations Research,1980,28(5):1130-1154.
[13] MARTELLO S,TOTH P.A new algorithm for the 0-1 knapsack problem[J].Management Science,1988,34(5):633-644.
[14] MARTELLO S,TOTH P.Knapsack Problems:Algorithms and Computer Implementations[M]. New Jersey:John Wiley&Sons,Inc.1990.
[15] PISINGER D.An expanding-core algorithm for the exact 0-1 knapsack problem[J].European Journal of Operational Research,1995,87(1):175-187.
[16] 王熙照,贺毅朝.求解背包问题的演化算法[J].软件学报,2017,28(01):1-16. WANG X Z,HE Y C.Evolutionary algorithms for knapsack problems[J].Journal of Software,2017,28(01):1-16.(in Chinese)
[17] 吴虎胜,张凤鸣,战仁军,李浩,梁晓龙.利用改进的二进制狼群算法求解多维背包问题[J].系统工程与电子技术,2015,37(05):1084-1091. WU H S,ZHANG F M,ZHAN R J,et al.Improved binary wolf pack algorithm for solving multidimensional knapsack problem[J].Systems Engineering and Electronics,2015,37(05):1084-1091.(in Chinese)
[18] 李迎,张璟,刘庆,张伟.求解大规模多背包问题的高级人工鱼群算法[J].系统工程与电子技术,2018,40(03):710-716. LI Y,ZHANG J,LIU Q,et al.Advanced artificial fish swarm algorithm for large scale multiple knapsack problem[J].Systems Engineering and Electronics,2018,40(03):710-716.(in Chinese)
[19] 薛俊杰,王瑛,孟祥飞,等.二进制反向学习烟花算法求解多维背包问题[J].系统工程与电子技术,2017,39(02):451-458. XUE J J,WANG Y,MENG X F,et al.Binary opposite back-ward learning fire works algorithm for multidimensional knapsack problem[J].Systems Engineering and Electronics,2017,39(02):451-458.(in Chinese)
[20] 印桂生,崔晓晖,董宇欣,杨雪.面向离散优化问题的改进二元粒子群算法[J].哈尔滨工程大学学报,2015,36(02):191-195. YIN G S,CUI X H,DONG Y X,et al.An improved binary particle swarm optimization for discrete optimization problems[J].Journal of Harbin Engineering University,2015,36(02):191-195.(in Chinese)
[21] 于永新,张新荣.基于蚁群系统的多选择背包问题优化算法[J].计算机工程,2003(20):75-76+84. YU Y X,ZHANG X R.Optimization algorithm for multiple-choice knapsack problem based on ant colony system[J].Computer Engineering,2003(20):75-76+84.(in Chinese)
[22] 韩燕燕,马良,赵小强.多选择背包问题的人工蜂群算法[J].计算机应用研究,2012,29(03):862-864. HAN Y Y,MA L,ZHAO X Q.Artificial bee colony algorithm for multi-choice knapsack problem[J].Application Research of Computers,2012,29(03):862-864.(in Chinese)
[23] IBARAKI T,HASEGAWA T,TERANAKA K,et al.The multiple-choice knapsack problem[J].Journal of the Operations Research Society of Japan,1978,21(01):59-95.
[24] 华中生,张斌.求解可分离连续凸二次背包问题的直接算法[J].系统工程与电子技术,2005,27(2):331-334. HUA Z S,ZHANG B.Direct algorithm for separable continuous convex quadratic knapsack problem[J].Systems Engineering and Electronics,2005,27(2):331-334.(in Chinese)
[25] 王粉兰.非线性整数规划问题的若干新算法[D].上海:上海大学,2006. WANG F L.New Algorithms for Nonlinear Integer Programming Problems[D].Shanghai:Shanghai University,2006.(in Chinese)
[26] ZHENG X,SUN X L,LI D,et al.Successive convex approximations to cardinality-constrained convex programs:a piecewise-linear DC approach[J].Computational Optimization and Applications,2014,59(1-2):379-397.
[27] SINHA P,ZOLTNERS A A.The multiple-choice knapsack problem[J].Operations Research,1979,27(3):503-515.
[28] DYER M E,RIHA W O,WALKER J.A hybrid dynamic programming/branch-and-bound algorithm for the multiple-choice knapsack problem[J].Journal of Computational and Applied Mathematics,1995,58(1):43-54.
[29] CLAUTIAUX F,SADYKOV R,VANDERBECK F,et al.Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem[J].Discrete,2018,29,18-44.
[30] PFERSCHY U,SCATAMACCHIA R.Improved dynamic programming and approximation results for the knapsack problem with setups[J].International Transactions in Operational Research,2017.667-682.
[31] LIU G S,LI J J,YANG H D,et al.Approximate and branch-and-bound algorithms for the parallel machine scheduling problem with a single server[J].Journal of the Operational Research Society,2019,70(9):1-17.
[32] SUNG C S,CHO Y K.Branch-and-bound redundancy optimization for a series system with multiple-choice constraints[J].IEEE Transactions on Reliability,1999,48(2):108-117.
[33] 郁磊,史峰,王辉,等.MATLAB智能算法30个案例分析[M].北京:北京航空航天大学出版社,2011.130-136.