Items:
| Name | Weight | Value | Bound |
The goal of this application is to use a genetic algorithm to find a solution to the Knapsack problem.
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.
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