求解背包问题的改进差异演化算法

doi:10.3778/j.issn.1002-8331.2008.32.004

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (32): 12-14.DOI: 10.3778/j.issn.1002-8331.2008.32.004

求解背包问题的改进差异演化算法

邓长寿^1,2,梁昌勇¹

1.合肥工业大学计算机网络系统研究所，合肥 230009
2.九江学院信息科学与技术学院，江西九江 332005

收稿日期:2008-07-29 修回日期:2008-08-18 出版日期:2008-11-11 发布日期:2008-11-11
通讯作者: 邓长寿

Improved differential evolution algorithm for knapsack problem

DENG Chang-shou^1,2,LIANG Chang-yong¹

1.Institute of Computer Network System，Hefei University of Technology，Hefei 230009，China
2.School of Information Science and Technology，Jiujiang University，Jiujiang，Jiangxi 332005，China

Received:2008-07-29 Revised:2008-08-18 Online:2008-11-11 Published:2008-11-11
Contact: DENG Chang-shou

摘要/Abstract

摘要： 提出一种求解0-1背包问题的改进差异演化算法。首先对差异演化算法的选择操作进行修改，得到的改进差异演化算法可以直接有效地处理约束优化问题。其次，利用一种新的区间编码映射机制，将差异演化算法扩展到求解离散领域优化问题。仿真实验结果表明，与其他进化算法相比，改进差异演化算法求解经典背包问题时，求解精度高，收敛速度快，是求解经典背包问题的一种高效算法。

关键词: 背包问题, 差异演化, 区间编码映射, 选择操作

Abstract: An improved differential evolution algorithm was proposed to solve the classical knapsack problem.The selection operation in original differential evolution was adapted to deal with constraints directly.Using a new range encoding mapping，the differential evolution algorithm can be used to deal with discrete optimization problem.The simulation results of the improved differential evolution algorithm show，compared with other evolution algorithm，the improved differential evolution is effective in solving 0-1 Knapsack Problems.

Key words: knapsack problem, differential evolution, range encoding mapping, selection operation

邓长寿^1,2,梁昌勇¹. 求解背包问题的改进差异演化算法[J]. 计算机工程与应用, 2008, 44(32): 12-14.

DENG Chang-shou^1,2,LIANG Chang-yong¹. Improved differential evolution algorithm for knapsack problem[J]. Computer Engineering and Applications, 2008, 44(32): 12-14.

[1]	郝翔，贺毅朝，朱晓斌，翟庆雷. 基于离散混合多宇宙算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(18): 103-113.
[2]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[3]	吴聪聪，贺毅朝，赵建立. 求解折扣{0-1}背包问题的新遗传算法[J]. 计算机工程与应用, 2020, 56(7): 57-66.
[4]	陈长倩，慕晓冬，牛犇，王立志. 结合高斯分布的改进二进制灰狼优化算法[J]. 计算机工程与应用, 2019, 55(13): 145-150.
[5]	杨洋1，潘大志1，贺毅朝2. 改进修复策略遗传算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(21): 37-42.
[6]	张健，郭星，李炜. 改进果蝇优化算法在多目标搜索的应用[J]. 计算机工程与应用, 2018, 54(2): 131-136.
[7]	刘雪静，贺毅朝，吴聪聪，才秀凤. 基于细菌觅食算法求解折扣{0-1}背包问题的研究[J]. 计算机工程与应用, 2018, 54(2): 155-162.
[8]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 自适应细菌觅食算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2018, 54(18): 139-146.
[9]	刘雪静1，贺毅朝1，吴聪聪1，李靓2. 求解0-1背包问题的混沌二进制乌鸦算法[J]. 计算机工程与应用, 2018, 54(10): 173-179.
[10]	钱汐，曾承，王甜. 时序范围最具稳定性服务集推荐算法[J]. 计算机工程与应用, 2017, 53(10): 73-78.
[11]	崔建双，王憧憬. 求解多重背包问题的限速粒子群算法[J]. 计算机工程与应用, 2015, 51(9): 244-247.
[12]	吴聪聪，贺毅朝，陈嶷瑛，刘雪静，才秀凤. 求解0-1背包问题的二进制蝙蝠算法[J]. 计算机工程与应用, 2015, 51(19): 71-74.
[13]	余娟，贺昱曜. 解决0-1背包问题的遗传分布估计算法[J]. 计算机工程与应用, 2014, 50(9): 12-16.
[14]	吴家皋1，张曦1，庄嵩杰1，邹志强1，胡斌2. 面向多图层的空间矢量数据缓存更新策略研究[J]. 计算机工程与应用, 2014, 50(7): 89-93.
[15]	李枝勇，马良，张惠珍. 遗传变异蝙蝠算法在0-1背包问题上的应用[J]. 计算机工程与应用, 2014, 50(11): 49-52.

求解背包问题的改进差异演化算法

Improved differential evolution algorithm for knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics