112. | 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

Example of a Traveling Salesperson Problem for Hand Calculation

Suppose there are four cities in the tour. Call these cities, C₁, C₂, C₃, and C₄. Let the matrix of distances be the following matrix D.

            0   10   14    7      D =  10    0    6   12           14    6    0    9            7   12    9    0

From our earlier discussion on the number of valid and distinct tours, we infer that there are just three such tours. Since it is such a small number, we can afford to enumerate the three tours, find the energy values associated with them, and pick the tour that has the smallest energy level among the three. The three tours are:

• Tour 1. 1 - 2 - 3 - 4 - 1 In this tour city 2 is visited first, followed by city 3, from where the salesperson goes to city 4, and then returns to city 1. For city 2, the corresponding ordered array is (1, 0, 0, 0), because city 2 is the first in this permutation of cities. Then x₂₁ = 1, x₂₂ = 0, x₂₃ = 0, x₂₄ = 0. Also (0, 1, 0, 0), (0, 0, 1, 0), and (0, 0, 0, 1) correspond to cities 3, 4, and 1, respectively. The total distance of the tour is d₁₂ + d₂₃ + d₃₄ + d₄₁= 10 + 6 + 9 + 7 = 32.

• Tour 2. 1 - 3 - 4 - 2 - 1

• Tour 3. 1 - 4 - 2 - 3 - 1

There seems to be some discrepancy here. If there is one, we need an explanation. The discrepancy is that we can find many more tours that should be valid because no city is visited more than once. You may say they are distinct from the three previously listed. Some of these additional tours are:

• Tour 4. 1 - 2 - 4 - 3 - 1

• Tour 5. 3 - 2 - 4 - 1 - 3

• Tour 6. 2 - 1 - 4 - 3 - 2

There is no doubt that these three tours are distinct from the first set of three tours. And in each of these three tours, every city is visited exactly once, as required in the problem. So they are valid tours as well. Why did our formula give us 3 for the value of the number of possible valid tours, while we are able to find 6?

The answer lies in the fact that if two valid tours are symmetric and have the same energy level, because they have the same value for the total distance traveled in the tour, one of them is in a sense redundant, or one of them can be considered degenerate, using the terminology common to this context. As long as they are valid and give the same total distance, the two tours are not individually interesting, and any one of the two is enough to have. By simple inspection, you find the total distances for the six listed tours. They are 32 for tour 1, 32 also for tour 6, 45 for each of tours 2 and 4, and 39 for each of tours 3 and 5. Notice also that tour 6 is not very different from tour 1. Instead of starting at city 1 as in tour 1, if you start at city 2 and follow tour 1 from there in reverse order of visiting cities, you get tour 6. Therefore, the distance covered is the same for both these tours. You can find similar relationships for other pairs of tours that have the same total distance for the tour. Either by reversing the order of cities in a tour, or by making a circular permutation of the order of the cities in a tour, you get another tour with the same total distance. This way you can find tours. Thus, only three distinct total distances are possible, and among them 32 is the lowest. The tour 1 - 2 - 3 - 4 - 1 is the shortest and is an optimum solution for this traveling salesperson problem. There is an alternative optimum solution, namely tour 6, with 32 for the total length of the tour. The problem is to find an optimal tour, and not to find all optimal tours if more than one exist. That is the reason only three distinct tours are suggested by the formula for the number of distinct valid tours in this case.

The formula we used to get the number of valid and distinct tours to be 3 is based on the elimination of such symmetry. To clarify all this discussion, you should determine the energy levels of all your six tours identified earlier, hoping to find pairs of tours with identical energy levels.

Note that the first term on the right-hand side of the equation results in 0 for a valid tour, as this term is to ensure there is no more than a single 1 in each row. That is, in any summand in the first term, at least one of the factors, x_ik or x_ij, where k ≠ j has to be 0 for a valid tour. So all those summands are 0, making the first term itself 0. Similarly, the second term is 0 for a valid tour, because in any summand at least one of the factors, x_ki or x_ji, where k ≠ j has to be 0 for a valid tour. In all, exactly 4 of the 16 x’s are each 1, making the total of the x’s 4. This causes the third term to be 0 for a valid tour. These observations make it clear that it does not matter for valid tours, what values are assigned to the parameters A₁, A₂, and A₃. Assigning large values for these parameters would cause the energy levels, for tours that are not valid, to be much larger than the energy levels for valid tours. Thereby, these tours become unattractive for the solution of the traveling salesperson problem. Let us use the value 1/2 for the parameter A₄.

Let us demonstrate the calculation of the value for the last term in the equation for E, in the case of tour 1. Recall that the needed equation is

E = A₁ Σ_iΣ_k Σ_j≠k x_ikx_ij + A₂ Σ_iΣ_k Σ_j≠kx_kix_ji + A₃[( Σ_iΣ_kx_jk) - n]² + A₄Σ_k Σ_j≠kΣ_id_kjx_ki(x_j,i+1 + x_j,i-1)

The last term expands as given in the following calculation:

     A₄{ ^d12[^x12(^x23 +^x21) + ^x13(^x24 + ^x22) + ^x14(^x21 + ^x23)] +     ^d13[^x12(^x33 + ^x31) + ^x13(^x34 + ^x32) + ^x14(^x31 + ^x33)] +     ^d14[^x12(^x43 + ^x41) + ^x13(^x44 + ^x42) + ^x14(^x41 + ^x43)] +     ^d21[^x21(^x12 + ^x14) + ^x23(^x14 + ^x12) + ^x24(^x11 + ^x13)] +     ^d23[^x21(^x32 + ^x34) + ^x23(^x34 + ^x32) + ^x24(^x31 + ^x33)] +     ^d24[^x21(^x42 + ^x44) + ^x23(^x44 + ^x42) + ^x24(^x41 + ^x43)] +     ^d31[^x31(^x12 + ^x14) + ^x32(^x13 + ^x11) + ^x34(^x11 + ^x13)] +     ^d32[^x31(^x22 + ^x24) + ^x32(^x23 + ^x21) + ^x34(^x21 + ^x23)] +     ^d34[^x31(^x42 + ^x44) + ^x32(^x43 + ^x41) + ^x34(^x41 + ^x43)] +     ^d41[^x41(^x12 + ^x14) + ^x42(^x13 + ^x11) + ^x43(^x14 + ^x12)] +     ^d42[^x41(^x22 + ^x24) + ^x42(^x23 + ^x21) + ^x43(^x24 + ^x22)] +     ^d43[^x41(^x32 + ^x34) + ^x42(^x33 + ^x31) + ^x43(^x34 + ^x32)] }

When the respective values are substituted for the tour 1 - 2 - 3 - 4 - 1, the previous calculation becomes:

     1/2{10[0(0 + 1) + 0(0 + 0) + 1(1 + 0)] + 14[0(0 + 0) + 0(0 + 1) +     1(0 + 0)] +     7[0(1 + 0) + 0(0 + 0) + 1(0 + 1)] + 10[1(0 + 1) + 0(1 + 0) +     0(0 + 0)] +     6[1(1 + 0) + 0(0 + 1) + 0(0 + 0)] + 12[1(0 + 0) + 0(0 + 0) +     0(0 + 1)] +     14[0(0 + 1) + 1(0 + 0) + 0(0 + 0)] + 6[0(0 + 0) + 1(0 + 1) +     0(1 + 0)] +     9[0(0 + 0) + 1(1 + 0) + 0(0 + 1)] + 7[0(0 + 1) + 0(0 + 0) +     1(1 + 0)] +     12[0(0 + 0) + 0(0 + 1) + 1(0 + 0)] + 9[0(1 + 0) + 0(0 + 0) +     1(0 + 1)]}     = 1/2( 10 + 0 + 7 + 10 + 6 + 0 + 0 + 6 + 9 + 7 + 0 + 9)     = 1/2(64)     = 32

Table 15.1 contains the values we get for the fourth term on the right-hand side of the equation, and for E, with the six listed tours.

**Table 15.1** Energy Levels for Six of the Valid Tours

Tour #	Non-Zero x’s	Value for the Last Term	Energy Level	Comment
1	x₁₄, x₂₁, x₃₂, x₄₃	32	32	1 - 2 - 3 - 4 - 1 tour
2	x₁₄, x₂₃, x₃₁, x₄₂	45	45	1 - 3 - 4 - 2 - 1 tour
3	x₁₄, x₂₂, x₃₃, x₄₁	39	39	1 - 4 - 2 - 3 - 1 tour
4	x₁₄, x₂₁, x₃₃, x₄₂	45	45	1 - 2 - 4 - 3 - 1 tour
5	x₁₃, x₂₁, x₃₄, x₄₂	39	39	3 - 2 - 4 - 1 - 3 tour
6	x₁₁, x₂₄, x₃₃, x₄₂	32	32	2 - 1 - 4 - 3 - 2 tour

Table of Contents