The zero/one multiple knapsack problem and genetic algorithms
Sami Khuri, Thomas Bäck, Jörg Heitkötter · ACM Symposium on Applied Computing · 1994
A genetic algorithm, GENEsYs, is applied to an NP-complete problem, the 0/1 multiple knapsack problem. The partitioning of the search space resulting from this highly constrained problem may include substantially large infeasible regions. Our implementation allows for the breeding and participation of infeasible strings in the population. Unlike many other GA-based algorithms that are augmented with domainspecific knowledge, GENEsYs uses a simple fitness function that uses a graded penalty term to penalize infeasibly bred strings. We apply our genetic algorithm to problem instances from the literature of well known test problems and report our experimental results. These encouraging results, especially for relatively large test problems, indicate that genetic algorithms can be successfully used as heuristics for finding good solutions for highly constrained NP-complete problems.
Cited by 259 works. doi:10.1145/326619.326694
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Genetic algorithms in search, optimization, and machine learning
- Adaptation in Natural and Artificial Systems
- Combinatorial Optimization: Algorithms and Complexity.
- Optimization of Control Parameters for Genetic Algorithms
- Uniform crossover in genetic algorithms
- Numerical optimization of computer models
- Knapsack Problems: Algorithms and Computer Implementations
- Rechenberg, Ingo, Evolutionsstrategie — Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. 170 S. mit 36 Abb. Frommann-Holzboog-Verlag. Stuttgart 1973. Broschiert
- Some guidelines for genetic algorithms with penalty functions