# Genetic Algorithms

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.

• Selection - A number of individuals are selected according to their fitness.
• Crossover - This is the reproduction step. The chromosomes of the selected individuals are mixed together to breed new ones.
• Mutation - A percentage of the process is randomized to maintain genetic diversity.

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.

### Population

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 : 1``

### Selection

We 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:

• Deterministically - The most fit individuals are selected.
• Probabilistically - The most fit individuals are most likely (but not necessarily) selected.

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.

### Crossover

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) -> Chromosome``

Note: 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

### Mutation

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 }``

### Termination

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:

• Initial population size
• Percentage of individuals that are selected / discarded
• Percentage of mutation

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.