贪心核加速动态规划算法求解折扣{0-1}背包问题
|
摘要
针对现有动态规划算法求解折扣{0-1}背包问题(D{0-1}KP)缓慢的问题,基于动态规划思想并结合新型贪心修复优化算法(NGROA)与核算法,通过缩小问题规模加速问题求解来提出一种贪心核加速动态规划(GCADP)算法。首先利用NGROA对问题进行贪心求解,得到非完整项;然后通过计算得到模糊核区间的半径和模糊核区间范围;最后对于模糊核区间内的物品及同一项集内的物品利用基础动态规划(BDP)算法求解。实验结果表明:GCADP算法适用于求解D{0-1}KP,且在求解速度上相比BDP算法平均提升了76.24%,相比FirEGA算法平均提升了75.07%。
As the existing dynamic programming algorithm cannot quickly solve Discounted {0-1} Knapsack Problem(D{0-1}KP), based on the idea of dynamic programming and combined with New Greedy Repair Optimization Algorithm(NGROA) and core algorithm, a Greedy Core Acceleration Dynamic Programming(GCADP) algorithm was proposed with the acceleration of the problem solving by reducing the problem scale. Firstly, the incomplete item was obtained based on the greedy solution of the problem by NGROA. Then, the radius and range of fuzzy core interval were found by calculation. Finally, Basic Dynamic Programming(BDP) algorithm was used to solve the items in the fuzzy core interval and the items in the same item set. The experimental results show that GCADP algorithm is suitable for solving D{0-1}KP. Meanwhile, the average solution speed of GCADP improves by 76.24% and 75.07% respectively compared with that of BDP algorithm and FirEGA(First Elitist reservation strategy Genetic Algorithm).
As the existing dynamic programming algorithm cannot quickly solve Discounted {0-1} Knapsack Problem(D{0-1}KP), based on the idea of dynamic programming and combined with New Greedy Repair Optimization Algorithm(NGROA) and core algorithm, a Greedy Core Acceleration Dynamic Programming(GCADP) algorithm was proposed with the acceleration of the problem solving by reducing the problem scale. Firstly, the incomplete item was obtained based on the greedy solution of the problem by NGROA. Then, the radius and range of fuzzy core interval were found by calculation. Finally, Basic Dynamic Programming(BDP) algorithm was used to solve the items in the fuzzy core interval and the items in the same item set. The experimental results show that GCADP algorithm is suitable for solving D{0-1}KP. Meanwhile, the average solution speed of GCADP improves by 76.24% and 75.07% respectively compared with that of BDP algorithm and FirEGA(First Elitist reservation strategy Genetic Algorithm).
引文
[1] GUDER J.Discounted knapsack problems for pairs of items [D].Nuremberg:University of Erlangen-Nurnberg,2005.
[2] GULDAN B.Heuristic and exact algorithms for discounted knapsack prob1ems[D].Nuremberg:University of Erlangen-Nuremberg,2007.
[3] 贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0- 1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630.(HE Y C,WANG X Z,Ll W B,et al.Research on genetic algorithms for the discounted {0- 1} knapsack problem[J].Chinese Journal of Computers,2016,39(12):2614-2630.)
[4] 杨洋,潘大志,刘益,等.折扣{0- 1}背包问题的简化新模型及遗传算法求解[J].计算机应用,2019,39(3):656-662.(YANG Y,PAN D Z,LIU Y,et al.New simplified model of discounted {0- 1} knapsack problem and solution by genetic algorithm[J].Journal of Computer Applications,2019,39(3):656-662.)
[5] RONG A Y,FIGUEIRA J R,KLAMROTH K.Dynamic programming based algorithms for the discounted {0- 1} knapsack problem[J].Applied Mathematics and Computation,2012,218(12):6921-6933.
[6] 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(10):634-647.
[7] 杨洋,潘大志,贺毅朝.改进修复策略遗传算法求解折扣{0- 1}背包问题[J].计算机工程与应用,2018,54(21):37-42.(YANG Y,PAN D Z,HE Y C.Improved repair strategy genetic algorithm solve discount {0- 1} knapsack problem[J].Computer Engineering and Applications,2018,54(21):37-42.)
[8] 杨洋,潘大志,贺毅朝.核加速遗传算法求解折扣{0- 1}背包问题[J].西华师范大学学报(自然科学版),2018,39(2):165-172.(YANG Y,PAN D Z,HE Y C.Core accelerated genetic algorithm to solve the discount {0- 1} knapsack problem[J].Journal of China West Normal University (Natural Sciences edition),2018,39(2):165-172.)
[9] FENG Y H,WANG G G,LI W,et al.Multi-strategy monarch butterfly optimization algorithm for discounted {0- 1} knapsack problem[J].Neural Computing and Applications,2018,30(10):3019-3016.
[10] 冯艳红,杨娟,贺毅朝,等.差分进化帝王蝶优化算法求解折扣{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.)
[11] FENG Y H,WANG G G.Binary moth search algorithm for discounted {0- 1} knapsack problem[J].IEEE Access,2018,6:10708-10719.
[12] 刘雪静,贺毅朝,路凤佳,等.基于Lévy飞行的差分乌鸦算法求解折扣{0- 1背包问题[J].计算机应用,2018,38(2):433-442.(LIU X J,HE Y C,LU F J,et al.Differential crow search algorithm based on Lévy flight for solving discount {0- 1} knapsack problem [J].Journal of Computer Applications,2018,38(2):433-442.)
[13] 刘雪静,贺毅朝,路凤佳,等.基于差分演化策略的混沌乌鸦算法求解折扣{0- 1}背包问题[J].计算机应用,2018,38(1):137-145.(LIU X J,HE Y C,LU F J,et al.Chaotic crow search algorithm based on differential evolution strategy for solving discount {0- 1} knapsack problem[J].Journal of Computer Applications,2018,38(1):137-145.)
[14] 吴聪聪,贺毅朝,陈嶷瑛,等.变异蝙蝠算法求解折扣{0- 1}背包问题[J].计算机应用,2017,37(5):1292-1299.(WU C C,HE Y C,CHEN Y Y,et al.Mutated bat algorithm for solving discounted {0- 1} knapsack problem[J].Journal of Computer Applications,2017,37(5):1292-1299.)
[15] 刘雪静,贺毅朝,吴聪聪,等.基于细菌觅食算法求解折扣{0- 1}背包问题的研究[J].计算机工程与应用,2018,54(2):155-162.(LIU X J,HE Y C,WU C C,et al.Research on bacterial foraging optimization algorithm for discounted {0- 1} knapsack problem[J].Computer Engineering and Applications,2018,54(2):155-162.)
[16] BALAS E,ZEMEL E.An algorithm for large zero-one knapsack problems[J].Operations Research,1980,28(5):1130-1154.
[17] PISINGER D.Core problems in knapsack algorithms[J].Operations Research,1999,47(4):570-575.
[18] PISINGER D.An expanding-core algorithm for the exact 0- 1 knapsack problem[J].European Journal of Operational Research,1995,87(1):175-187.
[19] BELLMAN R.Dynamic programming[J].Science,1966,153(3731):34-37.
[20] MARTELLO S,PISINGER D,TOTH P.Dynamic programming and strong bounds for the 0- 1 knapsack problem[J].Management Science,1999,45(3):414-424.
[21] KATHRIN K,WIECEK M M.Dynamic programming approaches to the multiple criteria knapsack problem[J].Naval Research Logistics,2015,47(1):57-76.
[22] BALEV S,YANEV N,FREVILLE A,et al.A dynamic programming based reduction procedure for the multidimensional 0- 1 knapsack problem[J].European Journal of Operational Research,2008,186(1):63-76.
[23] 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.
[24] MARTELLO S,TOTH P.Knapsack problems:algorithms and computer implementations[J].Journal of the Operational Research Society,1991,42(6):513-513.
[25] GAREY M R,JOHNSON D S,STOCKMEYER L.Some simplified NP-complete graph problems[J].Theoretical Computer Science,1976,1(3):237-267.
[26] KELLERER H,PFERSCHY U,PISINGER D.Knapsack Problems[M].Berlin:Springer,2004:1-17.
[2] GULDAN B.Heuristic and exact algorithms for discounted knapsack prob1ems[D].Nuremberg:University of Erlangen-Nuremberg,2007.
[3] 贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0- 1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630.(HE Y C,WANG X Z,Ll W B,et al.Research on genetic algorithms for the discounted {0- 1} knapsack problem[J].Chinese Journal of Computers,2016,39(12):2614-2630.)
[4] 杨洋,潘大志,刘益,等.折扣{0- 1}背包问题的简化新模型及遗传算法求解[J].计算机应用,2019,39(3):656-662.(YANG Y,PAN D Z,LIU Y,et al.New simplified model of discounted {0- 1} knapsack problem and solution by genetic algorithm[J].Journal of Computer Applications,2019,39(3):656-662.)
[5] RONG A Y,FIGUEIRA J R,KLAMROTH K.Dynamic programming based algorithms for the discounted {0- 1} knapsack problem[J].Applied Mathematics and Computation,2012,218(12):6921-6933.
[6] 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(10):634-647.
[7] 杨洋,潘大志,贺毅朝.改进修复策略遗传算法求解折扣{0- 1}背包问题[J].计算机工程与应用,2018,54(21):37-42.(YANG Y,PAN D Z,HE Y C.Improved repair strategy genetic algorithm solve discount {0- 1} knapsack problem[J].Computer Engineering and Applications,2018,54(21):37-42.)
[8] 杨洋,潘大志,贺毅朝.核加速遗传算法求解折扣{0- 1}背包问题[J].西华师范大学学报(自然科学版),2018,39(2):165-172.(YANG Y,PAN D Z,HE Y C.Core accelerated genetic algorithm to solve the discount {0- 1} knapsack problem[J].Journal of China West Normal University (Natural Sciences edition),2018,39(2):165-172.)
[9] FENG Y H,WANG G G,LI W,et al.Multi-strategy monarch butterfly optimization algorithm for discounted {0- 1} knapsack problem[J].Neural Computing and Applications,2018,30(10):3019-3016.
[10] 冯艳红,杨娟,贺毅朝,等.差分进化帝王蝶优化算法求解折扣{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.)
[11] FENG Y H,WANG G G.Binary moth search algorithm for discounted {0- 1} knapsack problem[J].IEEE Access,2018,6:10708-10719.
[12] 刘雪静,贺毅朝,路凤佳,等.基于Lévy飞行的差分乌鸦算法求解折扣{0- 1背包问题[J].计算机应用,2018,38(2):433-442.(LIU X J,HE Y C,LU F J,et al.Differential crow search algorithm based on Lévy flight for solving discount {0- 1} knapsack problem [J].Journal of Computer Applications,2018,38(2):433-442.)
[13] 刘雪静,贺毅朝,路凤佳,等.基于差分演化策略的混沌乌鸦算法求解折扣{0- 1}背包问题[J].计算机应用,2018,38(1):137-145.(LIU X J,HE Y C,LU F J,et al.Chaotic crow search algorithm based on differential evolution strategy for solving discount {0- 1} knapsack problem[J].Journal of Computer Applications,2018,38(1):137-145.)
[14] 吴聪聪,贺毅朝,陈嶷瑛,等.变异蝙蝠算法求解折扣{0- 1}背包问题[J].计算机应用,2017,37(5):1292-1299.(WU C C,HE Y C,CHEN Y Y,et al.Mutated bat algorithm for solving discounted {0- 1} knapsack problem[J].Journal of Computer Applications,2017,37(5):1292-1299.)
[15] 刘雪静,贺毅朝,吴聪聪,等.基于细菌觅食算法求解折扣{0- 1}背包问题的研究[J].计算机工程与应用,2018,54(2):155-162.(LIU X J,HE Y C,WU C C,et al.Research on bacterial foraging optimization algorithm for discounted {0- 1} knapsack problem[J].Computer Engineering and Applications,2018,54(2):155-162.)
[16] BALAS E,ZEMEL E.An algorithm for large zero-one knapsack problems[J].Operations Research,1980,28(5):1130-1154.
[17] PISINGER D.Core problems in knapsack algorithms[J].Operations Research,1999,47(4):570-575.
[18] PISINGER D.An expanding-core algorithm for the exact 0- 1 knapsack problem[J].European Journal of Operational Research,1995,87(1):175-187.
[19] BELLMAN R.Dynamic programming[J].Science,1966,153(3731):34-37.
[20] MARTELLO S,PISINGER D,TOTH P.Dynamic programming and strong bounds for the 0- 1 knapsack problem[J].Management Science,1999,45(3):414-424.
[21] KATHRIN K,WIECEK M M.Dynamic programming approaches to the multiple criteria knapsack problem[J].Naval Research Logistics,2015,47(1):57-76.
[22] BALEV S,YANEV N,FREVILLE A,et al.A dynamic programming based reduction procedure for the multidimensional 0- 1 knapsack problem[J].European Journal of Operational Research,2008,186(1):63-76.
[23] 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.
[24] MARTELLO S,TOTH P.Knapsack problems:algorithms and computer implementations[J].Journal of the Operational Research Society,1991,42(6):513-513.
[25] GAREY M R,JOHNSON D S,STOCKMEYER L.Some simplified NP-complete graph problems[J].Theoretical Computer Science,1976,1(3):237-267.
[26] KELLERER H,PFERSCHY U,PISINGER D.Knapsack Problems[M].Berlin:Springer,2004:1-17.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |