Lifeforms in nature need to adapt. Without adaptation the survival of a species would be impossible in changing environments. Animals and plants are are good examples. The same evolutionary principles that helped species in nature can be used in a simpler and faster matter on todays computers:
- Better adapted individuals survice
- Genes are passed to the children
- Mutations sometimes improve a species
Genes are encoded as strings of 'commands' in the DNA. This can be done with computer algorithms as well. In this example we will use an artificial ant.
This ant does not have a brain. It is just following simple commands. These commands are R for "turn right" and L for "turn left". The ant will turn in the opposite direction, if the place was already visited before. This can be a gene-code for such a path of an ant: LRLRLRLLRLLLRLRLRLLRLLLRRRLRL
If the last command was executed, the whole command-list will be repeated, resulting in an endless movement pattern. Since there are only 2 commands, the gene can be represented in binary form: 01010100100010101001000111010
A single ant cant reproduce and will not result in an evolutionary process. We need a whole ant population for that to occur. Since GA are much simpler than nature, 50 inidividuals will be okay for this example. They all start with random genes. Second, we need an environment that will tell us, if the ant is doing well in its simple artificial life. In this example we have a small two dimensional world and the goal for the ant is to visit as many places as possible. For this small example we can assume that each ant will live for a fixed amount of time.
All ants start with an unvisited world. After a fixed amount of time, 1000 steps, all ants die. The environment can tell us, wich ant has visited more places than other ants. The best ants are allowed to reproduce and the other ants wont be able to pass their genetic code to the next generation. The binary code of the well performing ants can be combined and mutations (bit-flips) will occur. Example:
Mother 01010100100010101001000111010 Father 10100011101010010111011000101
Child A 01011100100010010111011000101 Child B 01010100101010010011011000101
These genetic codes show which genes are passed to the next generation and where mutations occur. The algorithm will start again with the next generation of ants. The algorithm can be stopped if no big improvement is achieved and the genetic code somewhat stabilizes itself. In my example I tried to visualize the performance of ants. The path of an ant is shown in blue and if places are visited more often, the path gets yellow.
The optimal path would be an equal distribution of blue lines without many yellow or black areas.
This shows the progression of the algorithm on youtube: