Abstract
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.
Keywords
Knapsack problemSubset sum problemBin packing problemGenetic algorithmPopulationComputer scienceMathematical optimizationApproximation algorithmContinuous knapsack problemAlgorithmMathematicsBin
Affiliated Institutions
Related Publications
An interactive fuzzy satisficing method for multiobjective multidimensional 0-1 knapsack problems through genetic algorithms
In this paper, an interactive fuzzy satisficing method for multiobjective multidimensional 0-1 knapsack problems is proposed by incorporating the desirable features of both the ...
Hiding information and signatures in trapdoor knapsacks
The knapsack problem is an NP-complete combinatorial problem that is strongly believed to be computationally difficult to solve in general. Specific instances of this problem th...
Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach
Evolutionary algorithms (EAs) are often well-suited for optimization problems involving several, often conflicting objectives. Since 1985, various evolutionary approaches to mul...
A new version of ant system for subset problems
Early applications of Ant Colony Optimization (ACO) have been mainly concerned with solving ordering problems (e.g., traveling salesman problem). We introduce a new version of A...
MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition
Decomposition is a basic strategy in traditional multiobjective optimization. However, it has not yet been widely used in multiobjective evolutionary optimization. This paper pr...
Publication Info
- Year
- 2002
- Type
- article
- Volume
- 1
- Pages
- 632-637
- Citations
- 29
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
29
OpenAlex
Cite This
Richard Spillman
(2002).
Solving large knapsack problems with a genetic algorithm.
, 1
, 632-637.
https://doi.org/10.1109/icsmc.1995.537834
Identifiers
- DOI
- 10.1109/icsmc.1995.537834