A chromosome is one candidate solution in a genetic algorithm’s population. Its genes encode traits relevant to the problem, and its fitness measures how well it solves that problem. Across generations, fitter chromosomes are more likely to be selected; crossover combines parents, while mutation makes random changes. The algorithm can stop when a candidate reaches a fitness threshold or when it reaches its generation limit. section 5.1
A reusable Swift genetic algorithm asks each chromosome to provide six capabilities:
- Report a fitness value and make a copy of itself. section 5.3
- Create a random instance to populate the first generation. section 5.3
- Cross over with another chromosome of the same type to produce two children, and mutate by making a small random change. section 5.3
- Print a human-readable result. section 5.3
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 protocol makes these capabilities the contract between a problem-specific candidate and the generic algorithm. It uses prettyPrint() rather than CustomStringConvertible because repeated description() calls slowed the intended Xcode Playground runs. section 5.3
Encoding SEND+MORE=MONEY
One chromosome stores ten characters in an array whose indices stand for digits 0–9. Eight entries hold the puzzle’s distinct letters; two hold spaces. For example, placing E at index 4 assigns E the digit 4. Fitness is zero if a letter is missing; otherwise it is 1 / (difference + 1), where difference is the absolute gap between MONEY and SEND+MORE. A correct sum has fitness 1. This turns a smaller-error goal into the larger-fitness goal the genetic algorithm uses. section 5.5
Choosing an encoding is often the hard part. Binary strings can save space and simplify crossover, but complex solutions may not divide naturally into bits. Even with a suitable chromosome, stochastic selection, crossover, and mutation do not guarantee an optimum in predictable time; a good-enough solution may be the practical goal. section 5.6 section 5.1
