ga.c

本程序是由C语言编写的遗传算法源程序

#include   <stdio.h>   
#include   <math.h> 
/*  全局变量  */
struct   individual                                             /*  个体  */
     {
       int      *chrom;                                         /*  染色体  */
       double      fitness;                                /*  个体适应度  */
       double       cfitness;                          /*  个体适应度转化值  */
       double       totalcost;                           /*  个体的总成本  */
     };

struct   bestever                                           /*  最佳个体  */
    {   
       int       *chrom;                               /*  最佳个体染色体  */
       double    fitness;                            /*  最佳个体适应度  */
       double    cfitness;                        /*  最佳个体适应度转化值  */
       double       totalcost;                       /*  最佳个体的总成本  */
       int    generation;                             /*  最佳个体生成代  */
     };

struct   individual      *oldpop;                           /*  当前代种群  */
struct   individual      *newpop;                           /*  新一代种群  */
struct   bestever   bestfit;                               /*   最佳个体   */   
struct   bestever   finalresult;               
double   sumfitness;                                           /*  种群中个体适应度累计  */
double   sumcfitness;                                   /*  种群中个体适应度转化值的累计  */
double   max;                                                 /*  种群中个体最大适应度  */
double    avg;                                                    /*  种群中个体平均适应度  */
double   min;                                                    /*  种群中个体最小适应度  */
float    pcross;                                            /*  交叉概率  */
float    pmutation;                                       /*  变异概率  */ 
int    popsize;                                          /*  种群大小  */
int    lchrom;                                            /*  染色体长度  */
int    gen;                                                /*  当前世代数  */
int    maxgen;                                              /*  最大世代数  */
int    run;                                              /*  当前运行次数  */
int    maxruns;                                         /*  总运行次数  */
int    nmutation;                                   /*  当前代变异发生次数  */
int    ncross;                                       /*  当前代交叉发生次数  */
int    m;                                         /*  侯选仓库的总个数  */
int    n;                                         /*  需求点的总个数  */

/*   随机数发生器使用的静态变量  */   
static   double   oldrand[55];   
static   int   jrand;   
static   double   rndx2;   
static   int   rndcalcflag;
/*  输出文件指针  */
FILE  *outfp1,*outfp2,*outfp3;
/*  函数定义  */
void   intitialize();
void   initdata();
void   initmalloc();
void   freeall();
void   nomemory();
void   initpop();
void   statistics(struct  individual *);
void   findbest(struct  individual  *);
void   generation();
void   preselect();
int   select();
float   randomperc();
int    flip(float);
void   crossover(int *,int *,int *,int *);
void    mutation(int *);
void    objfunc(struct   individual  *);
void   changeobj(struct   individual  *);
void    report();
void   skip(FILE *,int);
void   advance_random();   
int    flip(float);
int    rnd(int,   int);   
void    randomize();   
double  randomnormaldeviate();   
float   randomperc(),rndreal(float,float);   
void   warmup_random(float);   



void   initialize()                /*遗传算法初始化*/
{
/*键盘输入遗传算法参数*/
initdata();
/*分配给全局数据结构空间*/
initmalloc();
/*   初始化随机数发生器   */   
randomize();   
/*初始化全局计数变量和一些数值*/
nmutation=0;
ncross=0;
bestfit.fitness=finalresult.fitness=0;
bestfit.cfitness=finalresult.cfitness=0;
bestfit.totalcost=finalresult.totalcost=0;
bestfit.generation=finalresult.generation=0;
/*初始化种群，并统计计算结果*/
initpop();
findbest(oldpop);
}

void    initdata()                       /*  遗传算法参数输入  */
{  
      printf("键盘输入侯选仓库的总个数和需求点的总个数\n");
      m=8;
      n=15;
      popsize=200;
      lchrom=n;
      maxruns=3;
      maxgen=300;
      pcross=0.9;
      pmutation=0.01;
   }


void    initmalloc()                     /*  为全局数据变量分配空间  */
{
   unsigned    nbetys;
   char     *malloc();
   int     j;
   /*  分配给当前代和新一代种群内存空间  */
   nbetys=popsize*sizeof(struct   individual);
   if((oldpop=(struct   individual   *)malloc(nbetys))==NULL)
        nomemory("oldpop");
   if((newpop=(struct   individual   *)malloc(nbetys))==NULL)
        nomemory("newpop");
   /*  分配给染色体内存空间  */
   nbetys=lchrom*sizeof(int);
   for (j=0;j<popsize;j++)
     {
        if((oldpop[j].chrom=(int   *)malloc(nbetys))==NULL)
      nomemory("oldpop  chromosomes");
        if((newpop[j].chrom=(int   *)malloc(nbetys))==NULL)
      nomemory("newpop  chromosomes");
      }
   if((bestfit.chrom=(int   *)malloc(nbetys))==NULL)
      nomemory("bestfit  chromosome");
   if((finalresult.chrom=(int  *)malloc(nbetys))==NULL)
      nomemory("finalresult  chromosome");
}


void      freeall()                        /*  释放内存空间  */
{
   int   i;
   for(i=0;i<popsize;i++)
      {
         free(oldpop[i].chrom);
         free(newpop[i].chrom);
       }
   free(oldpop);
   free(newpop);
   free(bestfit.chrom);
   free(finalresult.chrom);
}

void       nomemory(char   *string)                 /*  内存不足，退出  */
{
   printf("malloc:out   of   memory   making   %s!!\n",string);
   exit(-1);
}


void    initpop()                       /*  随机初始化种群  */
   {
     int  i,j;
     for(i=0;i<popsize;i++)
     {
         for(j=0;j<lchrom;j++)
         {
             oldpop[i].chrom[j]=rnd(0,7);
          }
             oldpop[i].fitness=0;
             oldpop[i].cfitness=0;
             oldpop[i].totalcost=0;
             objfunc(&(oldpop[i]));               /*  计算初始适应度  */
     }
     statistics(oldpop);
     for(i=0;i<popsize;i++)
        changeobj(&(oldpop[i]));               /*  适应度的尺度转换  */
   }

void   statistics(struct  individual *pop)              /*  计算种群统计数据  */
   {  int  i;
      struct   individual   *temp1;
      sumfitness=0;
      min=(*pop).fitness;
      max=(*pop).fitness;
      temp1=pop;
/*  计算最大、最小和累计适应度  */
      for(;pop<temp1+100;pop++)
        {
           sumfitness=sumfitness+(*pop).fitness;
           if((*pop).fitness>max)    max=(*pop).fitness;
           if((*pop).fitness<min)    min=(*pop).fitness;
          
        }
      /*  计算平均适应度  */
      avg=sumfitness/popsize;
   }


void   findbest(struct  individual *best)
{  
    int  i;
    struct   individual   *temp2;
    temp2=best;
    for(;best<temp2+popsize;best++)
    {
       if((*best).fitness>bestfit.fitness)
               {
                  bestfit.fitness=(*best).fitness;
                  bestfit.cfitness=(*best).cfitness;
                  bestfit.totalcost=(*best).totalcost;
                  bestfit.generation=gen;
                  for(i=0;i<lchrom;i++)
                     bestfit.chrom[i]=(*best).chrom[i];
                }
    }   
}

void   generation()                             /*  生成新一代  */
{
   int   mate1,mate2,jcross,i,k,j=0;
   int   *p1;
 /*  每代运算前进行预选  */
   preselect();
/*  选择,   交叉,   变异  */
   do
      {
         /*  挑选交叉配对  */
         if (j==0)                              /*  精英选择，父代最好的个体放在候选群的第一个位置  */
          { mate1=0;
            mate2=select();
            for(i=0;i<lchrom;i++)
               oldpop[0].chrom[i]=bestfit.chrom[i];
            oldpop[0].fitness=bestfit.fitness;
            oldpop[0].cfitness=bestfit.cfitness;
            oldpop[0].totalcost=bestfit.totalcost;
          }
         else
          {
            mate1=select();
            mate2=select();
          }
          /*  交叉  */
          if(flip(pcross))
             {ncross++;
              crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom);
             }
         else
            {
                for(i=0;i<lchrom;i++)
                    { newpop[j].chrom[i]=oldpop[mate1].chrom[i];
                      newpop[j+1].chrom[i]=oldpop[mate2].chrom[i];
                     }
            }
           /*  变异  */
           for(k=j;k<=j+1;k++)
             {
                for(i=0;i<lchrom;i++)
                  {
                     if(flip(pmutation))
                        {  nmutation++;
                         mutation(&newpop[k].chrom[i]);
                         }
                   }
              }
         /*  解码,  计算适应度  */
         objfunc(&(newpop[j]));
         objfunc(&(newpop[j+1]));
         j  =  j+2;
      }
   while(j<(popsize-1));
   statistics(newpop);
   for(j=0;j<popsize;j++)
      changeobj(&(newpop[j]));

}


void   preselect()                                     /*  计算种群总适应度  */
{ 
  int   j;
  sumcfitness=0;
  for(j=0;j<popsize;j++)   sumcfitness=sumcfitness+oldpop[j].cfitness;
}

int   select()                                     /*  轮盘赌选择  */
   {
      float   randomperc();
      float   sum,pick;
      int   i;
      pick=randomperc();
      sum=0;
      if(sumcfitness!=0)
      {
         for(i=0;(sum<pick)&&(i<popsize);i++)
         sum=sum+oldpop[i].cfitness/sumcfitness;
         return(i-1);
      }
      else
            i=rnd(0,(popsize-1));
      return(i);
   }



void   crossover(int  *parent1,int  *parent2,int  *child1,int  *child2)