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

Improved crowding genetic algorithm for 0-1 knapsack problem

作　　者：刘文涛[1] 胡家宝[2] 

机构地区：[1]武汉工业学院计算机与信息工程系,湖北武汉430023 [2]武汉理工大学计算机学院,湖北武汉430070

出　　处：《计算机工程与设计》2011年第6期2150-2153,2158,共5页Computer Engineering and Design

摘　　要：提出了两种用于求解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 function 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.

关 键 词：遗传算法 排挤 0-1背包问题 惩罚函数 贪婪算法 

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