in machine learning, tutorial, Unity3D

Evolutionary Computation – Part 4

Share Button

Our journey to harness the power of evolution is coming to an end. In the previous three parts of this tutorial we have constructed a bipedal body and a mutable genome that determines its behaviour. What’s left now is to actually implement the evolutionary computation that will find a successful walking strategy.

The Evolution Loop

Evolution is an iterative process. We will use a coroutine to ensure such a loop continues. In a nutshell, we start with a specific genome and make several mutated copies. We instantiate a creature for each copy and test its performance in a simulation. Then, we take the genome of the most performing creature, and iterate again.

The Simulation

To test how well a creature can actually walk, we need to create its body and to give it enough time to move. To simply things, let’s imagine that we have a sufficiently long floor in the game scene. We will instantiate creatures on top of it, at a sufficient distance from each other to avoid interferences. The code below does exactly this, spacing each creature (stored in prefab) by distance.

The function CreateCreatures keeps track of all the creatures that have been created, so that they can be easily manipulated. For a better control, we disable in the creature prefab the script Creature. This prevents the creature from moving. We can then start and stop the simulation with the following functions.

The Fitness Evaluation

Evolution is all about fitness evaluation. Once the simulation is over, we loop over all the creatures and get their final score. We keep track of the best one, so that we can mutate it in the next iteration.

Improvements

A careful reader might have noticed that the technique described in this tutorial relied on few parameters. Namely:  generations , simulationTime and variations. They represents, respectively, the number of generation to simulates, the duration of each simulation and the number of variations to generate ad each generation. A more careful reader, however, should have noticed that the strategy adopted is poisoned with hidden assumptions. They are the result of oversimplified design choices that have been made, and that are now becoming hard constraints. They will make the difference between a program that runs in one hour, and one that runs in one month. This section will try to address some of these constraints, providing more sensible alternatives that you can implement on your own.

  • Top K genomes. The genome that starts the next generation is the best one, across all the generations. This means that if the current generation is unable to improve the fitness, the next generation will start with the same genome. The obvious catch is that we might end up stuck in a loop where the same genome is simulated again and again, without any sensible improvement. A possible solution is to always take the best genome in the current run. The drawback of this choice is that the fitness can go down, if no mutation appear to bring an improvement. A more sensible approach is to take the best top k genomes from each generation, and use all of them as seeds for the next iteration. You can add in the unmutated best genome from the previous generation to ensure the fitness won’t go down, yet allowing space for better solutions to be found.
  • Adaptive learning rate. Every time we mutate a genome, we only alter a single parameter of a leg, and by a fixed amount. Mutations are what move us around the parameter space in which our solution lies. The speed at which we move is very important: if we move too much when we’re close we overshoot the target, but if we move too slow we might not overcome local maxima. The number of mutations performed (learning rate) on a genome should be related to the speed at which we are improving our score. The following animation shows how the dramatic effect that different strategies have in the convergence speed.

contours_evaluation_optimizers

  • Early termination. It’s easy to see that some simulations will bring us to a dead end. Every time the creature flips on its back, there is no way to get back on its feet. A good algorithm should detect this and interrupt their simulations to save resources.
  • Changing fitness function. If what you are trying to learn is rather complex, it might be worth it do to it in stages. This can be done by progressively changing the fitness function. This helps to focus the learning effort on a single task at a time.
  • Multiple tests. When it comes to simulate physics, chances are you’ll never get the same result twice. It is a good technique to instantiate multiple creatures with the same genome, in the same conditions, and averaging their performance to find a more reliable score.

Conclusion & Downloads

This tutorial has introduced and explained how evolutionary computation works. This topic is incredibly vast, so please take this as a general introduction.

You can download the complete Unity package for this project here. If you think this tutorial has helped you, please consider supporting me on Patreon.

Other resource

📧 Stay updated

A new tutorial is released every week.

💖 Support this blog

This websites exists thanks to the contribution of patrons on Patreon. If you think these posts have either helped or inspired you, please consider supporting this blog.

Paypal
Ko-fi
Twitter_logo

Write a Comment

Comment

12 Comments

  1. This was awesome, thank you so much!! It helped my understanding immensely. Most of all it really broadens the way in which I feel genetic computation can be utilised for modern day issues.
    Thanks again!

  2. So glad I could read this fantastic article.
    Very intriguing and interesting, the subject is well-explained and the steps are clear. I could talk about it for hours !
    Plus, the sources are given to anyone who wants it.
    Alan, you’re a shiny star in the dark sky of science 🙂

  3. Don’t think this is a good tutorial due to how everything is spaced out. you don’t have a good start point of this tutorial until right at the end. there’s no easy step by step guide of, like. make this thing with 2 legs then experiment with all the things!(no step by step due to how you setted up the series).

    The way you simulate the characters on their own plane is not a good idea because it means you wont have a good representation of how the things are doing. Would be better if they are all on the same plane and do not interact with each other(This would remove the jumpiness of the camera making the simulation feel broken and also entertain the person watching them race against each other^^)

  4. I’ve been writing a program to compare different optimisation methods on creature generation/evolution for my uni dissertation, and I’m definitely going to make use of some of the suggestions presented in these articles (along with a citation, of course, though not that it’ll get published or anything)! Thank you 😁

    • Hi Tom!
      If you’ll end up citing my work in your research, well it would be an honour for me.
      Let me know if you need any help. And feel free to send a copy to me when is done!
      I’m more than happy to read it! 🙂

Webmentions

  • Evolutionary Computation - Part 3 - Alan Zucconi July 14, 2017

    Hi Tom!
    If you’ll end up citing my work in your research, well it would be an honour for me.
    Let me know if you need any help. And feel free to send a copy to me when is done!
    I’m more than happy to read it! 🙂

  • Evolutionary Computation - Part 1 - Alan Zucconi July 14, 2017

    Hi Tom!
    If you’ll end up citing my work in your research, well it would be an honour for me.
    Let me know if you need any help. And feel free to send a copy to me when is done!
    I’m more than happy to read it! 🙂