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

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

为了利用多宇宙算法(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实例。

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 dia-gram 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.