Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 36 ยท Projects and Practice

Project: Knapsack Optimizer

Build a complete 0/1 knapsack optimizer with a genetic algorithm, check it against the exact dynamic programming answer, and report gap, speed and reliability.

In this project you build a small but complete optimizer, the way you would for a real task: define the problem, write an exact baseline so you know what "good" means, build the GA, measure it across many runs and write up the result. The problem is the 0/1 knapsack, a classic that models budgeting, cargo loading and portfolio picking.

The task: you have n items, each with a value and a weight. Choose a subset with total weight at most capacity and the largest total value.

Step 1: generate a problem and solve it exactly

For moderate capacities, dynamic programming (DP) solves knapsack exactly in O(n * capacity). Having the true optimum lets us measure the GA honestly. For real problems where no exact answer exists, the baseline would be a strong heuristic such as a greedy value-per-weight rule.

Python Problem generator, DP optimum and greedy baseline

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The in-place update best[w:] = np.maximum(best[w:], best[:-w] + v) is safe here because NumPy evaluates the right side into a new array before assigning, so each item is used at most once.

Step 2: design the GA

Decisions to write down before coding:

  • Chromosome: a bit vector with n genes (1 = packed).
  • Constraint handling: a repair operator (see Repair and Decoders). Over-weight bags drop the packed item with the worst value-to-weight ratio until they fit. Optionally, spare capacity is then filled with the best remaining item.
  • Fitness: total value of the (repaired) bag.
  • Selection: tournament of size 3.
  • Crossover: uniform crossover at probability 0.9.
  • Mutation: bit-flip with probability 2 / n.
  • Elitism: the best 2 individuals survive.
flowchart TD
    A["Random bit vectors"] --> B["Repair to feasible"]
    B --> C["Fitness = total value"]
    C --> D["Tournament selection"]
    D --> E["Uniform crossover + bit-flip mutation"]
    E --> B
    C --> F["Record best per generation"]

Repair happens after variation, so every individual that reaches the fitness function is feasible.

Step 3: implement and compare

Python The knapsack GA against the exact optimum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 4: evaluate like a professional

Report these numbers, not just "it works":

  1. Solution quality: average and worst gap to the optimum over many seeds.
  2. Reliability: how many runs reached the optimum.
  3. Cost: number of fitness evaluations (pop_size * gens) and wall time.
  4. Convergence curve: best value per generation, to decide if you ran long enough.

Use these to decide whether a bigger population or more generations are worth it.

Extension challenges

Try these, in roughly increasing difficulty:

  1. Remove the repair and use a penalty instead, using penalty functions. Compare the gap and the reliability.
  2. Count evaluations to reach 99 percent of the optimum. Which setting reaches it first?
  3. Multiple constraints: add a volume limit (a second capacity). The DP gets harder; does the GA still work?
  4. Two objectives: maximize value and minimize weight at the same time, using NSGA-II, and plot the front.
  5. Scale up: make 2,000 items. The DP table is now large but the GA still runs. How do they compare in time?

Common mistakes

  • Reporting one run. Use at least 8 seeds.
  • No exact baseline. Without it, "good" means nothing.
  • Repair that always leaves the same items out. The worst-ratio rule is deterministic; if the population loses diversity, add randomness to which item is dropped.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why compute the exact dynamic programming optimum for a test instance?

    A known optimum lets you compute the gap and judge the GA honestly.
  2. 2. In this project, what does the repair operator do to an over-weight bag?

    It makes every individual feasible before fitness is computed.
  3. 3. Which set of numbers best describes a stochastic optimizer's performance?

    You want typical and worst-case behavior, not luck.
  4. 4. When would a GA be preferable to dynamic programming for knapsack?

    DP cost grows with the capacity and extra constraints; heuristics scale more gently.

Summary

  • Start every optimization project with a problem generator and an exact or strong baseline.
  • Encode as bits, handle capacity with a greedy repair and use standard GA operators.
  • Evaluate with many seeds: mean gap, worst gap, hit rate, evaluation count.
  • Extend the project with penalties, extra constraints and a multi-objective version.

Next: Project: Evolve a Neural Network