Before You start have simulation you can add some obstacles using the left mouse button.
There is absolutely no guaranty that even a million generations will find the best path (this are random processes after all – no AI), but you can compere the A* solution with the current best path.
And of course this may be sometimes interesting to watch – after 10-20 generations the population has a tendency co create a coordinated colony
Here's how the current algorithm works:
1) Natural selection:
The task is very simple – go from point A to point B using a random path, the catch is – if You are not fast enough – You are dead. Only 10% of the population can survive, so only the best from the best will create offspring. Competing with the offspring is also the reword for surviving.
2) This is how they “do it” - recombination:
There are currently 3 active gens, the life span gen ant the mutation factor gen are nothing more than binary numbers, but the most important is the “patch gen” that tells witch direction to go in the current tick. In this simulation recombination works as fallows: You take the gens responsible for the same thing from two parents, You make sure that they have the same size, if not you cut off the end of the longest, than you copy the gens while tossing a coin on every node – if its head the child A gets a node from parent A and B from B, else child B gets the node from parent A and A from B.
3) Mutating is essential:
Mutation is simply swamping a node in a gen for something random. In this simulation there are 3 reasons for mutating: No genetic instruction – generation 0 starts with an empty path gens, and because the way recombination work first few generations can simply run out, so they need to write they own instruction; Invalid instruction – since the gen stores a instruction witch way to go, it will often tell to go in the wall – this kind of thing needs to be rewritten; Random mutation – Most of this kind of mutations will be deadly, but every once in a while a good one may happen injecting a fresh genetic material to the population. The first version of the simulation had no random mutations witch resulted in the inability to solve even the simplest problem, than I given all specimens the ability to mutate at random witch resulted with a 3 steps forward, two steps back pattern... than I decided that only the young can mutate witch was the most efficient (the part of the population that can mutate can be changed at any point)
4) Immortality is bad...
Well the combination of the ability of the parents to compete witch children and the inability of parents to mutate created a problem – parents dominated completely destroying the positive effect of mutations, so I've added a “dying from old age” mechanism...
