C++ Neural Networks and Fuzzy Logic by Valluru B. Rao M&T Books, IDG Books Worldwide, Inc. ISBN: 1558515526   Pub Date: 06/01/95

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.

Output for a Four-City Problem

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
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

-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

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
3
2

 distance of tour is : 32