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

摘要：

为了利用多宇宙算法（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}背包问题, 模运算, 突变策略, 局部搜索策略