Genetic algorithms search for strong solutions by repeatedly evolving a population of candidate solutions. Candidates with higher fitness are more likely to reproduce through crossover, while mutation introduces variation that may produce better solutions.
A genetic algorithm represents each candidate solution as a chromosome, often encoded as a binary string, sequence, or array of values. It then repeats an evolutionary cycle until a stopping condition is met.
| Stage | Mechanism |
|---|---|
| Population | Generate an initial set of candidate solutions, usually with random variation. A larger population explores more of the solution space but requires more processing. |
| Fitness evaluation | Apply a fitness function that assigns each candidate a score according to how well it solves the problem. The function must reflect the problem's objective accurately. |
| Selection | Choose fitter candidates as parents. Higher fitness normally increases the probability of selection, but weaker candidates may still be selected to preserve diversity. |
| Crossover | Combine parts of two parent chromosomes. For example, `110 |
| Mutation | Randomly alter a small part of a chromosome, such as changing a bit from 0 to 1. This introduces new genetic material and helps prevent premature convergence. |
| Replacement | Form a new population from offspring, sometimes retaining the best existing candidates through elitism. The cycle then repeats. |
The algorithm may stop after a fixed number of generations, when a target fitness is reached, or when improvement becomes insignificant. Genetic algorithms are useful for large optimization problems where testing every possible solution is impractical, but they do not guarantee the globally optimal solution.
A common misconception is that crossover creates entirely random solutions. It mainly recombines existing parent characteristics; mutation is the primary source of new variation.
Exam technique: For IB Computer Science HL A4.3, explain the stages in sequence and link each to its purpose. Distinguish clearly between fitness evaluation, selection, crossover, and mutation, and evaluate both computational cost and the risk of convergence on a suboptimal solution.
