C++ Neural Networks and Fuzzy Logic: Preface

Kohonen’s Approach for the Traveling Salesperson Problem

Kohonen’s self−organizing maps can be used for the traveling salesperson problem. We summarize the

discussion of this approach described in Eric Davalo’s and Patrick Naim’s work. Each city considered for the

tour is referenced by its x and y coordinates. To each city there corresponds a neuron. The neurons are placed

in a single array, unlike the two−dimensional array used in the Hopfield approach. The first and the last

neurons in the array are considered to be neighbors.

There is a weight vector for each neuron, and it also has two components. The weight vector of a neuron is the

image of the neuron in the map, which is sought to self−organize. There are as many input vectors as there are

cities, and the coordinate pair of a city constitutes an input vector. A neuron with a weight vector closest to the

input vector is selected. The weights of neurons in a neighborhood of the selected neuron are modified, others

are not. A gradually reducing scale factor is also used for the modification of weights.

One neuron is created first, and its weight vector has 0 for its components. Other neurons are created one at a

time, at each iteration of learning. Neurons may also be destroyed. The creation of the neuron and destruction

of the neuron suggest adding a city provisionally to the final list in the tour and dropping a city also

C++ Neural Networks and Fuzzy Logic:Preface

Other Approaches to Solve the Traveling Salesperson Problem

364

---

provisionally from that list. Thus the possibility of assigning any neuron to two inputs or two cities is

prevented. The same is true about assigning two neurons to the same input.

As the input vectors are presented to the network, if an unselected neuron falls in the neighborhood of the

closest twice, it is created. If a created neuron is not selected in three consecutive iterations for modification of

weights, along with others being modified, it is destroyed.

That a tour of shortest distance results from this network operation is apparent from the fact that the closest

neurons are selected. It is reported that experimental results are very promising. The computation time is

small, and solutions somewhat close to the optimal are obtained, if not the optimal solution itself. As was

before about the traveling salesperson problem, this is an NP−complete problem and near efficient (leading to

suboptimal solutions, but faster) approaches to it should be accepted.