Genetic Algorithm (Knapsack) Theory Guide

Rules & Common Mistakes

• Exam Trap: Children Do Not Inherit Their Parents' Fitness

  A common mistake is assuming a child inherits its parents' fitness score directly. Every single child must be re-decoded from scratch, with weight and benefit calculated entirely fresh. A parent being 'Valid' has zero bearing on the child — the moment a mutation flips a single bit, that same child could become instantly 'Overweight' and collapse straight to a fitness of $0$.
• Lab Trap: Don't Confuse Bit Position with Item Index

  Mixing up the bit position with the item index is a silent, sneaky error. If the rule says 'Bit 3,' the correct row to check is 'Item 3' in the table — nothing else. Looking at the wrong table row makes the benefit and weight math 100% wrong, silently corrupting the entire rest of the trace without ever throwing an obvious error to catch it.
• Pro Tip: Don't 'Fix' a Zero Fitness Score

  Seeing a fitness score of $0$ often triggers panic, leading students to assume they calculated incorrectly and start adjusting bits to fix it. A $0$ is a completely valid, correct score for an overweight bag — nothing needs fixing. Own that $0$ confidently, write it down exactly as calculated, and move on to the next generation without doubting the underlying math.
• Pro Tip: Draw the 'Capacity Line' Before Tallying Anything

  Losing track of the max weight limit mid-tally is an easy way to lose marks. Write the 'Max Weight Limit' at the top of the scratch paper in a big box before starting any calculations. For every chromosome, write the total weight calculation right next to its binary string. If the total exceeds the limit, circle the resulting $0$ in bold ink to avoid accidentally reselecting that parent later.

Strengths, Weaknesses & When To Use It

When to use it:Reach for this when constraint satisfaction is the entire game — a massive item table paired with a strict weight limit where trying every single combination would crash the computer. On an exam, this is the right tool when the question asks for a 'near-optimal' selection of items that respects the bag's capacity, rather than demanding an exact mathematical proof of the single best possible answer.

Genetic Algorithm vs. Dynamic Programming

Genetic Algorithms are the fast and flexible survivor; Dynamic Programming is the mathematically perfect but slow specialist. Both solve the exact same Knapsack problem, but they approach it from entirely opposite philosophies. DP methodically explores every possible state to guarantee the single best answer exists somewhere in its table. GA breeds, mutates, and gambles its way toward a 'good enough' answer, trading mathematical certainty for raw speed and scalability.

• Guarantees — Good Enough vs. Provably Optimal: A Genetic Algorithm finds 'good enough' solutions quickly through trial and error, breeding toward improvement over generations. Dynamic Programming guarantees the single, absolute optimal solution by methodically exploring every possible state combination. On an exam, if the question demands certainty, DP wins outright. If the question accepts a strong approximation in exchange for speed, GA becomes the practical choice instead.
• Computational Scaling — Memory Wall vs. Graceful Degradation: Dynamic Programming hits a brutal memory wall as the bag's weight capacity and item count grow, since its table size explodes combinatorially. A Genetic Algorithm can handle massive item tables where DP would run out of RAM entirely, by sacrificing mathematical perfection for raw speed and a fixed, predictable memory footprint regardless of problem size.
• Problem Flexibility — Messy Rules vs. Rigid Formulas: A Genetic Algorithm handles messy real-world constraints, like minimum profit requirements or item dependencies, with relative ease — just adjust the fitness function. Dynamic Programming requires building a completely new, complex state-transition formula for every tiny change in the problem rules, making it brittle and labor-intensive whenever the underlying constraints shift even slightly.
• Exam Context — Which One Does the Question Want? If the question explicitly asks for the 'optimal value' or proof of correctness, Dynamic Programming is the intended answer. If the question instead asks how to scale to 1,000-plus items or manage changing, messy constraints, Genetic Algorithms become the expected and correct response on the exam paper.

Implementation Pseudocode

// GENETIC ALGORITHM — Solving the Knapsack Problem
// Goal: evolve bit-strings representing packed items toward maximum
// profit, without ever exceeding the bag's maximum weight limit.

FUNCTION knapsackGA(popSize, itemTable, maxWeight, maxGenerations):

    // ── INITIALIZATION ──
    population = []
    FOR i = 1 TO popSize:
        chromosome = generateRandomBitString(LENGTH(itemTable))
        population.add(chromosome)
    END FOR
    // Each chromosome is a random pack/leave decision for every item.
    // No smart packing yet — evolution figures that out over time.

    generation = 0

    // ── MAIN GENERATION LOOP ──
    WHILE generation < maxGenerations:

        // ── STEP 1: FITNESS EVALUATION (THE GATEKEEPER) ──
        FOR EACH chromosome IN population:

            totalWeight = 0
            totalBenefit = 0

            FOR EACH bit, index IN chromosome:
                IF bit == 1:
                    totalWeight  = totalWeight  + itemTable[index].weight
                    totalBenefit = totalBenefit + itemTable[index].benefit
                END IF
            END FOR
            // Map every 1 back to the item table to find its weight
            // and benefit. A 0 means that item never gets touched.

            // Exam Trap: ALWAYS check capacity before trusting benefit.
            IF totalWeight > maxWeight:
                chromosome.fitness = 0
                // The bag physically rips. It does not matter how high
                // totalBenefit is — overweight bags get a flat 0, no
                // partial credit, no exceptions, no rounding mercy.
            ELSE:
                chromosome.fitness = totalBenefit
            END IF

        END FOR

        // ── STEP 2: SELECTION ──
        SORT population BY fitness DESCENDING
        // Overweight chromosomes (fitness 0) sink straight to the bottom
        // and effectively get excluded from the primary mating pool.

        // ── STEP 3: CROSSOVER ──
        newPopulation = []
        FOR EACH pair of top parents IN population:
            cutPoint = chooseCutPoint(LENGTH(itemTable))
            child1 = parent1.head(cutPoint) + parent2.tail(cutPoint)
            child2 = parent2.head(cutPoint) + parent1.tail(cutPoint)
            // Crossover is mechanically identical to One Max — it swaps
            // tails blindly, with zero awareness of weight or benefit.
            newPopulation.add(child1)
            newPopulation.add(child2)
        END FOR

        // ── STEP 4: MUTATION ──
        FOR EACH child IN newPopulation:
            FOR EACH bit IN child:
                IF randomChance() < mutationRate:
                    FLIP bit (0 becomes 1, or 1 becomes 0)
                END IF
            END FOR
        END FOR
        // Exam Trap: flipping a 0 to a 1 silently adds an item to the
        // bag. A child that was perfectly valid before mutation can become
        // instantly overweight. Never assume a child's fitness carries
        // over from its parent — it must be re-evaluated from scratch.

        // ── STEP 5: POPULATION REPLACEMENT ──
        population = newPopulation
        generation = generation + 1

    END WHILE

    RETURN the chromosome WITH the highest fitness FOUND across all generations

END FUNCTION

Time & Space Complexity

Knapsack Genetic Algorithm Questions Students Always Get Wrong

• Why do I give an overweight bag a fitness of 0 instead of just removing it?

  The algorithm needs a fixed population size to maintain the breeding structure throughout every generation. Removing it would break the loop logic entirely. A $0$ acts as a dead chromosome that naturally gets filtered out by the selection sort, keeping the trace consistent with the required population count.

• My mutation flip turned a valid bag into an overweight one. Did I make a mistake?

  This is a classic mutation trap, not a calculation error. Mutation is blind and has no awareness of weights whatsoever. If a manual trace shows a valid bag turning overweight after a single bit-flip, the trace is being done perfectly. Keep going and trust the process.

• Do I really need to decode the child's fitness if I already know the parents?

  Yes, always. Crossover and mutation change which items get packed, so every child must be treated as a fresh, unknown entity. Re-decoding from the item table for every single child is the only reliable way to catch mutations that secretly cross the capacity threshold unnoticed.

• I keep using the wrong item weight — what's the best way to avoid this?

  Looking at the wrong table row is a common slip. Physically point at the item table with a pen for every bit that reads a $1$. Never do the lookups purely in the head. Cross-reference the bit-index with the table index carefully before adding any numbers together.

• If two bags have the same weight, how do I break the tie?

  If weights tie, the tie-breaker becomes the benefit score. If both weight and benefit tie exactly, keep them in their original presented order. Never invent new rules on the fly. If the professor provides no tie-break rule, document the assumption clearly on the exam paper.