Traveling Salesman Problem solved with Kohonen Network.
Open html/index.html file in your browser. Draw some points and click Start button. Alternatively, pick one of the pre-defined examples from the dropdown list.
Solving the TSP problem with a brute-force approach is not feasible for a large number of cities die to O(n!) time complexity.
Thus, we can use algorithms that return sub-optimal results in an acceptable time. Kohonen Network is a type of neural network that can be used to solve TSP problem.
It is a type of unsupervised learning algorithm that is used to cluster data. In this case, it is used to find the shortest path between cities.
- Generate neurons described by [x, y] coordinates and place them in a circle. Numbers of neurons should be twice the number of cities.
- Pick a random city and find the closest neuron to it. This neuron is the winner.
- Adjust the weights of the winner and its neighbors to move them closer to the city.
- Reduce the learning rate and repeat steps 2 and 3 for all cities.
- Finish when the learning rate is small enough.
- θ - Used to calculate neighborhood function. The smaller the value, the smaller the neighborhood, meaning neurons that are located further away from the winning neuron will be less affected (moved) during learning.
- φ - Describes how much a neuron can learn (how much it can move) in a single algorithm iteration. The smaller the value, the smaller the movement.
- Momentum - Describes how quickly the algorithm slows down every iteration. The smaller the value, the greater the slowdown.
