Kohonen Self-Organizing Map for the Traveling Salesperson Problem
Lucas Brocki · 2005
This work shows how a modified Kohonen Self-Organizing Map with one dimensional neighborhood is used to approach the symmetrical Traveling Salesperson Problem (TSP). Solution generated by the Kohonen network is improved by the 2opt algorithm. The paper describes briefly self-organization in neural networks, 2opt algorithm and modifications applied to Self-Organizing Map. Finally, the algorithm is compared with Evolutionary Algorithm with Enhanced Edge Recombination operator and Lin-Kerninghan algorithm. Kohonen Self-Organizing Map basics In 1975 Teuvo Kohonen introduced new type of neural network that uses competitive, unsupervised learning [1]. This approach is based on WTA (Winner Takes All) and WTM (Winner Takes Most) algorithms. Therefore, these algorithms will explained here briefly. The most basic competitive learning algorithm is WTA. When input vector (a pattern) is presented, a distance to each neuron's synaptic weights is calculated. The neuron whose weights are most correlated to current input vector is the winner. Correlation is equal to scalar product of input vector and considered synaptic weights. Only the winning neuron modifies it's synaptic weights to the point presented by input pattern. Synaptic weights of other neurons do not change. The learning process can be described by the following equation: