蚁群算法 C语言程序(已运行).doc
/Basic Ant Colony Algorithm for TSP #include <iostream.h> #include <fstream.h> #include <math.h> #include <time.h> #include <conio.h> #include <stdlib.h> #include <iomanip.h> #define N 31 /city size #define M 31 /ant number double inittao=1; double taoNN; double detataoNN; double distanceNN; double yitaNN; int tabuMN; int routeMN; double solutionM; int BestRouteN; double BestSolution=10000000000; double alfa,beta,rou,Q; int NcMax; void initparameter(void); / initialize the parameters of basic ACA double EvalueSolution(int *a); / evaluate the solution of TSP, and calculate the length of path void InCityXY( double x, double y, char *infile ); / input the nodes coordinates of TSP void initparameter(void) alfa=1; beta=5; rou=0.9; Q=100; NcMax=200; void main(void) int NC=0; initparameter(); double xN; double yN; InCityXY( x, y, "city31.tsp" ); for(int i=0;i<N;i+) for(int j=i+1;j<N;j+) distanceji=sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj); distanceij=distanceji; / calculate the heuristic parameters for(i=0;i<N;i+) for(int j=0;j<N;j+) taoij=inittao; if(j!=i) yitaij=100/distanceij; for(int k=0;k<M;k+) for(i=0;i<N;i+) routeki=-1; srand(time(NULL); for(k=0;k<M;k+) routek0=k%N; tabukroutek0=1; /each ant try to find the optiamal path do int s=1; double partsum; double pper; double drand; /ant choose one whole path while(s<N) for(k=0;k<M;k+) int jrand=rand()%3000; drand=jrand/3001.; partsum=0; pper=0; for(int j=0;j<N;j+) if(tabukj=0) partsum+=pow(taorouteks-1j,alfa)*pow(yitarouteks-1j,beta); for(j=0;j<N;j+) if(tabukj=0) pper+=pow(taorouteks-1j,alfa)*pow(yitarouteks-1j,beta)/partsum; if(pper>drand) break; tabukj=1; routeks=j; s+; / the pheromone is updated for(i=0;i<N;i+) for(int j=0;j<N;j+) detataoij=0; for(k=0;k<M;k+) solutionk=EvalueSolution(routek); if(solutionk<BestSolution) BestSolution=solutionk; for(s=0;s<N;s+) BestRoutes=routeks; for(k=0;k<M;k+) for(s=0;s<N-1;s+) detataorouteksrouteks+1+=Q/solutionk; detataoroutekN-1routek0+=Q/solutionk; for(i=0;i<N;i+) for(int j=0;j<N;j+) taoij=rou*taoij+detataoij; if(taoij<0.00001) taoij=0.00001; if(taoij>20) taoij=20; for(k=0;k<M;k+) for(int j=1;j<N;j+) tabukroutekj=0; routekj=-1; NC+; while(NC<NcMax); /output the calculating results fstream result; result.open("optimal_results.log", ios:app); if(!result) cout<<"cant open the <optimal_results.log> file!n" exit(0); result<<"*-*"<<endl; result<<"the initialized parameters of ACA are as follows:"<<endl; result<<"alfa="<<alfa<<", beta="<<beta<<", rou="<<rou<<", Q="<<Q<<endl; result<<"the maximum iteration number of ACA is:"<<NcMax<<endl; result<<"the shortest length of the path is:"<<BestSolution<<endl; result<<"the best route is:"<<endl; for(i=0;i<N;i+) result<<BestRoutei<<" " result<<endl; result<<"*-*"<<endl<<endl; result.close(); cout<<"the shortest length of the path is:"<<BestSolution<<endl; double EvalueSolution(int *a) double dist=0; for(int i=0;i<N-1;i+) dist+=distanceaiai+1; dist+=distanceaia0; return dist; void InCityXY( double x, double y, char *infile ) fstream inxyfile( infile, ios:in | ios:nocreate ); if( !inxyfile ) cout<<"cant open the <"<<infile<<"> file!n" exit(0); int i=0; while( !inxyfile.eof() ) inxyfile>>xi>>yi; if( +i >= N ) break; 本文来自CSDN博客,转载请标明出处:http:/blog.csdn.net/lyp2003ok/archive/2009/01/04/3706252.aspx