Neural Networks, Vol. 1, pp. 289-293, 1988
Printed in the USA, All rights reserved.
0893-6080/88 $3.00 +.00 Copyright 1988 Pergamon Press plc

ORIGINAL CONTRIBUTION

Self-Organizing Feature Maps and the Travelling Salesman Problem
BERNARD ANGI~NIOL, GAI~L DE LA CROIX VAUBOIS AND JEAN-YVES LE TEXIER Thomson CSF/DSE
(Received March 1988; revised and accepted May 1988)
AhstractwBased on Kohonen's work on self-organizing feature maps, we derive an algorithm for solving the classical Travelling Salesman Problem. Given a set of cities defined by their positions in the plane, an evolving population of cells, featuring dupfication and selection, iteratively organizes towards a quasi-optimal solution. Simulations on sequential machines have been carried out for problems with a thousand cities. The algorithm naturally lends itself to implementation on a network of interconnected, analog processing elements.
INTRODUCTION A vast amount of effort has already been dedicated to the study of supervised learning algorithms, such as the Boltzman Machine (Hinton, Sejnowski, & Acldey, 1984), and the Back-Propagation algorithm (Le Cun, 1987; Rumelhart, Hinton, & Williams, 1986). Less attention has as yet been devoted to the class of algorithms which do not require explicit tutoring by input-output correlations and which spontaneously self-organize upon presentation of input patterns. This whole area of research is highly promising and directly relates to the difficult problem of understanding the internal representation of information in the brain, in particular, how structures and internal organization can emerge from the collective behaviour of interconnected neuronlike elements (Linsker, 1986; vonder Malsburg, 1985). Self-organizing feature maps (Kohonen, 1984) offer such a paradigm, by setting up some general functional principles that could be responsible for the self-organization of widely different kinds of information. Kohonen shows how input signals of arbitrary dimensionality can be mapped, or adaptively projected, onto a structured set of processing units, in such a way that topological relations of the input patterns and of the representation patterns are kept similar. Algorithmically, his method can be seen as an extension of competitive learning (Rumelhart & Zipser, 1985), in which
clusters are given a topology organizing them into 2-D structures (such as trees, rectangular or hexagonal lattices) When, for a given pattern, the best matching unit is found, not only its own weights but the weights of its topological neighbours are modified to increase the strength of the match. Applications to various cognitive tasks have been demonstrated by Kohonen. We intend to show the potential of this approach for optimization problems as well, by applying it to the well-known Travelling Salesman Problem (TSP). PREVIOUS WORK ON TSP The TSP has received extensive attention as the basis of comparison for different optimization algorithms: it can be easily stated as a search for the shortest path passing once and only once through every city in a given set. The problem has been shown to be NP-complete. The traditional approach of operations research has proved very efficient with the Lin and Kernighan algorithm (1973), or with Padberg and Rinaldi (1987) for verified optima (Johnson, 1987). More recently, a new connectionist approach has arisen, starting with Hopfield's work (Hopfield and Tank 1985). An analogy with spin-#ass systems suggested to him that a network of totally interconnected, analog, neuron-like elements should relax towards the minimum of an energy function, which is a quadratic form of the neuron states. By stating an optimization problem as the minimization of a quadratic function, it is then possible to adjust connecting weights so that
Requests for reprints should be sent to Bernard Ang6niol, Thomson CSF/DSE, 1, rue des Mathurins, F-92223 Bagneux C6dex, France. We thank D. Tank, J. Hopfield, R. Durbin, and D. J. Willshaw for providing us the sets of cities we have used to evaluate our approach.
B. AngOniol. G. de La Croix Vaubois, and J- Y Le Texter
the relaxation of an analog network can solve the problem. Unfortunately, representing the TSP in this framework is extremely expensive, since the number of fully interconnected processors grows as the square of the number of cities increases: N 2 neurons connected through N 4 links Moreover, since the optimization problem is not solved in the problem space of cardinality N!, but in the representation space of cardinality 2N2, a great deal of the computing effort is spent in ruling out states which do not correspond to tours, and there is no guarantee that the network eventually converges to a path. On the same representation, Aarts and Korst (1987) proposed a network with a reduced connectivity of N 3 connections for N cities and N 2 neurons. They obtained near-optimum solutions, and the different paths through cities were always valid. With a radically different approach, Durbin and Willshaw (1987) designed an algorithm using an elastic net method, derived from the work ofvon der Malsburg (1985) on the tea-trade model. A circular closed path is gradually elongated non-uniformly until it eventually passes sufficiently near all the cities to define a tour. It can be implemented on a network with the number of analog cells proportional to N; simulations show very good performance. We present here another approach, based on the above mentioned work of Kohonen on self-organizing feature maps (1984) The algorithm scales well with problem size: it ran for a I000 city problem on a sequential machine, in a reasonable time (20 minutes for a = 0.2, see Fig. 5). We next give its description, along with a number of experimental results. A L G O R I T H M DESCRIPTION The Euclidean Travelling Salesman Problem consists in finding the shortest possible route or closed tour that visits each of a given set of M cities placed in the plane. An approximate tour in our approach is given by a set of nodes joined together in a one dimensional ring, evolving in a continuous manner towards the ultimate solution path This continuous representation is quite different from the one found in more traditional discrete

algorithms, where all intermediate tours being examined are paths through various permutations of cities, In our case, all nodes are freely moving in the plane through an iterative process; eventually, an actual tour will be obtained, when every city has "caught" one node of the ring. An intuitive view of the algorithm is as follows, An iteration step consists in the presentation of one city. The node closest to the city being presented moves towards it and induces its neighbors on the ring to do so as well, but with a decreasing intensity along the ring. This correlation between the motion of neighbor nodes intuitively leads to a minimization of the distance between two neighbors, hence giving a short tour. The nodes will progressively become independent from one another, and, eventually, each will attach to one city. The cities in our algorithm are numbered from 1 to M. Each city i is denoted by its two coordinates: (X~, x~). The nodes are numbered from t to N. Each node j on the ring is characterized by the two coordinates (c~, cj ) of the associated point in the plane. EaCh node is also related to its two neighbors in the ring; nodes j - ! (mod N) a n d j + 1 (mod N). At the beginning of the process, only one node exists which is located at point (0, 0) in the plane, The number of nodes, N, grows subsequently according to a node creation process (see below). At each processing step, a city i is surveyed. One complete iteration takes M sequential steps, for i = t to i = M, thus picking every city once in a fixed order. This order may be chosen at random before simulation starts and it is kept fixed during the whole relaxation process. Different initial orders lead to different solutions. A gain parameter is used which decreases between two complete iterations Several iterations are needed to go from the high gain value to the low one giving the final result. Surveying the city i comprises the following steps: Step 1: Find the node jc which is closest to:city i: for each node j, compute its potential: W = (x~ - c~)2 + (x~- c~)-'

-,~'~Tf-i\ ,-d,

FIGURE 1. Evol~ion of the dng on a set of 30 cities used by Tank and Hopfleid ( ~ ). The ~ Lin-Kernighan's, and h a p p e ~ with ~ 1.5 x 10-s f o r. -- 0.2.

here is the san-~ as

Self-Organizing Feature Maps

number of tries per cent

[ 15 10

~ : 0.2 bOOtries)

~ = 0.02 (2,400 tries)

4.4 4.5 T o u r length

FIGURE 2. Two histograms showing how often each value of tour length was obtained for the 30 city problem, in 20,000 tries for parameter a = 0.2, and in 2,400 tries for a = 0.02. Each try corresponds to a random but fixed order of cities for all surveys during one simulation. The lowest, largest, and average lengths obtained are indicated. ~ = 0.2 gives an average length of 4.30 and reaches the optimal length 4.267 (from the Lin-Kernighan tour) with probability 1.-a (31 times in 20,000 tries). Each try takes less than 2 seconds on an Apollo workstation. The average value obtained after 10 tries is 4.31 (.), only 1 % off optimum, a = 0.02 gives a better average of 4.36, but never reaches optimum, and each simulation lasts ten times longer than with a = 0.2. Lower values of a do not enhance performances.

and determine jc by competition: ~ = rnin~.
Step 2." Move node Jc and its neighbors on the ring towards city i. The distance each node will move is determined by a functionf(G, n), where G is the gain parameter, and n is the distance measured along the ring between nodes j and j,.:
n = inf(j - L (rood N), L - J (mod N)). Every node j is moved from its position (c{, cg) to a new one:
a is the only parameter that has to be adjusted. It is directly related to the number of complete surveys needed to attain the result, hence to its quality. The gain is decreased from a high initial Gi which ensures large moves for all nodes at each iteration step to a sufficiently low G for which the network is stabilized. The total number of iterations can be computed from these two fixed values depending only on M.

Creation of nodes

CJk~ C~ +f(G, n).(xi, - c~).
The function f i s defined to be:
f(G, n) = (I / 1[-2).exp(-n2/G ~).
This means: - - w h e n G --* oo, all nodes move towards city i with the same strength (1/V2). - - w h e n G --* 0, only node jc moves towards city i. Decreasing the gain at the end of a complete survey is done by: G.~--(l - a).G.
A node is duplicated, if it is chosen as the winner for two different cities in the same complete survey. The newly created node is inserted into the ring as a neighbour of the winner, and with the same coordinates in the plane. Both the winner and the created node are inhibited. If chosen by a city, an inhibited node will induce no movement at all in the network for this city presentation. It is re-enabled on the next presentation. This guarantees that the "twin nodes" will be separated by the moves of their neighbors, before being "caught" by cities. The maximum number of nodes created on the ring experimentally appears to be less than twice the number of cities.
TABLE 1 Resulting lengths on five different sets of 50 randomly distributed cities in a square (Durbin and Willshaw, 1987). a m B e s t values reported by Durbin and Willshaw. b m T h e results obtained with their elastic net method, c ~ T h e best tour we found with our self-organization method, and the number of times it was obtained in 4,000 tries, d ~ T h e average lowest length obtained in ten tries with a = 0.2. e ~ A v e r a g e length in one try with a = 0.2. f ~ A v e r e g e with a = 0.02. Slightly better average are obtained for even lower a.

a - - A l l Other Algorithms

5.84 5.99

b--Elastic Net Method

5.98 6.09

c - - B e s t Selforganization

5.8361 5.10

d - - T e n Tries a = 0.2

e--Average ~ = 0.2

f--Average a = 0.02

5.99 6.18

5.57 5.70 6.17

5.70 5.86 6.49

5.575 [ 5.596 I 6.1941

6.07 5.69 5.72 6.52

6.25 5.83 5.87 6.70

5.77 5.96 6.58

B. Ang~niol, G. de La Croix Vaubois, and.L Y Le Texier

"\

~;--"-T ~.
FIGURE 3. The best solution found on the five sets of 50 cities (Table lc).
Deletion of nodes A node is deleted, if it has not been chosen as the winner by any city during three complete surveys. In our simulations this creation-deletion mechanism has proved particularly important to the attainment of near-optimum solutions. SIMULATION RESULTS We performed simulations on small sets o f cities taken from Tank and Hopfield (1985) and from Durbin and Willshaw (1987). The algorithm described above is the result of several variations on a basic idea derived from Kohonen's self organization principles (1984). The one we propose gives satisfactory solutions in all cases. Only the parameter a characterizing gain decrease has to be adjusted, and the results obtained are not particularly sensitive to it. Unlike simulated annealing with temperature decrease, there is no need to use very low values o f a, as no better solution would be obtained. Figure 2 shows two representative histograms of tour lengths obtained with different initial permutations of the 30 cities used by Tank and Hopfield (see Figure 1). It demonstrates that a low value of the parameter gives a better average, but a high value has the advantage that the optimum is sometimes reached; it also gives a
good solution in several tries in less time than one try with a low value of a. In either case, a good average solution (less than 3% greater than optimum) may be obtained in 2 seconds on classical hardware. We compared our self organization method with the elastic net method presented by Durbin and Willshaw. The results are displayed in Table 1 for their five sets of 50 cities (Figure 3) and show similar characteristics to those above. On the average, our approach is equivalent. However, the possibility of starting with a random order of the cities gives us some chance of getting better results. Two particular cases involving known optima with larger numbers of cities have helped us in our preliminary evaluation. They are given in Figure 4. A solution found by our algorithm for a set of 1000 cities is presented in Figure 5.

CONCLUSION Our approach to optimization problems through self-organizing feature-maps appears very promising due to the following features. First, the total number of nodes and connections in a connectionist parallel implementation will be proportional only to the number of cities in the problem, thus scaling very well with problem size: hardware based on analog technology, in
FIGURE 4. Two particulady visual cases show the conrect behaviour of ~

and ~ : 0.002.

a l g m l t h m. T h e y were obtained ~

with a = 0,!

S e l f Organizing Feature Maps
FIGURE 5. A set of 1000 randomly distributed cities. The solution proposed here was obtained with ~ = 0.01, to ensure a good result in one try (path length = 18,036 in a 1,000 x 500 rectangle). It took 12 hours. Simulations with a = 0.2 take 20 minutes and also give good results (lengths ranging from 18,200 to 18,800).
a way similar to previous proposals (Hopfield, 1985), could efficiently h a n d l e a large n u m b e r o f cities or variables. Second, only one parameter, which directly controis the total n u m b e r o f iterations, has to be tuned. Finally, typical values o f this p a r a m e t e r ensure a good, n e a r - o p t i m u m solution in a reasonable t i m e for the simulations we made. Theoretical work is now necessary to s u p p o r t these e x p e r i m e n t a l results, to provide a f o u n d a t i o n for further developments. We plan to generalize this m e t h o d to other o p t i m i z a t i o n p r o b l e m s b y varying the organizing topology.

REFERENCES

CS-84-119). Department of computer science, Carnegie-mellon University. Hopfield, J. J., & Tank, D. (1985). "Neural" computation of decisions in optimization problems. Biological Cybernetics. 5, 14 l - 152. Johnson, D. (1987). More approaches to the travellingsalesman guide. Nature 330, 525. Kohonen, T. (1984). Self-organization and associative memory. Berlin: Springer-Verlag. Le Curt, Y. (1987). Mod~les connexionnistes de l'apprentissage. Th~se de doctorat de l'Universit6 Paris 6. Lin, S., & Kernighan, B. W. (1973). An effectiveheuristic algorithm for the travelling-salesmanproblem. Operations Research 21,498516. Linsker, R. (1987). Towards an organizing principle for perception:
the role of Hebbian synapses in the emergence offeature-analysing function. Communication at the IEEE Conference on "Neural

Aarts, E., & Korst, J. (1987). Boltzmann machines and their applications. In J. W. de Bakker, A. J. Nijman, & E C. Treleaven (Eds.), Parallel architectures and languages europe, Lecture Notes in Computer Science, (Vol. 1) 258, Berlin: Springer-Verlag. Durbin, R., & Willshaw, D. (1987). An analogue approach to the travelling salesman problem using an elastic net method. Nature 326, 689-691. Hinton, G., Sejnowski, T., & Ackley, D. H. (1984). Boltzman Machines: constraint satisfaction networks that learn (Tech. rep. CMU-
information processing systems--Natural and Synthetic", Denver, CO. yon der Marlsburg, Ch. (1985). In Demongeot (Eds.), Dynamical systems and cellular automata. London: Academic Press. Padberg, M., & Rinaldi, G. 0987). Operations Research Letters, 6, 1-8. Rumelhart, D., & Zipser, D. (1985). Competitive learning. Cognitive science, 9, 75-112. Rumelhart, D., Hinton, G., & Williams, R. (1986). Learning internal representations by back-propagating errors. Nature 323, 533-536.