Evolving Item Selections with a Genetic Algorithm for Knapsack
Problem Setup
Scenario:Select a combination of items that maximizes total benefit while keeping the total weight within the knapsack capacity.
Given:Five items are available, each with a specified benefit and weight, with a maximum allowed weight of 10. A population of four binary chromosomes represents different item selections, along with defined crossover and mutation operations.
Task:Decode the initial chromosomes, evaluate their weight, benefit, and fitness under the weight constraint, then apply the specified selection, crossover, and mutation steps to determine the fitness of the resulting generation.
Need a quick refresher? Review Genetic Algorithm theory
Knapsack Items & Evolution Setup
Each bit in a chromosome corresponds to an item in the table, in order: 1 means the item is selected, and 0 means it is excluded. The selected items determine the chromosome's total weight and benefit.
| Data Point | Item Name✎ | Benefit (Score)✎ | Weight (Cost)✎ |
|---|---|---|---|
| P1 | Medical Kit | 9 | 4 |
| P2 | Water Supplies | 7 | 3 |
| P3 | Food Rations | 8 | 5 |
| P4 | Blankets | 4 | 2 |
| P5 | Radio | 5 | 1 |
Knapsack Constraints & Population
Step-by-Step Evolution
Step 1 & 2: Initial Decode & Fitness Evaluation
| Parent ID | Chromosome | Items Inside | Weight | Benefit | Constraint | Fitness |
|---|---|---|---|---|---|---|
| P1 | 11011 | 1, 2, 4, 5 | 10 | 25 | Valid | 25 |
| P2 | 10101 | 1, 3, 5 | 10 | 22 | Valid | 22 |
| P3 | 01110 | 2, 3, 4 | 10 | 19 | Valid | 19 |
| P4 | 11100 | 1, 2, 3 | 12 | 24 | Overweight | 0 |
Step 3: Rank by Fitness (Descending)
| New Rank | Chromosome | Weight | Benefit | Fitness |
|---|---|---|---|---|
| New #1 (P1) | 11011 | 10 | 25 | 25 |
| New #2 (P2) | 10101 | 10 | 22 | 22 |
| New #3 (P3) | 01110 | 10 | 19 | 19 |
| New #4 (P4) | 11100 | 12 | 24 | 0 |
Step 4: After Crossover
| Child ID | Chromosome |
|---|---|
| C1 | 11101 |
| C2 | 10011 |
| C3 | 01100 |
| C4 | 11110 |
Step 5: After Mutation
| Child ID | Chromosome |
|---|---|
| C1 (mutated) | 11111 |
| C2 | 10011 |
| C3 | 01100 |
| C4 | 11110 |
Step 6: Final Constraint Check & Fitness
| Child ID | New Chromosome | Genetics Status | Weight | Constraint | Final Fitness |
|---|---|---|---|---|---|
| C1 | 11111 | Mutated | 15 | Overweight | 0 |
| C2 | 10011 | Crossover | 7 | Valid | 18 |
| C3 | 01100 | Crossover | 8 | Valid | 15 |
| C4 | 11110 | Crossover | 14 | Overweight | 0 |
Final Answer
Best chromosome:10011
Total weight:7
Total benefit:18
Chromosome 10011 selects the Medical Kit, Blankets, and Radio, giving a total weight of 7 and benefit of 18. It is the best feasible offspring in this generation. However, the initial population contained chromosome 11011 with benefit 25, showing that the new generation can lose a stronger solution when the best parent is not preserved.
Exam Takeaway
- Decode the chromosome before calculating fitness: Each bit represents whether an item is included. Sum the weights and benefits of selected items separately, then apply the capacity constraint. Fitness is not simply the number of selected items.
- Always check feasibility after genetic operations: Crossover or mutation can change both total weight and benefit. In this example's fitness rule, any chromosome exceeding the capacity receives zero fitness, regardless of how high its raw benefit is.
- The best offspring may be worse than the best parent: Genetic operators do not guarantee improvement in every generation. Without elitism or another preservation mechanism, a strong parent can disappear even when its offspring have lower fitness.