Genetic Algorithm Knapsack: A Solved Numerical Example

Try Genetic Algorithm Solver →Read Genetic Algorithm Theory →

Scenario: Disaster Relief Supply Packing

The Objective: Simulate packing emergency supplies by evolving binary combinations to maximize the total survival benefit without exceeding the strict 10kg weight limit.

Core Mechanics

▼

The Binary Blueprint: Every candidate solution is just a string of $1$ s and $0$ s. A $1$ means the item goes in the bag; a $0$ means it stays behind. The algorithm’s entire job is to breed the perfect string.
The Overweight Death Penalty: A solution's fitness score is the total value of its packed items. However, if the total weight exceeds the bag's capacity, the solution is illegal! It must instantly receive a score of $0$ or a massive penalty.
Targeted Crossover: In textbook theory, parents are split randomly. On an exam, you are given the exact bit to slice at. Simply chop both parent strings at that specified point and swap their tails to create the two children.
Deterministic Mutation: Real mutation is a random wildcard. But here, you will be told exactly which bit to target. Find that specific position in your new child string and flip it (a $0$ becomes a $1$ , or a $1$ becomes a $0$ ).

Step 1: The Knapsack Items & Evolution Rules

The Genetic Knapsack problem aims to maximize the total benefit of selected items without exceeding the strict weight limit. A $1$ in the chromosome means the item is packed; a $0$ means it is left behind.

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 & SetupMax Weight Limit: 10 kg

Initial Chromosomes (Starting Population):

P111011

P210101

P301110

P411100

Crossover Rules:► Cross New #1 & New #2 after bit 2► Cross New #3 & New #4 after bit 2

Mutation Rules:► Mutate Child C1 at bit 4

Want to edit this data in the live solver?

Step 2 & 3: Decode & Fitness Evaluation

We decode each binary string to see which items are inside the bag. If the bag exceeds 10kg, the constraints are violated and it receives a penalty (Fitness = 0).

Parent ID	Chromosome	Items Inside	Weight	Benefit	Constraint	Fitness $f(x)$
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 4: Selection Pool (Descending)

Parents are sorted by their fitness score. Notice how any invalid chromosomes with a fitness of $0$ naturally sink to the bottom of the pool, meaning they will likely die off in this generation.

New Rank	Chromosome	Weight	Benefit	Fitness $f(x)$
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 5: Genetic Operations (Crossover & Mutation)

Parents swap packed items based on the crossover rules. If a parent had a fitness of 0 (invalid), it is struck out and does not reproduce. Then, target children undergo mutation.

1. Apply Crossover

Child ID	Chromosome
C1	11101
C2	10011
C3	01100
C4	11110

2. Apply Mutation

Child ID	Chromosome
C1 (mutated)	11111
C2	10011
C3	01100
C4	11110

Step 6: Final Generation Evaluation

We evaluate the fitness of the new children to see if they exceeded the weight limit. If the stopping criteria is not met, this new generation becomes the parent pool for the next iteration.

Child ID	New Chromosome	Genetics Status	Weight	Constraint	Final Fitness $f(x)$
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 Takeaway

Notice how Parent P4 and Child C1 are instantly slapped with a fitness score of 0, despite packing highly valuable items! This perfectly demonstrates the most crucial exam concept for the Knapsack problem: constraint violations must be penalized heavily so overweight solutions die off and cannot pass on their invalid genes.