C++ Neural Networks and Fuzzy Logic:Application to Nonlinear Optimization
Click Here! function GetCookie (name) { var arg = name + "="; var alen = arg.length; var clen = document.cookie.length; var i = 0; while (i < clen) { var j = i + alen; if (document.cookie.substring(i, j) == arg) { var end = document.cookie.indexOf (";", j); if (end == -1) end = document.cookie.length; return unescape(document.cookie.substring(j, end)); } i = document.cookie.indexOf(" ", i) + 1; if (i == 0) break; } return null; } var m1=''; var gifstr=GetCookie("UsrType"); if((gifstr!=0 ) && (gifstr!=null)) { m2=gifstr; } document.write(m1+m2+m3);           Keyword Title Author ISBN Publisher Imprint Brief Full  Advanced      Search  Search Tips Please Select ----------- Components Content Mgt Certification Databases Enterprise Mgt Fun/Games Groupware Hardware Intranet Dev Middleware Multimedia Networks OS Prod Apps Programming Security UI Web Services Webmaster Y2K ----------- New Titles ----------- Free Archive




To access the contents, click the chapter and section titles.


C++ Neural Networks and Fuzzy Logic


(Publisher: IDG Books Worldwide, Inc.)

Author(s): Valluru B. Rao

ISBN: 1558515526

Publication Date: 06/01/95










Search this book:
 





















Previous
Table of Contents
Next




Example of a Traveling Salesperson Problem for Hand Calculation
Suppose there are four cities in the tour. Call these cities, C1, C2, C3, and C4. 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 x21 = 1, x22 = 0, x23 = 0, x24 = 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 d12 + d23 + d34 + d41= 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, xik or xij, 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, xki or xji, 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 A1, A2, and A3. 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 A4.
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 = A1 ΣiΣk Σj≠k xikxij + A2 ΣiΣk Σj≠kxkixji + A3[( ΣiΣkxjk) - n]2 + A4Σk Σj≠kΣidkjxki(xj,i+1 + xj,i-1)
The last term expands as given in the following calculation:


A4{ 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
x14, x21, x32, x43
32
32
1 - 2 - 3 - 4 - 1 tour

2
x14, x23, x31, x42
45
45
1 - 3 - 4 - 2 - 1 tour

3
x14, x22, x33, x41
39
39
1 - 4 - 2 - 3 - 1 tour

4
x14, x21, x33, x42
45
45
1 - 2 - 4 - 3 - 1 tour

5
x13, x21, x34, x42
39
39
3 - 2 - 4 - 1 - 3 tour

6
x11, x24, x33, x42
32
32
2 - 1 - 4 - 3 - 2 tour








Previous
Table of Contents
Next






Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.