|
C++ Neural Networks and Fuzzy Logic
by Valluru B. Rao
MTBooks, IDG Books Worldwide, Inc.
ISBN: 1558515526 Pub Date: 06/01/95
Previous Table of Contents Next
The cost of the tour is the total distance traveled, and it is to be minimized. The total distance traveled in the
tour is the sum of the distances from each city to the next. The objective function has one term that
corresponds to the total distance traveled in the tour. The other terms, one for each constraint, in the objective
function are expressions, each attaining a minimum value if and only if the corresponding constraint is
satisfied. The objective function then takes the following form. Hopfield and Tank formulated the problem as
one of minimizing energy. Thus it is, customary to refer to the value of the objective function of this problem,
while using Hopfield−like neural network for its solution, as the energy level, E, of the network. The goal is to
minimize this energy level.
In formulating the equation for E, one uses constant parameters A
1
, A
2
, A
3
, and A
4
as coefficients in different
terms of the expression on the right−hand side of the equation. The equation that defines E is given as follows.
Note that the notation in this equation includes d
ij
for the distance from city i to city j.
E = A
1
£
i
£
k
£
j`k
x
ik
x
ij
+ A
2
£
i
£
k
x
i
£
k
£
j`k
x
ki
x
ji
+ A
3
[( £
i
£
k
x
ik
) − n]
2
+ A
4
£
k
£
k
£
j`k
£
i
d
kj
x
ki
(x
j,i+1
+ x
j,i−1
)
Our first observation at this point is that E is a nonlinear function of the x’s, as you have quadratic terms in it.
So this formulation of the traveling salesperson problem renders it a nonlinear optimization problem.
All the summations indicated by the occurrences of the summation symbol £, range from 1 to n for the values
of their respective indices. This means that the same summand such as x
12
x
33
also as x
33
x
12
, appears twice
with only the factors interchanged in their order of occurrence in the summand. For this reason, many authors
use an additional factor of 1/2 for each term in the expression for E. However, when you minimize a quantity
z with a given set of values for the variables in the expression for z, the same values for these variables
minimize any whole or fractional multiple of z, as well.
The third summation in the first term is over the index j, from 1 to n, but excluding whatever value k has. This
prevents you from using something like x
12
x
12
. Thus, the first term is an abbreviation for the sum of n
2
(n – 1)
terms with no two factors in a summand equal. This term is included to correspond to the constraint that no
more than one neuron in the same row can output a 1. Thus, you get 0 for this term with a valid solution. This
is also true for the second term in the right−hand side of the equation for E. Note that for any value of the
index i, x
ii
has value 0, since you are not making a move like, from city i to the same city i in any of the tours
you consider as a solution to this problem. The third term in the expression for E has a minimum value of 0,
which is attained if and only if exactly n of the n
2
x’s have value 1 and the rest 0.
The last term expresses the goal of finding a tour with the least total distance traveled, indicating the shortest
tour among all possible tours for the traveling salesperson. Another important issue about the values of the
subscripts on the right−hand side of the equation for E is, what happens to i + 1, for example, when i is
already equal to n, and to i–1, when i is equal to 1. The i + 1 and i – 1 seem like impossible values, being out
of their allowed range from 1 to n. The trick is to replace these values with their moduli with respect to n. This
means, that the value n + 1 is replaced with 1, and the value 0 is replaced with n in the situations just
described.
C++ Neural Networks and Fuzzy Logic:Preface
Solution via Neural Network
336
Modular values are obtained as follows. If we want, say 13 modulo 5, we subtract 5 as many times as possible
from 13, until the remainder is a value between 0 and 4, 4 being 5 – 1. Since we can subtract 5 twice from 13
to get a remainder of 3, which is between 0 and 4, 3 is the value of 13 modulo 5. Thus (n + 3) modulo n is 3,
as previously noted. Another way of looking at these results is that 3 is 13 modulo 5 because, if you subtract 3
from 13, you get a number divisible by 5, or which has 5 as a factor. Subtracting 3 from n + 3 gives you n,
which has n as a factor. So 3 is (n + 3) modulo n. In the case of –1, by subtracting (n – 1) from it, we get −n,
which can be divided by n getting –1. So (n – 1) is the value of (–1) modulo n.
Previous Table of Contents Next
Copyright ©
IDG Books Worldwide, Inc.
C++ Neural Networks and Fuzzy Logic:Preface
Solution via Neural Network
337
Do'stlaringiz bilan baham: | 
