改进的遗传算法在背包问题中的应用  

Improved Genetic Algorithm Applied to the Knapsack Problem

作　　者：潘玉奇[1] 栾虹[1] 张茜[2] 

机构地区：[1]济南大学信息科学与工程学院,山东济南250022 [2]中国地质大学(北京)地球物理与信息技术学院,100083

出　　处：《信息技术与信息化》2007年第2期119-120,共2页Information Technology and Informatization

摘　　要：介绍了一种最优保存遗传算法,针对该算法提出一种改进方案,一方面改变了保存最优个体的方法,另一方面对不满足约束条件的个体采用贪心策略进行改造,使其满足条件。最后通过一个具体的背包问题实例验证了改进算法的可行性和有效性。A genetic algorithm with best elitist preserved method is introduced. In allusion to this algorithm an improved project is proposed. On the one hand best elitist preserved method is changed, on the other hand those individuals ,which arenl satisfied with restrict condition, are reconstructed with greedy strategy. The feasibility and validity of improved algorithm is proved through a knapsack problem instance.

关 键 词：遗传算法 背包问题 贪心策略 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]