Solving the traveling salesman problem using different heuristic approaches. Visualized using SFML.
Solving TSP for n=50 using the genetic algorithm (slowed down to look nicer)
Currently, there are 3 different heuristic algorithms implemented for solving TSP:
Ant colony simulation takes inspiration from the natural behavior of ants searching for food.
Ants move freely through the graph starting at a source node and making a tour.
As they move they lay down pheromones whose strength is inversely proportional to the length of their tour.
When an ant picks the next node to visit the probability of visiting each node is proportional to pheromone
strength on the connecting edge.
References:
Dorigo et al. (2006)Ant Colony Optimization: link
The "Simulated annealing" method vaguely resembles annealing or forging metal.
The metal is first heated to some temperature at which it is malleable,
then it cools exponentially and becomes harder to deform - holding its new shape.
The algorithm follows a similar pattern at first we choose a starting temperature, and take some starting permutation.
At each step, we look at neighboring states of the current state (permutation) and compute their path lengths.
If we find a better solution we accept it and continue the local search.
Else we accept the worse solution with some probability
(dl being the difference in path length, c being a probability constant and T the temperature)
After the local search is completed, the temperature is reduced and the algorithm is repeated either until there are no changes made or the temperature reaches a very low point.
References:
S.Kirkpatrick et al. (1983) "Optimization by Simulated Annealing": link