遗传算法.cpp

遗传算法软件

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

//#define NeedInputInitialChrom  // 如果需要输入初始值,一般是因为上次没有
                                // 计算完成,可以接着再算
//#define NeedInputData //输入种群中第一个的大小(0~1.0之间)
#undef NeedInputInitialChrom

/*NOTICE:modify varnumber and perchrom for each problem.*/
#define varnumber  32     /* 变量个数 */
#define perchrom   5    /* 单变量染色体长度 */
#define popsize 20       /* 群体规模(应为偶数) */
#define maxgen 5000       /* 遗传世代数 */
#define maxstring varnumber*perchrom   /* 多变量总的染色体长度 */
#define pcross 0.80      /* 交叉概率[0.00,1.00] */
#define pmutation 0.001   /* 变异概率[0.00,1.00] */

extern double Obj_func(double *x);

struct pp {
        unsigned int chrom[maxstring];
        double x[varnumber],fitness;
        unsigned int parent1,parent2,xsite;  
   };

struct pp oldpop[popsize],newpop[popsize],p1[popsize];

unsigned int lchrom,gen,nmutation,ncross,jcross,maxpp,minpp;
double sumfitness,avg,max,min;
double coef;
long seedl[1];
double objfunc(double *); /* 目标函数,应该是正的,最小问题要化为最大问题 */
void statistics();           /* 群体适应度统计 */
int rselect();               /* 赌轮选择 */
int flip(double);            /* 贝努利测试 */
int crossover();             /* 一点交叉操作 */
int mutation(unsigned int);  /* 变异操作 */
void generation();           /* 世代更新 */
void initialize();           /* 初始化 */
void initpop();
void report();
void initdata();
void initreport();
void decode(unsigned int *, double *); /* 解码,变量取值在0到1之间 */
void encode(unsigned int *, double *); /* 编码,输入变量取值在0到1之间 */    
double randomd01();
int randomi01();
int randomi(int,int);

/* SGA main program */
/* xx[i] will be a double between 0 and 1.0 */
void sga(double *xx)
{
    long int i,gen,k,j;
    double oldmax;
    int oldmaxpp;

    gen=0;
    seedl[0]=-9l;
    //printf("initializing..........\n");
    initialize();
    for (i=0; i<popsize; i++)
    {
        p1[i]=newpop[i];
        newpop[i]=oldpop[i];
    }                                      
    report(gen);
    for (i=0; i<popsize; i++) newpop[i]=p1[i];
    do {
      gen=gen+1;
      oldmax=max;
      oldmaxpp=maxpp;
      generation();
      statistics(newpop);
      if (max<oldmax)
      {
         for (j=0; j<lchrom; j++)
             newpop[minpp].chrom[j]=oldpop[oldmaxpp].chrom[j];
         for (j=0; j<varnumber; j++)
             newpop[minpp].x[j]=oldpop[oldmaxpp].x[j];
         newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
         statistics(newpop);
      }
      report(gen);
      for (i=0; i<popsize; i++)
      {
          p1[i]=oldpop[i];
          oldpop[i]=newpop[i];    
          newpop[i]=p1[i];
      }
    } while (gen<maxgen);
    for (i=0; i<varnumber; i++)
    {
        xx[i]=oldpop[maxpp].x[i];
        //printf("xx[%d]=%f ",i,xx[i]);
    }
    //printf("\n");

    return;
}

/* calculate individual fitness */
double objfunc(double *x)
{
    double temp;

    temp=1.0/Obj_func(x);

    return temp;                            
}

/* statistics of the group fitness */
void statistics(pop)
struct pp *pop;
{
    int j;

    sumfitness=pop[0].fitness;
    min=pop[0].fitness;
    max=pop[0].fitness;
    maxpp=0;
    minpp=0;
    for (j=1;j<popsize;j++)
    {
        sumfitness=sumfitness+pop[j].fitness;
        if (pop[j].fitness>max)
        {
            max=pop[j].fitness;
            maxpp=j;
        }
        if (pop[j].fitness<min)   
        {
            min=pop[j].fitness;
            minpp=j;
        }
   }
   avg=sumfitness/(double)popsize;
}

/* new group */
void generation()
{
   unsigned int j,mate1,mate2;

   j=0;
   do {
     mate1=rselect();
     mate2=rselect();
     crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
     decode(newpop[j].chrom,newpop[j].x);
     newpop[j].fitness=objfunc(newpop[j].x);
     newpop[j].parent1=mate1;          
     newpop[j].parent2=mate2;
     newpop[j].xsite=jcross;
     decode(newpop[j+1].chrom,newpop[j+1].x);
     newpop[j+1].fitness=objfunc(newpop[j+1].x);
     newpop[j+1].parent1=mate1;
     newpop[j+1].parent2=mate2;
     newpop[j+1].xsite=jcross;
     j=j+2;
   } while (j<popsize);
}

/* initialize */
void initialize()
{
    coef=pow(2.00,perchrom)-1.0;
    initdata();
    initpop();
    statistics(oldpop);
    initreport();
}

/* contral parameters input */  
void initdata()
{
   lchrom=perchrom*varnumber;
   nmutation=0;
   ncross=0;
}

/* generation of initial group */
/* 按随机方式产生初始解群,或者直接输入前次结束时的染色体,
 * 或者按需要输入一个个体 */
void initpop()
{
   int i,j,j1;

   //printf("initializing populations........\n");
#ifdef NeedInputInitialChrom
   printf("input initial chrom:\n");
#endif
   for (j=0;j<popsize;j++)
   {                            
           //printf("j=%d\n",j);
       for (j1=0;j1<lchrom;j1++)
           oldpop[j].chrom[j1]=randomi01();
#ifdef NeedInputInitialChrom
       for (j1=0;j1<lchrom;j1++)
           scanf("%1d",&oldpop[j].chrom[j1]);
       printf("%d in %d has been readed.\n",j+1,popsize);
#endif
       decode(oldpop[j].chrom,oldpop[j].x);
#ifdef NeedInputInitialChrom
       for (j1=0;j1<varnumber;j1++)
           printf("x[%d]=%f\n",j1,oldpop[j].x[j1]);
#endif
       oldpop[j].fitness=objfunc(oldpop[j].x);
       oldpop[j].parent1=0;
       oldpop[j].parent2=0;
       oldpop[j].xsite=0;
   }
#ifdef NeedInputData
   printf("input %d initial data(0.0~1.0):\n",varnumber);
   for (i=0; i<varnumber; i++)
       scanf("%lf",&oldpop[0].x[i]);     
   encode(oldpop[0].chrom,oldpop[0].x);
   oldpop[0].fitness=objfunc(oldpop[0].x);
   oldpop[0].parent1=0;
   oldpop[0].parent2=0;
   oldpop[0].xsite=0;
#endif
}

/* initialization infomation output */
void initreport()
{
   int j,k;

   printf("\n--------------------------------------------------------------\n");
   printf("                     SGA Parameters \n");
   printf("--------------------------------------------------------------\n\n");
   printf("Population size (popsize) = %d \n",popsize);
   printf("Chromosome length (lchrom) = %d \n",lchrom);
   printf("Maximum # of generation (maxgen) = %d \n",maxgen);
   printf("Crossover probablity (pcross) = %f \n",pcross);
   printf("Mutation probablity (pmutation) = %f \n",pmutation);
   printf("------------------------------------------\n\n");     
   printf("Initial Population Maximum Fitness = %f \n",max);
   printf("Initial Population Average Fitness = %f \n",avg);
   printf("Initial Population Minimum Fitness = %f \n",min);
   printf("Initial Population Sum of Fitness = %f \n",sumfitness);
}

/* data output */
void report(int gen)
{
   int k,j,i;

   for (j=0; j<79; j++) printf("*");
   printf("\n");
   printf("Population Report \n");
   printf("Generation %3d \n",gen);
   printf("#parents xsite string x fitness \n");
   for (j=0; j<79; j++) printf("+");
   printf("\n");
   for (j=0; j<popsize; j++)
   {
       for (k=0; k<lchrom; k++)
           printf("%d",newpop[j].chrom[k]); 
       printf("\n");
   }
   printf("\n");
   //for (j=0; j<popsize; j++)
   j=maxpp;
   {
       printf("%d  %d ",j,newpop[j].parent1);
       printf("%d  %d ",newpop[j].parent2,newpop[j].xsite);
       //for (k=0; k<lchrom; k++)
       //    printf("%d",newpop[j].chrom[k]);
       for (i=0; i<varnumber; i++)
           printf(" %f ",newpop[j].x[i]);
       printf("fitness=%f \n",newpop[j].fitness);
   }
   for (k=0; k<79; k++) printf("*");
   printf("\n");
   printf("RESULT: GEN: %d ",gen);
   printf("AVG=%f MIN=%f MAX=%f \n",avg,min,max);
   printf("ncross=%d nmutation = %d \n",ncross,nmutation);
}

/* decode */                          
void decode(unsigned int *pp,double *x)
{
   int i,j;
   double tt,tt1;

   for (i=0; i<varnumber; i++)
   {
       tt1=1.0;
       tt=0.0;
       for (j=lchrom-1-i;j>-1+(varnumber-i-1);j-=varnumber)
       {
           if (pp[j]) tt=tt+tt1;
           tt1=2.0*tt1;
       }
       tt=tt/coef;//tt is between 0.0 and 1.0
       //change variable's value range
       x[i]=0.0001+7.0*tt/10.0;
   }
}

/* encode */
void encode(unsigned int *pp,double *x)  
{
    int i,j,dx;
    double fx;

    for (i=0; i<varnumber; i++)
    {
            // 注意编码和解码相对应
        fx=(x[i]-0.0001)*10.0/7.0;
        fx=fx*coef;
        dx=(int)(fx);
        if ((fx-dx)>0.5) dx+=1;
        for (j=lchrom-1-i;j>-1+(varnumber-i-1); j-=varnumber)
        {
            if (dx%2==1)
            {
                pp[j]=1;
                //printf("1");
            }
            else
            {
                pp[j]=0;
                //printf("0");          
            }
            dx=dx/2;
        }
    }
}

/* select operation */
/*
     几种流行的选择机制:
*  1.  赌轮选择(roulette wheel selection)机制;
       也叫适应度比例方式(fitness proportional model);
   2.  最佳保留(elitist model)选择机制;
   3.  期望值模型(expected value model)选择机制;
   4.  随机竞争(stochastic tournament)选择机制;
   5.  排序(ranking)选择机制;
   6.  排挤方法(crowding model);
*/

// 赌轮选择(roulette wheel selection)机制;
int rselect()
{                                       
   double rand1,partsum;
   int j;

   partsum=0.0;
   j=0;
   rand1=randomd01()*sumfitness;
   do {
     partsum=partsum+oldpop[j].fitness;
     j=j+1;
   } while ((partsum<rand1)&&(j<popsize));
   return j-1;
}

/* mutation operation */
int mutation(unsigned int ch)
{
   int mutate,j;

   mutate=flip(pmutation);
   if (mutate)
   {                       
      nmutation=nmutation+1;
      if (ch) ch=0;
      else    ch=1;
   }
   if (ch)
      return 1;
   else
      return 0;
}

/* crossover operation */
int crossover(unsigned int *parent1,unsigned int *parent2,int k5)
{
   int i,j,j1;

   if (flip(pcross))
   {
       jcross=randomi(1,lchrom-1);
       ncross=ncross+1;
   }
   else
       jcross=lchrom;        
   {
      for (j=0; j<jcross; j++)
      {
          newpop[k5].chrom[j]=mutation(parent1[j]);
          newpop[k5+1].chrom[j]=mutation(parent2[j]);
      }
      for (j=jcross;j<lchrom;j++)
      {
          newpop[k5].chrom[j]=mutation(parent2[j]);
          newpop[k5+1].chrom[j]=mutation(parent1[j]);
      }
   }
   else
   {
      for (j=0; j<lchrom; j++)
      {
          newpop[k5].chrom[j]=mutation(parent1[j]);
          newpop[k5+1].chrom[j]=mutation(parent2[j]);
      }
   }
   return 1;
}                      

/* Bernoulli Trials */
int flip(double probability)
{
   double ppp;

   ppp=randomd01();
   if (ppp<=probability)
      return 1;
   else
      return 0;
}

/* return a double random number between 0.0~1.0 */
double randomd01()
{
    int j;
    long k;
    static long idum2=123456789L;
    static long iy=0L;
    static long iv[32];
    double temp;          

    if (seedl[0] <= 0L) {
        if (-seedl[0] < 1L) seedl[0] = 1L;
        else seedl[0] = -seedl[0];

        idum2 = seedl[0];
        for (j=32+7;j>=0;j--) {
            k = seedl[0]/53668L;
            seedl[0] = 40014L * (seedl[0]-k*53668L)-k*12211L;
            if (seedl[0] < 0L) seedl[0] += 2147483563L;
            if (j < 32) iv[j] = seedl[0];
        }
        iy=iv[0];
    }
    k = seedl[0]/53668L;
    seedl[0] = 40014L*(seedl[0]-k*53668L)-k*12211L;
    if (seedl[0] < 0L) seedl[0] += 2147483563L;
    k = idum2/52774L;
    idum2 = 40692L*(idum2-k*52774L)-k*3791L;
    if (idum2 < 0L) idum2 += 2147483399L;
    j = (int)(iy/(1L+2147483562L/32L)) ;
    iy = iv[j]-idum2;                        
    iv[j] = seedl[0];
    if (iy < 1L) iy += 2147483562L;
    if ((temp=(double)(iy)/(double)(2147483563L)) > (1.0-1.2e-7 ))
        return (1.0-1.2e-7) ;
    else return temp;
}

/* return a integer random number between 0 and 1 */
int randomi01()
{
    if (randomd01()>0.5) return 1;
    else return 0;
}

/* return a interger random number amang 1 and lchrom-1 */
int randomi(int low, int high)
{
    int i;

    if (low>=high)
       i=low;
    else                         
    else
    {
       i=(int)(randomd01()*lchrom);
       if (i>high) i=high;
    }
    return i;
}