My Genetic Algorithm Solving the TSP Problem
I wrote a genetic algorithm (GA) back in 2011 to solve the traveling salesman problem (TSP). I wrote the algorithm in C++ and made a recording of the algorithm that I later uploaded on YouTube. It was during the time that I was obsessed with algorithms. While having a major interest in GAs, my primary focus was on writing a new algorithm to efficiently solve the boolean satisfiability problem (SAT). Which I eventually did, getting my results published in the Scientific Research Journal. Oh, those were fun times! So the recording of the GA has been on YouTube for close to 3 years, and has over 10000 views today. I thought I'd share it with you:
The video shows my algorithm solving the TSP problem, where the number of cities is 100. I used an elitist approach here, with 60 % order crossover, 10 % mutation and the algorithm ran for 10000 generations. What you see is the cities being plotted on a circle, and the different paths being computed by the algorithm. Instead of showing you the different paths, I probably should have only showed you the best paths being picked (elitism). But if I had done that, you wouldn't have been able to see so many pretty lines being drawn.
If I were to re-write the algorithm today, I would have made it better in many ways. Primarily in terms of readability of the code, but also structurally. Oh, and I wouldn't use a crappy laptop with 2 GB of RAM :)