tfp.cpp

本程序是基于Visual C++6.0平台采用C语言开发的求解铁路上无任何约束条件下技术站单组列车编组计划的双亲遗传算法源程序。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define N          8          /*站点个数*/
#define M          200      /*当连续M代没有优化时加入新个体*/
#define popsize    600        /*种群大小*/
#define maxgen     3000    /*最大代数*/
#define avavehicle 50         /*平均编组辆数*/

struct   individual                    /*  个体  */
     {
       int         chrom[85];          /*  染色体 */
       float       fitness;            /*  个体适应度  */
	   float       jijie;              /*集结耗费*/
	   float       gaibian;            /*改编耗费*/
	   float       xdfit;              /*计算相对适应度*/
	   float       xdfits;             /*计算相对适应度范围起点*/
	   float       xdfitf;             /*计算相对适应度范围终点*/
     }; 
struct   individ                   
     {
       int         chrom[85];          
       int         vehflow[N][N+1];  
       float       fitness;            
	   float       jijie;              
	   float       gaibian;           
 
     }; 


struct   individual      *oldpop;                           /*  当前代种群  */
struct   individual      *newpop;                           /*  新一代种群  */
struct   individ         bestever;                          /*   最佳个体   */   

int     generation;          /*记录最佳个体所处代数*/
int     chromnum[29];        /*第一个不计入，记录染色体所分的28个编码块中每个编码块的大小*/
int     chromsx[29];         /*记录每一个编码块对应染色体中的第几位*/
int     sx[N];               /*记录第i个车站在染色体中的位置*/
float   totalfit;            /*统计种群中所有个体的总适应度*/
float   jijie2[8]={0};       /*记录集结参数*/
float   gaibian2[8]={0};     /*记录无改编节省*/
int     flow[N][N+1];        /*记录原始车流量*/
int     flowcg[N][N+1];      /*个体最终车流量*/
int     statnum[85]={0};     /*染色体中对应车站编号*/
long int  nochange;          /*最优解连续不变化的代数*/
float    pcross=0.7;
float   pmutation=0.3;
int     flag=0;
int     flag1=0;
int     vehf[N*(N-1)+1][3]={0};       /*记录车站1-7出发的列车起点、终点、车流量*/


void    inputdata();
void    calculate();
void    initialize();
void    initmalloc();
void    initpop(); 
void    calculfit(struct   individual   *critter);
void    evaluat(struct  individual *pop,int gen);
void    selection();
void    mutation();
void    crossover();
int     randab(int a, int b);
float   rand01();
void    evaluat(struct  individual *popu,int gen1);
void    gxchromsx();
float   pcr(int,int);
float   pmr(int);
void    ddjc();
void    sdjc();
void    zsyjc(int);
void    check();


void main()
{ 
	clock_t start; 
	clock_t end; 
    start = clock(); 
	double time;
    struct individual *temp;
    int i,j,k;
	long int t;
	FILE *fp;

	inputdata();
    calculate(); 
	initialize();/*初始化，分配空间，初始化种群,计算适应度*/
    evaluat(oldpop,0);/*适应度排序*/

	for(i=1;i<85;i++)
		bestever.chrom[i]=oldpop[0].chrom[i];
	bestever.fitness=oldpop[0].fitness;
	bestever.jijie=oldpop[0].jijie;
	bestever.gaibian=oldpop[0].gaibian;
	for(i=1;i<84;i++)
		bestever.chrom[i]=oldpop[0].chrom[i];
	for(j=1;j<N;j++)
		for(k=1;k<N+1;k++)
			bestever.vehflow[j][k]=flowcg[j][k]; 

    fp=fopen("bestever.txt","w+");
    for(t=1;t<=maxgen;t++)
	{
	 	selection();
		crossover();
        mutation();
        check();

		totalfit=0;
        for(j=0;j<popsize;j++)  
			calculfit(&(newpop[j]));
   		evaluat(newpop,t); 

		if(bestever.fitness>newpop[0].fitness)
	   {
		 bestever.fitness=newpop[0].fitness;
		 bestever.jijie=newpop[0].jijie;
		 bestever.gaibian=newpop[0].gaibian;
		 for(i=1;i<85;i++)
			 bestever.chrom[i]=newpop[0].chrom[i];
		 for(j=1;j<N;j++)
			 for(k=1;k<N+1;k++)
				 bestever.vehflow[j][k]=flowcg[j][k]; 
	     generation=t;
	   }
        nochange=t-generation;
		flag=nochange;
		flag1=nochange;
        end=clock();
		time=(float)(end-start)/CLOCKS_PER_SEC;
        printf("   %ld   %ld  %ld  %g  %g  %g   %g \n",t,generation,nochange,bestever.fitness,bestever.gaibian,bestever.jijie,time);
		temp=oldpop;
		oldpop=newpop;
		newpop=temp;
		fprintf(fp," %g \n",bestever.fitness);
	}
 fclose(fp);

  printf("最佳个体:\n");
      printf("%d  %f  %f   %f \n",generation,bestever.fitness,bestever.jijie,bestever.gaibian);
 
 for(i=1;i<N;i++)
  {
	  for(j=1;j<N+1;j++)
		  printf("%d ",bestever.vehflow[i][j]);
	  printf("\n");
  } 
	  for(i=1;i<85;i++)
		  printf("%d---",bestever.chrom[i]);

 fp=fopen("best.txt","w+");
 fprintf(fp,"适应度值:");
 fprintf(fp," %g ",bestever.fitness);
 fprintf(fp,"集结耗费:");
 fprintf(fp," %g ",bestever.jijie);
 fprintf(fp,"改编耗费:");
 fprintf(fp," %g ",bestever.gaibian);
 fprintf(fp,"\n染色体\n");
 for(i=1;i<85;i++)
     fprintf(fp,"%d  ",bestever.chrom[i]);
 fprintf(fp,"\n");
 fprintf(fp,"车流\n");
 for(i=1;i<N;i++)
	 {
		 for(j=1;j<N+1;j++)
			 fprintf(fp,"%d   ",flowcg[i][j]);
         fprintf(fp,"\n");
	 }
 fprintf(fp,"所耗时间: ");
 fprintf(fp," %g\n",time);
 fclose(fp);

}   
   
void inputdata()              /*从文件读入数据到相应存储单元*/
{
 int  i,j;
 FILE *fp;

 fp=fopen("data.txt","r+");
 if(fp==NULL) 
  {
	 printf("不能打开data.txt文件!\n");
     return;
  }
 else
  {
	 for(i=0;i<29;i++)
        fscanf(fp,"%d",&chromnum[i]);        /*读入每个编码段的编码位数到数组中*/
     for(i=0;i<7;i++)
	    fscanf(fp,"%f",&jijie2[i+1]);         /*车站1-7的集结参数存储到数组中*/
     for(i=0;i<7;i++)
	    fscanf(fp,"%f",&gaibian2[i+1]);       /*车站1-7的改编参数存储到数组中*/
	 for(i=1;i<85;i++)
        fscanf(fp,"%d",&statnum[i]);         /*染色体对应车站编号读入*/
  }
  fclose(fp);

  for(i=0;i<N;i++)
	 for(j=0;j<N+1;j++)
	 {
		 flow[i][j]=0;
	 }
 fp=fopen("vehicleflow.txt","r+");
 if(fp==NULL) 
  {
	 printf("不能打开vehicleflow.txt文件!\n");
     return;
  }
 else
  {
	 for(i=1;i<N;i++)
       for(j=1;j<N+1;j++)
         fscanf(fp,"%d",&flow[i][j]);
  }
  fclose(fp);
}



void calculate()                     /*计算染色体分块的编号起止号*/
{
  int i,j,sum;
  sum=0;
  for(i=N-1;i>0;i--)
  {
	 for(j=1;j<=i;j++)
		 sum+=j;
     sx[N-i]=sum;
  }
}

void   initialize()                /*遗传算法初始化*/
  {
   /*分配给全局数据结构空间*/
    initmalloc();
    /*初始化种群，并统计计算结果*/
    initpop();
  }

void    initmalloc()                /*为全局数据变量分配空间*/
  {
   unsigned    nbetys;
   char *str;
   /*  分配给当前代和新一代种群内存空间  */
   nbetys=popsize*sizeof(struct   individual);
   if((oldpop=(struct   individual   *)malloc(nbetys))==NULL)
   {
	   str="老一代种群";
	   printf("malloc:分配 %s 的内存空间不足!!\n",str);
   }
   if((newpop=(struct   individual   *)malloc(nbetys))==NULL)
   {
	    str="新一代种群";
		printf("malloc:分配 %s 的内存空间不足!!\n",str);
   }
   nbetys=sizeof(struct   individual);
   
}

void    initpop()                       /*  随机初始化种群  */
{ 
	int i,j,k,up,down;
	int flag2;

	totalfit=0;
    for(i=0;i<popsize;i++)
	{
		   gxchromsx();
		   for(j=0;j<85;j++)
			   oldpop[i].chrom[j]=0;
	       for(j=1;j<29;j++)/*染色体初始化*/
		   {
			 up=chromsx[j-1];
			 down=chromsx[j];
			 k=randab(up,down);/*可以产生(a,b]区间的整数*/
			 oldpop[i].chrom[k]=1; 
		   }

         calculfit(&(oldpop[i]));
		 flag2=0; 
		 for(j=1;j<85;j++)
			 flag2+=oldpop[i].chrom[j];
		 if(flag2!=28)
		 {
			 printf("oldpop error flag2=%d\n",flag2);
			 printf("number %d\n",i);
			 for(j=1;j<85;j++)
				 printf("%d--",oldpop[i].chrom[j]);
			 exit(1);
		 }
	} 
}

void calculfit(struct   individual   *critter)/*计算适应度*/
{
	int i,j,k,n,m;
	float jijie1=0.0;
	float gaibian1=0.0;
	int  a[7*N][4]={0};
	int   gbeachstat[8]={0};   /*记录每个车站改编车流量*/
    int   fache[8]={0};        /*记录各站发车数目*/
	int   temp[7]={0};         /*记录每个车站发车*/

	for(i=1;i<N;i++)
		for(j=1;j<N+1;j++)
			flowcg[i][j]=0;
	for(i=1;i<N;i++)
		for(j=1;j<N+1;j++)
			flowcg[i][j]=flow[i][j];

	k=0;
	n=2;
    for(i=1;i<=sx[1];i++)/*为第一个车站开出的列车*/
	    if(((*critter).chrom[i])==1)
		{
			a[k][0]=1;
			a[k][1]=statnum[i];
			a[k][2]=n;
			a[k][3]=flow[a[k][0]][a[k][2]];
			n=n+1;
			k=k+1;
	   }
	k=7;
	n=3;
    for(i=sx[1]+1;i<=sx[2];i++)/*为第二个车站开出的列车*/
	    if(((*critter).chrom[i])==1)
		{
			a[k][0]=2;
			a[k][1]=statnum[i];
			a[k][2]=n;
			a[k][3]=flow[a[k][0]][a[k][2]];
			n=n+1;
			k=k+1;
 	   }
	k=14;
	n=4;
    for(i=sx[2]+1;i<=sx[3];i++)/*为第三个车站开出的列车*/
	    if(((*critter).chrom[i])==1)
		{
			a[k][0]=3;
			a[k][1]=statnum[i];
			a[k][2]=n;
			a[k][3]=flow[a[k][0]][a[k][2]];
            n=n+1;
			k=k+1;
		}

	k=21;
	n=5;
    for(i=sx[3]+1;i<=sx[4];i++)/*为第四个车站开出的列车*/
	    if(((*critter).chrom[i])==1)
		{
			a[k][0]=4;
			a[k][1]=statnum[i];
			a[k][2]=n;
			a[k][3]=flow[a[k][0]][a[k][2]];
			n=n+1;
			k=k+1;
		}

	k=28;
	n=6;
    for(i=sx[4]+1;i<=sx[5];i++)/*为第五个车站开出的列车*/
	    if(((*critter).chrom[i])==1)
		{
			a[k][0]=5;
			a[k][1]=statnum[i];
			a[k][2]=n;
			a[k][3]=flow[a[k][0]][a[k][2]];
			n=n+1;
			k=k+1;
		}
		
	k=35;
	n=7;
    for(i=sx[5]+1;i<=sx[6];i++)/*为第六个车站开出的列车*/
	    if(((*critter).chrom[i])==1)
		{
			a[k][0]=6;
			a[k][1]=statnum[i];
			a[k][2]=n;
			a[k][3]=flow[a[k][0]][a[k][2]];
			n=n+1;
			k=k+1;
		}

	k=42;
	n=8;
    for(i=sx[6]+1;i<=sx[7];i++)/*为第七个车站开出的列车*/
	    if(((*critter).chrom[i])==1)
		{
			a[k][0]=7;
			a[k][1]=statnum[i];
			a[k][2]=n;
			a[k][3]=flow[a[k][0]][a[k][2]];
 			n=n+1;
			k=k+1;
		}

/*每个车站改编车流计算*/
  for(i=6;i>=0;i--)
	  if(a[i][1]!=a[i][2])
	  {