Genetic Algorithm (One-Max) Theory Guide

Rules & Common Mistakes

• Exam Trap: Crossing the Original Parents Instead of the Ranked Pool

  After calculating initial fitness, carelessly applying crossover to $P_1$ and $P_2$ simply because they sit first on the paper is a common and costly mistake. The population must be sorted descending first, and crossover applied to the newly ranked New #1 and New #2. Forgetting to sort ruins the entire generation, since weak strings end up mating instead of the strongest survivors actually intended by the algorithm.
• Exam Trap: 0-Based vs. 1-Based Mutation Indexing

  The single most common way to lose marks is flipping the wrong bit during mutation. If the rule says 'Mutate Bit 2,' does that mean the second number in the string (1-based) or the third number (0-based)? Always rigorously check the professor's notes or previous worked examples to confirm the indexing convention being used before drawing a single line or flipping a single bit on the exam.
• Pro Tip: Physically Draw the Cut Line to Avoid Overwriting

  When swapping tails during crossover, accidentally copying bits from the same parent twice — overwriting the genetic code instead of properly mixing it — is a surprisingly frequent error. Drawing a hard vertical line down the paper, visually separating the 'heads' and 'tails,' creates a physical barrier. This prevents the eyes from wandering and mixing up the binary strings when writing out the final children chromosomes.
• Pro Tip: Don't Panic if Fitness Goes Down Temporarily

  During manual traces, a random mutation rule might force a perfect $1$ to flip back to a $0$, lowering a child's fitness below its parents. Resist the urge to panic or 'correct' the math. Destructive mutation is a real, intended part of the algorithm designed to maintain genetic diversity across the population. If the rule says to flip it, flip it, accept the lower score, and move confidently to the next step.

Strengths, Weaknesses & When To Use It

When to use it:Genetic Algorithms are the ultimate fallback when a search space becomes combinatorially explosive — think scheduling thousands of flights or routing delivery trucks across a city. On an exam, reach for a GA when the problem is too massive for brute force, and the question asks for a 'good enough' optimization rather than a mathematically guaranteed perfect answer. If a question strictly requires the absolute shortest or perfect path, a GA is the wrong choice entirely.

Genetic Algorithm: One Max vs. Knapsack

The One Max problem is the training ground; the Knapsack problem is the actual exam. Both use the exact same evolutionary machinery — Selection, Crossover, and Mutation are mathematically identical between them. The only real difference is the fitness function. One Max is unconstrained, meaning more $1$s is always better. Knapsack introduces a harsh physical constraint, fundamentally changing what it means for a chromosome to survive.

• The Fitness Constraint: One Max has an unconstrained fitness function — simply counting the $1$s with no penalty for an all-$1$s string. The Knapsack problem introduces a hard weight limit instead. Any chromosome whose total combined weight exceeds the bag's maximum capacity immediately receives a fitness score of $0$, automatically killing it off from the breeding pool entirely.
• The Definition of Perfection: In One Max, the perfect chromosome is completely obvious from the very start — a string of all $1$s ($1111$). In Knapsack, an all-$1$s chromosome represents packing every single item into the bag, which will almost always break the weight limit and result in total failure. The optimal Knapsack solution is a carefully balanced mix of $0$s and $1$s.
• Evaluation Complexity: One Max fitness evaluation is trivially fast — it requires a single visual glance to count the bits in the string. Knapsack fitness requires a multi-step decoding process instead. The chromosome must be mapped against an external item table, total weights summed, the constraint limit verified, and only then can the actual financial benefits be summed up.
• Exam Strategy Application: If a professor wants to strictly test the ability to manually trace crossover and mutation mechanics without wasting time on arithmetic, One Max gets used. If the goal is testing the ability to model real-world constraints and decode binary representations into physical items, Knapsack becomes the natural and expected exam choice instead.

Implementation Pseudocode

// GENETIC ALGORITHM — Solving the One Max Problem
// Goal: evolve a population of random bit-strings toward all 1s.
// Selection, Crossover, and Mutation repeat generation after generation.

FUNCTION geneticAlgorithm(popSize, stringLength, maxGenerations):

    // ── INITIALIZATION ──
    population = []
    FOR i = 1 TO popSize:
        chromosome = generateRandomBitString(stringLength)
        population.add(chromosome)
    END FOR
    // Every chromosome starts as a completely random mix of 0s and 1s.
    // There is no smart starting guess — evolution does all the work.

    generation = 0

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

        // ── STEP 1: FITNESS EVALUATION ──
        FOR EACH chromosome IN population:
            chromosome.fitness = countOnes(chromosome)
            // For One Max specifically, fitness is just counting the 1s.
            // No complex formula — more 1s always means a better score.
        END FOR

        // ── STEP 2: SELECTION ──
        SORT population BY fitness DESCENDING
        // Exam Trap: always sort descending. The strongest chromosomes
        // must land at the top of the mating pool, or the algorithm ends up
        // breeding weak strings instead of the fittest survivors.

        // ── STEP 3: CROSSOVER ──
        newPopulation = []
        FOR EACH pair of top parents IN population:
            cutPoint = chooseCutPoint(stringLength)
            child1 = parent1.head(cutPoint) + parent2.tail(cutPoint)
            child2 = parent2.head(cutPoint) + parent1.tail(cutPoint)
            // Swapping tails at the cut point mixes the genetic material of
            // two strong parents, hoping to produce an even stronger child.
            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: if tracing this by hand, check whether the exam
        // uses 0-based indexing (first bit is Bit 0) or 1-based indexing
        // (first bit is Bit 1) before flipping anything on paper.

        // ── STEP 5: POPULATION REPLACEMENT ──
        population = newPopulation
        // The newly bred children fully replace the previous generation.
        // The next loop iteration evaluates THEIR fitness from scratch.

        generation = generation + 1

    END WHILE

    RETURN the chromosome WITH the highest fitness FOUND across all generations

END FUNCTION

Time & Space Complexity

Genetic Algorithm Exam Questions Students Always Get Wrong

• What happens if I miscalculate just one initial fitness value, like $f(s_1)$ or $f(s_6)$?

  A single addition error at the very beginning catastrophically corrupts the entire generation. If one fitness value is wrong, the sorting order changes, the wrong parents get selected for crossover, and every subsequent bit-flip becomes mathematically invalid. Double-check the initial tally carefully before drawing any cut lines on the paper.

• If two chromosomes have the exact same fitness score of 3, which one gets ranked higher during selection?

  Mathematically, it does not matter. On a written exam, always break ties by keeping them in their original top-to-bottom order from the prompt. This keeps the trace perfectly aligned with the grading rubric and removes any ambiguity when the crossover pairs are checked afterward.

• What if the mutation rule forces me to flip a 1 back to a 0, making the child much worse?

  Leave it exactly as is. Destructive mutation is a deliberate feature designed to maintain genetic diversity. Panicking and trying to 'fix' the math to ensure the child improves is a common mistake — exams specifically test whether the discipline exists to follow the algorithm blindly, even when the score drops.

• Does the crossover cut point always have to be exactly in the middle of the string?

  No, the cut point can legally sit anywhere along the string. An exam question will almost always explicitly specify it, such as 'after Bit 3.' If it is completely missing from the prompt, default safely to the exact middle, but write a clear note stating that assumption to avoid losing points.

• If I accidentally breed the perfect string of all 1s in the first generation, do I stop?

  Only stop if the exam explicitly says 'halt on success.' Otherwise, algorithms are completely blind and continue running until hitting the maximum generation limit set by the `while` loop. Continue evaluating, crossing, and mutating the remaining generations exactly as instructed to receive full marks on the trace.