改进的差分演化算法求解多维背包问题

doi:10.3778/j.issn.1002-8331.1712-0355

计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (11): 153-160.DOI: 10.3778/j.issn.1002-8331.1712-0355

改进的差分演化算法求解多维背包问题

吴聪聪1，赵建立1，2，刘雪静1，陈嶷瑛1

1.河北地质大学信息工程学院，石家庄 050031
2.全北国立大学电子信息工程学院，韩国全州 54896

出版日期:2018-06-01 发布日期:2018-06-14

Modified differential evolution algorithm for solving multidimensional knapsack problem

WU Congcong1, ZHAO Jianli1，2, LIU Xuejing1, CHEN Yiying1

1.College of Information Engineering, Hebei GEO University,Shijiazhuang 050031, China
2.School of Electronics & Information Engineering, ChonBuk National University, Jeonju 54896, Republic of Korea

Online:2018-06-01 Published:2018-06-14

摘要/Abstract

摘要： 多维背包（MKP）是组合优化中一个典型的NP难问题，广泛应用于工程和管理中。提出了一种改进的二进制差分演化算法（Modified Binary Differential Evolution algorithm，MBDE）求解MKP问题，算法关键步骤可分为两部分：二进制群体生成；得到候选可行解。提出了一种有效的衡量商品价值密度的方法用于对二进制个体修正和优化；设计了反向测试搜索和精英局部搜索策略来提高算法探索和开发能力，从而进一步提高了MBDE的求解精度和收敛速度。为验证MBDE算法的有效性，进行了三组实验，并和近期提出的解决MKP问题的其他启发式算法进行了比较，实验结果显示，MBDE算法求解精度更高。从算法运行时间看，求解速度快，非常适合求解大规模的MKP问题。

关键词: 多维背包, 差分演化算法, 价值密度, 反向测试搜索, 精英局部搜索

Abstract: Multidimensional Knapsack（MKP） is a typical NP-hard problem in combinatorial optimization problem. It is widely used in engineering and management. A Modified Binary Differential Evolution algorithm（MBDE） is proposed to solve the MKP problem. The key steps of the proposed algorithm can be divided into two parts： the binary group is generated; the candidate feasible solutions are obtained. The feasible solution is obtained by modifying the binary individual in the process of calculating the fitness value of the individual. An effective method for measuring the density of values is proposed for the repair of binary individuals. In addition,an opposite search strategy and an elite local search strategy are designed to improve accuracy and convergence speed of MBDE by increasing the exploration and the exploitment of the algorithm. To demonstrate the efficiency of MBDE, three sets of benchmark instances are solved and some comparisons with other methods available in literature are shown. MBDE algorithm obtains higher precision and running speed. The experimental results show that MBDE algorithm is very suitable for solving large-scale MKP problem.

Key words: Multidimensional Knapsack（MKP）, Differential Evolution（DE）, density of value, opposite search, elite local search

吴聪聪1，赵建立1，2，刘雪静1，陈嶷瑛1. 改进的差分演化算法求解多维背包问题[J]. 计算机工程与应用, 2018, 54(11): 153-160.

WU Congcong1, ZHAO Jianli1，2, LIU Xuejing1, CHEN Yiying1. Modified differential evolution algorithm for solving multidimensional knapsack problem[J]. Computer Engineering and Applications, 2018, 54(11): 153-160.

[1]	万书振. 自适应迁移预测的动态多目标差分演化算法[J]. 计算机工程与应用, 2016, 52(2): 86-91.
[2]	杨格兰1，金辉霞2，朱幸辉3. 基于差分演化和克隆选择机制的优化算法[J]. 计算机工程与应用, 2013, 49(10): 50-52.
[3]	钟培华，吴志远，缪建群 . 区域分割粒子群算法及多维背包问题求解[J]. 计算机工程与应用, 2011, 47(36): 73-75.
[4]	姚跃华，艾浩峰. 基于离散差分演化的粗糙集属性约简算法[J]. 计算机工程与应用, 2011, 47(34): 134-136.
[5]	张敬敏，张有华，李霞. 多目标柔性作业车间调度问题的混合差分算法[J]. 计算机工程与应用, 2011, 47(20): 245-248.
[6]	陆建波，闭应洲，龙珑，元昌安. 基于有导向变异算子求解多维背包问题[J]. 计算机工程与应用, 2011, 47(15): 36-38.
[7]	李荣胜¹，赵文峰²，徐惠民¹. 结合价值密度和截止期的网格实时作业调度[J]. 计算机工程与应用, 2010, 46(24): 1-3.
[8]	苏清华^1，2，胡中波¹，熊一能¹. 聚类问题的自适应杂交差分演化模拟退火算法[J]. 计算机工程与应用, 2010, 46(23): 41-43.
[9]	张敬敏,张翠军. 求解VSPSTW问题的混合差分演化算法[J]. 计算机工程与应用, 2009, 45(9): 230-232.
[10]	夏慧明¹，周永权². 改进差分进化策略在多峰值函数优化中的应用[J]. 计算机工程与应用, 2009, 45(32): 41-44.
[11]	胡中波¹，王曙霞²，熊盛武³，苏清华¹. 求解约束优化的一个自适应杂交差分演化算法[J]. 计算机工程与应用, 2009, 45(31): 211-214.
[12]	胡中波^1,2,熊盛武² . 折衷的差分演化算法在有约束优化中的应用[J]. 计算机工程与应用, 2007, 43(29): 95-97.
[13]	胡中波^1,2，熊盛武². 巴斯卡分布在多峰值函数优化中的应用[J]. 计算机工程与应用, 2007, 43(21): 67-69.
[14]	杨广益欧阳智敏全惠云. 松驰互补分布估计算法求解多维背包问题[J]. 计算机工程与应用, 2007, 43(12): 77-80.

改进的差分演化算法求解多维背包问题

Modified differential evolution algorithm for solving multidimensional knapsack problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics