artificial life

Chapter 5: Genetic Algorithms

5.2 0-1 Knapsack Problem

The 0-1 Knapsack Problem lends itself well to showing the dvantages of a genetic algorithm. The problem is presented as a thief looting with a knapsack of finite capacity. Being a thief of great experience he is able to appraise both the weight and value of possible prizes at a glance [Cormen, et al. 1990].

The thief’s problem is that he can’t fit everything he sees into his Knapsack, but he wants to maximize the value of what he does take. Another limitation is that all items are indivisible, so he can’t choose to take a fraction of an item. Since there is not necessarily a correlation between weight and value, the search space of possible combinations is non-linear. This non-linearity makes a genetic algorithm an ideal candidate for a solution.