C++ Neural Networks and Fuzzy Logic
Activations, Outputs, and Their Updating
Download 1.14 Mb. Pdf ko'rish
|
C neural networks and fuzzy logic
- Bu sahifa navigatsiya:
- C++ Neural Networks and Fuzzy Logic by Valluru B. Rao MTBooks, IDG Books Worldwide, Inc. ISBN
- C++ Implementation of the Hopfield Network for the Traveling Salesperson Problem
- Program Details
|
Activations, Outputs, and Their Updating We denote the activation of the neuron in the ith row and jth column by a ij , and the output is denoted by x ij . A
time constant Ä, and a gain » are used as well. A constant m is another parameter used. Also, ”t denotes the increment in time, from one cycle to the next. Keep in mind that the index for the summation £ ranges from 1 to n, the number of cities. Excluded values of the index are shown by the use of the symbol `. The change in the activation is then given by ”a ij , where:
”a ij = ”t (Term 1 + Term
2 + Term
3 + Term
4 + Term
5 ) Term 1 = − a
ij /Ä Term 2 = − A
1 k`j x ik Term 3 = − A 2 £ k`i x kj Term 4 = − A
3 (£ i £ k x ik − m)
Term 5 = − A 4 £ k`i d ik (x k,j+1 + x
k,j−1 ) To update the activation of the neuron in the ith row and jth column, you take: a ijnew =
a ijold + ” a ij
x in = (1 + tanh(»a ij ))/2
NOTE: , which is the original sigmoid function The function used here is the hyperbolic tangent function. The gain parameter mentioned earlier » is. The output of each neuron is calculated after updating the activation. Ideally, you want to get the outputs as 0’s and 1’s, preferably a single one for each row and each column, to represent a tour that satisfies the conditions of the problem. But the hyperbolic tangent function gives a real number, and you have to settle for a close enough value to 1 or 0. You may get, for example, 0.96 instead of 1, or 0.07 instead of 0. The solution is to be obtained from such values by rounding up or down so that 1 or 0 will be used, as the case may be C++ Neural Networks and Fuzzy Logic:Preface Inputs
342 Previous Table of Contents Next Copyright © IDG Books Worldwide, Inc. C++ Neural Networks and Fuzzy Logic:Preface Inputs 343
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 Performance of the Hopfield Network Let us now look at Hopfield and Tank’s approach at solving the TSP. Hopfield and Tank Example The Hopfield network’s use in solving the traveling salesperson problem is a pioneering effort in the use of the neural network approach for this problem. Hopfield and Tank’s example is for a problem with 10 cities. The parameters used were, A 1 = 500, A 2 = 500, A 3 = 200, A 4 = 500, Ä = 1, » = 50, and m = 15. A good solution corresponding to a local minimum for E is the expected, if not the best, solution (global minimum). An annealing process could be considered to move out of any local minimum. As was mentioned before, the traveling salesperson problem is one of those problems for which a single approach cannot be found that will be successful in all cases. There isn’t very much guidance as to how to choose the parameters in general for the use of the Hopfield network to solve the traveling salesperson problem.
We present a C++ program for the Hopfield network operation for the traveling salesperson problem. The header file is in the Listing 15.1, and the source file is in the Listing 15.2. A tsneuron class is declared for a neuron and a network class for the network. The network class is declared a friend in the tsneuron class. The program follows the procedure described for setting inputs, connection weights, and updating.
The following is a listing of the characteristics of the C++ program along with definitions and/or functions. • The number of cities, the number of iterations, and the distances between the cities are solicited from the user. • The distances are taken as integer values. If you want to use real numbers as distances, the type for distance matrix needs to be changed to float, and corresponding changes are needed for calcdist ( ) function, etc. • tourcity and tourorder arrays keep track of the cities that have to be covered and the order in which it is to be done. • A neuron corresponds to each combination of a city and its order in the tour. The ith city visited in the order j , is the neuron corresponding to the element j + i*n, in the array for neurons. Here n is the number of cities. The i and the j vary from 0 to n – 1. There are n 2 neurons. • mtrx is the matrix giving the weights on the connections between the neurons. It is a square matrix of order n 2 .
• asgninpt ( ) function presents the input vector ip to the network and determines the initial activations of the neurons. • getacts ( ) function updates the activations of the neurons after each iteration. C++ Neural Networks and Fuzzy Logic:Preface Performance of the Hopfield Network 344
• getouts ( ) function computes the outputs after each iteration. la is used as abbreviation for lambda in its argument. • iterate ( ) function carries out the number of iterations desired. • findtour ( ) function determines the tour orders of cities to be visited using the outputs of the neurons. When used at the end of the iterations, it gives the solution obtained for the traveling salesperson problem.
//trvslsmn.h V. Rao, H. Rao #include #include #include #include #define MXSIZ 11 class tsneuron { protected: int cit,ord; float output; float activation; friend class network; public: tsneuron() { }; void getnrn(int,int); }; class network { public: int citnbr; float pra,prb,prc,prd,totout,distnce; tsneuron (tnrn)[MXSIZ][MXSIZ]; int dist[MXSIZ][MXSIZ]; int tourcity[MXSIZ]; int tourorder[MXSIZ]; float outs[MXSIZ][MXSIZ]; float acts[MXSIZ][MXSIZ]; float mtrx[MXSIZ][MXSIZ]; float citouts[MXSIZ]; float ordouts[MXSIZ]; network() { }; void getnwk(int,float,float,float,float); void getdist(int); void findtour(); void asgninpt(float *); void calcdist(); void iterate(int,int,float,float,float); void getacts(int,float,float); void getouts(float); //print functions void prdist(); C++ Neural Networks and Fuzzy Logic:Preface Performance of the Hopfield Network 345
void prmtrx(int); void prtour(); void practs(); void prouts(); }; Previous Table of Contents Next Copyright © IDG Books Worldwide, Inc. C++ Neural Networks and Fuzzy Logic:Preface Performance of the Hopfield Network 346
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 Source File for Hopfield Network for Traveling Salesperson Problem The following listing gives the source code for the C++ program for the Hopfield network for traveling salesperson problem. The user is prompted to input the number of cities and the maximum number of iterations for the operation of the network. The parameters a, b, c, d declared in the function main correspond to A 1 , A 2 , A 3 , and A 4 , respectively. These and the parameters tau, lambda, and nprm are all given values in the declaration statements in the function main. If you change these parameter values or change the number of cities in the traveling salesperson problem, the program will compile but may not work as you’d like.
//trvslsmn.cpp V. Rao, H. Rao #include “trvslsmn.h” #include #include //generate random noise int randomnum(int maxval) { // random number generator // will return an integer up to maxval return rand() % maxval; } //Kronecker delta function int krondelt(int i,int j) {
int k; k= ((i == j) ? (1):(0)); return k; }; void tsneuron::getnrn(int i,int j) {
cit = i; ord = j; output = 0.0; activation = 0.0; }; //distances between cities void network::getdist(int k) {
C++ Neural Networks and Fuzzy Logic:Preface Source File for Hopfield Network for Traveling Salesperson Problem 347
citnbr = k; int i,j; cout<<”\n”; for(i=0;i {
dist[i][i]=0; for(j=i+1;j { cout<<”\ntype distance (integer) from city “<<
i<<” to city “< cin>>dist[i][j];
} cout<<”\n”;
}
dist[i][j] = dist[j][i];
} }
prdist(); cout<<”\n”;
}
//print distance matrix {
int i,j; cout<<”\n Distance Matrix\n”; for(i=0;i { for(j=0;j { cout< } cout<<”\n”;
}
//set up network void network::getnwk(int citynum,float a,float b,float c,float d)
{ int i,j,k,l,t1,t2,t3,t4,t5,t6;
int p,q; citnbr = citynum;
pra = a; prb = b;
prc = c; prd = d;
getdist(citnbr); for(i=0;i { for(j=0;j { tnrn[i][j].getnrn(i,j);
C++ Neural Networks and Fuzzy Logic:Preface Source File for Hopfield Network for Traveling Salesperson Problem
348
} } //find weight matrix for(i=0;i {
for(j=0;j {
p = ((j == citnbr−1) ? (0) : (j+1)); q = ((j == 0) ? (citnbr−1) : (j−1));
t1 = j + i*citnbr; for(k=0;k { for(l=0;l { t2 = l + k*citnbr;
t3 = krondelt(i,k); t4 = krondelt(j,l);
t5 = krondelt(l,p); t6 = krondelt(l,q);
mtrx[t1][t2] = −a*t3*(1−t4) −b*t4*(1−t3)
−c −d*dist[i][k]*(t5+t6); }
} }
} prmtrx(citnbr);
}
//print weight matrix { int i,j,nbrsq;
nbrsq = k*k; cout<<”\nWeight Matrix\n”;
for(i=0;i {
for(j=0;j {
if(j%k == 0) {
cout<<”\n”; }
cout< }
cout<<”\n”; }
} //present input to network
void network::asgninpt(float *ip) {
int i,j,k,l,t1,t2; for(i=0;i { for(j =0;j { C++ Neural Networks and Fuzzy Logic:Preface
Source File for Hopfield Network for Traveling Salesperson Problem 349
acts[i][j] = 0.0; } } //find initial activations for(i=0;i { for(j =0;j { t1 = j + i*citnbr;
for(k=0;k {
for(l=0;l {
t2 = l + k*citnbr; acts[i][j] +=
mtrx[t1][t2]*ip[t1]; }
} }
} //print activations
cout<<”\ninitial activations\n”; practs();
}
void network::getacts(int nprm,float dlt,float tau) {
int i,j,k,p,q; float r1, r2, r3, r4,r5;
r3 = totout − nprm ; for(i=0;i { r4 = 0.0;
p = ((i == citnbr−1) ? (0) : (i+1)); q = ((i == 0) ? (citnbr−1) : (i−1));
for(j=0;j {
r1 = citouts[i] − outs[i][j]; r2 = ordouts[i] − outs[i][j];
for(k=0;k {
r4 += dist[i][k] * (outs[k][p] + outs[k][q]);
} r5 = dlt*(−acts[i][j]/tau −
pra*r1 −prb*r2 −prc*r3 −prd*r4); acts[i][j] += r5;
} }
}
void network::getouts(float la) {
float b1,b2,b3,b4; int i,j;
C++ Neural Networks and Fuzzy Logic:Preface Source File for Hopfield Network for Traveling Salesperson Problem
350
totout = 0.0; for(i=0;i {
citouts[i] = 0.0; for(j=0;j { b1 = la*acts[i][j];
b4 = b1/500.0; b2 = exp(b4);
b3 = exp(−b4); outs[i][j] = (1.0+(b2−b3)/(b2+b3))/2.0;
citouts[i] += outs[i][j];}; totout += citouts[i];
} for(j=0;j { ordouts[j] = 0.0;
for(i=0;i {
ordouts[j] += outs[i][j]; }
} }
//find tour void network::findtour()
{
float tmp; for (i=0;i { for(j=0;j { tag[i][j] = 0;
} }
for (i=0;i {
tmp = −10.0; for(j=0;j { for(k=0;k { if((outs[i][k] >=tmp)&&
(tag[i][k] ==0)) tmp = outs[i][k];
} if((outs[i][j] ==tmp)&&
(tag[i][j]==0)) {
tourcity[i] =j; tourorder[j] = i;
cout<<”\ntourcity “< <<” tour order “< for(k=0;k {
tag[i][k] = 1; tag[k][j] = 1;
} }
C++ Neural Networks and Fuzzy Logic:Preface Source File for Hopfield Network for Traveling Salesperson Problem
351
} } } //print outputs void network::prouts() {
int i,j; cout<<”\nthe outputs\n”; for(i=0;i { for(j=0;j { cout< } cout<<”\n”;
} }
//calculate total distance for tour void network::calcdist()
{
distnce = 0.0; for(i=0;i { k = tourorder[i];
l = ((i == citnbr−1 ) ? (tourorder[0]):(tourorder[i+1])); distnce += dist[k][l];
} cout<<”\n distance of tour is : “< }
void network::prtour() {
int i; cout<<”\n the tour :\n”;
for(i=0;i {
cout< cout<<”\n”;
} }
//print activations void network::practs()
{
cout<<”\n the activations:\n”; for(i=0;i { for(j=0;j { cout< } C++ Neural Networks and Fuzzy Logic:Preface
Source File for Hopfield Network for Traveling Salesperson Problem 352
cout<<”\n”; } } //iterate specified number of times void network::iterate(int nit,int nprm,float dlt,float tau,float la) {
int k; for(k=1;k<=nit;++k) { getacts(nprm,dlt,tau); getouts(la); } cout<<”\n” < practs(); cout<<”\n”;
prouts(); cout<<”\n”;
}
{
//numit = #iterations; n = #cities; u=intial input; nprm − parameter n’ // —————————————————− // parameters to be tuned are here: int u=1; int nprm=10; float a=40.0; float b=40.0; float c=30.0; float d=60.0; float dt=0.01; float tau=1.0; float lambda=3.0; //——————————————————− int i,n2; int numit=100; int n=4; float input_vector[MXSIZ*MXSIZ]; srand ((unsigned)time(NULL)); cout<<”\nPlease type number of cities, number of iterations\n”; cin>>n>>numit; cout<<”\n”; if (n>MXSIZ) { cout << “choose a smaller n value\n”; exit(1); } n2 = n*n; for(i=0;i {
if(i%n == 0)cout<<”\n”; input_vector[i] =(u + (float)(randomnum(100)/100.0))/20.0;
cout< }
C++ Neural Networks and Fuzzy Logic:Preface Source File for Hopfield Network for Traveling Salesperson Problem
353
//create network and operate network *tntwk = new network; if (tntwk==0) { cout << “not enough memory\n”; exit(1); } tntwk−>getnwk(n,a,b,c,d); tntwk−>asgninpt(input_vector); tntwk−>getouts(lambda); tntwk−>prouts(); tntwk−>iterate(numit,nprm,dt,tau,lambda); tntwk−>findtour(); tntwk−>prtour(); tntwk−>calcdist(); cout<<”\n”; } Previous Table of Contents Next Copyright © IDG Books Worldwide, Inc. C++ Neural Networks and Fuzzy Logic:Preface Source File for Hopfield Network for Traveling Salesperson Problem 354
|
