利用遗传算法求解静态与动态背包问题的研究  

Research on genetic algorithms for solving static and dynamic knapsack problems

作　　者：贺毅朝[1] 宋建民[2] 张敬敏[1] 苟海燕[3] 

机构地区：[1]石家庄经济学院信息工程学院,石家庄050031 [2]石家庄经济学院数理学院,石家庄050031 [3]石家庄经济学院华信学院,河北新乐050000

出　　处：《计算机应用研究》2015年第4期1011-1015,共5页Application Research of Computers

基　　金：河北省教育厅自然科学基金资助项目(Z2013110)

摘　　要：为了有效处理遗传算法在求解静态与动态背包问题时产生非正常编码个体的问题,在分析已有处理方法不足的基础上,基于贪心策略提出了一种贪心修正算子与贪心优化算子相结合的新方法,并将该方法与遗传算法相融合给出了求解静态与动态背包问题的有效算法。仿真计算结果表明,在求解静态与动态背包问题时,利用所提出的新方法不仅可以解决非正常编码个体的问题,而且还能够显著提高个体所对应的可行解的质量,极大地改善了遗传算法的求解效果。For solving the problem of non-normal coding individual by using genetic algorithms（ GAs） for static and dynamic knapsack problems,this paper analyzed and pointed the pitfalls of existent methods,and proposed a new method for handling the problem of non-normal coding individual by greedy strategy,which included greedy modify operator and greedy optimize operator. Then,it gave out two efficient algorithms which combined the new method with GAs for static and dynamic knapsack problems. The numerical computation results show that the new method not only modify non-normal coding individual but also improve the quality of individual,and greatly improves the performance of GAs for static and dynamic knapsack problems.

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

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