差分进化变异策略rand/3/bin求解0-1背包问题  

Differential Evolution Mutation Strategy rand/3/bin to Solve 0-1 Knapsack Problem

作　　者：王泽旭 文斌 罗自强[2,3] WANG Zexu;WEN Bin;LUO Ziqiang(Key Laboratory of Data Science and Intelligence Education of Ministry of Education(Hainan Normal University),Haikou 571158;Cloud Computing and Big Data Research Center,Hainan Normal University,Haikou 571158;.School of Information Science and Technology,Hainan Normal University,Haikou 571158)

机构地区：[1]数据科学与智慧教育教育部重点实验室(海南师范大学),海口571158 [2]海南师范大学云计算与大数据研究中心,海口571158 [3]海南师范大学信息科学技术学院,海口571158

出　　处：《计算机与数字工程》2021年第7期1383-1388,共6页Computer & Digital Engineering

基　　金：海南自然科学基金项目(编号:620R605,620MS045);国家自然科学基金项目(编号:61562024,61463012)资助。

摘　　要：0-1背包问题是背包问题中的基础也是最为经典的一大分支,其组合优化模型被广泛的应用于社会生产生活的各个领域,对NP完全问题的求解有重要价值。传统的启发式算法如遗传算法、基本差分进化算法、粒子群算法,在解决相同0-1背包问题时,差分进化算法在解决离散型0-1背包问题时收敛更快,但存在早熟问题。论文从启发式算法角度出发,结合差分进化算法中变异策略的特点,提出一种新的变异策略rand/3/bin求解方法,与遗传算法、粒子群算法、采取两种变异策略的差分进化进行性能对比实验(实验测试数据已公开在Github),结果表明:该算法实现了相对于原有实验收敛更快和结果更优的结果,具有良好的应用价值。0-1 knapsack problem is the basis of knapsack problem,and it is also a classical branch.Its combinatorial optimi⁃zation model is widely used in various fields of social production and life,and has important value for solving NP complete prob⁃lems.Traditional heuristic algorithms such as genetic algorithm,basic differential evolution algorithm,particle swarm optimization algorithm,when solving the same 0-1 knapsack problem,differential evolution algorithm converges faster when solving discrete 0-1 knapsack problem,but it has premature problem.In this paper,from the perspective of heuristic algorithm,combined with the characteristics of mutation strategy in differential evolution algorithm,a new mutation strategy rand/3/bin solution method is pro⁃posed.Compared with genetic algorithm,particle swarm optimization algorithm and differential evolution performance of two muta⁃tion strategies,the results show that the algorithm achieves faster convergence and better results than the original experiment.

关 键 词：0-1背包 遗传算法 差分进化算法 粒子群算法 

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