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

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

作　　者：郝翔 贺毅朝 朱晓斌 翟庆雷 HAO Xiang;HE Yichao;ZHU Xiaobin;ZHAI Qinglei(College of Information Engineering,Hebei GEO University,Shijiazhuang 050031,China;Shijiazhuang College of Culture and Media,Shijiazhuang 050000,China)

机构地区：[1]河北地质大学信息工程学院,石家庄050031 [2]石家庄文化传媒学校,石家庄050000

出　　处：《计算机工程与应用》2021年第18期103-113,共11页Computer Engineering and Applications

基　　金：河北省自然科学基金(F2020403013);河北省教育厅科学技术研究项目(ZD2021016)。

摘　　要：为了利用多宇宙算法(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.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]