Why should we care about efficiency? Genetic algorithms are incredibly expensive to compute over large sums of simulations. By understanding their behaivor, we can design better algorithms.
If you are interested only in the results, skip to the results section. Otherwise, We start from Here:
First we Create the ground plane:
We Add Gravity, Collisions, and a Friction. We also add a box to show that our physics are working corectly
They can be any shape, but for demonstration purposes, they will be made of cubes:
Bot Parts are connected by Joints. The parts of the bot can rotate around the joint by a set number of degrees. In our simulations, it will be between 0 and 90.
Our bots have two different kinds of blocks, sensor blocks and regular blocks. Sensor Blocks can sense their angle.
Or they can pass through a hidden layer
Before Training, bots will have the weights of each neuron be random, but through the process of training, the weights will adjust to produce higher fitness values
This same process is continued no matter how many parts are already added.
A mutation is the process of adding between 1 and 5 parts, in the same way shown above, or changing the weight of one or more of the neurons in a brain.
The fitness of the parent is measured against the fitness of the child. The ratio of parents to children kept is related to the fitness of each. The higher the fitness of an individual, the more likely it will be kept as part of the next generation
As you can see in the diagram, evolution does not always entail adding more parts. Sometimes, parts may even be removed
A phenotype is how a robot looks. The genotype is how a robot is stored or encoded. For this simulation, a direct graph encoding was used, meaning each robot is stored as a list of parts and what other parts they are attatched to. the brain is stored as a list of neurons, their synapses, and their weights. In the future it may be interesting to explore the consequences of an indirect encoding. Here we can see the encoding of a body and brain in plaintext:
A Correllation was found between fitness in the 10th and 100th generation. This Allows us to predict early on what the final fitness will be, and prune simulations that are not good enought.
1 population and 100 generations
20 population with 100 generations
From this, we can see that there is a correllation between fitness at generation 10 and generation 100. This makes intuitive sense if you look at a fitness landscape. The one shown here is perlin noise on a 3d graph
A bot will start at a random point in this landscape, then climb to the nearest local maximum. The problem is that most of the local maxima are much worse than the best local maxima
By the tenth generation, the bots usually have climbed close to their local maximum and there is a 50-70% correllation between the local maximum at gen 10 and the maximum at gen 100. By not running bots with low fitness at generation 10, we can save up to 85% computation time and power.
In this graph, the yellow and purple dots represent local maximum that would be pruned, and red are the bots that would be kept. One drawback is that some bots with the potential to be good are pruned prematurely.
Here we can see a large number of the bots are pruned at their 10th generation, while only a few are allowed to continue. This required 1450 simulations, but it returns a higher average maximum fitness than an equivilant run of 10000 simulations
It is clear that agressive pruning can lead to superior results with less simulations
This project was originally meant to analyze how body size and fitness were correllated, but since large body sizes were too difficult to simulate, I pivotted to how to better run genetic algorithms. Never the less, a large amount of data was still collected\
This project encompassed over 130k simulations. Thats equivilent to 7kwh of electricity. Now imagine a class being offered 3 times a year with 100 students all doing similar projects. That gets to be a lot (2100 kwhs) of electricity really fast. Genetic algorithms are expensive. Its important to optimize them. If given more time, I would want to find which early generation most strongly predicts final fitness.
The Code requires the following libraries, many of which are default on python 3.10, and the rest of which can be installed with pip os numpy matplotlib pyrosim pybullet random copy time sys math screenshot glob pandas csv
To run the program, you must be on windows 11 with the requisite libraries.
First, extract the four folders from the datas folder as shown
this should put four new folders into the the code
then find start.ps1, and click run with powershell as shown below
The shell will ask you if you want to see a robot. if you input y, it will display a fully evolved robot. if you input n, it will begin evolving robots. WARNING. EVOLVING ROBOTS QUICKLY GENERATES LARGE AMOUNTS OF NEW DATA, INCLUDING SCREENSHOTS OF YOUR SCREEN. IF YOU SCREEN IS THE WRONG SIZE, THE PROGRAM MAY FAIL.
this was done with the help of www.reddit.com/r/ludobots, pyrosim, my classmates, my TAs, and my professor at Northwestern University, Sam Kriegman. Much of the code is directly coppied from the subreddit's instructions. Other aspects of the code are made using generous support of coding forums like stack overflow.