求解0-1背包问题的混合贪婪遗传算法

doi:10.11772/j.issn.1001-9081.2020060981

计算机应用 ›› 2021, Vol. 41 ›› Issue (1): 87-94.DOI: 10.11772/j.issn.1001-9081.2020060981

所属专题：第八届中国数据挖掘会议(CCDM 2020)

• 第八届中国数据挖掘会议(CCDM 2020) • 上一篇下一篇

求解0-1背包问题的混合贪婪遗传算法

陈桢¹, 钟一文², 林娟¹

1. 福建农林大学计算机与信息学院, 福州 350002;
2. 智慧农林福建省高等学校重点实验室(福建农林大学), 福州 350002

收稿日期:2020-05-30 修回日期:2020-07-29 出版日期:2021-01-10 发布日期:2020-08-21
通讯作者: 陈桢
作者简介:陈桢(1982-),女,福建仙游人,讲师,硕士,主要研究方向:计算智能;钟一文(1968-),男,福建上杭人,教授,博士,主要研究方向:计算智能、生物信息学、科学数据可视化;林娟(1980-),女,福建福州人,副教授,硕士,主要研究方向:生物信息学、科学数据可视化。
基金资助:
福建省自然科学基金资助项目（2019J01401，2019J01661）；福建省教育厅中青年教师教育科研项目（KLA19027A）。

Hybrid greedy genetic algorithm for solving 0-1 knapsack problem

CHEN Zhen¹, ZHONG Yiwen², LIN Juan¹

1. College of Computer and Information Sciences, Fujian Agriculture and Forestry University, Fuzhou Fujian 350002, China;
2. Key Laboratory of Smart Agriculture and Forestry(Fujian Agriculture and Forestry University), Fujian Province University, Fuzhou Fujian 350002, China

Received:2020-05-30 Revised:2020-07-29 Online:2021-01-10 Published:2020-08-21
Supported by:
This work is partially supported by the Natural Science Foundation of Fujian Province (2019J01401, 2019J01661), the Young and Middle-Aged Teachers Education Research Project of Fujian Provincial Department of Education (KLA19027A).

摘要/Abstract

摘要： 求解0-1背包问题（KP）的最优解的时候，传统遗传算法（GA）的局部求精能力不足而简单局部搜索算法的全局探索能力有限，针对上述问题，将这两个算法整合并提出了混合贪婪遗传算法（HGGA）。在GA全局搜索框架下增加局部搜索模块，并改进传统仅基于物品价值密度的修复算子，增加基于物品价值的贪婪混合选项，从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索，另一方面依靠GA的经典操作算子开拓全局搜索空间，从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试，结果表明在第一组15个测试用例中的12个上，HGGA能够百分百找到最优解，成功率达到80%；在第二组小规模数据集上，HGGA的性能明显好于其他同类GA和其他元启发算法；在第三组大规模数据集上，HGGA较其他元启发式算法具有更好的稳定性和高效性。

关键词: 0-1背包问题, 混合贪婪遗传算法, 求精能力, 求泛能力, 混合贪婪算子, 局部搜索

Abstract: When solving the optimal solutions of 0-1 Knapsack Problems (KPs), the traditional Genetic Algorithm (GA) has insufficient local refinement ability and the simple local search algorithm has limited global exploration ability. Aiming at these problems, two algorithms were integrated to the Hybrid Greedy Genetic Algorithm (HGGA). Under the GA global search framework, local search module was added, and the traditional repair operator based only on item value density was improved, the greedy hybrid option based on item value was added, so as to accelerate the optimization process. In HGGA, the population was led to carry out fine search in the excellent solution space of evolution, and the classical operators of GA were relied on to expand the global search space, so as to achieve a good balance between the refinement ability and the development ability of the algorithm. HGGA was tested on three sets of data. The results show that in the first set of 15 test cases, HGGA is able to find the optimal solution on 12 cases, with a success rate of 80%; on the second small-scale dataset, the performance of HGGA is obviously better than those of other similar GA and other meta-heuristic algorithms; on the third large-scale dataset, HGGA is more stable and efficient than other meta-heuristic algorithms.

Key words: 0-1 Knapsack Problem (KP), Hybrid Greedy Genetic Algorithm (HGGA), refinement ability, generalization ability, hybrid greedy operator, local search

中图分类号:

TP18

陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.

CHEN Zhen, ZHONG Yiwen, LIN Juan. Hybrid greedy genetic algorithm for solving 0-1 knapsack problem[J]. Journal of Computer Applications, 2021, 41(1): 87-94.

参考文献

[1] DANTZIG G B. Discrete variable extremum problems[J]. Operations Research,1957,5(2):266-277.
[2] HAN K H,KIM J H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]//Proceedings of the 2000 Congress on Evolutionary Computation. Piscataway:IEEE,2000:1354-1360.
[3] 张玲玲, 张弘. 0-1背包问题的预期效率和线性拟合求解[J]. 计算机应用,2014,34(9):2581-2584.(ZHANG L L,ZHANG H. Solution of 0-1 knapsack problem based on expected efficiency and linear fitting[J]. Journal of Computer Applications,2014,34(9):2581-2584.)
[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] 韩小雷. 粒子群-模拟退火融合算法及其在函数优化中的应用[D]. 武汉:武汉理工大学,2008:15-23.(HAN X L. The particle swarm-simulated annealing fusion algorithm and its application in function optimization[D]. Wuhan:Wuhan University of Technology,2008:15-23.)
[6] ZHAN S,WANG L,ZHANG Z,et al. Noising methods with hybrid greedy repair operator for 0-1 knapsack problem[J]. Memetic Computing,2020,12(1):37-50.
[7] 李士勇. 蚁群优化算法及其应用研究进展[J]. 计算机测量与控制,2003,11(12):911-913,917.(LI S Y. Progresses in ant colony optimization algorithm with applications[J]. Computer Measurement and Control,2003,11(12):911-913,917.)
[8] KENNEDY J,EBERHART R. Particle swarm optimization[C]//Proceedings of the 1995 International Conference on Neural Networks. Piscataway:IEEE,1995:1942-1948.
[9] SRINIVAS N, DEB K. Multiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation,1994,2(3):221-248.
[10] FENG Y,WANG G,GAO X. A novel hybrid cuckoo search algorithm with global harmony search for 0-1 knapsack problems[J]. International Journal of Computational Intelligence Systems, 2016,9(6):1174-1190.
[11] FENG Y,WANG G,DEB S,et al. Solving 0-1 knapsack problem by a novel binary monarch butterfly optimization[J]. Neural Computing and Applications,2017,28(7):1619-1634.
[12] 欧阳海滨, 高立群, 孔祥勇, 等. 一种求解0-1背包问题的二进制修正和声搜索算法[J]. 控制与决策,2014,29(7):1174-1180.(OUYANG H B,GAO L Q,KONG X Y,et al. A binary modified harmony search algorithm for 0-1 knapsack problem[J]. Control and Decision,2014,29(7):1174-1180.)
[13] 王小平, 曹立明. 遗传算法-理论、应用与软件实现[M]. 西安:西安交通大学出版社,2002:136-140. (WANG X P,CAO L M. Genetic Algorithm-Theory, Application and Software Implementation[M]. Xi'an:Xi'an Jiaotong University Press, 2002:136-140.)
[14] MICHALEWICZ Z. Genetic Algorithm + Data Structure=Evolution Programs:3rd,Revised and Extended Edition[M]. Berlin:Springer,1996:13-103.
[15] 徐宗本. 计算智能——模拟进化计算[M]. 北京:高等教育出版社,2004:72-87. (XU Z B. Computational Intelligence-Simulated Evolutionary Computation[M]. Beijing:Higher Education Press,2004:72-87.)
[16] 贺毅朝, 刘坤起, 张翠军, 等. 求解背包问题的贪心遗传算法及其应用[J]. 计算机工程与设计,2007,28(11):2655-2657,2681. ((HE Y C,LIU K Q,ZHANG C J,et al. Greedy genetic algorithm for solving knapsack problems and its applications[J]. Computer Engineering and Design, 2007, 28(11):2655-2657, 2681.)
[17] 白东玲, 郭绍永. 一种改进的混合遗传算法求解0_1背包问题[J]. 电子设计工程,2013,21(14):9-11.(BAI D L,GUO S Y. An improved hybrid genetic algorithm for 0_1 knapsack problem[J]. Electronic Design Engineering,2013,21(14):9-11.)
[18] 刘寒冰, 张亚娟. 求解0-1背包问题的改进混合遗传算法[J]. 计算机系统应用,2015,24(6):197-201.(LIU H B,ZHANG Y J. Improved hybrid genetic algorithm for solving 0-1 knapsack problem[J]. Computer Systems and Applications,2015,24(6):197-201.)
[19] 金慧敏, 马良. 遗传退火进化算法在背包问题中的应用[J]. 上海理工大学学报,2004,26(6):561-564.(JIN H M,MA L. Genetic annealing evolutionary algorithm applied to the knapsack problem[J]. Journal of University of Shanghai for Science and Technology,2004,26(6):561-564.)
[20] 张盛意, 蔡之华, 占志刚. 基于改进模拟退火的遗传算法求解0-1背包问题[J]. 微电子学与计算机,2011,28(2):61-64. (ZHANG S Y,CAI Z H,ZHANG Z G. Solving 0-1 knapsack problem based on genetic algorithm with improved simulated annealing[J]. Microelectronics and Computer,2011,28(2):61-64.)
[21] 吕晓峰, 张勇亮, 马羚. 一种求解0-1背包问题的改进遗传算法[J]. 计算机工程与应用,2011,47(34):44-46,63.(LYU X F, ZHANG Y L,MA L. Improved genetic algorithm to 0-1 knapsack problem[J]. Computer Engineering and Applications,2011,47(34):44-46,63.)
[22] FENG Y,YANG J,WU C,et al. Solving 0-1 knapsack problems by chaotic monarch butterfly optimization algorithm with Gaussian mutation[J]. Memetic Computing,2018,10(2):135-150.
[23] KONG X,GAO L,OUYANG H,et al. A simplified binary harmony search algorithm for large scale 0-1knapsack problems[J]. Expert Systems with Applications,2015,42(12):5377-5355.
[24] SCHAFFER J D,CARUANA R,ESHELMAN L J,et al. A study of control parameters affecting online performance of genetic algorithms for function optimization[C]//Proceedings of the 3rd International Conference on Genetic Algorithms. San Francisco:Morgan Kaufmann Publishers Inc.,1989:51-60.
[25] FENG Y,WANG G,DONG J,et al. Opposition-based learning monarch butterfly optimization with Gaussian perturbation for largescale 0-1 knapsack problem[J]. Computers and Electrical Engineering,2018,67:454-468.

求解0-1背包问题的混合贪婪遗传算法

Hybrid greedy genetic algorithm for solving 0-1 knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	邓文瀚, 张铭, 王李进, 钟一文. 混合群体增量学习算法求解闭环布局问题[J]. 计算机应用, 2021, 41(1): 95-102.
[2]	张玉州, 徐廷政, 郑军帅, 饶舜. 考虑紧急度的救灾车辆路径问题建模与优化[J]. 计算机应用, 2019, 39(8): 2444-2449.
[3]	宋婷, 陈矛, 吴超, 张龚钊. 基于多类迭代局部搜索的自动化排课算法[J]. 计算机应用, 2019, 39(6): 1760-1765.
[4]	吕进锋, 赵怀慈. 基于记忆库粒子群算法的海上协作搜寻计划制定[J]. 计算机应用, 2018, 38(9): 2477-2482.
[5]	李斌, 陈爱斌, 周国雄, 周涛. 基于Cell-DEVS的森林灭火资源调度狼群优化算法[J]. 计算机应用, 2018, 38(5): 1494-1499.
[6]	王晓静, 彭虎, 邓长寿, 黄海燕, 张艳, 谭旭杰. 基于均匀局部搜索和可变步长的萤火虫算法[J]. 计算机应用, 2018, 38(3): 715-721.
[7]	顾军华, 霍士杰, 武君艳, 尹君, 张素琪. 求解最大团问题的并行多层图划分方法[J]. 计算机应用, 2018, 38(12): 3425-3432.
[8]	宋月振, 裴腾达, 裴炳南. 基于中心解的改进人工蜂群算法[J]. 计算机应用, 2016, 36(4): 1022-1026.
[9]	王佳君, 喻强, 张晶晶. 基于先验置信传播的图像修复改进算法[J]. 计算机应用, 2016, 36(4): 1115-1119.
[10]	欧阳秋萍, 李杰, 沈林成. 考虑3G/4G网络特性的多无人机环保监测任务调度[J]. 计算机应用, 2016, 36(3): 871-877.
[11]	刘翱, 邓旭东, 李维刚. 基于模拟退火的混合萤火虫Memetic算法[J]. 计算机应用, 2016, 36(11): 3055-3061.
[12]	程毕芸, 鲁海燕, 徐向平, 沈莞蔷. 求解旅行商问题的改进局部搜索混沌离散粒子群优化算法[J]. 计算机应用, 2016, 36(1): 138-142.
[13]	宋潇潇, 王军. 改进膜蜂群算法求解0-1背包问题[J]. 计算机应用, 2015, 35(7): 2088-2092.
[14]	马震远, 叶树锦, 林智勇, 梁钰彬, 黄翰. 基于Memetic框架和改进DFP局部搜索的改进差分进化算法[J]. 计算机应用, 2015, 35(10): 2766-2770.
[15]	黄敏江渝毛安姜琪. 基于全局最优位置自适应选取与局部搜索的多目标粒子群优化算法[J]. 计算机应用, 2014, 34(4): 1074-1079.