aco2.c

蚁群算法在路径规划中的应用:在启发式因子的设计上考虑了路径的方向性,在算法中加入了蚁群学习机制

/********3.6号 加入蚂蚁学习功能 蚂蚁死亡更新待考虑********/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define maxnodes  160000/*总节点数*/
#define rdata_file "F:\\rd_aco2_vnp6400_1200_400.txt"
#define vn_file_name "F:\\vnpdata160000.txt"
#define num_ants   30 /*蚂蚁数量*/
#define alpha      1
#define beta       2
#define rho        0.05  /*蚁群基本参数*/
#define Drho       0.08  /****死亡路径信息素挥发参数********/
#define q_0        0.3  
#define NeiSearch  0.2
#define num_maxturns 5     /*节点中最大分支数*/

#define NONE 9999

float totalpossibility[num_maxturns];     /************概率计算后存放数组****************/
int totalchange=0;
int onceflag=0;
int deadants=0;                      /***************记录蚂蚁死亡个数***********************/
/****************随机数产生参数********************/
#define IA 1680
#define IM 2147483647
#define AM (1.0/IM)
#define IQ 127773
#define IR 2836
#define MASK 123459876
#define Q 50
#define MaxPh 3
#define AvePh 1.5 
#define MinPh 0.5                 /*最小最大蚂蚁系统参数*/
#define MaxTrial   500
#define MaxTurn    30
#define NestTurn   200
#define MidTurn    200
#define TestNum    3
extern long int seed;
long int seed = 23456789;
long int seed1 = 23456789;
float ad_rho=rho;
/******************************************************/
long destnodeid,sourcenodeid;               /******目标地址编号**********/
float destrx,destry;           /*目标地址坐标*/
int firstrun=1;

/*连接节点结构体*/
struct TRNode{
	long    RNodeid;   
	float   RX;
	float   RY;   
	float   TWeight;     
	float   TPheromone;  
	struct TRNode  *nextTRNode; 
};            /*line18*/
typedef struct TRNode TRNODE;
/*节点结构体*/
struct Ptrnode{     /*****转向信息限制结构体*******/
	long  frnodeid;
	long  nrnodeid;
	struct Ptrnode *nextPtrnode;
};
typedef struct Ptrnode PTRNODE;
/*已访问城市链表结构体*/
struct VNodes{
        long vnodeid;
        struct VNodes *nextVnode;
};
typedef struct VNodes VNODES;
typedef struct {
	long   RNodeid;    
	float  RX;
	float  RY;     
	TRNODE  *firstTRNode;
	PTRNODE *firstPtrnode;           /********指向第一个转向限制表*************/
	VNODES *bestnodepath;                 /******指向经过的最好的蚂蚁的访问路径，其他蚂蚁经过时自动学习*********/
    float bestnodepathdistance;       /*****最短路径值********/
	long prevnodeid;                    /*********指向前一节点**************/
} RNode;



/*蚂蚁结构体*/
typedef struct{
        VNODES *curNode;          /*当前所在节点*/
        int  terminate;          /*0代表未终止解搜索，1代表找到终点终止，2代表未找到终点终止*/
        long turNode;          /*前一次所在节点编号,用于转向限制判断*/
        VNODES *nodes_visited;  /*指向起点*/
	//	long nodenum;          /*运行到哪一点*/     /*待考虑*/
		int localstep;             /*邻域搜索一次*/
		float antcurrentpathdistance;          /*********当前总的路径消耗***********/
		long lastnodeid;         /*************上一学习过程后的最优解保存**************/
		int visitedflag[maxnodes];
}ant_struct;



RNode rNodes[maxnodes];
ant_struct ants[num_ants];
VNODES *bestPath=NULL;

float bestDistance=0;
/***************************时间相关变量及函数**************************/
extern clock_t start_time;
extern double elapsed;
int time_expired();

void start_timers();
double elapsed_time();
typedef enum type_timer {REAL, VIRTUAL} TIMER_TYPE;
clock_t start_time;
double elapsed,totaltime=0;
double totalpath=0;
int allocatedstepid=1;

/************************************************************************/



/**********************************启动函数*****************************/
void InitNodes();           /*所有节点初始化函数*/
void SigleDirection();
void TestNodes();
void InitAnts(long,long);
void TestAnts();
void TestAntDistance();
long CheckInput();       /**输入源地址与目标地址编号,返回原地址编号**/
void GetDestPar();
/***********************************************************************/
double ran01(long *);
/*********************************路径选择函数 主体部分****************************/
float NodeAngle(float,float,float,float,float,float);/*当前节点 下一节点与目标节点角度计算函数 返回主启发式因子*/
int CheckDirPath(long,long);
void UpdateGlobalTPheromone();  /*全局信息素更新函数*/
void UpdateGlobalTPheromone2();
void UpdateLocalTPTPheromone();
void UpdateSigalTPheromone(VNODES *);
void UpdateP2PTPheromone(int);
void SearchBestPath();               /*搜索一次迭代后的最短路径 保存该最优路径*/
void SearchBestPath2();
float oneAntPathDistance(int) ;       /*计算一只蚂蚁构造的路径的度量*/
void ConstructSolution();
void LocalSearch_Move(int);
int AntMoveTerminate(int);
void SearchNeiMost(long [],float [][6],float[],int,int);
void SearchNeiBest(long [],float [][6],float[],int,int);
void AntTeaching(int,int);
void AntLearning(int,int);
void testteaching();

//void SearchNeiMost(long [],float[],int,int);
float CalculateTotal(float [][6],int,int);
float CalculateTotal2(float [][6],int);
void Empty_Ants_Memory();
void EmptyOneantMemory(int);
void PringOutBestPath();
void AdaptiveACO();
void ClearPH();
void PrintOutTest();
int GetBestPathSteps();
void AllocateLocalSearchAnts();
void TestAllocated();
void DeathPathPHVaporate();
void InitPenalty();
void testpenalty();
void AntLearning();
void AntTeaching();
void TestPrintBestPath();
void print_path (nodeid);
main()
{
int i=0,j,k;
int dist[MaxTrial];
FILE *rdfile;
firstrun=1;
sourcenodeid=CheckInput();

//sourcenodeid=2;//test
for(j=0;j<TestNum;j++){

//printf("took %.10f seconds\n",clock());
InitNodes();
SigleDirection();
InitPenalty();        //读入转向限制表
start_timers();
//testpenalty();
//return;
GetDestPar(); /*获取目标地址参数*/
if(CheckDirPath(sourcenodeid,destnodeid))
   return;
for(i=0;i<MaxTrial;i++){   
   deadants=0;    
   if(totalchange>NestTurn)
         AllocateLocalSearchAnts();
   else
	     InitAnts(sourcenodeid,1);  
    //if(totalchange=NestTurn)

    //if(totalchange>NestTurn)
     //    AllocateLocalSearchAnts();
   //else
      //   InitAnts(sourcenodeid,1);
  // TestAllocated();
                /*测试函数*/
  // TestAnts();
//TestAntDistance();       /*度量计算测试函数*/
   ConstructSolution();
   SearchBestPath2();   
  // printf("\nsteps:%d\n",GetBestPathSteps());
  //TestAnts();
  //print_path (destnodeid);
  // print_path (destnodeid);
   UpdateLocalTPTPheromone();
  // totalchange=1;
   //PrintOutTest();
  // getchar();
   if(deadants!=num_ants)
   UpdateGlobalTPheromone2();
   //PrintOutTest();
  // getchar();
   dist[i]=bestDistance;
   Empty_Ants_Memory();
  //printf("deadants:%d\n",deadants);
/*ConstructSolution();*/
 //  AdaptiveACO();  
  // AllocateLocalSearchAnts();
   //TestAllocated();
   firstrun=0;
   if(totalchange>MaxTurn){
      printf("totalnum:%d,\n",i);
      break;
   }
   //ClearPH();
  // print_path (destnodeid);
}
//AllocateLocalSearchAnts();
//TestAllocated();
//TestPrintBestPath();
//TestNodes(); 
print_path (destnodeid);
/*
printf("\n:convergence:");
rdfile=fopen(rdata_file,"w");
fprintf(rdfile,"%d",sourcenodeid);
fprintf(rdfile,"%c",32);
fprintf(rdfile,"%d",destnodeid);
fprintf(rdfile,"%c",13);
k=i;
for(i=0;i<k;i++){
    printf("%d->",dist[i]);
	fprintf(rdfile,"%d",dist[i]);
	fprintf(rdfile,"%c",44);
}
fprintf(rdfile,"%c",13);
fprintf(rdfile,"%d",k);*/


//PringOutBestPath();
totalpath+=bestDistance;
printf(" distance: %.10f\n",bestDistance);
bestDistance=0;
totalchange=0;
totaltime=totaltime+elapsed_time( VIRTUAL );
}
printf("took %.10f seconds\n",totaltime/TestNum);
printf(" avrpath %.10f\n",totalpath/TestNum);
getchar();
}

/***************所有节点初始化函数 ******************************/
void InitNodes(){
   FILE *vn_file;
   RNode *p;
   TRNODE * q, *head;   
   int i=0,tCount,j;
   float rnode_rx,rnode_ry,TWeight;
   int nextnodeid;
   head=NULL,q=NULL;
   vn_file=fopen(vn_file_name,"r");
   if(vn_file==NULL){
      printf("file open error\n");
      exit(1);
   }
   else{
      for(;i<maxnodes;i++){
         p=&rNodes[i];
         if(fscanf(vn_file,"%f",&rnode_rx)<0)
                exit(1);
         if(fscanf(vn_file,"%f",&rnode_ry)<0)
                exit(1);
         p->RNodeid=i;
         p->RX=rnode_rx;
         p->RY=rnode_ry;
		 p->bestnodepath=NULL; 
		 p->bestnodepathdistance=0;        /******节点路径初始化为0*********/
		 p->prevnodeid=NONE;               /**********所有节点初始化为NONE*******/
		// p->firstPtrnode=NULL;
        /* printf("%f",p->RX);*/
       /*  printf("%f",p->RY);     */           
         fscanf(vn_file,"%d",&tCount);     
       /*  printf("%d",tCount);  */     
         if(tCount==0){                                            
                  p->firstTRNode=NULL;
                  continue;                 
         }
         else{
               for(j=0;j<tCount;j++){
                    q=malloc(sizeof(TRNODE));              
                    fscanf(vn_file,"%d",&nextnodeid);
                    fscanf(vn_file,"%f",&rnode_rx);
                    fscanf(vn_file,"%f",&rnode_ry);    
                    fscanf(vn_file,"%f",&TWeight);
                    q->RNodeid=nextnodeid; 
                    q->RX=rnode_rx;
                    q->RY=rnode_ry;
                    q->TWeight=TWeight;
                    q->TPheromone=AvePh;     /*所有路径信息素初始化为*/
                    q->nextTRNode=NULL;
                    if(j==0)
                        p->firstTRNode=q;                  
                    else
                        head->nextTRNode=q;
                   /* printf("%d",q->RNodeid);*/
                  /*  printf("%f",q->RX);*/
                    head=q;                  
               }
                           
         }         
      } 
     /* printf("\nnumber:%d\n",i);     */
   }      
}
/********************输入检测函数*****************************************/
long CheckInput(){
   int sourcenodeid;
   RNode *rnode;
   int flag=1;
   //flag=0;
   while(flag){
	  printf("请输入源地址编号:");
      scanf("%d",&sourcenodeid);
      printf("请输入目标节点编号:");
      scanf("%d",&destnodeid);
	  if(sourcenodeid!=destnodeid&&!(sourcenodeid<0||sourcenodeid>=maxnodes)&&!(destnodeid<0||destnodeid>=maxnodes))
		  flag=0;
   }
  // sourcenodeid=2,destnodeid=5;
   //printf("%d,%d",sourcenodeid,destnodeid);
   return sourcenodeid;
}
/*********************目标参数获取函数**************************/
void GetDestPar(){
	RNode *rnode;
	rnode=rNodes+destnodeid;
    destrx=rnode->RX,destry=rnode->RY;
	//printf("destnodeid:%f,%f",destrx,destry);
}
/**********************所有蚂蚁初始化函数,********************************/
void InitAnts(long firnodeid,long turnodeid){
     int i=0,j=0;     
     ant_struct *ant;
     VNODES *firNode;
     /*printf("%d\n",turnodeid);*/
     for(;i<num_ants;i++){        
        ant=ants+i;
        firNode=malloc(sizeof(VNODES));    
        firNode->vnodeid=firnodeid;
        firNode->nextVnode=NULL;
        ant->nodes_visited=firNode;
        ant->curNode=firNode;
        ant->terminate=0;
        ant->turNode=turnodeid;     
		ant->localstep=0;
		ant->antcurrentpathdistance=0;
		ant->lastnodeid=firNode->vnodeid;         /*******初始访问节点登入********/
		for(j=0;j<maxnodes;j++)
		    ant->visitedflag[j]=0;
    }
}
void Empty_Ants_Memory(){       /*释放蚂蚁记忆空间*/
	int i=0;
	VNODES *vnode,*q;
	for(i=0;i<num_ants;i++){
		//(ants+i)->terminate=0;
		vnode=(ants+i)->nodes_visited;
		q=vnode;
		if(vnode!=NULL){
		  while(vnode->nextVnode!=NULL){
			   vnode=vnode->nextVnode;
			   free(q);
			   q=vnode;
		  }
		}
		free(q);
		//q=(ants+i)->curNode;
	//	free(q);
		(ants+i)->nodes_visited=NULL;
	}
}
void EmptyOneantMemory(int oneant){
	VNODES *vnode,*q;
	(ants+oneant)->terminate=0;
    vnode=(ants+oneant)->nodes_visited->nextVnode;	
	q=vnode;
	if(vnode!=NULL){
		while(vnode->nextVnode!=NULL){
			vnode=vnode->nextVnode;
			free(q);
			q=vnode;
		}
	}
	free(q);
	(ants+oneant)->nodes_visited->nextVnode=NULL;
	(ants+oneant)->curNode=(ants+oneant)->nodes_visited;
	(ants+oneant)->localstep=0;
}