# 119.

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

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   d =    2 1 0 1 2          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( -d2/λ) / √ (2 )

Header File for C++ Program for Kohonen’s Approach

Listing 15.3 contains the header file for this program, and listing 15.4 contains the corresponding source file:

Listing 15.3 Header file for C++ program for Kohonen’s approach

` //tsp_kohn.h V.Rao, H.Rao #include<iostream.h> #include<math.h> #define MXSIZ 10 #define pi 3.141592654 class city_neuron        {        protected:               double x,y;               int mark,order,count;               double weight[2];               friend class tspnetwork;        public:               city_neuron(){};               void get_neuron(double,double);        }; class tspnetwork        {        protected:               int chosen_city,order[MXSIZ];               double gain,input[MXSIZ][2];               int citycount,index,d[MXSIZ][MXSIZ];               double gain_factor,diffsq[MXSIZ];               city_neuron (cnrn)[MXSIZ];        public:               tspnetwork(int,double,double,double,double*,double*);               void get_input(double*,double*);               void get_d();               void find_tour();               void associate_city();               void modify_weights(int,int);               double wtchange(int,int,double,double);               void print_d();               void print_input();               void print_weights();               void print_tour();        }; `

Source File Listing

The following is the source file listing for the Kohonen approach to the traveling salesperson problem.

Listing 15.4 Source file for C++ program for Kohonen’s approach

` //tsp_kohn.cpp  V.Rao, H.Rao #include “tsp_kohn.h” void city_neuron::get_neuron(double a,double b)        {        x = a;        y = b;        mark = 0;        count = 0;        weight[0] = 0.0;        weight[1] = 0.0;        }; tspnetwork::tspnetwork(int k,double f,double q,double h, double *ip0,double *ip1)        {        int i;        gain = h;        gain_factor = f;        citycount = k;        // distances between neurons as integers between 0 and n-1        get_d();        print_d();        cout<<”\n”;        // input vectors        get_input(ip0,ip1);        print_input();        // neurons in the network        for(i=0;i<citycount;++i)               {               order[i] = citycount+1;               diffsq[i] = q;               cnrn[i].get_neuron(ip0[i],ip1[i]);               cnrn[i].order = citycount +1;               }        } void tspnetwork::associate_city()        {        int i,k,j,u;        double r,s;        for(u=0;u<citycount;u++)               {               //start a new iteration with the input vectors               for(j=0;j<citycount;j++)                        {                        for(i=0;i<citycount;++i)                               {                               if(cnrn[i].mark==0)                                       {                                       k = i;                                       i =citycount;                                       }                               }                        //find the closest neuron                        for(i=0;i<citycount;++i)                               {                               r = input[j][0] - cnrn[i].weight[0];                               s = input[j][1] - cnrn[i].weight[1];                               diffsq[i] = r*r +s*s;                               if(diffsq[i]<diffsq[k]) k=i;                               }                        chosen_city = k;                        cnrn[k].count++;                        if((cnrn[k].mark<1)&&(cnrn[k].count==2))                               {                               //associate a neuron with a position                               cnrn[k].mark = 1;                               cnrn[k].order = u;                               order[u] = chosen_city;                               index = j;                               gain *= gain_factor;                               //modify weights                               modify_weights(k,index);                               print_weights();                               j = citycount;                               }                        }               }        } void tspnetwork::find_tour()        {        int i;        for(i=0;i<citycount;++i)               {               associate_city();               }               //associate the last neuron with remaining position in        // tour               for(i=0;i<citycount;++i)                        {                        if( cnrn[i].mark ==0)                               {                               cnrn[i].order = citycount-1;                               order[citycount-1] = i;                               cnrn[i].mark = 1;                               }                        }                        //print out the tour.                        //First the neurons in the tour order                        //Next cities in the tour                        //order with their x,y coordinates                        print_tour();               } void tspnetwork::get_input(double *p,double *q)        {        int i;        for(i=0;i<citycount;++i)               {               input[i][0] = p[i];               input[i][1] = q[i];               }        } //function to compute distances (between 0 and n-1) between //neurons void tspnetwork::get_d()        {        int i,j;        for(i=0;i<citycount;++i)               {               for(j=0;j<citycount;++j)                       {                       d[i][j] = (j-i);                       if(d[i][j]<0) d[i][j] = d[j][i];                       }               }        } //function to find the change in weight component double tspnetwork::wtchange(int m,int l,double g,double h)        {        double r;        r = exp(-d[m][l]*d[m][l]/gain);        r *= (g-h)/sqrt(2*pi);        return r;        } //function to determine new weights void tspnetwork::modify_weights(int jj,int j)        {        int i;        double t;        double w[2];        for(i=0;i<citycount;++i)               {               w[0] = cnrn[i].weight[0];               w[1] = cnrn[i].weight[1];               //determine new first component of weight               t = wtchange(jj,i,input[j][0],w[0]);               w[0] = cnrn[i].weight[0] +t;               cnrn[i].weight[0] = w[0];               //determine new second component of weight               t = wtchange(jj,i,input[j][1],w[1]);               w[1] = cnrn[i].weight[1] +t;               cnrn[i].weight[1] = w[1];               }        } //different print routines void tspnetwork::print_d()        {        int i,j;        cout<<”\n”;        for(i=0;i<citycount;i++)               {               cout<<” d: “;               for(j=0;j<citycount;j++)                       {                       cout<<d[i][j]<<”   “;                       }               cout<<”\n”;               }        } void tspnetwork::print_input()        {        int i,j;        for(i=0;i<citycount;i++)               {               cout<<”input : “;               for(j=0;j<2;j++)                       {                       cout<<input [i][j]<<”   “;                       }               cout<<”\n”;               }        } void tspnetwork::print_weights()        {        int i,j;        cout<<”\n”;        for(i=0;i<citycount;i++)               {               cout<<” weight: “;               for(j=0;j<2;j++)                       {                       cout<<cnrn[i].weight[j]<<”   “;                       }               cout<<”\n”;               }        } void tspnetwork::print_tour()        {        int i,j;        cout<<”\n tour : “;        for(i=0;i<citycount;++i)               {               cout<<order[i]<<” —> “;               }        cout<<order[0]<<”\n\n”;        for(i=0;i<citycount;++i)               {               j = order[i];               cout<<”(“<<cnrn[j].x<<”, “<<cnrn[j].y<<”) —> “;               }        j= order[0];        cout<<”(“<<cnrn[j].x<<”, “<<cnrn[j].y<<”)\n\n”;        } void main()        {        int nc= 5;//nc = number of cities        double q= 0.05,h= 1.0,p= 1000.0;        double input2[][5]= {7.0,4.0,14.0,0.0,5.0,3.0,6.0,13.0,12.0,10.0};        tspnetwork tspn2(nc,q,p,h,input2[0],input2[1]);        tspn2.find_tour();        } `