求解0-1背包问题的改进排挤遗传算法

摘要

提出了两种用于求解0-1背包问题的改进排挤遗传算法PFCGA和GCGA,PFCGA使用惩罚函数和排挤操作使算法能够比较稳定地求得最优解,GCGA把排挤遗传和贪婪算法相结合,对种群中非法染色体表示的不可行解进行修复使其变为可行解,对非优可行解进行修正使其尽量靠近最优解,GCGA在保证求解精度的前提下加快求解速度.通过仿真实验和比较分析结果表明,PFCGA和GCGA能够获得很高的求解精度和正确率,是求解0-1背包问题的有效算法.%Two kinds of improved crowding genetic algorithm for 0-1 knapsack problem are proposed, PFCGA and GCGA. PFCGA uses the penalty fimction and crowding genetic operation to get the optimal solution more stably. GCGA combines the greedy algorithm with crowding genetic. GCGA repairs the infeasible solution expressed by the illegal chromosome in the population and transform it to the feasible solution. GCGA modifies the non-optimal feasible solution and make it approach the optimal solution as much as possible.GCGA can get both high speed and high solution accuracy. According to the experiment simulation and comparative analysis, the test results demonstrate that the PFCGA and GCGA can get high solution accuracy and correct rate and they are rather efficient for solving 0-1 knapsack problem.