Solving large knapsack problems with a genetic algorithm
Solving large knapsack problems with a genetic algorithm
复制标题
用遗传算法解决大型背包问题
DOI：
10.1109/icsmc.1995.537834
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
R. Spillman
中科院分区：
文献类型：
--
作者：
R. Spillman
本文提出了一种求解子集和问题的新方法。子集和问题是计算机科学中一个重要的NP完全问题，在运筹学、密码学和装箱等领域有着广泛的应用。遗传算法的开发，很容易解决这个问题。遗传算法从一个随机生成的解的种群开始，并使用前一种群的最佳元素来繁殖新的种群。每一代的解决方案产生更好的解决方案的子集和问题比前一代。结果表明，这种方法将有效地产生大（10,000元素或更多）子集和问题的解决方案。为了提高算法的性能，改变了算法的各种参数。
This paper develops a new approach to finding solutions to the subset sum problem. The subset sum problem is an important NP-complete problem in computer science which has applications in operations research, cryptography, and bin packing. A genetic algorithm is developed which easily solves this problem. The genetic algorithm begins with a randomly generated population of solutions and breeds a new population using the best elements of the previous population. Each generation of solutions produces better solutions to the subset-sum problem than the previous generation. It is shown that this approach will efficiently produce solutions to large (10,000 elements or more) subset sum problems. Various parameters of the algorithm are varied in order to improve its performance.