计算机应用研究

作者：代祖华,周斌,龙玉晶,王宗泉,

单位：西北师范大学计算机科学与工程学院,兰州730070；

关键词：折扣{0-1}背包问题,启发式算法,粒子群算法,非正常编码个体,贪心修复与优化,D{0-1}KP数据集,

基金：兰州市科技发展指导性计划项目(2020-ZD-136)；西北师范大学研究生培养与课程改革项目(2020KGLX01009)；国家自然科学基金资助项目(61762080)；；

群智能启发式算法求解折扣{0-1}背包问题（D{0-1}KP）时，为提升求解效率和求解质量，需采用某种修复与优化策略将非正常编码个体转换为符合解约束条件的编码个体。在引入项集价值密度概念基础上，以粒子群算法（PSO）为例，提出一组基于项集的贪婪修复与优化方法（group greedy repair and optimization algorithm，GGROA），并进一步构造PSO-GGRDKP算法（PSO based GGROA for solving D{0-1}KP）以探究GGROA方法的可行性和性能。PSO-NGROADKP（PSO based NGROA for solving D{0-1}KP）和PSO-GRDKP（PSO based GROA for solving D{0-1}KP）是基于项贪心修复与优化方法的粒子群算法。在D{0-1}KP标准数据集的实验结果表明：与PSO-NGROADKP和PSO-GRDKP相比，PSO-GGRDKP算法的解误差率略高，但算法时间性能分别提升了13.8%、12.9%。

来源：2022年第8期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2022年第8期