C++ Neural Networks and Fuzzy Logic:Application to Nonlinear Optimization



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




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 A1, A2, A3, and A4 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 dij for the distance from city i to city j.
E = A1 ΣiΣk Σj≠kxikxij + A2 Σi Σk xiΣk Σj≠kxkixji + A3[( ΣiΣkxik) - n]2 + A4Σk Σk Σj≠k Σidkjxki(xj,i+1 + xj,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 x12x33 also as x33x12, 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 x12x12. Thus, the first term is an abbreviation for the sum of n2(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, xii 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 n2 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.



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.