Evolution in a genetic algorithms
Timo Hondema 500757333
Since 1859, when Charles Darwin published On the origins of species we as a species have learned a lot about our evolution and evolution as a whole. Darwin proposed that creatures aren’t directly or perfectly created but populations change over time to better adapt to their environment. The creatures in the population that adapt to their environment the best are the fittest of the population. In nature only the fittest of them all survive. The fittest animals are the ones that are best equipped to survive. In the example of a forest butterfly a brown colored butterfly might survive better than a butterfly that has a yellow color. But that same yellow color could be crucial in survival for a desert butterfly. So when a forest butterfly is born brown that could mean it is better camouflaged. This could mean it could take longer for it to be seen by predators, so it has more time to reproduce and so more are born brown. This will eventually cause the entire population to turn brown overtime.
To build a genetic algorithm that is capable to reproduce such a theory as evolution it is important to understand all aspects of evolution. So first we must go through all important information.
The changes that animals go through as a population in the form of evolution are not just random events. Each animal has its own set of genetics. These are its characteristics , features and its normal behaviour. These genetics are stored in the DNA. Every animal has in every cell of its body strains of DNA.
Each creature’s characteristics, features and behaviour is stored in DNA (DeoxyriboNucleic Acid). It is present in every cell of every living organism, from flies to elephants and from bananas to humans.
DNA itself contains straines called genes. The genes of a DNA are the parts of the DNA that store the information. DNA can be seen as a list of features and each of the parts in the list is a gene. The genes can have a range of definitions. It could say what color the animal is or how fast it can run.
Genetic Algorithms are a way of simulating these elements from Darwin’s theory of evolution. All the elements are represented in their own respected way.
A genetic algorithm
To make a genetic algorithm we first start with a population. The population is made up of creatures. The size of a population can grow and shrink based on how well a population reproduces.
Each of the creatures in the population has its own set of DNA. In this DNA the genes are stored. The genes can have one of two values , a zero or a one. But the location of these genes in its DNA is crucial in deciding what will happen to the creature. Because the place of a gene in its DNA can tell it to be faster or slower.
But to make a generation better than the one before it it must mutate its genes. Mutation is the process that adds a new change in one of the genes in order to make a change in behaviour possible.
In normal reproduction the DNA is split and one half of the offspring’s DNA comes from its father and one half of it comes from its mother’s DNA. This would mean that no real change has happened. It only means that the genes of the parents survive to a new generation. But mutation brings a new element to this. Mutation basically means that at a certain point in the offspring’s DNA a gene is changed. This will give the offspring a potential new advantage or disadvantage.
To make a genetic algorithm it is important to translate all the aforementioned aspects to a program. In this chapter I am going to explain how I build a genetics algorithm and how it works.
The population of the algorithm is filled by agents. Each agent has a set behaviour in which they move. The setup for this behaviour is the same for each agent. But the attributes of each agent differ from each generation. Certain variables of its behaviour are affected by its DNA.
The behaviour that the agents go through is very easy and manageable. Each agent has a rotate time and walk time. The rotate and walk time are the time they take to walk and to rotate. Then there is a Rotate interval and Walk wait. the rotate interval is the time it takes between times it rotates. Walkwait is time it waits to start walking after rotating.
The agent’s DNA will need to be stored separately from its behaviour. This will give a more organised system. The DNA itself will need to have all the information needed to give it its proper genetic aspects. A set List of genes and the information of the geness. But not only that but also what must happen if procreation takes place and what needs to happen when a mutation takes place.
As seen in the code, every agent has a list of genes; this list has a set maximum value and a set minimal value. Then we fill the list with random numbers until the list is filled.
To let the agents procreate when they touch each other , it is important to mutate their genes from time to time.
This is done by taking a random number in the list of genes and changing one of it to a different number.
But just these two scripts won’t work on their own. They need a master script to spawn the agents and to manage them.
Agents are spawned as long as the population size is not exceeded. They are spawned on a random location on the map and they are given a brain, which in turn gives it a DNA set.
When agents get near eachother they can reproduce. This reproduction is mostly done with their respected DNA. When they get near eachother they will share their DNA. It will take the DNA of the one and the DNA of the other and perform breeding.
To breed two things are necessary the dnaset of the father and the dna set of the mother. This is the combined and fed to the DNA script where it will go through a breeding sequence.
But breeding is not the only thing the agent can do. In order for the population to grow it uses breeding but there has to be a way for the population to shrink. To be able for the population to shrink, agents need to die. The health of each agent is stored in the amount of fuel an agent has. Each agent starts with the same amount of fuel. Slowly but surely the fuel depleets. When the amount of fuel of the agent reaches zero it dies. But an agent is also capable of recharging their fuel. Throughout the world an agent can encounter fuel. When an agent comes into view of a fuel they will move towards the fuel. When they reach the fuel their fuel will be recharged and they will have more time to reproduce so more of their DNA will be spread amongst the population.
Before the simulation is run it is important to state what we are looking at. Most of all it is important to describe what I would want to see happen. The goal of the simulation is to simulate evolution. I hope to see changes in behaviour of the agents in terms of speed and paths that they will make. I hope to see them find fuel and then try to reproduce. I hope to be able to spot differences in DNA by just looking at an agent behaviour.
When the simulation is run it becomes clear that at first sight now real difference in behaviour between the agents is visible.
What is immediatly visible is that some will jump off to the side of the screen. They have a very high overall statistic so they move fast and rotate quickly. But they die off fairly quickly because by hugging the wall they won’t find any fuel. when they die their high stat genes die off. The ones that survive are the ones with lower movement variables. They have lower movement so they stay more centered and can more easily reproduce.
As is visible in the results some mutating takes place and the population size can expand and shrink. But so far evolution is not as clear as I would have hoped. You do see that the behaviour of the agents changes. Where the agents first all drift off to find fuel, they later on cluster together. When they cluster together they can reproduce more often and thus the population will be sustained. But I had hoped to see more diverse behaviour. I had hoped to see that some agents would go off to find fuel and some would move less and reproduce more. But at the same time these results are what could be expected from evolution. As Charles Darwin put it, only the fittest most well adapted individuals survive. The simulation that I have made has caused an environment in which breeding to keep the population alive is more beneficial than going out to find fuel.
For the future
The simulation that I have created is far from perfect. For one thing, it becomes clear that after a certain time the population will inevitably die out. The population can sustain itself for some time but not forever. This is something I would want to change and fix in the future.
A different thing I have noticed is the lack of variables that can change for every agent. Each agent now has 6 different variables that can change. This will only give so much change. I hope to be able to give the agents more variables. Not only variables that limit their movement but also impulses and maybe size differences.
The third thing that bothers me in the current simulation is the role fuel plays. Fuel is only there to give the agent a fuel toi survive, but as the simulation results show they don’t use them as I would have hoped. The agents prefer to reproduce to refuel their offspring. In the future I would change certain aspects of the agents DNA so that inbreeding and incest can become an issue for them. This would give them stimuli to go out and find fuel and not cluster around.
A better program
In order to improve the simulation it is important to analyse what does and what does not work. In the simulation as laid out above certain elements indeed work pretty well. Elements such as;
- The DNA
- The Breeding
- Fuel collecting
To change these is unnecessary. But more structural change will need to be made to the behaviour of the subjects. The subjects now move and rotate in relation to the same speed, their movement speed. This is a variable that can change according to its DNA. But the way their movement is programmed inherently limits its rotation. The speed at which they rotate does not give the same rotation speed as their relative forward speed. Which means they hardly ever rotate entirely around their own axis. To change this I split the movement speed and the rotation speed. I made two new variables, RotationSpeed and MoveSpeed.
By doing this I could make them rotate more and I could give their DNA an extra piece of information which ultimately brings out more results to the simulation. So by changing this I cleaned up the code and made for more interesting results.
A second change that I deemed necessary was the way fuel worked on the part of the subjects. Fuel is managed quite easily, they have a starting amount that empties out over time. When their fuel is gone they die. This was too simple in my opinion. So in order to simulate a kind of fullness in the subjects I gave them a capacity. The capacity is a variable that indicates how much fuel a subject can carry at a time. If a subject has a capacity of 100 fuel and that capacity is totally filled they can add new fuel to it. This capacity variable is also inheritable through the subject’s DNA. Which gives it an additional new factor in the simulation.
But to make sure that these changes did not adversely harm or damage the simulation I tested the changes in the simulation.
The simulation shows that hardly any visible changes have occurred. In comparison to earlier results it almost seems the same. But if you look carefully some changes are visible. Some of the subjects are now rotating very quickly while others aren’t. This shows that their DNA has a gene that makes them move that way.
Comparing these results with the results that came from the previous iteration of the simulation, I have noticed that the subjects no longer strongly center around one single position, I believe that the changes in their movement have made them more agile in their movement and thus more likely to move around. The changes that I have made have altered the simulation in a way I did not anticipate beforehand but it has been beneficial.
But I believe just fiddling around with the variables is not enough to improve the simulation.
Because ,a normal real world environment does not just contain an isolated and “safe” population in a set location. In the real world every animal has their own predator that hunts them and ultimately damages the population of the prey. To better emulate real evolution I found it important to take this into account too. Therefore I recreated a predator creature.
To recreate it realistically , I didn’t want to have to totally recreate it’s behaviour from scratch. I want it to be not identical but similar to the subjects. It moves in the same way as the subjects. The key difference is that when the predator comes into contact with one of the subjects , the subject will die. Such a predator will serve as a deterrent for the subjects to cluster in one place, as they did in the first iteration of the simulation.
To make such a predator does not have to be too complicated. The predator contains a wandering behaviour that essentially works in the same way as the subjects do. The difference is that the subjects have an entire list of variable s and dna mutations that make them move more agile and much less predictable. The predator does not have that. The only predictable thing in his behaviour is his timing. In his movement some pauses occur in which the predator will change direction or turn around. The exact timing of these pauses and when they will occur changes based on a random range for each of the variables.
As you can see in the simulation the predator moves much more fluently through the stage then the subjects do. But the predator moves more in a sweeping kind of way. It sweepes up all the subjects in its path. But as you can see in this result it does not kill very many subjects. You could say that that is a good thing but I want the predator to have more prey , so in the next simulation I have increased the number of subjects in the simulation to show that the predator can be much more deadly if given the opportunity.
In this simulation I wish to look at the effects of split environments on evolution. Where in earlier examples all the subjects were all living in one big area for this simulation and one kind of result is what came out. In the next example I have chosen to split the environments. As this article sets out the notion that when environments change for a population that then too does the population change. I want to emulate this in my simulation.
To effectively emulate this I have chosen to simply split the population in two , by making a huge wall through the middle of the playing field. On one side of the playing field a predator will spawn, and on the other side there won’t be a predator. This will clearly give one side an advantage over the other, I suspect. But what is more interesting in my opinion is the behaviour that the two sides will show. Will there be a difference?
What can be seen in the results is a drastic difference between the both sides. The populations on the predator side are much more spread out. They still cluster a little bit but they are far enough away that they all inhibit different behaviour. The predator forces them to move away from each other. At some point it even happens that a group of subjects tries to cluster but the predator comes in and kills one of them.
On the other side in the meantime, the subjects clearly cluster to each other. Because there is no clear danger in them doing so. They cluster as much as they did in the very first results but they clearly cluster more than the other side. I find it very interesting to see a different behaviour considering they get the same amount of fuel and start with a similar set of DNA.
To summarise, the changes I have made to the program have made the subjects more agile and more likely to behave in different ways. The addition of the predator has given the subjects a danger and a reason to not cluster in a single position. This is an extra factor for change in their behaviour, because it forces the more agile subjects to seek eachother out and reproduce. The test environment in which two separate populations are studied shows that the way their DNA works forces different behaviour under different circumstances.