蚁群算法解决TSP

时间：2010-04-19 来源：xu_jie100

文件:	readme.rar
大小:	0KB
下载:	下载

本算法由蚁群算法解决TSP，程序收敛性好。 #include "iostream"
#include "fstream"
#include "string"
#include "ctime"
#include "cmath" using namespace std; //////////////////////////////////////////////////////////////////////////
//根据需要可修改参数
#define debug 0                                   //打开调试赋予1，关闭调试赋予0
#define city_num 80                               //城市数目，更改城市数目之后，请修改此参数
#define ant_num 200                               //蚂蚁数量 //////////////////////////////////////////////////////////////////////////
//可修改，但建议不修改参数
#define alpha 1                                   //信息素对选取路径的影响度量，建议为1
#define beita 5                                   //预测信息对选取路径的影响度量
#define gama 0.5                                  //信息素挥发参数 //////////////////////////////////////////////////////////////////////////
//不需修改参数 //定义城市名称及坐标的结构体
struct city_info{
string city_name;
float x;
float y;
};
int creat_ans[city_num];                          //一次蚂蚁走完全程路径
int ans[ant_num+1][city_num];                     //蚁群走完全程路径
int fur[city_num];                                //蚂蚁下次可达的城市
city_info citys[city_num];                        //城市信息数组
double ans_trac[city_num][city_num];              //信息素数组
double pre_beita[city_num][city_num];             //预测信息数组
double ran_max=RAND_MAX;                          //随机数的最大值 //////////////////////////////////////////////////////////////////////////
//读取城市坐标，并赋到城市信息数组中
void tsp()
{
int i;
float x,y;
char file_name[255]="cites1.txt";
string name;
ifstream file_in(file_name);           //读取城市坐标文件
if(!file_in)cout<<"打开城市坐标文件失败！"<<endl;
for(i=0;i<city_num;i++)
{
  //把一个城市名称坐标赋到城市信息数组///////////////////////////
  //begin..
  file_in>>name>>x>>y;
  citys[i].city_name=name;
  citys[i].x=x;
  citys[i].y=y;
  //end
  if(debug)cout <<citys[i].city_name<<" "<<citys[i].x<<"--"<<citys[i].y<<endl;
}
file_in.close(); } //////////////////////////////////////////////////////////////////////////
//计算两个城市之间的距离，并返回这两个城市间距
double city_dis(int a,int b)
{
double dis =sqrt((citys[a].x-citys[b].x)*(citys[a].x-citys[b].x)+(citys[a].y-citys[b].y)*(citys[a].y-citys[b].y));
return dis;
} //////////////////////////////////////////////////////////////////////////
//计算一组解城市间的距离
double distances(int a){
int i;
double len=0;
for(i=0;i<city_num-1;i++)len=len+city_dis(ans[a][i+1],ans[a][i]);
len=len+city_dis(ans[a][city_num-1],ans[a][0]);
return len;
} //////////////////////////////////////////////////////////////////////////
//根据两个城市距离的倒数，计算预测信息数组，每个元素为距离倒数的beita倍
void pre_init(){
int i,j;
for(i=0;i<city_num;i++)
  for(j=0;j<city_num;j++){
   if(i==j)pre_beita[i][j]=0;
   else pre_beita[i][j]=pow(1/city_dis(i,j),beita);
  }
} //////////////////////////////////////////////////////////////////////////
//初始化信息素，当同一个城市时为0，不为同一个城市时为1/(city_num*city_num-city_num)
void init()
{
int i,j;
for(i=0;i<city_num;i++)
  for(j=0;j<city_num;j++)
  {
   if(i!=j)ans_trac[i][j]=1/(double)(city_num*city_num-city_num);    else ans_trac[i][j]=0;
  }
} //////////////////////////////////////////////////////////////////////////
//创建蚂蚁路径
void creat_tra()
{
int i,j=city_num,next=0,k;
double rand1,total_l=0;
for(i=0;i<city_num;i++)fur[i]=i;
for(i=0;i<city_num;i++)
{   next=0;
if(i>0)
{ total_l=0;
for(k=0;k<j;k++)total_l=total_l+ans_trac[creat_ans[i-1]][fur[k]]*pre_beita[creat_ans[i-1]][fur[k]]; rand1=rand()/ran_max;
rand1=rand1*total_l;
for(k=0;k<j;k++)
{ next=k;
rand1=rand1-ans_trac[creat_ans[i-1]][fur[k]]*pre_beita[creat_ans[i-1]][fur[k]];
if(rand1<=0)
{k=j;} }
}
creat_ans[i]=fur[next];
fur[next]=fur[j-1];
j--; } } //////////////////////////////////////////////////////////////////////////
//更新信息素
void update_info(int p)
{
int i,j,k,temp;
for(i=0;i<city_num;i++)
  for(j=0;j<city_num;j++)
  {
   temp=0;
   for(k=0;k<city_num-1;k++)if(ans[p][k]==i&&ans[p][k+1]==j)temp=1;
   if(i==j)ans_trac[i][j]=0;
   else if (temp==1&&ans_trac[i][j]>0.01)ans_trac[i][j]=0.01;                    //设置信息素上限值
   else if(temp==1&&ans_trac[i][j]<0.01)ans_trac[i][j]=ans_trac[i][j]*gama+(double)gama/city_num;
   else if(ans_trac[i][j]<0.000001)ans_trac[i][j]=0.000001;                      //设置信息素下限值
   else ans_trac[i][j]=ans_trac[i][j]*gama;
  }
} //////////////////////////////////////////////////////////////////////////
//主函数
void main()
{
int i,j,k=0,temp,l,num;
long step;
double dis_opt;
double dis[ant_num+1];
char file_out[255]="tsp_ans_acoa.txt";
clock_t time_start,time_end;
srand((unsigned)time(NULL));
tsp();
pre_init();
ofstream ans_file(file_out,ios::app);
if(!ans_file)cout<<"输出结果文件打开失败！"<<endl;
cout<<"正在执行20次操作，请稍后.......................................................";
for(num=1;num<21;num++)
{
  for(i=0;i<city_num;i++)ans[ant_num][i]=i;
  time_start=clock();
  step=0;
for(l=0;l<30;l++)
{
  init();
  k=0;
while(1)
  {
  step++;
  if(step!=1)
  update_info(ant_num);

  temp=0;
  for(i=0;i<ant_num;i++)
   {
   creat_tra();
   for(j=0;j<city_num;j++){ans[i][j]=creat_ans[j];}
   dis[i]=distances(i);
   }
  for(i=1;i<ant_num-1;i++)if(dis[0]>dis[i]){dis[0]=dis[i];temp=i;}
  if(distances(ant_num)>distances(temp))
   {
   for(j=0;j<city_num;j++)ans[ant_num][j]=ans[temp][j];
   dis[ant_num]=dis[0];
   dis_opt=dis[0];
   k=0;    }
  else {
   k++;
   if(k>4)
    break;
   }
  if(debug)
  cout <<"当前最短距离为："<<dis[ant_num]<<"             第"<<step<<"次循环"<<endl;   }
}
time_end=clock();
ans_file<<"////////////////////////////////////////////////////////////"<<endl;
ans_file<<"第 "<<num<<" 次最佳路径："<<"        路径长度为："<<dis[ant_num]<<endl;
for(i=0;i<city_num;i++){ans_file<<ans[ant_num][i]<<"--";if(i%15==0&&i!=0)ans_file<<endl;}
ans_file<<ans[ant_num][0]<<endl;
ans_file<<"Run Time:   "<<(double)(time_end - time_start) / CLOCKS_PER_SEC<<"S"<<"   蚁群个数为： "<<ant_num<<"    挥发因子为： "<<gama<<endl<<endl; }
ans_file.close();
if(debug)
system("PAUSE");
}