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

群智能启发式算法求解折扣{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%。

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

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.