I’ve been working on a code in C to solve the Travelling Salesman Problem using Genetic Algorithms. In the past this problem has been attacked using brute force, simply trying every possible passage. Yet as the size of a dataset rises, the computation time increases exponentially with this method, such that a thousand points can take a very long time to solve.
Genetic Algorithms try a few random solutions, then keep the best and generate new ones to fill in the holes left byt the old solutions. Therefore, if a great solution is stumbled upon, it sticks around unless a better solution is found. This is left a bit up to chance. Another method is to, at each iteration, split the solution stack in thirds, sorted by those which give the best distance: keep those at the top, create the middle third by using chunks from the top third, and randomly generate the bottom. In this manner, solutions that are very far from the intended result those close to that will never have to be tried, yet the random factor protects against finding a “local minimum” as opposed to an “absolute minimum”.
My code has a few issues yet, but should work soon.
Leave a comment
Leave a Reply