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

Previous | Table of Contents | Next |

Suppose there are four cities in the tour. Call these cities, *C*_{1}, *C*_{2}, *C*_{3}, and *C*_{4}. 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*_{21}= 1,*x*_{22}= 0,*x*_{23}= 0,*x*_{24}= 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*_{12}+*d*_{23}+*d*_{34}+*d*_{41}= 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

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_{1} Σ_{i}Σ_{k} Σ_{j≠k} x_{ik}x_{ij} + A_{2} Σ_{i}Σ_{k} Σ_{j≠k}x_{ki}x_{ji} + A_{3}[( Σ_{i}Σ_{k}x_{jk}) - n]^{2} + A_{4}Σ_{k} Σ_{j≠k}Σ_{i}d_{kj}x_{ki}(x_{j,i+1} + x_{j,i-1})

The last term expands as given in the following calculation:

A_{4}{^{d}12[^{x}12(^{x}23 +^{x}21) +^{x}13(^{x}24 +^{x}22) +^{x}14(^{x}21 +^{x}23)] +^{d}13[^{x}12(^{x}33 +^{x}31) +^{x}13(^{x}34 +^{x}32) +^{x}14(^{x}31 +^{x}33)] +^{d}14[^{x}12(^{x}43 +^{x}41) +^{x}13(^{x}44 +^{x}42) +^{x}14(^{x}41 +^{x}43)] +^{d}21[^{x}21(^{x}12 +^{x}14) +^{x}23(^{x}14 +^{x}12) +^{x}24(^{x}11 +^{x}13)] +^{d}23[^{x}21(^{x}32 +^{x}34) +^{x}23(^{x}34 +^{x}32) +^{x}24(^{x}31 +^{x}33)] +^{d}24[^{x}21(^{x}42 +^{x}44) +^{x}23(^{x}44 +^{x}42) +^{x}24(^{x}41 +^{x}43)] +^{d}31[^{x}31(^{x}12 +^{x}14) +^{x}32(^{x}13 +^{x}11) +^{x}34(^{x}11 +^{x}13)] +^{d}32[^{x}31(^{x}22 +^{x}24) +^{x}32(^{x}23 +^{x}21) +^{x}34(^{x}21 +^{x}23)] +^{d}34[^{x}31(^{x}42 +^{x}44) +^{x}32(^{x}43 +^{x}41) +^{x}34(^{x}41 +^{x}43)] +^{d}41[^{x}41(^{x}12 +^{x}14) +^{x}42(^{x}13 +^{x}11) +^{x}43(^{x}14 +^{x}12)] +^{d}42[^{x}41(^{x}22 +^{x}24) +^{x}42(^{x}23 +^{x}21) +^{x}43(^{x}24 +^{x}22)] +^{d}43[^{x}41(^{x}32 +^{x}34) +^{x}42(^{x}33 +^{x}31) +^{x}43(^{x}34 +^{x}32)] }

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.

Tour # | Non-Zero x’s | Value for the Last Term | Energy Level | Comment |
---|---|---|---|---|

1 | x_{14}, x_{21}, x_{32}, x_{43} | 32 | 32 | 1 - 2 - 3 - 4 - 1 tour |

2 | x_{14}, x_{23}, x_{31}, x_{42} | 45 | 45 | 1 - 3 - 4 - 2 - 1 tour |

3 | x_{14}, x_{22}, x_{33}, x_{41} | 39 | 39 | 1 - 4 - 2 - 3 - 1 tour |

4 | x_{14}, x_{21}, x_{33}, x_{42} | 45 | 45 | 1 - 2 - 4 - 3 - 1 tour |

5 | x_{13}, x_{21}, x_{34}, x_{42} | 39 | 39 | 3 - 2 - 4 - 1 - 3 tour |

6 | x_{11}, x_{24}, x_{33}, x_{42} | 32 | 32 | 2 - 1 - 4 - 3 - 2 tour |

Previous | Table of Contents | Next |

Copyright © IDG Books Worldwide, Inc.

C++ Neural Networks and Fuzzy Logic

ISBN: 1558515526

EAN: 2147483647

EAN: 2147483647

Year: 1995

Pages: 139

Pages: 139

Authors: Valluru B. Rao, Hayagriva Rao

Similar book on Amazon

flylib.com © 2008-2017.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net