Genetic Algorithms in 15 Minutes

Hey everybody, in this blog post we’re going to be going over how genetic algorithms work and how they can find a solution to a problem. I’m currently working on a virtual ant farm where the ants are controlled using genetic algorithms, so I’m going to use this blog post as a quick reference for anyone trying to understand that project.

Genetic Algorithms

For a genetic algorithm to work, the solution to the problem must able to be encoded into a sequence of characters or numbers, which we’ll call a genome. Something like chess doesn’t really translate terribly well to genetic algorithms, because encoding an entire chess strategy into a relatively small sequence of characters or numbers is very hard. On the other hand, something like moving efficiently through 2d or 3d space in a video game would work much better. We can encode the behavior as properties like the distance that your character stays away from walls, or how fast your character will prefer to turn as it moves.

After initially setting up our starting population (which just involves  picking random values for all the attributes in our genome for the entire population), a genetic algorithm has three parts: selection, crossover, and mutation. In selection, we evaluate how well each member of the population solves the problem at hand, and delete the ones that are found to be the most unfit. In crossover, we generate new members of the population out of the individuals that survived selection. Then we do mutation, where for each member of the population that we just created, we randomly tweak their genome a little bit. This helps to be able to explore new values for the attributes instead of just cycling between the values that our initial population started with.

If any of that was confusing, bear with me. It’ll become a lot clearer after seeing a couple of examples.

A Trivial Example

For a very simple example, let’s consider a player in a 2×3 grid world. The player has to get from the start to the goal as quickly as possible.

The catch is that the player doesn’t get to decide where they’re going to move each turn. Before the game starts, the player declares what probability they’re going to take each possible action (left, right, up, down), and then the game plays out through random chance with no interaction from the player. For example, if the player says “50% right, 50% up”, then they’ll move up half the time and right half the time, but they won’t get to pick when they move where.

The actual solution here is completely obvious, it’s just “go up 100% of the time”. It’s easier to see how genetic algorithms work in a game with an obvious strategy than in a complicated one, though.

The first thing we do is set up our initial population, and we’ll just have 3 individuals in our population. Each round we’ll eliminate the worst one, and then repopulate back up to 3 individuals by crossing the remaining two.

Here’s our random initial population (it’s not actually random because I chose examples that would work well for the demo, but just pretend it’s random):

Now we need to do selection. We run our agents and get the following results:

Player 3 is our genetic loser, so they’re removed from the population. We’ll now do crossover between the remaining players. We take the average of Player 1 and Player 2, and get this new player:

We want to do mutation as well, so we pick two attributes and increase one and decrease the other. Normally, mutation can just influence one attribute instead of two, but our percentages have to add to 100%, so we can’t just change 1

In this case our mutation ended up hurting instead of helping. This individual will eventually be removed from the population in a future run anyway.

You can see that if we re-run this over and over, we’ll eventually reach a situation where all three agents are at (or extremely close to) 100% up, 0% everything else. A good way to determine if the algorithm is done is to see when the agents have all stopped changing each time. If you’ve got a way to check when an optimal solution has been found, you can just check every round if any members of the population are optimal or close enough to optimal.

A Slightly More Interesting Game

Alright, let’s do one where our agent has to do a bit more learning. The rules are the same, but we’ll be using this map:

That spot in the center is valid to move into, but the agent can only move out of it by going back (so the thick black bars represent walls). The optimal strategy is going to involve moving forward some, left some, right some, and back just enough to make sure you can get unstuck if you fall into the center space.

Let’s also up the number of individuals in the population. We’ll do 5 individuals, 2 of which are removed each round. In a real genetic algorithms problem, you’re more likely to have hundreds of individuals or more, but for the sake of simplicity, I’m definitely not about to do that many.

Initial Population:

Selection:

The result of this is that players 2 and 3 are eliminated.

Crossover:

We need to create 2 players. We’ll draw randomly (with replacement) among the rest of the population. The players that made it to the goal in fewer steps are more likely to be selected.

Note that player 7 was just a crossover between player 4 and itself. While mating with yourself is perfectly natural and nothing to be ashamed of, it doesn’t really make sense in biological evolution for that to result in an offspring. For the purposes of genetic algorithms (at least this exact flavor of genetic algorithms), it’s valid to cross over an individual with itself.

Mutation:

That mutation on player 7 is probably not going to be very helpful. Moving right more than twice as much as moving left is probably bad because an optimal solution involves 1 left move and 1 right move. Our algorithm doesn’t know that, though. If that mutation ends up being unhelpful, then this player will be removed from the pool once it becomes one of the most unfit.

Let’s go ahead and do one more iteration of the algorithm to see what happens. Feel free to jump to the end if you’re bored with this toy example.

Current population:

 

Selection:

Players 5 and 7 are eliminated. Player 7 definitely would have been eliminated eventually anyway. This time it just got a little bit unlucky and took too long to get to the goal. With 0% moving back, it’s going to get stuck in that center space and never reach the goal most of the time.

Crossover:

Mutation:

 

Developer Choices

A lot of things in genetic algorithms come down to whatever the developer chooses. Here are some things that you could change to get different behavior out of the system:

  • Number of individuals in the population
  • What the genome is (and what genomes are valid/invalid)
  • How much to mutate each genome
  • If mutation should always happen, or randomly
  • If only two individuals should be combined for crossover, or if 3 or more can be combined.
  • How genomes get combined (is it always half of one and half of the other, or something else?)

 

Other Examples

Genetic algorithms has actually accomplished some pretty cool stuff in recent years. There’s tons of great examples, but here’s a few neat ones.

NASA uses genetic algorithms to design antennas that need specific and unusual shapes.

Computational creativity can create stories, jokes, music, paintings, and much more.

Automated design and engineering can automate the design of physical components:

 

Virtual Ant Farm

The reason why I’ve gotten into genetic algorithms in the first place is that I’m trying to make a virtual ant farm. This is sort of a more advanced version of my virtual fish tank (link), but they’re going to function pretty differently.

The goal of the project is to build a continually running ant farm where two colonies start on opposite sides of the screen. The two colonies will generate ants and send them out to get food. The fit ants will return with food, and the unfit ants will die. When enough food is brought back to the colony, another ant will be created (according to genetic algorithms by sampling the remaining ants). Eventually, one of the colonies will kill off the other, and then the game will restart.

When I’m done with it, my virtual ant farm will be available here: https://twitch.tv/virtualantfarm

I’ll have another post up once I’ve made enough progress to put up a first iteration on twitch.

Thanks for Reading!

If you’ve got any questions/comments, feel free to reach out to me on twitter or email me at artificiallyinteresting@gmail.com.

One thought on “Genetic Algorithms in 15 Minutes

Leave a Comment

Your email address will not be published. Required fields are marked *