A Genetic Knapsack Problem Solver

The Knapsack Problem

To stuff a knapsack of fixed size as fully as possible with packets taken from a collection of packets of fixed sizes.

[One version of the knapsack problem requires packets that fill up the knapsack.] If N is the total number of packets, then there are 2N subsets of the packet collection. So an exhaustive search for a solution to the knapsack problem generally takes exponential running time. Therefore, the obvious brute-force approach is infeasible. Some dynamic programming techniques also have exponential running time, but have proven useful in practice. Here, we take a different approach, and investigate the problem using genetic methods.

A Genetic Algorithm

Genetic algorithms have been useful in obtaining fast converging, if occasionally approximate, solutions to problems traditionally thought of as computationally infeasible, e. g., the traveling salesman problem (where a salesman wants to determine a shortest tour of certain cities). For the knapsack problem, we describe (below) and implement (in the above applet) the following genetic algorithm.

At the start, solution points are randomly selected. If N is the total number of packets, then a solution point is just a finite sequence s of N terms such that s[n] is either 0 or the size of the n-th packet. s[n] = 0 if and only if the n-th packet is not selected in the solution point. At each stage ("generation"), the solution points are evaluated for "fitness" (according to how much of the knapsack capacity they fill), and the best and worst performers are identified. When conditions are ripe for "breeding", the best solution "mates" with a random (non-extreme) solution, and the offspring replaces the worst one. A random solution is also possibly "mutated" to vary the gene pool. [The natural selection and mutation routines that are performed during each generation mirror the two major processes that biologists currently believe are responsible for the emergence and development of the species.]

The "genes" of a solution are just its sequence terms. Two solutions mate to produce (provided knapsack capacity is not exceeded) an offspring which inherits about half of each parent's genes. The inherited sets of genes are fused at a randomly selected "crossover" point. For example, if the solutions

1 2 3 4 15 16

7 8 9 10 11 12

mate with crossover point at position five, then the first three genes can come from the first solution starting at this position, i.e., 15 16 1, and the other three genes then come from the remaining positions from the second solution, i.e., 8 9 10. The offspring has genes 15 16 1 8 9 10.

A mutation of a solution is a random change of up to half of its current genes. A gene change sets a term to 0 if the term is currently nonzero, and sets a term to the corresponding packet size if the term is currently zero.

In the above applet, press the "Enter" button after keying in the problem parameters.

You can browse through the Java source code here.