aco2.c

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

	nodevnode->nextVnode=NULL;
	q=nodevnode,head=nodevnode;
    //xx=nodevnode->vnodeid;
	rnode->bestnodepath=head;
    vnode=vnode->nextVnode;
	while(vnode!=NULL){
         nodevnode=malloc(sizeof(VNODES));
		 nodevnode->vnodeid=vnode->vnodeid;
		 nodevnode->nextVnode=NULL;
		 q->nextVnode=nodevnode;
		 q=nodevnode;
		 vnode=vnode->nextVnode;
	} 
	//rnode->bestnodepath=head;
	//printf("  %d xx",head->vnodeid); 
	rnode->bestnodepathdistance=ant->antcurrentpathdistance;
	//ant->antcurrentpathdistance=rnode->bestnodepathdistance;
//	ant->curNode=q;
}
/*******************概率计算函数*********************************/

float CalculateTotal3(float posspar[][6],int num){           /*启发式因子重新修整比较 仿TSP启发因子比较*/
	float allpossibility=0,heur;
	int i=0,j;
	for(i=0;i<num;i++){
		heur=posspar[i][4];//+sqrt((destrx-posspar[i][2])*(destrx-posspar[i][2])+(destry-posspar[i][3])*(destry-posspar[i][3]));
        //printf("%f\n",heur);
		totalpossibility[i]=pow(posspar[i][5],alpha)*pow(1000/heur,beta);   //此计算式子有待斟酌
			  allpossibility= totalpossibility[i]+allpossibility;
			  //printf("%f\n",allpossibility);
              
    }
	 for(i=0;i<num;i++){
		 totalpossibility[i]/=allpossibility;
		 //printf("route%d:%f",i,totalpossibility[i]);
		 //***********************扰动信号***********************//
		/* if(totalchange>=NestTurn&&totalchange<MidTurn){
             for(j=NestTurn;j<=totalchange;j++)
                totalpossibility[i]=totalpossibility[i]-(totalpossibility[i]-1/num)/(MidTurn-j+1);
		 }
         //test
        /*****************************邻域搜索******************************/
		/* if(totalchange>=NestTurn){
			 if(NeiSearch>ran01(&seed)){
                 //for(j=NestTurn;j<=totalchange;j++)
                     //totalpossibility[i]=totalpossibility[i]-(totalpossibility[i]-1/num)/(MidTurn-j+1);
					 totalpossibility[i]=1/num;
			 }    
		 }         
         //printf("route%d:%f",i,totalpossibility[i]); //test
	 }
       //	printf("\ntotal:%f",allpossibility);*/
	 }
    return i;

}


/*************************蚂蚁移动终止条件 1.移动到终点 2.无路可走（由于单向行驶或禁止转弯引起)或此蚂蚁搜索时间过大（解太差引起)**************************************/
int AntMoveTerminate(int oneant){
       
}
void ClearPH(){
	TRNODE *trnode;
	RNode *rnode;
    if(!onceflag){
		if(totalchange>NestTurn){
	        int i;
	        for(i=0;i<maxnodes;i++){
		       rnode=(rNodes+i);
			   for(trnode=rnode->firstTRNode;trnode!=NULL;trnode=trnode->nextTRNode)
				   trnode->TPheromone=MinPh;         
			}
	        onceflag=1;
		}
	}
}
/*************************搜索一次迭代后最优路径函数********************************/
void TestPrintBestPath(){
	RNode *rnode;
	long i;
	for(i=destnodeid,rnode=rNodes+i;rnode->prevnodeid!=NONE;i=rnode->prevnodeid,rnode=rNodes+i)
		printf("%d->",rnode->prevnodeid);	
}


void SearchBestPath2(){
	int ischange=0;
	VNODES *p,*q;
    if(bestDistance==0||bestDistance>(rNodes+destnodeid)->bestnodepathdistance){
		ischange=1;
		bestDistance=(rNodes+destnodeid)->bestnodepathdistance;
	}
	if(ischange)
		totalchange=0;
	else
		totalchange++;
}



void SearchBestPath(){
   int ischange=0;
   int i,bestAntNum=0;
   VNODES *p,*q;//*q;
   float antDistance=0;
   for(i=0;i<num_ants;i++){
        p=(ants+i)->nodes_visited;
	  /*  printf("ant%d  ",i);
        for(;p!=NULL;p=p->nextVnode)
	       printf("%d->",p->vnodeid);*/
        //if((ants+i)->terminate==1){
       //     antDistance=oneAntPathDistance(i);
		  	//printf("%f",antDistance);
      // }	    
	   if((ants+i)->terminate==1){
		    // printf("成功达到");
            if(bestDistance==0||bestDistance>(ants+i)->antcurrentpathdistance){
		        ischange=1;
                bestDistance=(ants+i)->antcurrentpathdistance;
                bestAntNum=i;
		      //  printf("%d\n",bestAntNum);
            }
       }
	   else
	    	;//printf("无路可走");	
	  /* printf("\n");*/
   }    
  // printf("\n目前最短距离:%f\n",bestDistance);
   if(ischange){      
      p=bestPath;
	  q=p;
	  if(p!=NULL){
        while(p->nextVnode!=NULL){
		   p=p->nextVnode;
           free(q);
		   q=p;
		}
		free(q);
	  }
      bestPath=(ants+bestAntNum)->nodes_visited;   /*最佳路径指针定位在最佳蚂蚁访问路径*/
      (ants+bestAntNum)->nodes_visited=NULL;       /*最佳蚂蚁路径必须脱离链表，否则会在下一次迭代中被冲掉*/
      totalchange=0;
   }
   else
	      totalchange++;
}    
void AllocateLocalSearchAnts(){ //得到经过制定循环次数后 得到最佳路径城市 分配蚂蚁到每一个城市点 进行邻域搜索
    VNODES *p,*q,*head;
	int i,BestPathSteps,j,turid;
	BestPathSteps=GetBestPathSteps()-1;
	q=bestPath;
	//for(;q!=NULL;q=q->nextVnode)
	//	printf("%d->",q->vnodeid);
	if(q==NULL)
		return;
	for(i=0;i<num_ants;i++,allocatedstepid=(++allocatedstepid)%BestPathSteps){
        q=bestPath;
		p=malloc(sizeof(VNODES));
		p->vnodeid=q->vnodeid;
	    p->nextVnode=NULL;
		(ants+i)->nodes_visited=p;
		head=(ants+i)->nodes_visited;
		q=q->nextVnode;
		for(j=0;j<allocatedstepid&&q!=NULL;j++,q=q->nextVnode){
		     p=malloc(sizeof(VNODES));
		     p->vnodeid=q->vnodeid;
			 p->nextVnode=NULL;
			 head->nextVnode=p;
			 head=p;
			 if(j==(allocatedstepid-2))
				 (ants+i)->turNode=p->vnodeid;
		}
		if(allocatedstepid==1)
              (ants+i)->turNode=sourcenodeid;
		(ants+i)->terminate=0;
		(ants+i)->curNode=head;
	//	printf("antcur:%d\n",(ants+i)->curNode->vnodeid);
	} 
}
void TestAllocated(){
	int i;
	VNODES *p;
	for(i=0;i<num_ants;i++){
		p=(ants+i)->nodes_visited;
		for(;p!=NULL;p=p->nextVnode){
			printf("%d->",p->vnodeid);
		}
		printf("\n");
	}
}

int GetBestPathSteps(){
    VNODES *p;
	int stepcount=0;
	p=bestPath;
	while(p!=NULL){
		stepcount++;
		p=p->nextVnode;
	}
	return stepcount-1;
}
	
/********************************计算蚂蚁访问的路径度量*********************************/ 
float oneAntPathDistance(int oneant){
      TRNODE *trnode;
      RNode *rnode;
      VNODES *fvnode,*nvnode;
      long nodeid;
      float antdistance=0;
      fvnode=(ants+oneant)->nodes_visited;
      nvnode=fvnode->nextVnode;      
      for(;nvnode!=NULL;fvnode=nvnode,nvnode=nvnode->nextVnode){
         nodeid=nvnode->vnodeid;  
         rnode=rNodes+(fvnode->vnodeid);
         trnode=rnode->firstTRNode;
         for(;trnode->RNodeid!=nodeid&&trnode!=NULL;trnode=trnode->nextTRNode);{
         antdistance=antdistance+trnode->TWeight;
		// printf("%f->",trnode->TPheromone);//test
		 }
      }   
	 // printf("\n");//test
      return antdistance;    
}  
void PringOutBestPath(){
/*	VNODES *vnode;
	vnode=bestPath;
	while(vnode!=NULL){
		printf("%d->",vnode->vnodeid);
		vnode=vnode->nextVnode;
	}*///test
	bestDistance=(rNodes+destnodeid)->bestnodepathdistance;
	if(bestDistance==0)
		printf("no way!!!");
	else{
	    printf("distance:%f",bestDistance);
		totalpath=totalpath+bestDistance;
	}
}
/***********************检测是否存在直接路径****************************************/
int CheckDirPath(long firnode,long destnode){
     TRNODE *p;
     /*printf("%d",destnode);*/
     p=(rNodes+firnode)->firstTRNode;
     for(;p!=NULL&&p->RNodeid!=destnode;p=p->nextTRNode);
     if(p!=NULL){
          printf("The shortest path:%d->%d,distance:%f\n",firnode,destnode,p->TWeight);
          printf("%d",destnode);
          printf("%f",p->TWeight);
		  return 1;
     }
	 return 0;
}     
/********************************蚂蚁路径度量测试函数************************************/         
void TestAntDistance(){
    VNODES *p,*head;
    head=ants->nodes_visited;
    p=malloc(sizeof(VNODES));
    p->vnodeid=3;
    p->nextVnode=NULL;
    head->nextVnode=p;
    head=p;
    p=malloc(sizeof(VNODES));
    p->vnodeid=5;
    p->nextVnode=NULL;
    head->nextVnode=p;
    head=p;
    p=malloc(sizeof(VNODES));
    p->vnodeid=4;
    p->nextVnode=NULL;
    head->nextVnode=p;
    head=p; 
   /* printf("%f\n",oneAntPathDistance(0));
    for(head=ants->nodes_visited;head!=NULL;head=head->nextVnode)
        printf("%d\n",head->vnodeid);*/
}      
     
/*蚂蚁初始化信息测试函数*/
void TestAnts(){
    ant_struct *ant;
    int i;
	VNODES *head;
    ant=ants;
    /*printf("tur:%d\n",ant->turNode);*/
    head=ant->nodes_visited;
	for(i=0;i<num_ants;i++){
		ant=ants+i;
	    printf("ant%d:",i);
		head=ant->nodes_visited;
		for(;head!=NULL;head=head->nextVnode)
			printf("%d->",head->vnodeid);
		printf("\n");
	}
    /*printf("cur:%d\n",head->vnodeid);*/
}
    
/**********************节点信息测试函数**********************************/
void TestNodes(){
      TRNODE *p;
      RNode *head; 
	  int i;
      head=rNodes;
     // p=head->firstTRNode;
	  head=head+sourcenodeid;
      printf("%d--",head->prevnodeid);
	  head=rNodes;
	  head=rNodes+destnodeid;
      printf("%d--",head->prevnodeid);
	  head=rNodes+head->prevnodeid;
	  printf("%d--",head->prevnodeid);
	  head=rNodes+head->prevnodeid;
	  printf("%d--",head->prevnodeid);
	  head=rNodes+head->prevnodeid;
	  printf("%d--",head->prevnodeid);
	  	  head=rNodes+head->prevnodeid;
	  printf("%d--",head->prevnodeid);
	  head=rNodes+(head->prevnodeid);
	  printf("%d--",head->prevnodeid);
      
      head=rNodes+(sourcenodeid);
	  printf("  try: %d--%d",head->prevnodeid,sourcenodeid);

      /*

	  while(head->prevnodeid!=NONE){		     
	         printf("%d--",head->prevnodeid);
			 head=rNodes+(head->prevnodeid);
	  }
			
          /*printf("%d\n",p->RNodeid);*/
		   
}
 
 void print_path (int nodeid)
 {
   if ((rNodes+nodeid)->prevnodeid!= NONE)
   {
     print_path((rNodes+nodeid)->prevnodeid);
   }
   printf ("%d->", nodeid);
 }
 
    
/*****************************0-1随机数生成函数*****************************/
double ran01( long *idum )
/*    
      FUNCTION:       generate a random number that is uniformly distributed in [0,1]
      INPUT:          pointer to variable with the current seed
     OUTPUT:         random number uniformly distributed in [0,1]
      (SIDE)EFFECTS:  random number seed is modified (important, this has to be done!)
      ORIGIN:         numerical recipes in C
*/{
  long k;
  double ans;
  k =(*idum)/IQ;
  *idum = IA * (*idum - k * IQ) - IR * k;
  if (*idum < 0 ) *idum += IM;
  ans = AM * (*idum);
  return 10*ans;
}                
/******************************************************************************/
/******************************挥发系数自适应算子****************************/
void AdaptiveACO(){
 if(totalchange>30)
	   ad_rho*=0.95;
   if(ad_rho<0.5)
	   ad_rho=0.5;
}
/*******************************************时间相关函数*******************/

void start_timers()
{
   start_time = clock();
}
double elapsed_time( type )
	TIMER_TYPE type;
{
   elapsed = clock()- start_time;
   return elapsed/CLK_TCK;/* / CLOCKS_PER_SEC;*/
}

void InitPenalty(){	
	int i,rnodeid,pcount,frnodeid,nrnodeid;//读取参数
	FILE *vn_file;
	PTRNODE *ptrnode,*head;
    vn_file=fopen("F:\\penalty.txt","r");
	if(vn_file==NULL){
          printf("file open error\n");
        exit(1);
	}
	while(fscanf(vn_file,"%d",&rnodeid)>0){
         fscanf(vn_file,"%d",&pcount);
		 head=NULL,ptrnode=NULL;
		 for(i=0;i<pcount;i++){
                    ptrnode=malloc(sizeof(PTRNODE));              
                    fscanf(vn_file,"%d",&frnodeid);
                    fscanf(vn_file,"%d",&nrnodeid);
                    ptrnode->frnodeid=frnodeid;
					ptrnode->nrnodeid=nrnodeid;
                    ptrnode->nextPtrnode=NULL;			        
                    if(i==0)
                        (rNodes+rnodeid)->firstPtrnode=ptrnode;                  
                    else
                        head->nextPtrnode=ptrnode;
                   /* printf("%d",q->RNodeid);*/
                  /*  printf("%f",q->RX);*/
                    head=ptrnode; 
		 }
	}
}
void testpenalty(){
	int i;
	PTRNODE *ptrnode;
	for(i=0;i<maxnodes;i++){
		printf("%d:",(rNodes+i)->RNodeid);
		for(ptrnode=(rNodes+i)->firstPtrnode;ptrnode!=NULL;ptrnode=ptrnode->nextPtrnode)
			printf("%d->%d **",ptrnode->frnodeid,ptrnode->nrnodeid);
	}
}