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 |

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

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}*x*_{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}*x*_{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

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 |

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