蚁群算法.doc

//段海滨教授主编的《蚁群算法原理及其应用》。//BasicAntColonyAlgorithmforTSP#include<>#include<>#include<>#include<>#include<>#include<>#include<>#defineN31//citysize#defineM31//antnumberdoubleinittao=1;doubletao[N][N];doubledetatao[N][N];doubledistance[N][N];doubleyita[N][N];inttabu[M][N];introute[M][N];doublesolution[M];intBestRoute[N];doubleBestSolution=**********;doublealfa,beta,rou,Q;intNcMax;voidinitparameter(void);//initializetheparametersofbasicACAdoubleEvalueSolution(int*a);//evaluatethesolutionofTSP,andcalculatethelengthofpathvoidInCityXY(doublex[],doubley[],char*infile);//inputthenodes'coordinatesofTSPvoidinitparameter(void){alfa=1;beta=5;rou=;Q=100;NcMax=200;}voidmain(void){intNC=0;initparameter();doublex[N];doubley[N];InCityXY(x,y,"");for(inti=0;i<N;i++)for(intj=i+1;j<N;j++){distance[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));distance[i][j]=distance[j][i];}//calculatetheheuristicparametersfor(i=0;i<N;i++)for(intj=0;j<N;j++){tao[i][j]=inittao;if(j!=i)yita[i][j]=100/distance[i][j];}for(intk=0;k<M;k++)for(i=0;i<N;i++)route[k][i]=-1;srand(time(NULL));for(k=0;k<M;k++){route[k][0]=k%N;tabu[k][route[k][0]]=1;}//eachanttrytofindtheoptiamalpathdo{ints=1;doublepartsum;doublepper;doubledrand;//antchooseonewholepathwhile(s<N){for(k=0;k<M;k++){intjrand=rand()%3000;drand=jrand/3001.;partsum=0;pper=0;for(intj=0;j<N;j++){if(tabu[k][j]==0)partsum+=pow(tao[route[k][s-1]][j],alfa)*pow(yita[route[k][s-1]][j],beta);for(j=0;j<N;j++){if(tabu[k][j]==0)pper+=pow(tao[route[k][s-1]][j],alfa)*pow(yita[route[k][s-1]][j],beta)/partsum;if(pper>drand)break;}tabu[k][j]=1;route[k][s]=j;}s++;}//thepheromoneisupdatedfor(i=0;i<N;i++)for(intj=0;j<N;j++)detatao[i][j]=0;for(k=0;k<M;k++){solution[k]=EvalueSolution(route[k]);if(solution[k]<BestSolution){BestSolution=solution[k];for(s=0;s<N;s++)BestRoute[s]=route[k][s];}}for(k=0;k<M;k++){for(s=0;s<N-1;s++)detatao[route[k][s]][route[k][s+1]]+=Q/solution[k];detatao[r