In a genetic algorithm, fitness is a score for how well a chromosome solves a problem. Higher scores make a chromosome more likely to be selected as a parent. The algorithm can stop when a score meets a threshold; otherwise, it returns the best candidate found within its generation limit. Because selection, crossover, and mutation involve chance, that candidate is not guaranteed to be optimal. section 5.1
A Swift `Chromosome` exposes its score as `var fitness: Double { get }`. The generic algorithm measures fitness each generation, caches the scores for selection, and tracks the best candidate. A useful fitness calculation must therefore rank candidates in the direction the algorithm expects: higher is better. section 5.3 section 5.5
Maximize an equation
Let a chromosome's genes be integers `x` and `y`. Its fitness can return `Double(6*x - x*x + 4*y - y*y)`. The highest value is 13, at `x = 3` and `y = 2`, so 13 is a suitable stopping threshold when that answer is known. Without a known target, use a high threshold and inspect the best result after a fixed number of generations. section 5.4
Score distance from a solution
For SEND+MORE=MONEY, calculate `difference = abs(MONEY - (SEND + MORE))` and return `1 / Double(difference + 1)`. A difference of zero scores 1; larger errors score less. Return 0 if a required letter is missing. This turns a distance to minimize into a score to maximize, though the conversion can introduce bias. section 5.5
The same choice arises when adapting constraint satisfaction to a genetic algorithm: one possible fitness score is the number of constraints a chromosome satisfies. section 5.8
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 `Chromosome` interface places fitness alongside the operations that create and change candidates. section 5.3
final class SendMoreMoney: Chromosome {
var genes: [Character]
static let letters: [Character] = ["S", "E", "N", "D", "M", "O", "R",
"Y", " ", " "]
var fitness: Double {
if let s = genes.index(of: "S"), let e = genes.index(of: "E"), let
n = genes.index(of: "N"), let d = genes.index(of: "D"),
let m = genes.index(of: "M"), let o = genes.index(of: "O"),
let r = genes.index(of: "R"), let y = genes.index(of: "Y") {
let send: Int = s * 1000 + e * 100 + n * 10 + d
let more: Int = m * 1000 + o * 100 + r * 10 + e
let money: Int = m * 10000 + o * 1000 + n * 100 + e * 10 + y
let difference = abs(money - (send + more))
return 1 / Double(difference + 1)
}
return 0
}
init(from: SendMoreMoney) {
genes = from.genes
}
init(genes: [Character]) {
self.genes = genes
}
static func randomInstance() -> SendMoreMoney {
return SendMoreMoney(genes: letters.shuffled())
}
func crossover(other: SendMoreMoney)
-> (child1: SendMoreMoney, child2: SendMoreMoney) {
let crossingPoint = Int(arc4random_uniform(UInt32(genes.count)))
let childGenes1 = genes[0..<crossingPoint] +
other.genes[crossingPoint..<other.genes.count]
let childGenes2 = other.genes[0..<crossingPoint] +
genes[crossingPoint..<genes.count]
return (child1: SendMoreMoney(genes: Array(childGenes1)), child2:
SendMoreMoney(genes: Array(childGenes2)))
}
func mutate() {
// put a random letter in a random place
let position1 =
Int(arc4random_uniform(UInt32(SendMoreMoney.letters.count)))
let position2 = Int(arc4random_uniform(UInt32(genes.count)))
if drand48() < 0.5 { // half the time random letter
genes[position2] = SendMoreMoney.letters[position1]
} else { // half the time random swap
if position1 != position2 { genes.swapAt(position1, position2) }
}
}
func prettyPrint() {
if let s = genes.index(of: "S"), let e = genes.index(of: "E"),
let n = genes.index(of: "N"), let d = genes.index(of: "D"),
let m = genes.index(of: "M"), let o = genes.index(of: "O"),
let r = genes.index(of: "R"), let y = genes.index(of: "Y") {
let send: Int = s * 1000 + e * 100 + n * 10 + d
let more: Int = m * 1000 + o * 100 + r * 10 + e
let money: Int = m * 10000 + o * 1000 + n * 100 + e * 10 + y
print("\(send) + \(more) =
\(money) difference:\(money - (send + more))")
} else {
print("Missing some letters")
}
}
}
The cryptarithmetic implementation shows how a problem-specific `fitness` property scores valid candidates and rejects incomplete ones. section 5.5
