关键词: 离散混合多宇宙算法, 折扣{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