A Genetic Algorithm Example Using Swift
This post is a showcase and (hopefully) the beginning of a series of posts about the AI world in Swift. Genetic Algorithms (GA) are really easy to understand, yet still so powerful that I decided to explore them further.
The basic idea behind a Genetic Algorithm is pretty simple, we are trying to “grow” a solution, using a natural selection mechanism, similar to the one used by nature to create better living beings. Sounds easy? In fact, it is easy, especially with the example I present below in Swift.
Tip: the aim of this post is not to introduce the Genetic Algorithm topic in general, so I suggest you visit the below sources to get some basic knowledge before going further (it will be much easier to understand what’s going on):
Genetic algorithms – Wikipedia
//: Simple Genetic Algorithm Starter in Swift 3
import UIKit
import Foundation
let AVAILABLE_GENES:[Int] = Array(1...100)
let DNA_LENGTH = 6
let TOURNAMENT_SIZE = 5
let MAX_GENERATIONS_COUNT = 100
let POPULATION_SIZE = 30
let MUTATION_CHANCE = 0.1
let SAVE_FITTEST = true
struct Individual: CustomStringConvertible {
var data:[Int] = [Int](repeating: 0, count: DNA_LENGTH)
var fitness = 0
mutating func randomize() {
for index in 0...DNA_LENGTH-1 {
data[index] = AVAILABLE_GENES[Int(arc4random_uniform(UInt32(AVAILABLE_GENES.count)))]
}
}
//Fitnes value should range in 0 to Int max, where 0 is solution equal to OPTIMAL
mutating func calculateFitness() { //can use reduce
for index in 0...DNA_LENGTH-1 {
self.fitness += abs(data[index] - OPTIMAL_SOLUTION.data[index])
}
}
func cross(_ otherIndividual: Individual) -> Individual {
var individual = Individual()
//DIFFERENT METHODS ARE AVAILABLE:
//single cross, multi cross, uniform cross (we are using single cross)
let crossIndex = Int(arc4random_uniform(UInt32(DNA_LENGTH)))
for i in 0...crossIndex {
individual.data[i] = self.data[i]
}
for i in crossIndex...DNA_LENGTH-1 {
individual.data[i] = otherIndividual.data[i]
}
return individual
}
mutating func mutate() {
for index in 0...DNA_LENGTH-1 {
if Double(Float(arc4random()) / Float(UINT32_MAX)) <= MUTATION_CHANCE {
self.data[index] = AVAILABLE_GENES[Int(arc4random_uniform(UInt32(AVAILABLE_GENES.count)))]
}
}
}
var description : String {
return "(self.data) Fitness: (self.fitness)"
}
}
//FRAMEWORK
struct Population {
var individuals = [Individual]()
var fittestIndividual: Individual?
mutating func calculateFittestIndividual() {
fittestIndividual = individuals.sorted(by: { (first, second) -> Bool in
first.fitness < second.fitness
}).first!
}
}
func runGeneticAlgorithm() {
//Create Initial Population
var population = createInitialPopulation()
population.calculateFittestIndividual()
for generation in 1...MAX_GENERATIONS_COUNT {
var newPopulation = Population()
if SAVE_FITTEST {
newPopulation.individuals.append(population.fittestIndividual!)
}
for _ in newPopulation.individuals.count...POPULATION_SIZE-1 {
//TOURNAMENT METHOD (other is roulette wheel)
let individual1 = selectParentTournament(population)
let individual2 = selectParentTournament(population)
var childrenIndividual = individual1.cross(individual2)
childrenIndividual.mutate()
childrenIndividual.calculateFitness()
newPopulation.individuals.append(childrenIndividual)
}
population = newPopulation
population.calculateFittestIndividual()
if population.fittestIndividual!.fitness == 0 {
print("!!! Generation:(generation) Fittest:(population.fittestIndividual!)")
break
}
print("Generation:(generation) Fittest:(population.fittestIndividual!)")
}
}
func selectParentTournament(_ population:Population) -> Individual{
var tournamentPopulation = Population()
for _ in 1...TOURNAMENT_SIZE {
tournamentPopulation.individuals.append(population.individuals[Int(arc4random_uniform(UInt32(population.individuals.count)))])
}
tournamentPopulation.calculateFittestIndividual()
return tournamentPopulation.fittestIndividual!
}
func createInitialPopulation() -> Population{
var population = Population()
for _ in 1...POPULATION_SIZE {
var individual = Individual()
individual.randomize()
individual.calculateFitness()
population.individuals.append(individual)
}
return population
}
var OPTIMAL_SOLUTION = Individual()
OPTIMAL_SOLUTION.randomize()
print("OPTIMAL: (OPTIMAL_SOLUTION.data)")
runGeneticAlgorithm()
The code isn’t very long, but is worth explaining further to be clear, starting from the very beginning:
AVAILABLE_GENES: is an array of all possible values of genes, you can put nearly anything here, chars, other arrays, even emojis, it’s just important to have every possible value here, as the algorithm is unable to use other genes.
DNA_LENGTH: this is probably self-explanatory, it’s the length of the sequence which we are looking for.
TOURNAMENT_SIZE: in this implementation, we are using a tournament method to select “parents”. In other words, we randomly select a group of individuals and select which one is the fittest, this one will be the parent for next generation.
MUTATION_CHANCE: a value between 0 and 1, which defines how a particular gene is likely to mutate. 0.1 (which refers to 10%) is used by default in many implementations.
SAVE_FITTEST: this boolean defines if the fittest individual from the current generation will survive to the next one without any changes.
Individual: the core of this implementation. Each individual object represents a potential solution to our problem, and also defines every operation needed in the GA.
randomize(): allows us to create an individual with random genes drawn from the AVAILABLE_GENES pool.
calculatefitness(): this method returns an integer value, which is interpreted as the distance between the current solution and the one we are looking for. The closer to zero, the better. Zero means the solution is as good as the optimal.
cross(): this gets one param, which is another individual object and returns a new individual (children of the received individual and the one which was used to call the method). The implementation in this post is using a single cross, but there are many different methods including multi-cross, uniform cross, and others.
mutate(): based on MUTATION_CHANCE, this is a randomly changing value of particular genes in an individual.
Summary
Everything you need to know to start playing with genetic algorithms in Swift has been explained in the example above (hopefully). After a few tests, I noticed that in the default configuration this code takes ~80 generations to find the solution.
Population struct and the runGeneticAlgorithm() method don’t need to be modified at all. Once the individual struct is properly defined, then it will work without any problems.
In the case of any questions, suggestions, or errors… please feel free to let me know.
