Lots of circles doing their best to reach the goal as quickly as possible
What's going on?
What you are seeing on the image above, are lots of bups (My name for these circles) trying to jump their way towards the end goal, shown here as a floating yellow sun. These bups know nothing of their environment and have no specific instructions programmed in. The only thing they have is a list of 10 vectors, indicating in what direction they should jump and with which force. These vectors are being changed by a genetic algorithm, which does its best to improve the "AI" of these bups. This genetic algorithm knows very little as well - the only info it has is the time needed for each bup to reach to goal, or if it couldn't reach the goal in 10 jumps, the distance it was removed from it. Let's go a bit more in detail.
The inner workings
As mentioned before, each bup has 10 vectors which it uses one by one to jump around. These are initially random, but the goal of this little program is to optimize these vectors to ensure a quickest path is found. After each bup used its 10 jumps (or reached the goal), the genetic algorithm will order them by fitness. This is a value given to each bup based on how quickly or how close it got to the goal. The higher the fitness of a bup, the higher odds it has of passing on its genes to the next generation of bups (an "iteration" of the program). These genes are of course, the vectors. New young bups will be created by mixing the vectors of parents with high fitness. Occasionally, a vector will be completely mutated (randomized) to ensure new strategies can always emerge. Using this continuous improvement, bups should perform better and better until they eventually reach the goal and start optimizing their times.
Results
Picking the best vector from a randomized pool sounds strange. What's even more strange however, is that this actually produces results, and boy are they good. Often in a few hundred generations time (less than a second if skipping the visual representation) bups will have found an extremely fast path towards the goal, and keep improving to shave milliseconds off their best time. Personally I found it extremely surprising how well this worked. The bups know absolutely nothing, yet they successfully keep improving with the help of the genetic algorithm. While it's not as advanced as a neural network, it has been a fun little project to see the effects of evolution in nature in action.
Test it out here yourself!
https://winnie334.github.io/smart_bups/
Thanks to:
- p5.js for making this possible and being a great library overall.
- Daniel Shiffman for inspiring me to make this project.
- Github for encouraging me to write this post for their graduation yearbook!
If you are interested in the code, check it out here.
winnie334
/
smart_bups
My first genetic algorithm!
Smart_bups
A small project showcasing genetic algorithms.
How does it work:
There are small creatures called "bups", and their goal is to reach the yellow circle. They can jump a limited amount of times, after which they will be evaluated based on their distance to the goal. They will then create a new generation of bups, using genes randomly (although better performing bups have a higher chance to be chosen). The original population is killed off (except for the best bup) and the process repeats.
The indicators on top show you the statistics. Fitness increases the closer a bup gets to the goal. As soon as a bup reaches the goal, its fitness is increased massively. However, the fitness can be increased even more by reaching the goal faster (this is the time indicator).
Note that not every simulation will reach the end. Sometimes the RNG is so bad that…
Top comments (0)