Evolving Digital Circuits for the Knapsack Problem
This work addresses the knapsack problem, an NP-Complete issue, using a genetic programming variant, but it is incremental as it applies an existing method to a new domain.
The paper tackled the knapsack problem by evolving digital circuits using Multi Expression Programming, achieving good performance on test problems as shown in numerical experiments.
Multi Expression Programming (MEP) is a Genetic Programming variant that uses linear chromosomes for solution encoding. A unique feature of MEP is its ability of encoding multiple solutions of a problem in a single chromosome. In this paper we use Multi Expression Programming for evolving digital circuits for a well-known NP-Complete problem: the knapsack (subset sum) problem. Numerical experiments show that Multi Expression Programming performs well on the considered test problems.