蚁群算法(C语言版)

//段海滨教授主编的《蚁群算法原理及其应用》附录里的C程序代码. 并有几位网友修改。
//Basic Ant Colony Algorithm for TSP
#include
#include
#include
#include
#include
#include
#include

#define N 31 //city size
#define M 31 //ant number

double inittao=1;
double tao[N][N];
double detatao[N][N];
double distance[N][N];
double yita[N][N];
int tabu[M][N];
int route[M][N];
double solution[M];
int BestRoute[N];
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 x[N];
double y[N];
InCityXY( x, y, "city31.tsp" );

for(int i=0;ifor(int j=i+1;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];
}
// calculate the heuristic parameters
for(i=0;ifor(int j=0;j{
tao[i][j]=inittao;
if(j!=i)
yita[i][j]=100/distance[i][j];
}
for(int k=0;kfor(i=0;iroute[k][i]=-1;
srand(time(NULL));
for(k=0;k{
route[k][0]=k%N;
tabu[k][route[k][0]]=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{
for(k=0;k{
int jrand=rand()%3000;
drand=jrand/3001.;
partsum=0;
pper=0;
for(int j=0;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{
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++;
}
// the pheromone is updated
for(i=0;ifor(int j=0;jdetatao[i][j]=0;
for(k=0;k{
solution[k]=EvalueSolution(route[k]);
if(solution[k]{
BestSolution=solution[k];
for(s=0;sBestRoute[s]=route[k][s];
}
}
for(k=0;k{
for(s=0;sdetatao[route[k][s]][route[k][s+1]]+=Q/solution[k];
detatao[route[k][N-1]][route[k][0]]+=Q/solution[k];
}
for(i=0;ifor(int j=0;j{
tao[i][j]=rou*tao[i][j]+detatao[i][j];
if(tao[i][j]<0.00001)
tao[i][j]=0.00001;
if(tao[i][j]>20)
tao[i][j]=20;
}
for(k=0;kfor(int j=1;j{
tabu[k][route[k][j]]=0;
route[k][j]=-1;
}
NC++;
} while(NC//output the calculating results
fstream result;
result.open("optimal_results.log", ios::app);
if(!result)
{
cout<<"c

an't open the file!\n";
exit(0);
}
result<<"*-------------------------------------------------------------------------*"<result<<"the initialized parameters of ACA are as follows:"<result<<"alfa="<result<<"the shortest length of the path is:"<result<<"the best route is:"<for(i=0;iresult<result<result<<"*-------------------------------------------------------------------------*"<result.close();
cout<<"the shortest length of the path is:"<}


double EvalueSolution(int *a)
{
double dist=0;
for(int i=0;idist+=distance[a[i]][a[i+1]];
dist+=distance[a[i]][a[0]];
return dist;
}


void InCityXY( double x[], double y[], char *infile )
{
fstream inxyfile( infile, ios::in | ios::nocreate );
if( !inxyfile )
{
cout<<"can't open the <"< file!\n";
exit(0);
}
int i=0;
while( !inxyfile.eof() )
{
inxyfile>>x[i]>>y[i];
if( ++i >= N ) break;
}
}

//另外：你需要建立一个名为city31.tsp的文件，存放31个城市的坐标。