Genetic Algorithm (Knapsack) Calculator

Read the Theory Guide →

Enter an item table with benefits and weights, set the maximum weight limit, and define a starting population of binary chromosomes with crossover and mutation rules. The solver runs one evolution cycle and shows how each chromosome is decoded, ranked, crossed, mutated, and checked against the weight constraint.

What You Can Explore

  • Edit the item table's benefits and weights, adding or removing items. Each chromosome must contain exactly one bit for every item.
  • Set the Max Weight Limit to decide whether a chromosome is Valid or Overweight.
  • Add, edit, or remove chromosomes, crossover rules, and mutation rules to control how the next generation is produced.
  • Press Run Evolution Cycle and follow each chromosome from decoding and fitness evaluation through selection, crossover, mutation, and the final constraint check.
Core Mechanics
▼
  • The Binary Blueprint: Every candidate solution is just a string of 11s and 00s. A 11 means the item goes in the bag; a 00 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 00 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 00 becomes a 11, or a 11 becomes a 00).
Initializing Workspace...

Understanding Your Result

The output is one generation produced from your items, weight limit, initial chromosomes, and evolution rules. The solver first decodes each chromosome into its selected items, total weight, and total benefit, then ranks the population and applies crossover and mutation before checking the resulting children against the weight limit again.

  • Fitness equals the total benefit when a chromosome is Valid and 0 when it is Overweight. Compare the Weight and Constraint columns to see why a chromosome received its fitness.
  • Step 3 ranks chromosomes by fitness and shows their original IDs in parentheses. Crossover rules use these ranked positions, such as New #2 and New #3, rather than the original P1, P2, and P3 IDs.
  • Each bit represents one item, and bit positions start at 1. A 1 means the corresponding item is selected; a 0 means it is not selected.
  • Crossover and mutation operate directly on the chromosome bits. They do not check the weight limit or benefit while creating children.
  • Step 6 decodes every child again and recalculates its weight, benefit, constraint status, and final fitness. A chromosome that looked strong before mutation can therefore become Overweight and receive a fitness of 0.

Try These Experiments

Raise the Weight Limit

Setup: Run the preloaded data with a Max Weight Limit of 22. In the initial evaluation, C1 has weight 24, so it is Overweight with fitness 0.

Action: Change Max Weight Limit from 22 to 26, keep the chromosomes and evolution rules unchanged, and press Run Evolution Cycle again.

What to Observe: C1 is now Valid with weight 24 and fitness 19, and it ranks below C2 and C3 in the selection pool. The later mutations can still make another child Overweight, because the higher limit only changes the constraint check.

Takeaway: The weight limit determines which chromosomes are allowed to keep their benefit as fitness. Changing the limit can turn an Overweight chromosome into a valid one without changing its bits, weight, or benefit.

Remove the Mutation Rules

Setup: Run the preloaded data with a Max Weight Limit of 22. The current mutation rules change C2 and C3 after crossover, producing different final chromosomes.

Action: Click × on all four Mutation rules so that no mutation rules remain, then press Run Evolution Cycle again.

What to Observe: C2 remains at 1100011 after crossover instead of being mutated further. Its weight is 25 and it remains Overweight, so its final fitness is 0. C3 remains at 0100100 with weight 12, benefit 15, and fitness 15.

Takeaway: Mutation can change a child's weight and benefit after crossover. Removing mutation lets you see the chromosomes produced by crossover alone and how the weight constraint evaluates them.

Mutate the Best Initial Chromosome

Setup: Run the preloaded data with a Max Weight Limit of 22. C3 starts with the highest initial fitness of 21, while C1 is Overweight with fitness 0.

Action: Click + Add Mutation and use the new rule's default setting, Mutate 1 at Bit 1. Keep the existing rules and run the evolution cycle again.

What to Observe: C1 changes from 0101010 to 1101010. Its weight increases from 24 to 31 and its benefit increases from 19 to 24, but it remains Overweight, so its final fitness is 0.

Takeaway: A mutation that changes a 0 to 1 adds another item to the chromosome. That can increase benefit but also increase weight enough to violate the constraint, so a higher benefit does not always produce higher fitness.