2008 · 32 citations · 20 references
Natural SciencesEvolutionary BiologyDirected EvolutionEvolutionary DesignOptimizationCombinatorial OptimizationEvolutionary ComputationGenetic ProgrammingHeuristic OptimizationMetaheuristic OptimizationMultiobjective Optimization0-1 Knapsack ProblemEvolutionary AlgorithmsEvolutionary SearchFinal SolutionHeuristicsKnapsack ProblemsPareto Optimal SolutionStrongly Typed Genetic Programming
The 0/1 knapsack problem is one of the most exhaustively studied NP-hard combinatorial optimization problems. Many different approaches have been taken to obtain an approximate solution to the problem in polynomial time. Here we consider the biobjective 0/1 knapsack problem. The contribution of this paper is to show that a genetic programming system can evolve a set of heuristics that can give solutions on the Pareto front for multiobjective combinatorial problems. The genetic programming (GP) system outlined here evolves a heuristic which decides whether or not to add an item to the knapsack in such a way that the final solution is one of the Pareto optimal solutions. Moreover, the Pareto front obtained from the GP system is comparable to the front obtained from other human-designed heuristics. We discuss the issue of the diversity of the obtained Pareto front and the application of strongly-typed GP as a means of obtaining better diversity.
20
A Genetic Algorithm for the Multidimensional Knapsack Problem
P.C. Chu, J. E. Beasley · Journal of Heuristics · 1998 · 816 citations