计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (18): 103-113.DOI: 10.3778/j.issn.1002-8331.2008-0454

• 理论与研发 • 上一篇    下一篇

基于离散混合多宇宙算法求解折扣{0-1}背包问题

郝翔,贺毅朝,朱晓斌,翟庆雷   

  1. 1.河北地质大学 信息工程学院,石家庄 050031
    2.石家庄文化传媒学校,石家庄 050000
  • 出版日期:2021-09-15 发布日期:2021-09-13

Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem

HAO Xiang, HE Yichao, ZHU Xiaobin, ZHAI Qinglei   

  1. 1.College of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China
    2.Shijiazhuang College of Culture and Media, Shijiazhuang 050000, China
  • Online:2021-09-15 Published:2021-09-13

摘要:

为了利用多宇宙算法(MVO)求解折扣{0-1}背包问题(D{0-1}KP),基于模运算建立了离散型隧道模型和离散虫洞模型,引入具有反向搜索与突变特性的局部搜索策略,提出了第一个具有四进制编码的离散混合多宇宙算法DHMVO。在利用修复与优化算法消除不可行解的基础上,基于DHMVO提出了求解D{0-1}KP的一个新方法。为了检验DHMVO求解D{0-1}KP的性能,利用Kruskal-walli检验确定了其参数的最佳取值;将DHMVO求解四类大规模D{0-1}KP实例的计算结果与已有最好算法的计算结果进行比较,比较结果表明:DHMVO比其他算法的求解精度更高、稳定性更强,非常适合高效求解大规模D{0-1}KP实例。

关键词: 离散混合多宇宙算法, 折扣{0-1}背包问题, 模运算, 突变策略, 局部搜索策略

Abstract:

In order to effectively solve the discounted {0-1} knapsack problem (D{0-1}KP) by using the Multi-Verse Optimization algorithm(MVO), the discrete tunnel model and discrete wormhole model are firstly established based on modular operation, and a local search strategy with reverse search and mutation is introduced, then a Discrete Hybrid Multi-Verse Optimization algorithm(DHMVO) with quaternary coding is proposed. After that, on the basis of eliminating the infeasible solution based on the repair and optimization algorithm, a new method for solving D{0-1}KP is proposed by using DHMVO. In order to validate the performance of DHMVO in solving D{0-1}KP, kruskal-walli test and box diagram are firstly used to determine the best value of parameters, and then a comparison of the calculation results of DHMVO and existing algorithms in terms of solving four kinds of large-scale D{0-1}KP instances is made, which shows that DHMVO has higher accuracy and stronger stability than other algorithms, and it is more suitable and effective algorithm to solve large-scale D{0-1}KP instances.

Key words: discrete hybrid multi-verse optimization algorithm, discounted {0-1} knapsack problem, modular arithmetic, mutation strategies, local search strategy