you can see how the green dots(agents) try to reach the big blue dot(goal)

Hello! this is my new blog and website and I decided to kick it of with something interesting .
I have spent the last few days reaserching the genetic algorithm, and I decided to implement it into pygame .

Explanation

Each of the agents, which are being represented as green dots, have a list of moves .
This list is 250 moves long, each moves is one of 5 possible move types represented by there numbers .

1. Move left 1 x coordinate
2. Move up 1 y coordinate
3. Move right 1 x coordinate
4. Move down 1 y coordinate
5. Sleep for an update cycle

After each agent either reaches the goal or runs out of moves the next generation begins .
A generation is created by selecting the best agent from the last generation, making copies of it and then mutating all of the copys .

The best of the last generation is also included in the next generation just to insure that there is no way for a generation to be worse then the last .
The best of the previous generation is colored blue to distinguish it from its fellow agents .

This basic loop repeats until the user decides to stop the application .

Scoring

This section is about how the agents are scored . This score is then used to select the best agent out of all of them .

Here is the scoring code.

def value(ag):
  dist = hypot(ag.x-goalx,ag.y-goaly)
  if ag.reached_goal:
    return 10000.0/(ag.move_count*ag.move_count)
  else:
    return 1.0/(dist*dist)

This code returns 10000 divided by the amount of moves the agent has made in its life span if the agent made it to the goal.
If the agent didn't make it to the goal, it's score is based on 1 divided by the distance to the goal squared.

I have done it like this so that even the worst agent that reaches the goal will get a higher score then even the best agent that doesnt reach the goal.

Mutation

This section is about how the movelists of the agents are mutate once they are created.

Here is the code for mutating the list of moves.

def mutate(self):
  mutrate = 0.1
  for i in range(len(self.moves)):
    rand = random()
    if rand < mutrate:
      self.moves[i] = choice(moves)

It goes through all of the moves and gets a random float from 0-1 (rand), if this number is less then the mutation rate (mutrate) a new random move is chosen from the list of possible moves.

This may look like it won't work due to its simplicity, but in practice it works very well.

In practice

this graph shows how over 60 generations the amount of moves the best agent needs to get to goal decreases

As shown in the image above, this algorithm is pretty good at quickly optimizing the agents movelists.
This took around 5-10 minutes to reach the best score.
This can be made even quicker by running it with a higher frame rate instead of just 60 fps one could run it at 600 or 6000 fps to make generations go by in seconds.

Possible Improvements

There are many possible improvements that can be used to help with this implementation, if you want to you can implement these into the code yourself.

The first of many improvements is to use multiple parents instead of just using the best one. This can be done by getting the 2 best parents and for each of the children randomly "cross over" some of the moves from each parents move list.

Another possible improvement is to allow the agents to move at 45 degree angles, this would allow the agents to more efficiently reach the goal if it is not straight on to them.

One can also add walls to the implementation to make it more challenging for the agents to reach the goal.
One would also need to add an incentive to go around the wall instead of just going near the wall, as I have tried to implement this into the simulation however the agents simply hit the wall and never went around it.

Conclusion

This implmentation of the genetic algorithm is able to quickly determine the best path from the spawn to the goal, however some improvements can still be made.

The source code to the simulation is on github, the link is above.

Thank you for reading this blog post, as it was the first one I have ever written. I hope you found it helpful.