/********************************************************************/
/* 西安电子科技大学 AnTColony4TSP 2.0 版本 */
/* Ph.D acesohn E_mail: ym@mail.xidian.edu.cn */
/* 注:参数调整问题,找到最好解。 */
/********************************************************************/
/*** begin include file ,predefine and declaration ****************/
#include <stdio.h>
#include <stdlib.h>
#include"time.h"
#include <math.h>
#define NCMAX 100 //最大迭代次数
#define AntNum 7 //蚂蚁数
#define DIMENSION 1024 /*设置最大的维数,但是实际的维数(城市个数由main
函数中的cityNumber确定),由此可知该程序只能解决最多1024个城市节点问题 */
#include "seqqueque.h"
float dis[DIMENSION][DIMENSION]={0}; //城市距离邻接矩阵
#define TAO_0 0.1 //初始信息矩阵元素的常量值
static double TAO[DIMENSION][DIMENSION]={0.0};
static double DetaTAO[DIMENSION][DIMENSION]={0.0};
#define alpha 0.5 //残留信息指数(信息启发因子),(0.05,1)
#define beta 1 //期望值指数(期望启发因子),(1,4)
#define Qtatol 20 //循环一周释放出来的信心总量
#define ROU 0.5 //信息素挥发系数
# include "PutInfo.h" //调试信息函数集
#define rdint(i) (rand()%(int)(i))
#define rdft() (float)((double)rdint(16384)/(16383.0))
#define rnd(a,b) (rdint((int)(b)-(int)(a)+1)+(int)(a))
/*** end include file ,predefine and declaration ****************/
void PutAnt(unsigned X[][DIMENSION],int cityNumber)
{
int i;
srand(time(NULL));
for(i=1;i<=AntNum;i++)
{
X[i][1]=rand()%cityNumber+1; //城市编号从1开始
printf("第%d只蚂蚁第一个位置 %d城市 ",i,X[i][1]);
printf("\n");
//getchar();
}
}
Allowed(SeqQueque *AntBatu, int k)
{
int f,r;
f=AntBatu->front;r=AntBatu->rear;
while (f!=r)
if(AntBatu->element[f]==k)
{
return(0);
}
else
f=f+1;
return(1);
}
double PorbTran(int i,int j)
{
double p=0.0;
p=pow(TAO[i][j],alpha)*pow(1.0/dis[i][j],beta);
return p;
}
void ResetDetaTao(int cityNumber)
{
int i,j;
for(i=1;i<=cityNumber;i++)
for(j=1;j<=cityNumber;j++)DetaTAO[i][j]=0;
}
//读取地图坐标信息
int readMap(char *map_file_name,float *X,float *Y )
{
int intTmp,i=0;
FILE *fp = fopen(map_file_name,"rb");
if(fp == NULL)
{
printf("can't open input file %s\n",map_file_name);
exit(1);
}
while((fscanf(fp,"%d %f %f",&intTmp,X+i,Y+i))!=EOF)
i=i+1;
fclose(fp);
return intTmp;
}
//求出 i,j两个城市之间的距离
void distance(float *X,float *Y,int cityNumber)
{
int i, j;
float s1,s2,d;
for(i=1;i<cityNumber+1;i++)
for(j=i+1;j<cityNumber+1;j++)
{
s1=pow(X[j-1]-X[i-1],2);
s2=pow(Y[j-1]-Y[i-1],2);
d=sqrt(s1+s2);
dis[i][j]=d;
dis[j][i]=d;
}
printdis(cityNumber);//getchar();
}
void main(){
int cityNumber; //实际城市数目
unsigned X[AntNum+1][DIMENSION]; //AntNum只蚂蚁就是AntNum条路径,下标从1开始使用
SeqQueque AntBatu[AntNum+1]; //AntNum只蚂蚁对应AntNum个禁忌表
int i,j,s,k; // 循环变量
//int AllowedNum; //允许每只蚂蚁下次选择的城市数量
double pij; //转移概率值
double pijMax=0.0;
int tempn; //临时变量
double * routeLength; //完整的路径长度
int t;
int Nc;
double * delK; //每只蚂蚁的经过i,j城市间释放的信息素
double sumpij,prob[DIMENSION]={0},p; //计算转移城市时用
//读取地图信息,给距离矩阵赋值
float *X_map,*Y_map;
char map_file_name[1024]="map.txt";
//cityNumber=(int *)malloc(sizeof(int));
X_map=(float *)malloc(1024*sizeof(float));
Y_map=(float *)malloc(1024*sizeof(float));
srand(time(NULL));
cityNumber=readMap(map_file_name,X_map,Y_map);
distance(X_map,Y_map,cityNumber);
/*分配存储空间*/
routeLength=(double *)malloc((AntNum+1)*sizeof(double));
delK=(double *)malloc((AntNum+1)*sizeof(double));
/*第一步:初始化*/
t=0; //时间t;
Nc=0; //循环次数
//信息量矩阵、信息量增量矩阵 初始化 在声明时完成
for(i=1;i<=cityNumber;i++)
for(j=1;j<=cityNumber;j++)TAO[i][j]=TAO_0;
for(i=1;i<=cityNumber;i++)
for(j=1;j<=cityNumber;j++)DetaTAO[i][j]=0;
/*将m只蚂蚁随机的放在n个城市上,并加入各自禁忌表*/
PutAnt(X,cityNumber);
while(Nc<NCMAX)
{
//初始化禁忌表
for(i=1;i<=AntNum;i++)
InitQueque(&AntBatu[i]);
//加入禁忌表.
for(i=1;i<=AntNum;i++)
EnterQueque(&AntBatu[i],X[i][1],cityNumber);
/*调试信息,输出各个蚂蚁中禁忌表中的内容
for(i=1;i<=AntNum;i++)
PrintQueque(&AntBatu[i],cityNumber);getchar();*/
/*每只蚂蚁单独构造解
循环计算直到禁忌表满,共循环cityNumber -1 次 */
for(s=2;s<=cityNumber;s++)
{
for(i=1;i<=AntNum;i++)
{
pijMax=0; tempn=0;sumpij=0;
for(k=1;k<=cityNumber;k++)
{
//城市标号数组下标从0开始,但距离矩阵标号是从1开始。
if(Allowed(&AntBatu[i],k)) /*第k个城市不在该蚂蚁的禁忌表中,
可成为下个城市的选择*/
{
printf("第%d只蚂蚁,当前城市号%d,下个可选择城市号%d ,",i,X[i][s-1],k);//getchar();
pij=PorbTran(X[i][s-1],k); //计算 转移概率概率
printf("%d->%d,pij=%f..\n",X[i][s-1],k,pij);//getchar();
printf("转移概率分子值为 %5.2f \n",pij);
//概率转移,归一化
prob[k]=pij;
sumpij=sumpij+pij;
}
}
//概率转移,归一化
for(j=1;j<=cityNumber;j++)
{
prob[j]=prob[j]/sumpij;
printf(" prob[%d]=%f ,",j,prob[j]);
}
printf("\n");
//概率选择下个城市
sumpij=0;
p=rdft();//printf("\np=%f",p);
//p=0.5;
for(j=1;j<=cityNumber;j++){
sumpij=sumpij+prob[j];printf("sumpij(%d)=%f ",j,sumpij);
if(sumpij>=p && Allowed(&AntBatu[i],j))
{
break;
}
}
tempn=j;printf("\np=%f,选择%d ",p,tempn);
pij=sumpij=0;for(j=1;j<=cityNumber;j++)prob[j]=0.0;
X[i][s]=tempn;
EnterQueque(&AntBatu[i],tempn,cityNumber);
}
}
PrintRoute(X,cityNumber);getchar();
for(i=1;i<=AntNum;i++)
{
routeLength[i]=0.0;
for(j=1;j<=cityNumber-1;j++)
{
routeLength[i]=routeLength[i]+dis[X[i][j]][X[i][j+1]];
}
routeLength[i]=routeLength[i]+dis[X[i][cityNumber]][X[i][1]];
//再求经过的每段路上释放的信息素多少
delK[i]=Qtatol/routeLength[i];
//printf("\n routeLength=%4.2f,del=%4.2f \n",routeLength[i],delK[i]);
//更新 DetaTao矩阵
for(j=1;j<=cityNumber-1;j++)
{
DetaTAO[X[i][j]][X[i][j+1]]=DetaTAO[X[i][j]][X[i][j+1]]+delK[i];
DetaTAO[X[i][j+1]][X[i][j]]=DetaTAO[X[i][j+1]][X[i][j]]+delK[i];
}
DetaTAO[X[i][cityNumber]][X[i][1]]=DetaTAO[X[i][cityNumber]][X[i][1]]+delK[i];
DetaTAO[X[i][1]][X[i][cityNumber]]=DetaTAO[X[i][1]][X[i][cityNumber]]+delK[i];
}
//最后更新信息素矩阵TAO,
for(i=1;i<=cityNumber;i++)
for(j=1;j<=cityNumber;j++)
{
TAO[i][j]=(1-ROU)*TAO[i][j]+ROU*DetaTAO[i][j];
}
ResetDetaTao(cityNumber);
Nc=Nc+1;
//
printf("**********Nc=%d**********************\n",Nc);
}
}
- 1
- 2
- 3
前往页