Genetic Algorithm (Knapsack)
Genetic Algorithm, Knapsack Problem, Constrained Optimization, Penalty Function, Fitness, Chromosomes
If the One-Max problem is learning to walk, the Knapsack problem is learning to run an obstacle course. You are given a bag (the knapsack) with a strict weight limit, and a list of items that each have a Weight and a Benefit. Your goal is to pack the bag with the maximum possible benefit without breaking the strap! In our Genetic Algorithm, a chromosome like '101' means we pack Item 1, skip Item 2, and pack Item 3. It introduces a massive real-world concept: Constraint Handling.
The Fitness & Penalty Function
What do these variables mean?
- Total Benefit. The sum of the benefits of all the items you actually packed (where the bit is 1).
- Total Weight. The sum of the weights of all the items you packed.
- The strict weight limit of your bag.
- The FormulaThis is a 'Piecewise' function. It checks a condition first: If your bag is under the weight limit, your score is your Total Benefit. But if your bag goes even 1 gram over the limit, your score instantly drops to 0 (a Penalty).
- The Penalty RuleWe give overweight bags a 0 instead of deleting them so our population size stays perfectly consistent for our code loops!
How Does it Work?
Define the Constraint: Establish your bag's Maximum Weight and list out your items with their specific (Benefit, Weight) values.
Decode the Chromosome: Look at your binary string. A '1' means the item goes in the bag; a '0' means it stays out.
Evaluate Weight & Benefit: Add up the weights and benefits of the packed items.
The Penalty Check: If Total Weight > Max Weight, the fitness score is 0. Otherwise, the fitness score is the Total Benefit.
Selection: Sort the population by fitness score from highest to lowest. Overweight bags (score 0) sink to the bottom and won't be chosen as parents.
Crossover & Mutation: Breed the top-scoring bags by swapping tails and randomly flipping bits to discover even better packing combinations.
Repeat: Keep evaluating new generations, applying the penalty to any overweight children, until you find the ultimate packing list.
Important Rules & Conventions
- Exam Trick 1: Always calculate the Weight *first*. If a chromosome is overweight, don't even waste your time calculating the Benefit! Just write 'Fitness = 0' and move to the next one.
- Exam Trick 2: A chromosome of all 0s (0000) is technically valid (Weight = 0), but its Fitness is 0. A chromosome of all 1s (1111) is almost always overweight, so its Fitness is also 0. The optimal answer is always a careful mix of 1s and 0s.
- Exam Trick 3: Make a table with columns for 'Binary String', 'Total Weight', 'Total Benefit', 'Valid?', and 'Final Fitness'. It prevents silly addition mistakes.
Advantages
- ✓ Perfect for solving NP-Hard problems. Checking every possible combination of 50 items would take computers years; a GA finds a great answer in seconds.
- ✓ Beautifully handles strict, unbending real-world constraints simply by adding a math penalty.
- ✓ Highly adaptable. You can easily change the constraints (e.g., adding a 'Max Volume' limit alongside the 'Max Weight' limit).
Disadvantages
- × Can suffer from 'Mass Extinction'. If you have a tiny bag and heavy items, randomly generating starting chromosomes might result in a population where *everyone* is overweight (Fitness = 0), giving the algorithm no 'good parents' to start with.
- × Just like One-Max, it is an estimation algorithm. It guarantees a 'really good' answer, but not always the mathematically perfect answer.
Summary
The Genetic Knapsack problem takes the biological evolution we learned in One-Max and forces it to survive in a harsh environment with strict rules. By heavily penalizing chromosomes that break the rules, the algorithm naturally learns to pack the most valuable, efficient bag possible without ever needing to guess every single combination.