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 2^{N} 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.

This page was created on November 23, 1998. Applet © 1998 by J. L. Pe