//利用acs算法求解tsp问题
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <ctime>
#include <conio.h>
using namespace std;
int NodeNum;//结点个数
int AntNum;//蚂蚁个数
double **NodeCoor;//结点坐标
int Alpha=1,Beta=2;
double Rho=0.95;
const int MaxIterNum=20;//最大迭代次数
const double Q=1.0;
int *GBestRoute;//全局最优路径
int *IBestRoute;//迭代最优路径
double GBestLength=0.0;//全局最优路径长度
double IBestLength=0.0;//迭代最优路径长度
const double Max=1000000000.0;
double MaxTau=0.0;//限定的最大信息素
double MinTau=0.0;//限定的最小信息素
void ReadFile()
{
char FileName[30];
char Str[50];
int count,i;
cout<<"输入文件名: ";
cin>>FileName;
ifstream Fin;
Fin.open(FileName);
if(Fin.fail())
{
cout<<"\nfile open error!\n";
exit(0);
}
Fin>>Str;
if(Fin.eof())
{
cout<<"\nfile open error!\n";
exit(0);
}
while(!Fin.eof())
{
if(strcmp(Str,"DIMENSION")==0)
{
Fin>>Str;
Fin>>NodeNum;
NodeCoor=new double *[NodeNum];
for(i=0;i<NodeNum;i++)
{
NodeCoor[i]=new double[2];
}
break;
}
Fin>>Str;
}
while(!Fin.eof())
{
if(strcmp(Str,"1")==0)
{
count=0;
Fin>>NodeCoor[count][0]>>NodeCoor[count][1];
count++;
while(!Fin.eof())
{
Fin>>Str;
Fin>>NodeCoor[count][0]>>NodeCoor[count][1];
count++;
}
break;
}
Fin>>Str;
}
return;
}
double Dist(int a,int b)
{
double temp;
temp=sqrt(pow(NodeCoor[a][0]-NodeCoor[b][0],2)+pow(NodeCoor[a][1]-NodeCoor[b][1],2));//在这里进行了取整。
return (double)((int)(temp+0.5));
}
void ToNull(int *table)
{
int i;
for(i=0;i<NodeNum;i++)
{
table[i]=-1;
}
return;
}
int find(const int *Tabu, int *Allowed)
{//返回Allowed表元素的个数
int i=0;
int count=0;
int *Visited=new int[NodeNum];
ToNull(Visited);
ToNull(Allowed);
while(Tabu[i]!=-1)
{
Visited[Tabu[i]]=1;
i++;
}
for(i=0;i<NodeNum;i++)
{
if(Visited[i]==-1)
{
Allowed[count]=i;
count++;
}
}
return count;
delete [] Visited;
}
int main(int argc, char **argv)
{
int i,j,k,DNode,SNode;
ReadFile();
double temp=exp(log(0.05)/double(NodeNum));
double rate=(2.0/temp-2.0)/(temp-2.0);//最大信息素与最小信息素的比值
GBestRoute=new int[NodeNum];
IBestRoute=new int[NodeNum];
AntNum=NodeNum;
int ** Tabu=new int* [AntNum];
int ** Allowed=new int* [AntNum];
for(i=0;i<AntNum;i++)
{
Tabu[i]=new int[NodeNum];
Allowed[i]=new int[NodeNum];
}
double ** Tau=new double* [NodeNum];
double ** DeltaTau=new double* [NodeNum];
double ** Eta=new double* [NodeNum];
for(i=0;i<NodeNum;i++)
{
Tau[i]=new double[NodeNum];
DeltaTau[i]=new double[NodeNum];
Eta[i]=new double[NodeNum];
}
for(i=0;i<NodeNum;i++)
{
for(j=0;j<NodeNum;j++)
{
if(i!=j)
{
Tau[i][j]=10000.0;//初始信息素的浓度
if(Dist(i,j)!=0)
Eta[i][j]=1/Dist(i,j);//初始化Eta
else
Eta[i][j]=Max;//如果两个点重合(例如a280.tsp)
}
else
Tau[i][j]=0.0;
}
}
//迭代
srand(time(NULL));
cout<<"迭代开始"<<endl;
int IterNum=1;
double *P,*PSum;
while(IterNum<=MaxIterNum)
{
//将AntNum个蚂蚁放在NodeNum个结点上
for(i=0;i<AntNum;i++)
{
ToNull(Tabu[i]);
Tabu[i][0]=i;//rand()%NodeNum+1;
}
//蚂蚁按照概率函数选择下一个结点,完成各自的周游
for(j=0;j<NodeNum-1;j++)
{
for(i=0;i<AntNum;i++)
{
//得到待访问的结点集合
int count;
count=find(Tabu[i],Allowed[i]);
SNode=Tabu[i][j];
P=new double[count];
double Sum=0.0;
//计算待选择城市的概率分布
for(k=0;k<count;k++)
{
DNode=Allowed[i][k];
P[k]=pow(Tau[SNode][DNode],Alpha)*pow(Eta[SNode][DNode],Beta);
Sum+=P[k];
}
for(k=0;k<count;k++)
{
P[k]=P[k]/Sum;
}
//按照概率选择下一个城市(不是选择概率最大的城市)
double temp=double(rand()%100)/double(100);
PSum=new double[count];
PSum[0]=P[0];
for(k=0;k<count-1;k++)
{
if(PSum[k]>=temp)
{
break;
}
PSum[k+1]=P[k+1]+PSum[k];
}
Tabu[i][j+1]=Allowed[i][k];
delete [] P;
delete [] PSum;
}
}
//记录本次迭代最优路径
int IBestAnt;
double *Length=new double[AntNum];
for(i=0;i<AntNum;i++)
{
Length[i]=0.0;
j=0;
while(j<NodeNum-1)
{
Length[i]+=Dist(Tabu[i][j],Tabu[i][j+1]);
j++;
}
Length[i]+=Dist(Tabu[i][0],Tabu[i][NodeNum-1]);
if(i==0)
{
IBestLength=Length[i];
}
else
{
if(Length[i]<IBestLength)
{
IBestLength=Length[i];
IBestAnt=i;
}
}
}
for(i=0;i<NodeNum;i++)
{
IBestRoute[i]=Tabu[IBestAnt][i];
}
//更新全局最优路径
if(IterNum==1)
{
GBestLength=IBestLength;
for(i=0;i<NodeNum;i++)
{
GBestRoute[i]=IBestRoute[i];
}
}
else
{
if(GBestLength>IBestLength)
{
GBestLength=IBestLength;
for(i=0;i<NodeNum;i++)
{
GBestRoute[i]=IBestRoute[i];
}
}
}
//更新信息素
//只对当前最优和全局最优进行更新,
//每5次迭代使用一次全局最优蚂蚁更新信息素
for(i=0;i<NodeNum;i++)
{
for(j=0;j<NodeNum;j++)
{
DeltaTau[i][j]=0.0;
}
}
double TempLength=0.0;
int *TempRoute=new int[NodeNum];
if(IterNum%5==0)
{
TempLength=GBestLength;
for(i=0;i<NodeNum;i++)
{
TempRoute[i]=GBestRoute[i];
}
}
else
{
TempLength=IBestLength;
for(i=0;i<NodeNum;i++)
{
TempRoute[i]=IBestRoute[i];
}
}
for(i=0;i<NodeNum-1;i++)
{
DeltaTau[TempRoute[i]][TempRoute[i+1]]=Q/TempLength;
}
DeltaTau[NodeNum-1][0]=Q/TempLength;
//让DeltaTau对称
double TempTau;
for(i=0;i<NodeNum;i++)
{
for(j=0;j<i;j++)
{
TempTau=DeltaTau[j][i];
DeltaTau[j][i]+=DeltaTau[i][j];
DeltaTau[i][j]+=TempTau;
}
}
//更新信息素并限定信息素的大小
MaxTau=1.0/(GBestLength*(1-Rho));
MinTau=rate*MaxTau;
for(i=0;i<NodeNum;i++)
{
for(j=0;j<NodeNum;j++)
{
Tau[i][j]=Rho*Tau[i][j]+DeltaTau[i][j];
if(Tau[i][j]>MaxTau)
{
Tau[i][j]=MaxTau;
}
if(Tau[i][j]<MinTau)
{
Tau[i][j]=MinTau;
}
}
}
//输出目前的最优解
cout<<"["<<IterNum<<"]: "<<GBestLength<<endl;
delete [] Length;
IterNum++;
}
//输出最优路径
cout<<endl<<"最优路径:"<<endl;
for(i=0;i<NodeNum;i++)
{
cout<<GBestRoute[i]+1<<" ";
}
cout<<endl<<"最优路径长度:"<<endl<<GBestLength<<endl;
//释放存储空间
for(i=0;i<AntNum;i++)
{
delete [] Tabu[i];
delete [] Allowed[i];
}
for(i=0;i<NodeNum;i++)
{
delete [] Tau[i];
delete [] DeltaTau[i];
delete [] Eta[i];
}
return 0;
}