Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (18): 103-113.DOI: 10.3778/j.issn.1002-8331.2008-0454

Previous Articles     Next Articles

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



  1. 1.河北地质大学 信息工程学院,石家庄 050031
    2.石家庄文化传媒学校,石家庄 050000


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



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