Hopfield net and Traveling Salesman problem

1. Hopfield net and Traveling Salesman problem

• We consider the problem for n=4 cities
• In the given figure, nodes represent cities
and edges represent the paths between
the cities with associated distance.
dCD
D
dDA
dAC
A
C
dBD
dAB
dBC
B

2. Traveling Salesman Problem

• Goal
– Come back to the city A, visiting j = 2 to n (n is
number of cities) exactly once and minimize
the total distance.
• To solve by Hopfield net we need to
decide the architecture:
– How many neurons?
– What are the weights?

3. Constraints decide the parameters

1. For n cities and n positions, establish city
to position correspondence, i.e.
Number of neurons = n cities * n positions
2. Each position can take one and only one
city
3. Each city can be in exactly one position
4. Total distance should be minimum

4. Architecture

• n * n matrix where
rows denote cities
and columns denote
positions
city(i)
• cell(i, j) = 1 if and only
if ith city is in jth
position
• Each cell is a neuron
• nr neurons, O(n4)
connections
pos(α)

5. Expressions corresponding to constraints

1. Each city in one and only one position i.e. a
row has a single 1.
A n
E1
xi xi
2 i 1, 1 1
Above equation partially ensures each row has
a single 1
xiα is I/O cost at the cell(i, α)

6. Expressions corresponding to constraints (contd.)

2. Each position has a single city
i.e. each column has at most single 1.
B n n n
E2 xi x j
2 1 i 1 j 1,i j

7. Expressions corresponding to constraints (contd.)

3. Each city must be in exactly one position
– i.e. Each position must have a city
– This can be ensured by exactly n 1’s in the matrix
– We want quadratic expression because the energy
expression of the Hopfield net is quadratic
C n n
2
E3 ( xi n)
2 i 1 1

8. Expressions corresponding to constraints (contd.)

• E1, E2, E3 ensure that each row has
exactly one 1 and each column has
exactly one 1
• If we minimize
E1 + E2 + E3
• Ensures a Hamiltonian circuit on the city
graph which is NP-complete problem

9. Expressions corresponding to constraints (contd.)

4. Minimum Distance traversed.
D n n
E4 [ dij xi ( x j ,( 1) x j ,( 1) )]
2 i 1 j 1, j i
dij = distance between city i and city j

10. Expressions corresponding to constraints (contd.)

• We minimize constraint energy
E E1 E2 E3 E4
n
A
E1
xi xi
2 i 1, 1 1
n
n
B n
E2
xi x j
2 1 i 1 j 1,i j
n
n
C
E3
( xi n) 2
2 i 1 1
D n n
E4 [ dij xi ( x j ,( 1) x j ,( 1) )]
2 i 1 j 1, j i

11. Expressions corresponding to constraints (contd.)

• We equate constraint energy:
EP = Enet
• Find the weights