Genetic Algorithm: 0/1 Knapsack Evolution

Evolution

Population size 30

Mutation rate 3%

Crossover rate 80%

Speed 3 gen/s

Live Stats

Generation

Best fitness

Avg fitness

Best weight

0 / 0

Items (weight / value)

How it works

The 0/1 knapsack problem: given items each with a weight and a value, choose a subset that fits inside a capacity limit while maximizing total value. Each chromosome is a bit-string, one bit per item (1 = packed):

fitness(c) = sum(value_i for bit_i=1)  if  sum(weight_i for bit_i=1) <= capacity
fitness(c) = 0                          otherwise (infeasible, culled)

Each generation:

Elitism — the best 2 chromosomes are copied unchanged into the next generation.
Tournament selection — pick 3 random individuals, keep the fittest as a parent.
Single-point crossover — with probability = crossover rate, splice two parents at a random bit position to make a child.
Bit-flip mutation — each bit of the child flips independently with probability = mutation rate, injecting new genetic material.

In the 3D view, each row of cubes is one chromosome in the population, sorted best-to-worst front-to-back; each column is one item. A green cube means that item is packed in that individual; height and brightness scale with the item's value. The gold row is this generation's best solution. Watch the grid turn progressively greener as the population converges on a near-optimal packing.

Gen 0

Item packed Item left out Best of generation

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.