Mutation-Based Evolution Simulation
I created this project to investigate the dynamics of evolution through random mutation. The cool part is they intelligently solve a problem without any hard-coded understanding of what the problem is or how well they are doing. Each agent has a neural network that mutates as it reproduces. What separates my investigation from the others that inspired me, was that I wanted to use dynamic neural network topologies in their evolution. In theory, their brains would grow or shrink to fit the complexity of their task.
I found lots of very interesting mechanics and behavior through these experiments. I also learned that dynamic neural networks weren't very promising, and figured out why they aren't too different to regular NN's in the first place.
This project falls into the category of a "zero player game", meaning that the game runs itself. Here's how the game works:
Rules
- Agents spawn in a random location on the board
- Each cell of the board can be occupied by only one agent
- Sections of the board is designated the target area
- An agent reproduces iff it makes it to the target area at the end of the round
- Agents mutate slightly when they reproduce
- Agents always reproduce enough times to repopulate the board
Agents
- Agents have a neural network that is randomized initially
- They also have a value for mutation rates and neural network size, these can mutate as well.
- They do not know if they are in the target area
-
Agents have a series of primitive sensors which ask
- Am I blocked?
- Am I at a wall?
- How far north and east am I?
- Which direction am I facing?
- How many timesteps has it been?
-
Agents have a series of actions they can take
- Move forward
- Turn left
- Turn right
- Turn 180
Running a simulation
Here's a summary of the run, and a video of the simulation. It only took about a minute to simulate these generations.
The reward boundary is covered by '~'.
***********************************************************************************
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ *
* ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ *
* ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ *
* ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ *
* ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ *
* ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ *
* ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ *
* ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
***********************************************************************************
Generation 0 survival rate was: 0%
Generation 2 survival rate was: 9%
Generation 4 survival rate was: 8%
Generation 8 survival rate was: 9%
Generation 16 survival rate was: 10%
Generation 32 survival rate was: 10%
Generation 64 survival rate was: 8%
Generation 128 survival rate was: 6%
Generation 256 survival rate was: 31%
Generation 512 survival rate was: 47%
Generation 905 survival rate was: 41%
Generation 1024 survival rate was: 49%
Generation 2048 survival rate was: 42%
Generation 2953 survival rate was: 54%
Generation 3977 survival rate was: 54%
Generation 4096 survival rate was: 50%
Generation 4489 survival rate was: 41%
Generation 4745 survival rate was: 34%
Generation 4873 survival rate was: 49%
Generation 4937 survival rate was: 50%
Generation 4969 survival rate was: 51%
Generation 4985 survival rate was: 46%
Generation 4993 survival rate was: 48%
Generation 4997 survival rate was: 48%
Generation 4999 survival rate was: 44%
Generation 5000 survival rate was: 49%
Interesting Behavior
Dynamic Neural Network Shortcomings
The dynamic neural network was a cool idea, but it didn't work out. The problem is that a regular neural network can already "grow" to fit the complexity of the problem, it just emphasizes certain connections more. So the dynamic neural network ended up interupting training or not really mattering.
Non-monotonic improvement
Because agents interact with each other, when a tribe of agents discovers a successful strategy, a new tribe may emerge that knows how to beat their strategy. But when the new tribe becomes dominant, their strategy may be inferior to the previous strategy because it relied on interactions between them. For example one tribe may be good at travelling vertically, while another learns to travel horizontally until they collide with the first tribe.
AI Extinction
Sometimes a bad strategy will work well, due to the random chance of spawning in the target area. If this is paired with an unlucky round for more intelligent tribes, then the bad strategy can become dominant. This has been observed to lead survival rates to drop from 30% to single digits.
Sacrifice (my favorite)
Sometimes the agents will hover at about a 50% survival rate for a long time, and no matter how many generations are run the strategy never changes. This suggests that even though the the survival rate is lower, that strategy has taken over 100% of the population.
The way it works is that agents have recessive and expressed behavior. So the agents learn two simple strategies rather than one more complex one. If an agent spawns in the bottom half, their goal is to reach stop on a diagonal line and stop. If they spawn in the top half they go down and left until they hit someone, usually someone who started on the bottom half. Ultimately, what happens is many agents on the bottom half sacrifice themselves to help the top half, but they are still siblings so the stragey lives on.
Notes and Refs:
- [0]: Inspired by David Miller's, "I progrmammed some creatures. They evolved" (December 2020).