Neural Networks without Training for Optimization - Neural Networks: Methodology and Applications - page 471

Table 8.1. Valid solution for a TSP with 5 cities

12345

ityA00100
ityB10000
ityC01000
ityD00010
ityE00001

8.6.4.4 Example of Hopfield Neural Network to Solve the TSP

To illustrate the previous methodology with a concrete example, we will detail
the resolution of a traveling salesman problem, proposed by Hopfield and Tank
in 1985 [Hopfield et al. 1985]. This resolution is not the most e cient one, as
we will se later, but it has an educational interest.

Step 1: Encoding the Problem

The first step consists in mathematically reformulating the problem, in order
to solve it with a neural network.
A problem solution, i.e., a tour of the different cities, can be encoded as a
permutation matrix, i.e., a square matrix with binary elements, which contains
exactly one 1 in each row and in each column. In other words, given N cities,
a tour is represented by a ( N,N ) having N 2 elements. In that matrix, a row
represents a city, and a column the position of a city in the tour. Therefore,
a feasible tour is represented by a permutation matrix that has exactly N 1s
and N 2 N 0s. Table 8.1 shows an example of a matrix encoding a feasible

solution to a problem with 5 cities.
The corresponding solution is a tour in which the cities A, B, C, D and E
are visited in the following order: B-C-A-D-E-B.
A neuron is associated to each matrix coe cient. Therefore, that encoding
makes use of N 2 neurons and N 4 connections between the neurons. We will
denote by y i,j the output of the neuron ( i , j ) corresponding to the i -th row
and to the j -th column, and v i,j its potential. Moreover, the distances between
any pair of cities are known a priori: d ij

−

represents the distance between city

i and city j .

Step 2: Defining the Network Energy

8.6.4.5 Cost Function

The cost function to be minimized is the length of the journey performed
during the round. It can be expressed as a function of the outputs of the N
neurons that are equal to 1 in the permutation matrix. Mathematically, it is
given by