Genetic Algorithm (One-Max)

Genetic Algorithm, Evolutionary Computing, One-Max Problem, Crossover, Mutation, Fitness Function, Chromosomes

Genetic Algorithms (GAs) are search and optimization techniques inspired by Charles Darwin's theory of natural evolution. Instead of using complex calculus, they 'breed' solutions. The 'One-Max' problem is the classic "Hello World" of GAs. The goal is simple: evolve a random string of 0s and 1s until it becomes entirely 1s. It does this by mimicking natural selection—scoring each string's fitness, keeping the strongest 'parents', and combining their 'DNA' (bits) to create an even stronger next generation.

The Fitness Function

f(x) = \sum_{i=1}^{n} x_i

What do these variables mean?

$f(x)$ The fitness score of the chromosome (the binary string).
$x_i$ The value of a specific bit (either 0 or 1) at position $i$ .
$n$ 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!

Important Rules & Conventions

Exam Trick 1: When doing Crossover by hand, draw a literal vertical line '|' through the strings at the crossover point on your paper. It makes it impossible to accidentally swap the wrong bits.
Exam Trick 2: 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!
Exam Trick 3: 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 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.

Summary

The Genetic Algorithm is a brilliant mimicry of biology. By continuously evaluating, sorting, mating, and mutating a population of binary strings, the One-Max problem beautifully demonstrates how random chance—guided by 'survival of the fittest'—can quickly breed a perfect mathematical solution.