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:
- tourcity 1 tour order 2
- Output for a Four−City Problem
- C++ Neural Networks and Fuzzy Logic by Valluru B. Rao MTBooks, IDG Books Worldwide, Inc. ISBN
- global inhibition term
- Kohonen’s Approach for the Traveling Salesperson Problem
- Algorithm for Kohonen’s Approach
- squashing
- Gaussian density
|
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 Output from Your C++ Program for the Traveling Salesperson Problem A three−city tour problem is trivial, since there is just one value for the total distance no matter how you permute the cities for the order of the tour. In this case the natural order is itself an optimal solution. The program is run for two cases, for illustration. The first run is for a problem with four cities. The second one is for a five−city problem. By the way, the cities are numbered from 0 to n – 1. The same parameter values are used in the two runs. The number of cities, and consequently, the matrix of distances were different. In the first run, the number of iterations asked for is 30, and in the second run it is 40. The solution you get for the four−city problem is not the one in natural order. The total distance of the tour is 32. The tour in the solution is 1 − 0 − 3 − 2 − 1. This tour is equivalent to the tour in natural order, as you can see by starting at 0 and reading cyclically right to left in the previous sequence of cities. The solution you get for the five−city problem is the tour 1 − 2 − 0 − 4 − 3 − 1. This reads, starting from 0 as either 0 − 4 − 3 − 1 − 2 − 0, or as 0 − 2 − 1 − 3 − 4 − 0. It is different from the tour in natural order. It has a total distance of 73, as compared to the distance of 84 with the natural order. It is not optimal though, as a tour of shortest distance is 0 − 4 − 2 − 1 − 3 − 0 with total distance 50. Can the program give you the shorter tour? Yes, the solution can be different if you run the program again because each time you run the program, the input vector is different, as it is chosen at random. The parameter values given in the program are by guess. Note that the seed for the random number generator is given in the statement srand ((unsigned)time(NULL)); The program gives you the order in the tour for each city. For example, if it says tourcity 1 tour order 2, that means the second (tour) city is the city visited third (in tour order). Your tour orders are also with values from 0 to n – 1, like the cities. The user input is in italic, and computer output is normal, as you have seen before.
Please type number of cities, number of iterations 4 30 0.097 0.0585 0.053 0.078 //input vector—there are 16 neurons in the network 0.0725 0.0535 0.0585 0.0985 0.0505 0.061 0.0735 0.057 0.0555 0.075 0.0885 0.0925 type distance (integer) from city 0 to city 1 C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 355
10 type distance (integer) from city 0 to city 2 14 type distance (integer) from city 0 to city 3 7 type distance (integer) from city 1 to city 2 6 type distance (integer) from city 1 to city 3 12 type distance (integer) from city 2 to city 3 9 Distance Matrix 0 10 14 7 10 0 6 12 14 6 0 9 7 12 9 0 Weight Matrix //16x16 matrix of weights. There are 16 neurons in the network. −30 −70 −70 −70 −70 −630 −30 −630 −70 −870 −30 −70 −30 −70 −70 −630 −70 −30 −70 −70 −630 −70 −630 −30 −870 −70 −870 −70 −70 −30 −70 −30 −70 −70 −30 −70 −30 −630 −70 −630 −30 −870 −70 −70 −70 −70 −30 −630 −70 −70 −70 −30 −630 −30 −630 −70 −870 −30 −870 −70 −630 −30 −630 −30 −70 −630 −30 −630 −30 −70 −70 −70 −70 −390 −30 −630 −70 −630 −30 −70 −630 −70 −630 −30 −70 −30 −70 −70 −390 −70 −390 −30 −630 −70 −630 −70 −30 −630 −70 −630 −70 −70 −30 −70 −30 −390 −70 −630 −30 −630 −70 −70 −630 −30 −630 −70 −70 −70 −70 −30 −390 −30 −390 −70 −870 −30 −870 −70 C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 356
−70 −870 −30 −870 −70 −390 −30 −390 −30 −70 −70 −870 −70 −870 −30 −390 −870 −70 −870 −30 −390 −70 −390 −30 −70 −30 −70 −30 −870 −70 −870 −30 −30 −870 −70 −870 −30 −390 −70 −390 −70 −70 −30 −870 −30 −870 −70 −390 −870 −30 −870 −70 −390 −30 −390 −70 −70 −70 −70 −70 −450 −30 −450 −70 −70 −450 −30 −450 −70 −750 −30 −750 −70 −570 −30 −450 −70 −450 −30 −750 −450 −70 −450 −30 −750 −70 −750 −30 −570 −70 −570 −30 −450 −70 −450 −30 −30 −450 −70 −450 −30 −750 −70 −750 −30 −570 −70 −450 −30 −450 −70 −750 −450 −30 −450 −70 −750 −30 −750 −70 −570 −30 −570 −70 −70 −70 −70 −30 initial activations the activations: −333.680054 −215.280014 −182.320023 −371.280029 −255.199997 −207.580002 −205.920013 −425.519989 −258.560028 −290.360016 −376.320007 −228.000031 −278.609985 −363 −444.27005 −377.400024 the outputs 0.017913 0.070217 0.100848 0.011483 0.044685 0.076494 0.077913 0.006022 0.042995 0.029762 0.010816 0.060882 0.034115 0.012667 0.004815 0.010678 30 iterations completed the activations: −222.586884 −176.979172 −195.530823 −380.166107 −164.0271 −171.654053 −214.053177 −421.249023 −158.297867 −218.833755 −319.384827 −245.097473 −194.550751 −317.505554 −437.527283 −447.651581 C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 357
the outputs 0.064704 0.10681 0.087355 0.010333 0.122569 0.113061 0.071184 0.006337 0.130157 0.067483 0.021194 0.050156 0.088297 0.021667 0.005218 0.004624 tourcity 0 tour order 1 tourcity 1 tour order 0 tourcity 2 tour order 3 tourcity 3 tour order 2 the tour : 1 0
2 distance of tour is : 32 Previous Table of Contents Next Copyright © IDG Books Worldwide, Inc. C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 358
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 Output for a Five−City Problem Please type number of cities, number of iterations 5 40 0.0645 0.069 0.0595 0.0615 0.0825 //input vector—there are 25 neurons in the network 0.074 0.0865 0.056 0.095 0.06 0.0625 0.0685 0.099 0.0645 0.0615 0.056 0.099 0.065 0.093 0.051 0.0675 0.094 0.0595 0.0635 0.0515 type distance (integer) from city 0 to city 1 10 type distance (integer) from city 0 to city 2 14 type distance (integer) from city 0 to city 3 7 type distance (integer) from city 0 to city 4 6 type distance (integer) from city 1 to city 2 12 type distance (integer) from city 1 to city 3 9 type distance (integer) from city 1 to city 4 18 type distance (integer) from city 2 to city 3 24 type distance (integer) from city 2 to city 4 16 type distance (integer) from city 3 to city 4 32 Distance Matrix 0 10 14 7 6 10 0 12 9 18 14 12 0 24 16 7 9 24 0 32 6 18 16 32 0 Weight Matrix //25x25 matrix of weights. There are 25 neurons in the network. −30 −70 −70 −70 −70 −70 −630 −30 −30 −630 −70 −70 −30 −70 −70 −70 −630 −70 −630 −30 −30 −870 −70 −70 −30 C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 359
−70 −30 −70 −70 −70 −630 −70 −630 −30 −30 −870 −70 −70 −30 −70 −70 −30 −630 −70 −630 −30 −30 −70 −70 −70 −70 −70 −30 −70 −70 −30 −630 −70 −630 −30 −30 −70 −70 −70 −30 −70 −30 −30 −630 −70 −630 −30 −70 −70 −70 −70 −70 −70 −30 −70 −30 −30 −630 −70 −630 −30 −70 −70 −70 −70 −30 −630 −30 −30 −630 −70 −870 −70 −630 −30 −70 −70 −70 −70 −30 −630 −30 −30 −630 −70 −870 −70 −630 −30 −30 −630 −30 −70 −70 −70 −70 −70 −630 −70 −630 −70 −630 −30 −30 −630 −30 −70 −70 −70 −70 −70 −630 −70 −630 −30 −30 −70 −30 −70 −70 −70 −750 −30 −630 −70 −630 −70 −630 −30 −30 −70 −30 −70 −70 −70 −750 −30 −630 −70 −630 −30 −70 −70 −30 −70 −70 −30 −30 −30 −630 −30 −630 −70 −630 −30 −70 −70 −30 −70 −70 −30 −30 −30 −630 −70 −630 −70 −70 −70 −30 −70 −30 −630 −30 −30 −30 −30 −630 −70 −630 −70 −70 −70 −30 −70 −30 −630 −30 −30 −630 −70 −70 −70 −70 −70 −30 −750 −70 −870 −30 −630 −30 −30 −630 −70 −70 −70 −70 −70 −30 −750 −70 −870 −30 −30 −870 −70 −750 −30 −30 −750 −30 −870 −70 −870 −70 −870 −30 −30 −870 −70 −750 −30 −30 −750 −30 −870 −70 −870 −30 −30 −750 −70 −750 −30 −30 −70 −30 −870 −70 −870 −70 −870 −30 −30 C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 360
−750 −70 −750 −30 −30 −70 −30 −870 −70 −870 −30 −30 −750 −70 −750 −30 −70 −30 −30 −870 −30 −870 −70 −870 −30 −30 −750 −70 −750 −30 −70 −30 −30 −870 −70 −870 −30 −30 −750 −70 −750 −70 −870 −30 −30 −30 −30 −870 −70 −870 −30 −30 −750 −70 −750 −70 −870 −30 −30 −870 −70 −750 −30 −30 −750 −70 −70 −70 −450 −30 −870 −30 −30 −870 −70 −750 −30 −30 −750 −70 −70 −70 −450 −30 −30 −450 −70 −570 −30 −30 −570 −70 −450 −70 −450 −70 −450 −30 −30 −450 −70 −570 −30 −30 −570 −70 −450 −70 −450 −30 −30 −570 −70 −570 −30 −30 −1470 −30 −450 −70 −450 −70 −450 −30 −30 −570 −70 −570 −30 −30 −1470 −30 −450 −70 −450 −30 −30 −570 −70 −570 −30 −30 −30 −30 −450 −30 −450 −70 −450 −30 −30 −570 −70 −570 −30 −30 −30 −30 −450 −70 −450 −30 −30 −570 −70 −570 −30 −450 −30 −30 −30 −30 −450 −70 −450 −30 −30 −570 −70 −570 −30 −450 −30 −30 −450 −70 −570 −30 −30 −570 −70 −1470 −70 −390 −30 −450 −30 −30 −450 −70 −570 −30 −30 −570 −70 −1470 −70 −390 −30 −30 −390 −70 −1110 −30 −30 −1110 −70 −390 −70 −390 −70 −390 −30 −30 −390 −70 −1110 −30 −30 −1110 −70 −390 −70 −390 −30 −30 −1110 −70 −1110 −30 −30 −990 −30 −390 −70 −390 −70 −390 −30 −30 −1110 −70 −1110 −30 −30 −990 −30 −390 −70 −390 C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 361
−30 −30 −1110 −70 −1110 −30 −30 −30 −30 −390 −30 −390 −70 −390 −30 −30 −1110 −70 −1110 −30 −30 −30 −30 −390 −70 −390 −30 −30 −1110 −70 −1110 −30 −390 −30 −30 −30 −30 −390 −70 −390 −30 −30 −1110 −70 −1110 −30 −390 −30 −30 −390 −70 −1110 −30 −30 −1110 −70 −990 −30 −30 −990 −390 −30 −30 −390 −70 −1110 −30 −30 −1110 −70 −990 −30 −30 −990 −70 −1950 −30 −30 −1950 −70 −70 −70 −70 −70 −30 initial activations the activations: −290.894989 −311.190002 −218.365005 −309.344971 −467.774994 −366.299957 −421.254944 −232.399963 −489.249969 −467.399994 −504.375 −552.794983 −798.929871 −496.005005 −424.964935 −374.639984 −654.389832 −336.049988 −612.870056 −405.450012 −544.724976 −751.060059 −418.285034 −545.465027 −500.065063 the outputs 0.029577 0.023333 0.067838 0.023843 0.003636 0.012181 0.006337 0.057932 0.002812 0.003652 0.002346 0.001314 6.859939e−05 0.002594 0.006062 0.011034 0.000389 0.017419 0.000639 0.00765 0.001447 0.000122 0.006565 0.001434 0.002471 40 iterations completed the activations: −117.115494 −140.58519 −85.636215 −158.240143 −275.021301 −229.135956 −341.123871 −288.208496 −536.142212 −596.154297 −297.832794 −379.722595 −593.842102 −440.377625 −442.091064 −209.226883 −447.291016 −283.609589 −519.441101 −430.469696 −338.93219 −543.509766 −386.950531 −538.633606 −574.604492 the outputs 0.196963 0.156168 0.263543 0.130235 0.035562 0.060107 0.016407 0.030516 0.001604 0.000781 0.027279 0.010388 0.000803 0.005044 0.004942 0.07511 0.004644 0.032192 0.001959 0.005677 0.016837 0.001468 0.009533 0.001557 0.001012 tourcity 0 tour order 2 tourcity 1 tour order 0 tourcity 2 tour order 1 tourcity 3 tour order 4 tourcity 4 tour order 3 C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 362
the tour : 1 2 0 4 3 distance of tour is : 73 Previous Table of Contents Next Copyright © IDG Books Worldwide, Inc. C++ Neural Networks and Fuzzy Logic:Preface Output from Your C++ Program for the Traveling Salesperson Problem 363
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 Other Approaches to Solve the Traveling Salesperson Problem The following describes a few other methods for solving the traveling salesperson problem. Anzai’s Presentation Yuichiro Anzai describes the Hopfield network for the traveling salesperson problem in a slightly different way. For one thing, a global inhibition term is not used. A threshold value is associated with each neuron, added to the activation, and taken as the average of A 1 and A 2 , using our earlier notation. The energy function is formulated slightly differently, as follows: E = A
1 £ 1 (£ k x ik −1)
2 + A
2 £ i (£ k x ki −1)
2 + A
4 £ k £ j`k
£ i`k
d kj x ki (x j,i+1 + x j,i−1
) The first term is 0 if the sum of the outputs is 1 in each column. The same is true for the second term with regard to rows. The output is calculated using a parameter », here called the reference activation level, as: x ij
ij /»))/2
The parameters used are A 1 = 1/2, A 2 = 1/2, A 4 = 1/2, ”t = 1, Ä = 1, and » = 1. An attempt is made to solve the problem for a tour of 10 cities. The solution obtained is not crisp, in the sense that exactly one 1 occurs in each row and each column, there are values of varying magnitude with one dominating value in each row and column. The prominent value is considered to be part of the solution.
Kohonen’s self−organizing maps can be used for the traveling salesperson problem. We summarize the discussion of this approach described in Eric Davalo’s and Patrick Naim’s work. Each city considered for the tour is referenced by its x and y coordinates. To each city there corresponds a neuron. The neurons are placed in a single array, unlike the two−dimensional array used in the Hopfield approach. The first and the last neurons in the array are considered to be neighbors. There is a weight vector for each neuron, and it also has two components. The weight vector of a neuron is the image of the neuron in the map, which is sought to self−organize. There are as many input vectors as there are cities, and the coordinate pair of a city constitutes an input vector. A neuron with a weight vector closest to the input vector is selected. The weights of neurons in a neighborhood of the selected neuron are modified, others are not. A gradually reducing scale factor is also used for the modification of weights. One neuron is created first, and its weight vector has 0 for its components. Other neurons are created one at a time, at each iteration of learning. Neurons may also be destroyed. The creation of the neuron and destruction of the neuron suggest adding a city provisionally to the final list in the tour and dropping a city also C++ Neural Networks and Fuzzy Logic:Preface Other Approaches to Solve the Traveling Salesperson Problem 364
provisionally from that list. Thus the possibility of assigning any neuron to two inputs or two cities is prevented. The same is true about assigning two neurons to the same input. As the input vectors are presented to the network, if an unselected neuron falls in the neighborhood of the closest twice, it is created. If a created neuron is not selected in three consecutive iterations for modification of weights, along with others being modified, it is destroyed. That a tour of shortest distance results from this network operation is apparent from the fact that the closest neurons are selected. It is reported that experimental results are very promising. The computation time is small, and solutions somewhat close to the optimal are obtained, if not the optimal solution itself. As was before about the traveling salesperson problem, this is an NP−complete problem and near efficient (leading to suboptimal solutions, but faster) approaches to it should be accepted. Algorithm for Kohonen’s Approach A gain parameter » and a scale factor q are used while modifying the weights. A value between 0.02 and 0.2 was tried in previous examples for q. A distance of a neuron from the selected neuron is defined to be an integer between 0 and n – 1, where n is the number of cities for the tour. This means that these distances are not necessarily the actual distances between the cities. They could be made representative of the actual distances in some way. One such attempt is described in the following discussion on C++ implementation. This distance is denoted by d
for neuron j. A squashing function similar to the Gaussian density function is also used. The details of the algorithm are in a paper referenced in Davalo. The steps of the algorithm to the extent given by Davalo are:
w jnew = w jold
+ (l new
− w jold
)g(»,d j ), where g(»,dj) = exp(− dj 2 /») /
• Reset » as » (1 − q) Previous Table of Contents Next Copyright © IDG Books Worldwide, Inc. C++ Neural Networks and Fuzzy Logic:Preface Other Approaches to Solve the Traveling Salesperson Problem 365
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 C++ Implementation of Kohonen’s Approach Our C++ implementation of this algorithm (described above) is with small modifications. We create but do not destroy neurons explicitly. That is, we do not count the number of consecutive iterations in which a neuron is not selected for modification of weights. This is a consequence of our not defining a neighborhood of a neuron. Our example is for a problem with five neurons, for illustration, and because of the small number of neurons involved, the entire set is considered a neighborhood of each neuron. When all but one neuron are created, the remaining neuron is created without any more work with the algorithm, and it is assigned to the input, which isn’t corresponded yet to a neuron. After creating n – 1 neurons, only one unassigned input should remain. In our C++ implementation, the distance matrix for the distances between neurons, in our example, is given as follows, following the stipulation in the algorithm that these values should be integers between 0 and n – 1. 0 1 2 3 4 1 0 1 2 3
3 2 1 0 1 4 3 2 1 0 We also ran the program by replacing the previous matrix with the following matrix and obtained the same solution. The actual distances between the cities are about four times the corresponding values in this matrix, more or less. We have not included the output from this second run of the program. 0 1 3 3 2 1 0 3 2 1 d = 3 3 0 4 2 3 2 4 0 1 2 1 2 1 0 In our implementation, we picked a function similar to the Gaussian density function as the squashing function. The squashing function used is: f(d,») = exp( −d 2 /») / (2 ) Download 1.14 Mb. Do'stlaringiz bilan baham: 
|