Genetic Algorithms simulate the process of natural evolution, applying concepts that Charles Darwin identified, such as selection, reproduction and mutation. Running the simulation for a number of generations can result in a highly optimized set of parameters that would be computationally expensive to produce otherwise.
We start by creating a population with random genes. The evolution then happens for a number of generations. On each generation, the population goes through a 3-step process.
If we are successful, the population will eventually converge to a set of predominant genes that are ideal for the goal we’re trying to achieve.
Let’s look at each step in detail and implement them in Swift.
At the start of the simulation we initialize each individual with a random chromosome. Let’s use the gi notation to represent genes.
| g0 | g1 | g2 | g3 | g4 | |
|---|---|---|---|---|---|
| Individual A | 0 | 1 | 0 | 1 | 1 |
| Individual B | 1 | 0 | 1 | 1 | 0 |
| Individual C | 1 | 1 | 0 | 0 | 1 |
| (Etc…) |
Each value in this table is a gene. In this example we have binary genes that can be either 0 or 1, representing some parameter. A full row in the table is the chromosome for that individual.
At this point the genes are assigned randomly.
g0 = Int.random(in: 1...100) > 50 ? 0 : 1We use a fitness function to determine which individuals are the most successful at a given task. The criteria will be unique to each use case, but generally we can define a protocol that all individuals will implement.
protocol Individual {
init(chromosome: Chromosome)
func fitnessScore() -> Double
}For example, if our algorithm is trying to approximate some value, the fitnessScore implementation could be something like this:
func fitnessScore() -> Double {
let error = abs(realValue - computedValue)
return 1 / error
}Once we have the fitnessScore we can select the individuals in two ways:
The latter is what happens in Nature, the most fit individual is not guaranteed to be selected, and the worst is not always discarded, but their chances are proportional to their fitness. On my own research I often find this approach gives the best results.
On this step we create new individuals based on the previous selected ones. The crossover function has the signature:
func crossover(_ first: Chromosome, with second: Chromosome) -> ChromosomeNote: There are multiple ways to implement this function, depending on the type of genes and the reproduction strategy. I discuss several approaches here.
In summary, if the individuals A and B were selected we would have a new offspring with a genetic mix from both:
| g0 | g1 | g2 | g3 | g4 | |
|---|---|---|---|---|---|
| Individual A | 0 | 1 | 0 | 1 | 1 |
| Individual B | 1 | 0 | 1 | 1 | 0 |
| Offspring A + B | 0 | 1 | 0 | 1 | 0 |
On this step we allow a small percentage of mutations to happen. We can either create entirely new random chromosomes, or we can tweak individual genes during the crossover step. This helps maintain some genetic diversity and in general yields better results.
guard Int.random(in: 1...100) > mutationPercentage else { mutate(); return }When the population converges, we may have a found solution. If it is suboptimal however, we can re-run the simulation tweaking the hyperparameters. Those are:
Depending on the complexity of the task we’re trying to achieve, this may require some trial and error, but often we can find a good solution surprisingly fast.
Give it a try.