折扣{0-1}背包问题粒子群算法的贪婪修复策略探究  

Greedy repair strategy of particle swarm optimization for discounted{0-1}knapsack problem

作　　者：代祖华 周斌 龙玉晶 王宗泉 Dai Zuhua;Zhou Bin;Long Yujing;Wang Zongquan(College of Computer Science&Engineering,Northwest Normal University,Lanzhou 730070,China)

机构地区：[1]西北师范大学计算机科学与工程学院,兰州730070

出　　处：《计算机应用研究》2022年第8期2363-2368,共6页Application Research of Computers

基　　金：兰州市科技发展指导性计划项目(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%。Swarm intelligence heuristic algorithm is used to solve discounted{0-1}knapsack problem(D{0-1}KP).In order to improve the solution efficiency and quality,a repair and optimization strategy is needed to convert abnormal coding individuals into coding individuals that meet the solution constraints.On the basis of introducing the concept of group value density,taking particle swarm optimization algorithm(PSO)as an example,this paper proposed a set of greedy repair and optimization methods based on group(GGROA),and further constructed the PSO based GGROA for solving D{0-1}KP algorithm(PSO-GGRDKP)to explore the feasibility and performance of GGROA.PSO-NGROADKP and PSO-GRDKP were PSO algorithms based on item greedy repair and optimization method.The experimental results on D{0-1}KP standard data set show that compared with PSO-NGROADKP and PSO-GRDKP,PSO-GGRDKP has slightly higher error rate,but the time performance of the algorithm is improved by 13.8%and 12.9%respectively.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]