The goal of this application is to use a genetic algorithm to find a solution to the Knapsack problem.

Genetic Algorithm

Genetic Algorithms work by creating a population of randomly generated possible solutions to a problem. Each individual competes against others to see who will reproduce based on a fitness which is determined by how close an individual is to the best solution. Two individuals are selected, and their genetic material (pieces of the possible answer) are combined randomly. As each generation passes, the solutions evolve closer to the ideal answer. The "correct" answer may never be found, but a "close enough" answer usually is.

Once the optimal solution is found, the algorithm continues to search, because it doesn't know if it has found the best answer yet. In order to avoid searching forever, we limit the number of generations before stopping the search.

Sample Data Solution

To verify the performance of the genetic algorithm, the actual solution is provided below:

Count Item unit weight unit value
1 map 9 150
1 compass 13 35
1 water 153 200
2 glucose 15 60
3 banana 27 60
1 cheese 23 30
1 suntan, cream 11 70
1 waterproof, overclothes 43 75
1 note-case 22 80
1 sunglasses 7 20
1 socks 4 50

Total value: 1010
Total weight: 396