ant.cpp

蚂蚁算法又称蚁群算法

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "a.h"

void main()
{ 
 int i,j;
  srand((unsigned)time( NULL ));
  network();                             // generate a random network
  
a:printf("Set the source node:");        // set source node and destation node 
  scanf("%d",&sour_n);
  printf("\n");
  printf("Set the destation node:");
  scanf("%d",&dest_n);
  printf("\n");
  if(sour_n>=n||dest_n>=n||sour_n==dest_n)
	 {printf("Input error!\nInput again please:\n");
      goto a;
	 }
  
  if(dv[dest_n]>Jw)                       //  pass over the problem of delay jitter  
     {printf("system error!/n");
	  return;
     }
  
  for(i=1;i<n;i++)                       // delete the link whose bandwidth is not enough 
	  for(j=1;j<n;j++)
         if(bw[i][j]<Bw)
			{link[i][j]=0;
             cost[i][j]=0;
             ldl[i][j]=0;
             bw[i][j]=0;
			}

   for(i=1;i<n;i++)                       // initialization  of pheromone 
	  for(j=1;j<n;j++)
         if(link[i][j]==1)
            phero[i][j]=constant;
         else  phero[i][j]=0;
   printf("The initialization  of pheromone are:\n");
   for(i=1;i<n;i++)
		{for(j=1;j<n;j++)
		     printf("%-7.4f  ",phero[i][j]);
	     printf("\n");
		}
   
   rout();
}



void network()              // randomly generate a network
{int i,j,m;

 n=rand()%(N-7)+8;          // set the number of node range from  8 to N
 printf("The number of nodes is%4d\n",n-1);
 for(i=1;i<n;i++)
	{ndl[i]=rand()%2+1;    //the delay of nodes range from 1 to 2
     dv[i]=rand()%4;       //the delay variration of nodes range from 0 to 3
     m=rand()%6+1;          
     lr[i]=exp(m);         //the loss rate of nodes range from 1e-1 to 1e-6
	}
 printf("The delay of nodes are:\n");
 for(i=1;i<n;i++)
	 printf("%4d",ndl[i]);
 printf("\n");
 printf("The delay variration of nodes are:\n");
 for(i=1;i<n;i++)
	 printf("%4d",dv[i]);
 printf("\n"); 
 printf("The loss rate of nodes are:\n");
 for(i=1;i<n;i++)
	 printf("%7.6f  ",lr[i]);
 printf("\n");
 
 for(i=1;i<n;i++)
	 for(j=i;j<n;j++)
         if(i!=j) 
			{link[i][j]=rand()%2;
		     cost[i][j]=(rand()%3+1)*link[i][j];   //the cost of links range from 1 to 3
			 bw[i][j]=(rand()%8+8)*10*link[i][j];  //the bandwidth of links range from 80 to 150
             ldl[i][j]=(rand()%3+1)*link[i][j];    //the delay of links range from 1 to 3
			}
         else link[i][j]=0;
 for(i=1;i<n;i++)
	 for(j=1;j<i;j++)
		{link[i][j]=link[j][i];
         cost[i][j]=cost[j][i];
		 bw[i][j]=bw[j][i];
		 ldl[i][j]=ldl[j][i];
		}
 printf("\nThe links of network are:\n");
 for(i=1;i<n;i++)
	{for(j=1;j<n;j++)
        printf("%6d",link[i][j]);
	    printf("\n");
	}
 printf("\nThe cost of links are:\n");
 for(i=1;i<n;i++)
	{for(j=1;j<n;j++)
        printf("%6d",cost[i][j]);
	 printf("\n");
	}
 printf("\nThe bandwidth of links are:\n");
 for(i=1;i<n;i++)
	{for(j=1;j<n;j++)
        printf("%6d",bw[i][j]);
	 printf("\n");
	}
 printf("\nThe delay of links are:\n");
 for(i=1;i<n;i++)
	{for(j=1;j<n;j++)
        printf("%6d",ldl[i][j]);
	 printf("\n");
	}
} 
double exp(int x)             // exp -- index is x
{int i;
 double a=1.0;
 for(i=0;i<x;i++)
     a=(double)(a*0.1);
 return(a); 
}		 



void rout()
{ int i,j,k,t,a,b;
  int current_n=0;
  int next_n=0;

  int temp[N][N]={0};
  double m[N]={0};
  double p[N]={0};
  double sum_ph=0;
  double F[M+1]={0};
  
  
  for(t=0;t<=T;t++)
	{for(i=1;i<=M;i++)
b:		{path[i][1]=sour_n;
		 current_n=sour_n;
		 
		 for(j=1;j<n;j++)                            // intitalize optional path 
		    for(k=1;k<n;k++)
				temp[j][k]=link[j][k];

			
		  for(j=2;j<n;j++)
			{		
			  for(k=1;k<n;k++)
				{
			     if(temp[current_n][k]==1)
				   m[k]=phero[current_n][k];    // adjust of pheromone 
				 else m[k]=0;
				
				}
             sum_ph=SUM(m);                      // sum of pheromone 
			 if(sum_ph==0) 
				{ 
				 goto b;
				}                               // if no path,how to deal with 
			 for(k=1;k<n;k++)
				{p[k]=m[k]/sum_ph;          	// select propability 
				}  
			 next_n=CHOOSE(p);
			 for(k=1;k<n;k++)                   // avoid cycle
				{temp[current_n][k]=0;
			     temp[k][current_n]=0;
				}
             current_n=next_n;
             path[i][j]=current_n;
			 if(path[i][j]==dest_n) break;
		    }
	
		path[i][j]=dest_n;
		j++;

        for(;j<n;j++)
			 path[i][j]=0;       	                  // if no situable path,send another ant 
	    COST_F(path[i]);
        
		if((path[i][n-1]==0||path[i][n-1]==dest_n)&&s1>0&&s2>0)
			{ F[i]=COST_F(path[i]);
			   for(j=1;j<n-1;j++)
					{a=path[i][j];
					 b=path[i][j+1];
					 if(a!=0&&b!=0)
					    phero[a][b]=L_UPDATE(phero[a][b]);        // local update 
					}
			 }
        else i--; 
	}
   
  
  
    for(i=1;i<n;i++)
		for(j=1;j<n;j++)
			 phero[i][j]=phero[i][j]*(1-a1);

	i=OPTIMIZATION(F);
	for(j=1;j<n-1;j++)
		{ a=path[i][j];
		  b=path[i][j+1];
		  if(a!=0&&b!=0)
			  phero[a][b]=G_UPDATE(phero[a][b],F[i]);         // global update
		}

    printf("The pheromone of every paths are:\n");
         for(i=1;i<n;i++)
			{for(j=1;j<n;j++)
			    printf("%-7.4f  ",phero[i][j]);
		     printf("\n");
			}
		 getchar();
	     printf("The number %d is:\n",t+1);	
	     for(i=1;i<=M;i++)
			{for(j=1;j<n;j++)
				 if(path[i][j]!=0)
					{printf("%d",path[i][j]);
					 printf("---");
					}
				else break;
		     printf("\n");
			}
		 getchar();
	}
}
double SUM(double x[N])       // double array summing 
{ int i;
  double t=0;
  for(i=1;i<n;i++)
      t=x[i]+t;
  return(t);
}
int CHOOSE(double x[N])      // choose the next node 
{ int k=1,s;
  double e,d,r[N];
  d=0.0;
  r[0]=0.0;
  do
	 {d=d+x[k];
	  r[k]=d;
	  k++;
	 }while (k<n);
  
  e=(double)rand()/(double)RAND_MAX;
  for(k=1;k<n;k++)
	  if(r[k-1]<e&&e<=r[k]&&x[k]!=0)
		{s=k;
		 break;
		}
	  else s=1;
	  return(s);
}
double L_UPDATE(double x)     // local update  
{
  x=(1-a0)*x+a0*cons;
  return(x);
}
double G_UPDATE(double x, double z)    // global update 
{
  x=x+a1*z;
  return(x);
}
double COST_F(int x[N])           // cost function 
{ int i,a,b;
  int cos=0;
  int z1=0;
  int z2l=0;
  int z2n=0;
  double s=1.0;
  double z3=1.0;
  for(i=1;i<n-1;i++)
	  { a=x[i];
		 b=x[i+1];
		 if(a!=0&&b!=0)
			{cos=cos+cost[a][b];
			 z1=z1+bw[a][b]-Bw;
			 z2l=z2l+ldl[a][b];
			}
	  }
  for(i=2;i<n;i++)
	  { a=x[i];
		 if(a!=dest_n)
			{ z2n=z2n+ndl[a];
			  z3=z3*(1-lr[a]);
			}
	  }
  s1=Dw-z2l-z2n;         
  s2=z3-(1-Lw);          
  s=cos/(A*z1+B*s1+C*s2);
  return(s);
}
int OPTIMIZATION(double x[M+1])   // select the shortest path 
{ int i,j=0;
  double y;
  y=x[1];
  for(i=1;i<=M;i++)
	 if(y<=x[i])
		{y=x[i];
	   	 j=i;
		}
  return(j);
}