C++ Neural Networks and Fuzzy Logic: Preface

Network Choice and Layout

We will describe the use of a Hopfield network to attempt to solve the traveling salesperson problem. There

are n

2

 neurons in the network arranged in a two−dimensional array of n neurons per row and n per column.

The network is fully connected. The connections in the network in each row and in each column are lateral

connections. The layout of the neurons in the network with their connections is shown in Figure 15.1 for the

case of three cities, for illustration. To avoid cluttering, the connections between diagonally opposite neurons

are not shown.

Figure 15.1

  Layout of a Hopfield network for the traveling salesperson problem.

The most important task on hand then is finding an appropriate connection weight matrix. It is constructed

taking into account that nonvalid tours should be prevented and valid tours should be preferred. A

consideration in this regard is, for example, no two neurons in the same row (column) should fire in the same

cycle of operation of the network. As a consequence, the lateral connections should be for inhibition and not

for excitation.

In this context, the Kronecker delta function is used to facilitate simple notation. The Kronecker delta

function has two arguments, which are given usually as subscripts of the symbol ´. By definition ´

ik

 has value

1 if i = k, and 0 if i ` k. That is, the two subscripts should agree for the Kronecker delta to have value 1.

Otherwise, its value is 0.

We refer to the neurons with two subscripts, one for the city it refers to, and the other for the order of that city

in the tour. Therefore, an element of the weight matrix for a connection between two neurons needs to have

four subscripts, with a comma after two of the subscripts. An example is w

ik,lj

 referring to the weight on the

connection between the (ik) neuron and the (lj) neuron. The value of this weight is set as follows:

W

ik,lj

 = −A

1

´

il

(1−´

kj

)−A

2

´

kj

(1−´

kj

(1−´

il

)−A

3

−A

4

 d

il

(´

j, k+1

 + ´

j,k−1

)

C++ Neural Networks and Fuzzy Logic:Preface

Neural Network for Traveling Salesperson Problem

341

---

Here the negative signs indicate inhibition through the lateral connections in a row or column. The −A

3

 is a

term for global inhibition.

Inputs

The inputs to the network are chosen arbitrarily. If as a consequence of the choice of the inputs, the

activations work out to give outputs that add up to the number of cities, an initial solution for the problem, a

legal tour, will result. A problem may also arise that the network will get stuck at a local minimum. To avoid

such an occurrence, random noise can be added. Usually you take as the input at each neuron a constant times

the number of cities and adjust this adding a random number, which can differ for different neurons.