%0 Journal Article %A HAO Xiang %A HE Yichao %A ZHU Xiaobin %A ZHAI Qinglei %T Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem %D 2021 %R 10.3778/j.issn.1002-8331.2008-0454 %J Computer Engineering and Applications %P 103-113 %V 57 %N 18 %X

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.

%U http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2008-0454