dd.cpp

简单遗传算法(SGA) 主要算法模块有:选择 交叉 变异 (三个遗传操作) 和 群体更新

#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; 
   if (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 
    { 
       i=(int)(randomd01()*lchrom); 
       if (i>high) i=high; 
    } 
    return i; 
}