改进的克隆选择算法求解0-1背包问题  

Solution of 0-1 Knapsack Problem Applying Improved CSA Algorithm

作　　者：王炼红[1] 章兢[1] 龚固丰[1] 何昭晖[1] 

机构地区：[1]湖南大学电气与信息工程学院,湖南长沙410082

出　　处：《湖南大学学报（自然科学版）》2009年第3期81-84,共4页Journal of Hunan University:Natural Sciences

基　　金：国家自然科学基金重点资助项目(60634020);教育部高等学校博士学科点专项科研基金资助项目(20060532026)

摘　　要：提出了一种改进的克隆选择算法(Improved CSA),该算法采用贪婪策略与宽限边界值相结合的方法,利用未成熟优良子群体提供的信息修改个体基因位来改善种群质量;同时增加一个历史至当前代最佳个体记忆单元防止种群退化.通过对2个0-1背包问题的仿真实验表明:该算法比一般CSA算法和遗传算法能更快的找到最优解;其搜索效率更高,性能更加稳定.This paper proposed an improved Clonal Selection Algorithm （CSA）, which combined greedy strategy with an extended boundary, and modified individuality＇s gene bit to improve population by using the good gene bit information in the immaturate subpopulation. Meanwhile an additional memory cell of the best individuality was set up to avoid population devolution. The simulation test of two 0-1 Knapsack Problems shows that the algorithm can search for the best solution more quickly than the current CSA, and its efficiency is higher and its stability is better than the CSA and Genetic Algorjthm（GA）.

关 键 词：算法 克隆选择 贪婪策略 背包问题 

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