by Valluru B. Rao
M&T Books, IDG Books Worldwide, Inc.
ISBN: 1558515526 Pub Date: 06/01/95
|
|
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 |
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();
}
| Previous | Table of Contents | Next |