Suppose a problem has no fast, reliable way to search every possible solution, but a candidate answer can be scored. A genetic algorithm searches by repeatedly improving a population of candidate answers. It is useful when a good solution is enough; its randomness means it cannot promise the optimum or a predictable runtime. section 5.0 section 5.6
Each candidate is a chromosome made of genes. A fitness function scores how well it solves the problem. Across generations, fitter chromosomes are more likely to become parents; crossover combines parents, and mutation randomly changes a gene. The search returns a candidate that meets a fitness threshold, or the best found after a generation limit. section 5.1 section 5.3
To implement the search, separate the reusable loop from the problem-specific chromosome:
- Define how to create and copy a candidate, measure its fitness, cross it with another candidate, and mutate it. section 5.3
- Create a random population, score it, select parents, form the next generation, and allow mutation. Configure population size, selection method, crossover and mutation chances, and stopping limits. section 5.3
- Choose a representation and fitness function that make progress measurable. This is often harder than writing the loop. section 5.5 section 5.6
public protocol Chromosome {
var fitness: Double { get } // how well does this individual solve
the problem?
init(from: Self) // must be able to copy itself
static func randomInstance() -> Self
func crossover(other: Self)
-> (child1: Self, child2: Self) // combine with other to form children
func mutate() // make a small change somewhere
func prettyPrint()
}
The Swift Chromosome protocol shows the small problem-specific interface needed by the generic algorithm: fitness, copying, random creation, crossover, mutation, and printing. section 5.3
First test: maximize an equation
Let the genes be integers x and y, and score them with 6x − x² + 4y − y². Crossover swaps the parents’ y values; mutation increments or decrements x or y. The known maximum, x = 3 and y = 2, has fitness 13, so a threshold of 13 makes success easy to recognize. One sample run reached it in 18 generations; another run can differ. section 5.4
Harder test: SEND+MORE=MONEY
Represent digits as positions in a ten-element array holding eight letters and two spaces. Score a candidate as 1 / (difference + 1), where difference is the absolute gap between MONEY and SEND+MORE; a missing letter scores zero. An exact match scores 1. This turns a yes-or-no constraint into a graded signal for selection, without preassigning letters as in the earlier backtracking attempt. section 5.5
Prefer a fast deterministic algorithm when one exists. For harder searches, possible applications include scheduling, protein-ligand docking, and good-enough Traveling Salesman routes. Further implementation challenges include probabilistic tournament selection, a genetic solver for arbitrary constraint-satisfaction problems, and a bit-string chromosome. section 5.6 section 5.7 section 5.8
