ECAI-2000 Conference Paper

[full paper]

A Kohonen-like Decomposition Method for the Traveling Salesman Problem - KNIES_DECOMPOSE

Necati Aras, I. Kuban Altinel, John Oommen

In this paper a new self-organizing map (SOM) called The Kohonen Network Incorporating Explicit Statistics (KNIES) is presented which is used to solve both the traveling salesman problem (KNIES_TSP) and the Hamiltonian path problem (KNIES_HPP). The primary difference between the SOM and the KNIES is the fact that every iteration in the training phase includes two distinct modules - the attracting module and the dispersing module. In the attracting module a subset of the neurons migrate towards the data point that has been presented to the network. This phase is essentially identical to the learning phase of the SOM. However, subsequent to this phase the rest of the neurons which have not been involved in the attracting module participate in a dispersing (repellent) migration. Indeed, these neurons now move away from their current positions in a manner that ensures that the global statistical properties of the data points are imitated by the neurons. Thus, although in the SOM the neurons asymptotically find their places both statistically and topologically, in the KNIES they collectively maintain their means to be the means of the data points which they represent. Solving large instances of the TSP via self-organizing map is time consuming (When the number of cities is larger than 100 for example). Decomposing the problem into subproblems is an intelligent approach to overcome this difficulty. The subproblems can be solved faster because the number of cities for each subproblem is much smaller than the original problem. Once the solutions to each subproblem are obtained they may be combined in an elegant way to find a solution for the original problem. The idea of decomposition is not new and was applied to solve large traveling salesman problems. What is new in this paper is that an all-neural decomposition approach is introduced meaning that all the steps of the approach are performed by neural networks.

Keywords: Neural networks, Self-organizing maps, Traveling salesman problem

Citation: Necati Aras, I. Kuban Altinel, John Oommen: A Kohonen-like Decomposition Method for the Traveling Salesman Problem - KNIES_DECOMPOSE. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.261-265.