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

• 模式识别与人工智能 • 上一篇    下一篇

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

吴聪聪1,赵建立1,2,刘雪静1,陈嶷瑛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. 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

摘要: 多维背包(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