一种改进的混合遗传算法求解0_1背包问题  

An improved hybrid genetic algorithm for 0_1 knapsack problem

作　　者：白东玲[1] 郭绍永[2] 

机构地区：[1]新乡医学院计算机中心,河南新乡453003 [2]新乡医学院现代教育技术中心,河南新乡453003

出　　处：《电子设计工程》2013年第14期9-11,共3页Electronic Design Engineering

基　　金：2012年河南省社科联;经团联调研课题(SKL-2012-719)

摘　　要：背包问题是组合优化中的NP(Non-Deterministic Polynomial)难题之一,论文将贪婪算法与遗传算法相结合提出一种改进的混合遗传算法来求解0_1背包问题。改进的混合遗传算法通过遗传算法的择优,重复执行选择、交叉和变异以及贪婪算法的修正这样一个过程,使得所求解在可以接受的时间内越来越接近最优解。同时采用精英保留机制来加快算法的收敛速度。最后通过实证明该改进的算法可以有效地克服遗传算法中早熟的现象,该方法同样也适用其他优化问题。knapsack problem is a combinatorial optimization of one of the NP.This paper proposes an improved hybrid genetic algorithm,which is composed by genetic algorithm and greedy algorithm,for solving the 0-1 knapsack problem.The hybrid genetic algorithm repeats the process,which is done by selection,crossover,mution and greedy algorithm,until the optimal solution is found out in a reasonable amount of time,using the elitism mechanism to accelerate the convergence process.The experimentl results show that the improved GA effectively overcome the premature phenomenon and is also suitable for other combinatorial optimization problems.

关 键 词：遗传算法 贪婪算法 背包问题 精英选择 

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