Genetic Algorithm in Swift
While researching and writing a completely different tutorial, I came across a really fun video by a YouTuber named Code Bullet. In the video, he shows viewers how to teach an A.I. agent to learn how to play Flappy Birds using a genetic algorithm named NeuroEvolution of Augmenting Topologies, or better known as NEAT. Now, I'd never heard of NEAT let alone genetic algorithm, but after watching the video, I was very curious about how it worked.
In this tutorial, you're going to work through a writing the code for a very basic genetic algorithm using Swift. The final project uses SwiftUI to help illustrate the point.
I want to clarify that I'm not an authority on the topic of genetic algorithm. Instead, this tutorial will present my understanding of the topic, and how CoreML could fit into the picture. If you're interested in the topic, reading the original paper written by Ken Stanley in 2002 serves as a great starting point.
The code for this tutorial can be downloaded here
Genetic Algorithm's Big Picture
At its simplest, genetic algorithms use the rules of evolution to improve how and A.I. agent might solve a problem. The general steps might be break down as follows:
1. First establish a population of agents with possibly a random set of decision making rules
2. Establish what constitutes improvement, success and failure, also know as **fitness**, for the agent
3. Allow those agents to do either improve, succeed, or fail given those rules
4. Pick the best performing agent(s), and mutate their decision making rules just slightly, removing all the low performing agents.
5. Repeat step 3.
The hope is that, with each iteration, or epoch, or generation of the above loop, you eventually converge on an agent with a set of decision making rules that's the best of the bunch.
Consider how this relates back to the idea of evolution. Over the span of tens of millions of years, a minor mutation in a species could give it a little extra advantage when it comes to survival. Another example might be knowledge from parent when they pass it on to their child. Although no exactly a mutation at the genetic level, the idea is, given some baseline established by the parent, the child can start its learning from that baseline, and improve from there.
Getting Started
In this tutorial, you're going to create a small app that will spawn a large population of dots to reach a pre-defined target coordinate. The dots each start with a brain that consists of some fixed number of random directions vectors. At each frame, the dot will move in the direction of one of those vectors, hoping to reach the target. The dots can either:
* Get as close as possible to the dot before running out of directions its brain can give it
* Die crossing an established boundary or wall
* Succeed by hitting the target.
This is probably best described with a GIF. Below are two images, one for the first generation, and one for the tenth generation.
Notice how in the first generation, the dots just go in any random direction. By the end, through copying what previous generations had learned, and randomly tweaking the knowledge, the dots are able to reach the target in fewer and fewer steps.
Ok, with the setup out of the way, in the next section, you'll go over the classes involved.
Building Block
There are effectively three pieces to creating a genetic algorithm. The Population, the Species, and the Brain. In this tutorial, each class is named accordingly except for Species, which is instead named Dot.
The relationship between each piece is simple, a Population has a one to many Species (hereafter referred to as Dots). In reality, your population should probably be in the thousands. A Dot has a one-to-one relationship with a Brain. It would be cool to consider what a dot with multiple brains might look like, but trying to figure out which brain makes decisions is hurting my brain. You'll start by creating the Brain class.
If I only had a Brain!
class Brain {
public let size: Int
public let directions: [Vector]
public var step: Int
init(_ directions: [Vector]) {
self.size = directions.count
self.step = 0
self.directions = directions
}
}
Note: There's no
Vectorclass in Swift. This is just a small class I wrote that contains anx, andyFloat property. I wrote some helpers that allowed me to add twoVectors together, and compute the Euclidean distance between twoVectors.
The brain takes in a list of directions. These are just precomputed random unit vectors that the brain will use to determine a dot's "next step". In case you were wondering, here's the code for how to randomly generate the direction of the brain:
var newDots: [Dot] = []
for _ in 0..<size {
var directions: [Vector] = []
for _ in 0..<brainSize {
let angle = Float.random(in: 0...(2 * Float(Double.pi)))
directions.append(Vector(x: cos(angle), y: sin(angle)))
}
let brain = Brain(directions)
// Add brain to dot
}
This is a pretty simple approach, but hopefully it will help root the idea. In practice, the brain could be written to be any high level object that makes a decision based on a given input. One example might be a Neural Network which can take in the dot's current position, and output if it should go left, right, up or down. Or it could be a some absurd heuristic, where if your brain is given a coordinate that tells you to go left if the value of x value is prime, and to go down if the y value is even. The basic idea is, the brain can be anything! With one caveat of course... You should be able to randomly mutate the rules of the brain at the end of an epoch. That is, when everyone in the population dies, when you start the next generation, you'll need a way to randomly change the rules.
The brain class also has a step property. This property is used as a pointer into the brain's current position in the directions vector. At each frame, the dot will ask its brain, "Where should I go next?", and the brain will simply return the vector at the current step position, and then increment the step. Once that pointer has reached the end of the directions list, the dot is considered to be dead. If you're interested in what that code might look like, here's an example:
func nextDirection() -> Vector? {
if (self.directions.count <= self.step) {
return nil;
}
let direction = self.directions[self.step];
self.step += 1;
return direction;
}
Essentially, the brain above doesn't care about the current state and so takes no input. It either tells the dot where to go next, or it just returns nil, which in this case means "I'm all out of ideas!"
Ok, now that you have a brain that can make decisions for you, time to give that brain to a dot.
Dots
The dots here are a stand-in for a Species. In practice, a Species is the agent, or object, or device or thing that you want to train over a number of generations. Here's the class definition that you'll work with.
class Dot {
public let brain: Brain;
public var position: Vector;
public var dead: Bool
public var success: Bool
func update(target: Vector) {}
func fitness(target: Vector) -> Float { return 0; }
}
The dot has a Brain, which you learned about in the previous section. It also has a Vector pointing to its current location. You'll have every dot start at the same place every time. The dot also has two properties which indicate if the dot is dead (i.e. its hit a wall, or its brain has no more directions to give it), or if the dot has succeeded (i.e. its hit the target). You can also see two methods which you'll implement in a bit. The update method is called each frame, and will move the dot based on the direction given to it by its brain, or it will stay put. The fitness method is used between epochs when trying to determine "how well" this dot did. How "fit" is it to survive this epoch. You'll implement this method later when you go over what happens at the end of the epoch.
Great! Now you have a Species with a Brain. Now you have create a population of them, and evolve the best version.
Population
A population is exactly as it sounds. You create a list of Dots with a randomly assigned brain, update each dot every frame until each of them dies, then you shake out the best version, and create copies of it with slight variations to its brain to see if it can do better. Let's start with the class for Population.
class Population {
public var dots: [Dot] = []
public var generation: Int
private let size: Int
private let minTargetDistance: Float
private let mutationRatio: Float
func update(target: Vector) {}
func naturalSelection(target: Vector) {}
func allDead() -> Bool { return false }
}
Looking at the obvious, you can see that the Population class contains a list of dots. Next you can see that it also contains a counter named generation to keep track the number of iterations or epochs the your experiment will go through. Next is the minTargetDistance which is just a value for an "acceptable distance" that a dot can be to the target and say that the dot "succeeded." Finally, there's the mutationRatio. This is a constant value that defines how much of a brain should be mutated at each epoch, you'll hard code this value to 1% or 0.01.
Great, looking at the methods, you'll see update. Like the same method found in the Dot class, this method is called once a frame. Actually, now would be a good time to tell you what happens at each frame. In the SwiftUI code, the following is called at each frame:
if self.population.allDead() {
self.population.naturalSelection(target: self.target)
} else {
self.population.update(target: self.target)
}
Pretty simple. The idea here is, you iterate on each frame until every dot has died. When they've all died, you perform a naturalSelection. You'll see what that method does in the next section, however to end this section, we'll end off with what's included in allDead() and update(), the implementation is very straight forward:
func allDead() -> Bool {
for dot in dots {
if !dot.dead && !dot.success {
return false
}
}
return true
}
func update(target: Vector) {
self.dots.forEach { $0.update(target: target) }
}
As you can see, the definition of dead is, if all the dots are either dead, or succeeded. Maybe a better name for the method might be done, but you'll just leave it as allDead() because it goes well with the idea of natural selection :)
Wow, if you've made it this far, then get ready for the most interesting part. You've made it to the part where we get to throw away a whole population of dots, and give their evolved counterparts a chance to survive!
Natural Selection
You've reached a point in the code where all your Dots have died, and you need to see what they've learned, find the best candidate to participate in "natural selection", and have that Dot give birth (so to speak) to the next generation.
The naive implementation here might be as easy as generating a brand new list of Dots the same way you initialized your first generation, and hope that that population is better. It's an option, but its not a great one. Let's see if you can do better.
Survival of the fittest
First we need to define what we mean by "best candidate" here. Remember that fitness() function you added to Dot earlier but only returned 0, well now's the time to implement it. Fitness is one of those things that's hard to make generic, since it completely depends on the domain at hand. In the case of these dots trying to reach a target, a simple measure of fitness might be their distance to the target. Here's an implementation of that.
func fitness(target: Vector) -> Float {
let distance = self.position.distance(target);
let fitness = 1.0 / (distance * distance);
return fitness;
}
The idea here is that we reward dots that are closer to the target, and punish those that are furthest (we punish them by using the squared distance, so dots that are slighter further away get punished harder). And this works, but this doesn't take into account Dots that have reached the target. Taking a second stab at the fitness implementation, you might end up with something as follows:
func fitness(target: Vector) -> Float {
if (self.success) {
let size = Float(self.dotSize)
let step = Float(self.brain.step)
let targetFitness = 1.0 / (size * size)
let stepFitness = 10000.0 / (step * step)
let fitness = targetFitness + stepFitness
return fitness;
} else {
let distance = self.position.distance(target);
let fitness = 1.0 / (distance * distance);
return fitness;
}
}
You can see that you kept the same distance fitness calculation, however, you add a check to reward dots that reach the target in the least amount of steps more heavily. The let stepFitness = 10000.0 / (step * step) calculation is exactly same calculation as the fitness distance, but applied to the number of times the dot needed to ask its brain for a direction. Essentially the lower number of steps, the better.
Note: Here
dotSizeis simply the size of the dot rendered on screen. I was playing around with random values for size, but you can take this value to be 1.
You might be wondering how you ended up on these calculations. The truth is, its a mix of trial and error, and common techniques. Generally, if smaller is better, you should use a variation of 1/(value * value), if larger is better, then some variation of value * value.
Now that you have the fitness function implemented, its time to select which of the dots will define the next generation. There are a few approaches to solving this problem. The first is simply to choose the Dot with the highest fitness. This is a viable approach, however, in the case of genetic algorithm, this Species is actually known as the "champion", and is generally added to the next generation unchanged. Another approach, which probably more closely mimics natural selection in our world is to sum all the fitness levels, then pick a value between zero and the total, and pick the Dot that ends up closest to that value. Did I lose you?
Maybe a diagram will make more sense.
From the diagram, you can see that this works more closely to a lottery system, where the species with the most number of tickets has the highest probability of being chosen. The truth is, in the real world, survival needs a little luck, and with this approach, you're throwing in a level of luck. You can achieve this with some code that looks as follows:
var fitnessSum: Float = 0;
for index in 0..<dots.count {
fitnessSum += fitness;
}
let fittestValue = Float.random(in: 0...1) * fitnessSum;
var fittest: Dot? = nil;
var runningSum: Float = 0;
for index in 0..<dots.count {
runningSum += self.dots[index].fitness(target: target);
if (runningSum >= fittestValue) {
fittest = self.dots[index];
break;
}
}
Ok, now you've picked the fittest dot to survive, now it's time to create the next generation of dots.
Making babies
In the normal case, you wouldn't only pick one dot to create the next generation of dots. You would normally pick two parents and copy certain traits from each. This is known as crossover. In the case of the dots, you might pick two parents, and select some directions from one and some directions from the other. In the name of not adding more to this already lengthy tutorial, you will simply use the Dot you randomly selected in the previous section, and you will pass your genes (in this case your brain and the corresponding directions array) on to the next generation of Dots.
You'll accomplish this by copying the direction list into a new Dot's brain, but you'll mutate a few directions using the mutationRatio you read about earlier. You'll do this until you have created enough dots to fill your population. Here's an example of how you might do this:
var newDots: [Dot] = [];
for _ in 0..<dots.count {
// Copy the fittest brain, but mutate it by the slightest
var directions: [Vector] = []
for index in 0..<minSteps {
if Float.random(in: 0...1) >= self.mutationRatio {
let direction = fittest!.brain.directions[index]
directions.append(Vector(x: direction.x, y: direction.y))
} else {
let angle = Float.random(in: 0...(2 * Float(Double.pi)))
directions.append(Vector(x: cos(angle), y: sin(angle)))
}
}
let nextDot = Dot(
width: self.width,
height: self.width,
dotSize: self.dotSize,
minTargetDistance: minTargetDistance,
brain: Brain(directions)
)
newDots.append(nextDot)
}
That's it! If you run the above code, eventually, you should see a cluster of dots slowly try to figure out how to reach the target over a number of generations.
Making things better
Although the code presented above work, in the final project, you'll see two slight additions to this approach. The first improvement was touched upon previously, which was to add your current generation's "champion" into your next generation. Since this Dot achieves the best fitness by either being the closest or hitting the target, it gives the next generation the best chance of getting a copy of its brain.
The second change was to use the minimum number of steps used by any successful Dot. In evolution, if you're able to do things more efficiently, you're chances of surviving go up.
NEAT and Deep Learning
So far, you've only established what genetic algorithm is, you haven't covered what exactly NEAT is. NEAT is a technique to creating a neural network. Specifically, its goal is create the neural network without back-propagation. NEAT can also use the process of natural selection to determine the best architecture for a neural network. That is, it may start with a two-level neural network, and then randomly mutate the network during natural selection to add another layer to see if this helps improve the species.
Takeaways
Although this tutorial outlines a very small use case for genetic algorithm, in practice scaling the fitness function can be very complex based on the problem you're trying to solve.
However, unlike typical deep learning techniques, you don't need prior data in order to build your Neural Network (in the case NEAT).
Consider checking out Code Bullet's YouTube channel where he applies the Neat Algorithm to a bunch of different games to see if he can teach the A.I to learn to play the game.
The code for this tutorial can be downloaded here
If you enjoyed this tutorial on working with CoreML LSTMs, consider checking out mlfairy.com. MLFairy is a service that helps you create better CoreML model for all your Apple edge devices.