Genetic Algorithm (One-Max) Theory Guide
Try the Genetic Algorithm (One-Max) Solver →Genetic Algorithm, Evolutionary Computing, One-Max Problem, Crossover, Mutation, Fitness Function, Chromosomes
The Genetic Algorithm is a population-based optimization technique inspired by Darwinian natural selection, evolving candidate solutions toward an optimal answer through successive generations of selection, crossover, and mutation. Where calculus-based optimizers require a smooth, differentiable landscape to navigate, a Genetic Algorithm treats the search space like an ecosystem — brutal, competitive, and indifferent to mathematical convenience. The One-Max problem is the canonical entry point: starting from a population of random binary strings, the algorithm scores each string by counting its 1s, selects the fittest survivors as parents, recombines their bits through crossover, and introduces random mutations — repeating until natural selection converges the entire population to a string of all 1s.
The Fitness Function
What do these variables mean?
- The fitness score of the chromosome (the binary string).
- The value of a specific bit (either 0 or 1) at position .
- The total length of the binary string (e.g., 10 bits).
- The FormulaIt is literally just adding up all the bits! Since 0 contributes nothing, the fitness score is simply the total number of 1s in the string. A perfect 10-bit string has a fitness score of 10.
How Does it Work?
Initial Population: Start with a randomly generated set of binary strings (chromosomes).
Fitness Evaluation: Count the number of 1s in each string to get its score. Higher is better.
Selection (Sorting): Rank the population from highest score to lowest. The top scorers are selected as the 'Parents' for the next generation.
Crossover (Mating): Take two parents, slice them at a specific 'crossover point', and swap their tails. This creates two new 'Children' that share traits from both parents.
Mutation: Randomly pick a specific bit in a child and flip it (0 becomes 1, or 1 becomes 0). This injects fresh genetic material to prevent the population from getting stuck.
Repeat: Replace the old population with the new children and re-evaluate their fitness. Repeat the loop until you breed a perfect string!
Solved Example: Evolving a 4-Bit String
We want to evolve a 4-bit string to all 1s (1111). Our current population has two parents: P1 (1010) with Fitness=2, and P2 (0110) with Fitness=2. We will use a Crossover Point of 2.
Step 1 (Crossover): Slice P1 and P2 after the 2nd bit. P1: [10 | 10], P2: [01 | 10].
Step 2 (Mating): Swap the tails. Child 1 gets P1's head and P2's tail: (1010). Child 2 gets P2's head and P1's tail: (0110).
Step 3 (Mutation): We randomly flip the 1st bit of Child 2. (0110) becomes (1110).
Step 4 (Evaluation): Child 1 Fitness is still 2. New Child 2 Fitness is now 3 (three 1s).
Conclusion: The population improved! Child 2 is now a stronger candidate for the next generation's selection process.
Student Tip: You can verify these exact manual calculations using our interactive Genetic Algorithm (One-Max) step-by-step solver. Simply plug in the values from the table above to see the logic in action.
Implementation Pseudocode
function runGeneticAlgorithm(initialPopulation, crossoverRules, mutationRules):
// 1. Evaluate Initial Fitness
evaluatedPop = []
for each chromosome in initialPopulation:
fitness = countNumberOfOnes(chromosome)
evaluatedPop.push({ chromosome, fitness })
// 2. Selection (Sorting)
sortedPop = sort(evaluatedPop) by fitness descending
nextGeneration = getChromosomes(sortedPop)
// 3. Crossover (Mating)
for each rule in crossoverRules:
parent1 = nextGeneration[rule.p1Index]
parent2 = nextGeneration[rule.p2Index]
head1, tail1 = split(parent1, rule.point)
head2, tail2 = split(parent2, rule.point)
// Swap tails to create children
nextGeneration[rule.p1Index] = head1 + tail2
nextGeneration[rule.p2Index] = head2 + tail1
// 4. Mutation
for each rule in mutationRules:
child = nextGeneration[rule.childIndex]
bitToFlip = rule.bitPosition - 1 // Convert to 0-based array index
if child[bitToFlip] == '1':
child[bitToFlip] = '0'
else:
child[bitToFlip] = '1'
nextGeneration[rule.childIndex] = child
// 5. Final Evaluation
finalPopulation = []
for each chromosome in nextGeneration:
fitness = countNumberOfOnes(chromosome)
finalPopulation.push({ chromosome, fitness })
return finalPopulationRules & Common Mistakes
Exam Trap: When doing Crossover by hand, draw a literal vertical line '|' through the strings at the crossover point on your paper. It makes it extremely easy to accidentally swap the wrong bits if you try to do it visually in your head, which ruins the entire generation's math.
Remember that Arrays and Strings start at index 0 in coding, but exam questions usually use 1-based counting (e.g., 'Mutate the 5th bit'). Double-check how your professor is counting before flipping!
Don't get confused during the Selection step. The strings themselves aren't changing their 1s and 0s yet; they are just changing their rank/order in the list based on their fitness score.
Advantages
- ✓ Does not require complex calculus or derivatives. If you can write a simple scoring function, you can use a Genetic Algorithm.
- ✓ Excellent at escaping 'local optima' (getting stuck on a merely okay solution) thanks to the random variations introduced by Mutation.
- ✓ Highly flexible. The exact same flow can be applied to almost any optimization problem, from scheduling university classes to training neural networks.
Disadvantages
- × There is no mathematical guarantee that it will ever find the absolute perfect, optimal solution.
- × Can be computationally expensive, sometimes requiring thousands of generations to evolve a good answer for complex problems.
- × You have to manually guess good parameters for the Mutation Rate and Crossover Rate. If mutation is too high, it devolves into completely random guessing.
Algorithm Complexity
| Scenario | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Time Complexity (Per Generation) | Where is Population Size and is Chromosome Length. Evaluating fitness takes , and sorting the population takes . | ||
| Overall Time (Full Evolution) | Where is the total number of generations required to reach the target fitness. The exact number of generations is nondeterministic (randomized) and depends heavily on mutation/crossover rates. | ||
| Overall Space | Highly memory efficient. You only need to keep the 'Current Generation' and 'Next Generation' string arrays in memory at any given time. |
Genetic Algorithm (One-Max) vs. Genetic Algorithm (Knapsack)
The One-Max problem is the training ground; the Knapsack problem is the real exam. Both use identical evolutionary machinery — Selection, Crossover, Mutation — but Knapsack adds a hard constraint that fundamentally changes how fitness is evaluated and what 'surviving' means.
- •One-Max has an unconstrained fitness function: more 1s is always better, and there is no penalty for any string; the Knapsack problem introduces a hard weight limit — any chromosome whose total weight exceeds the bag capacity immediately receives a fitness score of 0, regardless of its potential benefit.
- •In One-Max, the perfect chromosome ('1111...1') is always a valid and desirable answer; in Knapsack, the all-1s chromosome is almost always an overweight bag with zero fitness — the optimal solution is a carefully balanced mix of items, not the maximum number of them.
- •One-Max fitness evaluation is trivially fast — just count the 1s; Knapsack fitness requires decoding the chromosome against an external item list, summing weights, checking the constraint, and only then summing benefits — three separate calculation steps instead of one.
Detailed Comparisons & Guides
Summary
The One-Max Genetic Algorithm is a beautiful proof of concept: that randomness, guided by selection pressure, can reliably climb toward an optimal solution without any calculus or gradient information. It demonstrates all three pillars of evolution — Selection keeps the strong, Crossover combines the best traits, and Mutation preserves diversity. For exams, always draw a vertical splice line during Crossover, use 1-based bit counting unless told otherwise, and remember that Sorting is the entire Selection step — the strings themselves don't change, only their rank in the list does.
Common Exam Questions & FAQ
+ Why is the One-Max problem used to teach Genetic Algorithms instead of a harder problem?
Because the fitness function (count the 1s) is so simple that the student can focus entirely on understanding the *mechanics* — how Selection sorts the population, how Crossover mixes parent chromosomes at a splice point, and how Mutation flips a single bit. When the evaluation is trivial, the evolutionary logic itself becomes visible. Once you understand One-Max, adding the complexity of Knapsack constraints is straightforward.
+ What is 'Elitism' in Genetic Algorithms?
Elitism is a selection strategy where the single best-performing chromosome from the current generation is automatically copied, unchanged, into the next generation — before crossover or mutation happen. This guarantees that the best solution discovered so far can never be accidentally destroyed by an unlucky mutation. It is the simplest and most common way to ensure the algorithm never backtracks in fitness.
+ How do the Crossover Point and Mutation Rate affect the algorithm's speed?
The Crossover Point determines how much genetic material is exchanged between parents — a midpoint split shares equal traits, while a very early or late split gives one child most of one parent's genes. A high Mutation Rate injects variety and prevents the population from becoming too uniform, but if it is too high, the algorithm degenerates into a random search and loses its directional improvement. Finding the right balance is part of 'hyperparameter tuning'.
🎓 Core University Curriculum
This algorithm and its manual calculation methods are foundational requirements in leading Computer Science and Software Engineering programs worldwide. You will find this topic heavily featured in the syllabi of these standard AI courses:
Explore Related Algorithms
Try the Genetic Knapsack Calculator
Apply a Genetic Algorithm to the classic 0/1 Knapsack problem interactively—configure population size, crossover rate, and mutation rate to watch evolution find near-optimal solutions in real time.
Genetic Knapsack Theory
The Genetic Knapsack is the canonical applied instance of the Genetic Algorithm framework: it maps binary chromosome encoding directly to item selection vectors, making it the ideal case study for understanding how fitness functions, selection operators, and mutation pressure translate abstract GA theory into a concrete NP-Hard optimization.