111. | C++ Neural Networks and Fuzzy Logic

C++ Neural Networks and Fuzzy Logic
by Valluru B. Rao
M&T Books, IDG Books Worldwide, Inc.
ISBN: 1558515526 Pub Date: 06/01/95

Table of Contents

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₁, A₂, A₃, and A₄ 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₁ Σ_iΣ_k Σ_j≠kx_ikx_ij + A₂ Σ_i Σ_k x_iΣ_k Σ_j≠kx_kix_ji + A₃[( Σ_iΣ_kx_ik) - n]² + A₄Σ_k Σ_k Σ_j≠k Σ_id_kjx_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₁₂x₃₃ also as x₃₃x₁₂, 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₁₂x₁₂. Thus, the first term is an abbreviation for the sum of n²(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² 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.

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.

Table of Contents