I have learn about the theory of genetic algorithms while ago but I have never put this knowledge into practice. Thus I decided to do a project that implements a genetic algorithm to find the shortest path to a destination. In the samples bellow the destination is the pink circle. In this project the DNA of each individual is defined by an move toward a direction.
I used OpenGL because I think having a visual representation is more enjoyable and also more easy to debug. Based on this version I can later: change the map, put obstacles, and many more things!
Bellow a sample of the first generation tracing their own way. We can see that each individual goes totally randomly in the map.
25 generations later, we can see that the individuals seem to have found a decent direction toward the destination. The computation of the fitness is based on several parameters like: the death of the individual (out of the map), the distance to the destination, the average distance during their life, the speed depending of the relief (slower depending of the hill) and the water, repeated position, etc.
With all these variables I don't have to write explicitely to go to the destination by going between the lakes, it just works thanks to promotion according to the fitness of each individual. At the 60th generation, some individuals have reached the destination. The bright yellow model is the best fit of the previous generation.
