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

N N N

F c = 1
2

d i,k y i,j ( y k,j− 1 + y k,j +1 ) ,

i =1 j =1

k =1
k = i

where, by definition, y k, 0 = y k,N and y k,N +1 = y k, 1 .
It can be written in a simpler way as follows:

N N N

F c = 1
2

d i,k y i,j⊕ 1 .

i =1 j =1

k =1
k = i

In that equation, d i,k is the distance between cities i and k . The operator

⊕ is defined as follows:

For j<N,j ⊕ 1= j +1 , and N ⊕ 1=1 .

The term in the multiple sums is non-zero when city i is position j ,and
that term is equal to the distance of the journey between that city and the
next one on the tour. The output of the neuron ( i , j ) is therefore multiplied
by the outputs of the neurons of column j

1. Therefore, each neuron is
connected to 2 N neurons in the network. As a consequence, the encoding of
that cost function does not require N 4 connections, but N 3 .

⊕

8.6.4.6 Constraints

To guarantee that, after convergence, the matrix of neuron outputs is a per-
mutation matrix that guarantees the validity of the solution, some additional
constraints are defined. A penalty function is associated to their violation.
For a tour to be valid, each city must be visited exactly once. That requires
that, in each row, no two neurons have their outputs equal to 1. Therefore, the
following function is defined, such that it is non-zero if at least two neurons
have an output equal to 1 in a row:

N N N

F 1 = 1
2

y i,j y i,l .

i =1 j =1

l =1
l = j

Similarly, at each step on the tour, the traveling salesman cannot be in
more than one city. As a consequence, in each column, there no two neurons
have their outputs equal to 1 after convergence of the network. Therefore, the
following function is defined, such that it is non-zero if at least two neurons
have an output equal to 1 in a column:

N N N

F 2 = 1
2

y i,j y k,j .

i =1 j =1

k =1
k = i