Optimization selects a solution that minimizes or maximizes an objective under given conditions. Graphs frame optimization as finding shortest routes or the minimum track connecting a network. section 4.0
A genetic algorithm turns optimization into an executable search:
- Represent a candidate solution as a chromosome with genes and a fitness value. section 5.4
- Generate random candidates, combine them through crossover, and alter them through mutation. section 5.4
- Maximize fitness; convert a minimization target into a maximization score when necessary. section 5.5
Two optimization problems
For 6x − x² + 4y − y², a genetic algorithm reaches x = 3 and y = 2 with fitness 13. For SEND+MORE=MONEY, fitness 1/(difference + 1) makes an exact solution score 1, producing 6419 + 724 = 7143. section 5.4 section 5.5
final class SimpleEquation: Chromosome {
var x: Int = Int(arc4random_uniform(100))
var y: Int = Int(arc4random_uniform(100))
var fitness: Double { // 6x - x^2 + 4y - y^2
return Double(6 * x - x * x + 4 * y - y * y)
}
init(from: SimpleEquation) { // like making a copy
x = from.x
y = from.y
}
init() {}
static func randomInstance() -> SimpleEquation {
return SimpleEquation()
}
func crossover(other: SimpleEquation)
-> (child1: SimpleEquation, child2: SimpleEquation) {
let child1 = SimpleEquation(from: self)
let child2 = SimpleEquation(from: other)
child1.y = other.y
child2.y = self.y
return (child1: child1, child2: child2)
}
func mutate() {
if drand48() > 0.5 { // mutate x
if drand48() > 0.5 {
x += 1
} else {
x -= 1
}
} else { // otherwise mutate y
if drand48() > 0.5 {
y += 1
} else {
y -= 1
}
}
}
func prettyPrint() {
print("x:\(x) y:\(y) fitness:\(fitness)")
}
}
Shows a concrete Swift chromosome whose fitness, crossover, and mutation methods can be adapted to another optimization problem. section 5.4
