This is a try at an approximate solution to the famous Traveling Salesman problem using the Genetic Algorithm heuristic. There are countless articles on the topic out there. I just wanted to make my own 'general' GA module that could be used for any suitable problem. So, here is the implementation. As in the last post, the videos by The Coding Train on the subject were really helpful.
Some observations I made while playing around with the model:
- Size of the population was directly proportional to the amount of time it took to converge to a solution up to a point. After that, the computations for the increased population probably swamps any gains to be made by the large diversity of the large population.
- Mutations are pivotal. Setting mutation rate to 0 will make the algorithm settle pretty early on on a local optimum which often isn't a good enough solution.
- There's probably a lot that could be improved on it. Maybe a large initial mutation rate that decays over time could overcome local optima in favor of global optima. Maybe improved fitness function. Improved cross-over, maybe a stronger mutation.
Anyway, here is a demo gif:
Some observations I made while playing around with the model:
- Size of the population was directly proportional to the amount of time it took to converge to a solution up to a point. After that, the computations for the increased population probably swamps any gains to be made by the large diversity of the large population.
- Mutations are pivotal. Setting mutation rate to 0 will make the algorithm settle pretty early on on a local optimum which often isn't a good enough solution.
- There's probably a lot that could be improved on it. Maybe a large initial mutation rate that decays over time could overcome local optima in favor of global optima. Maybe improved fitness function. Improved cross-over, maybe a stronger mutation.
Anyway, here is a demo gif:
No comments:
Post a Comment