C++ Neural Networks and Fuzzy Logic
C++ Neural Networks and Fuzzy Logic
Download 1.14 Mb. Pdf ko'rish
|
C neural networks and fuzzy logic
- Bu sahifa navigatsiya:
- objective
- nonlinear
- C++ Neural Networks and Fuzzy Logic by Valluru B. Rao MTBooks, IDG Books Worldwide, Inc. ISBN
- Table 15.1
- Network Choice and Layout
- Kronecker delta
|
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
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
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
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
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 Example of a Traveling Salesperson Problem for Hand Calculation 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 C++ Neural Networks and Fuzzy Logic:Preface Example of a Traveling Salesperson Problem for Hand Calculation 338
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
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
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 1 , A 2 , and A 3 . 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 4 . 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)] + C++ Neural Networks and Fuzzy Logic:Preface Example of a Traveling Salesperson Problem for Hand Calculation 339
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.
1x 14 , x 21 , x 32 , x
43 32321 − 2 − 3 − 4 − 1 tour 2x 14
23 , x
31 , x
42 45451 − 3 − 4 − 2 − 1 tour 3x 14
22 , x
33 , x
41 39391 − 4 − 2 − 3 − 1 tour 4x 14
21 , x
33 , x
42 45451 − 2 − 4 − 3 − 1 tour 5x 13
21 , x
34 , x
42 39393 − 2 − 4 − 1 − 3 tour 6x 11
24 , x
33 , x
42 32322 − 1 − 4 − 3 − 2 tour Previous Table of Contents Next Copyright © IDG Books Worldwide, Inc. C++ Neural Networks and Fuzzy Logic:Preface Example of a Traveling Salesperson Problem for Hand Calculation 340
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 Neural Network for Traveling Salesperson Problem Hopfield and Tank used a neural network to solve a traveling salesperson problem. The solution you get may not be optimal in certain instances. But by and large you may get a solution close to an optimal solution. One cannot find for the traveling salesperson problem a consistently efficient method of solution, as it has been proved to belong to a set of problems called NP−complete problems. NP−complete problems have the distinction that there is no known algorithm that is efficient and practical, and there is little likelihood that such an algorithm will be developed in the future. This is a caveat to keep in mind when using a neural network to solve a traveling salesperson problem. Network Choice and Layout We will describe the use of a Hopfield network to attempt to solve the traveling salesperson problem. There are n 2 neurons in the network arranged in a two−dimensional array of n neurons per row and n per column. The network is fully connected. The connections in the network in each row and in each column are lateral connections. The layout of the neurons in the network with their connections is shown in Figure 15.1 for the case of three cities, for illustration. To avoid cluttering, the connections between diagonally opposite neurons are not shown. Figure 15.1 Layout of a Hopfield network for the traveling salesperson problem. The most important task on hand then is finding an appropriate connection weight matrix. It is constructed taking into account that nonvalid tours should be prevented and valid tours should be preferred. A consideration in this regard is, for example, no two neurons in the same row (column) should fire in the same cycle of operation of the network. As a consequence, the lateral connections should be for inhibition and not for excitation. In this context, the Kronecker delta function is used to facilitate simple notation. The Kronecker delta function has two arguments, which are given usually as subscripts of the symbol ´. By definition ´
has value 1 if i = k, and 0 if i ` k. That is, the two subscripts should agree for the Kronecker delta to have value 1. Otherwise, its value is 0. We refer to the neurons with two subscripts, one for the city it refers to, and the other for the order of that city in the tour. Therefore, an element of the weight matrix for a connection between two neurons needs to have four subscripts, with a comma after two of the subscripts. An example is w ik,lj
referring to the weight on the connection between the (ik) neuron and the (lj) neuron. The value of this weight is set as follows: W ik,lj
= −A 1 ´ il (1−´
kj )−A
2 ´ kj (1−´ kj (1−´ il )−A
3 −A 4 d il (´ j, k+1 + ´
j,k−1 ) C++ Neural Networks and Fuzzy Logic:Preface Neural Network for Traveling Salesperson Problem 341
Here the negative signs indicate inhibition through the lateral connections in a row or column. The −A 3 is a term for global inhibition. Inputs The inputs to the network are chosen arbitrarily. If as a consequence of the choice of the inputs, the activations work out to give outputs that add up to the number of cities, an initial solution for the problem, a legal tour, will result. A problem may also arise that the network will get stuck at a local minimum. To avoid such an occurrence, random noise can be added. Usually you take as the input at each neuron a constant times the number of cities and adjust this adding a random number, which can differ for different neurons. Download 1.14 Mb. Do'stlaringiz bilan baham: 
|