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

Research on genetic algorithms for solving static and dynamic knapsack problems

为了有效处理遗传算法在求解静态与动态背包问题时产生非正常编码个体的问题,在分析已有处理方法不足的基础上,基于贪心策略提出了一种贪心修正算子与贪心优化算子相结合的新方法,并将该方法与遗传算法相融合给出了求解静态与动态背包问题的有效算法。仿真计算结果表明,在求解静态与动态背包问题时,利用所提出的新方法不仅可以解决非正常编码个体的问题,而且还能够显著提高个体所对应的可行解的质量,极大地改善了遗传算法的求解效果。

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.