/********************************************************************/
/*        基于基本遺傳算法的函數(shù)最優(yōu)化任意隨機(jī)交叉父體   SGAM.C     */
/*     A Function Optimizer using Simple Genetic Algorithm          */
/* developed from the Pascal SGA code presented by David E.Goldberg */
/*              華南理工大學(xué)電子與信息學(xué)院   蘇勇          2004年4月*/
/********************************************************************/
#include <stdio.h>
#include <math.h>
/* 全局變量 */
struct individual                       /* 個(gè)體*/
{
    unsigned *chrom;                    /* 染色體 */
    double   fitness;                   /* 個(gè)體適應(yīng)度*/
    double   varible;                   /* 個(gè)體對(duì)應(yīng)的變量值*/   
    int      xsite;                     /* 交叉位置 */
    int      parent[2];                 /* 父?jìng)€(gè)體  */
    int      *utility;                  /* 特定數(shù)據(jù)指針變量 */
};
struct bestever                         /* 最佳個(gè)體*/
{
    unsigned *chrom;                    /* 最佳個(gè)體染色體*/
    double   fitness;                   /* 最佳個(gè)體適應(yīng)度 */
    double   varible;                   /* 最佳個(gè)體對(duì)應(yīng)的變量值 */
    int      generation;                /* 最佳個(gè)體生成代 */
};
 struct individual *oldpop;             /* 當(dāng)前代種群 */
 struct individual *newpop;             /* 新一代種群 */
 struct bestever bestfit;               /* 最佳個(gè)體 */
 double sumfitness;                     /* 種群中個(gè)體適應(yīng)度累計(jì) */
 double max;                            /* 種群中個(gè)體最大適應(yīng)度 */
 double avg;                            /* 種群中個(gè)體平均適應(yīng)度 */
 double min;                            /* 種群中個(gè)體最小適應(yīng)度 */
 float  pcross;                         /* 交叉概率 */
 float  pmutation;                      /* 變異概率 */
 int    popsize;                        /* 種群大小  */
 int    lchrom;                         /* 染色體長(zhǎng)度*/
 int    chromsize;                      /* 存儲(chǔ)一染色體所需字節(jié)數(shù) */
 int    gen;                            /* 當(dāng)前世代數(shù) */
 int    maxgen;                         /* 最大世代數(shù)   */
 int    run;                            /* 當(dāng)前運(yùn)行次數(shù) */
 int    maxruns;                        /* 總運(yùn)行次數(shù)   */
 int    printstrings;                   /* 輸出染色體編碼的判斷，0 -- 不輸出, 1 -- 輸出 */
 int    nmutation;                      /* 當(dāng)前代變異發(fā)生次數(shù) */
 int    ncross;                         /* 當(dāng)前代交叉發(fā)生次數(shù) */

/* 隨機(jī)數(shù)發(fā)生器使用的靜態(tài)變量 */
static double oldrand[55];
static int jrand;
static double rndx2;
static int rndcalcflag;
/* 輸出文件指針 */
FILE *outfp ;
/* 函數(shù)定義 */
void advance_random();
int flip(float);rnd(int, int);
void randomize();
double randomnormaldeviate();
float randomperc(),rndreal(float,float);
void warmup_random(float);
void initialize(),initdata(),initpop();
void initreport(),generation(),initmalloc();
void freeall(),nomemory(char *),report();
void writepop(),writechrom(unsigned *);
void preselect();
void statistics(struct individual *);
void title(),repchar (FILE *,char *,int);
void skip(FILE *,int);
int select();
void objfunc(struct individual *);
int crossover (unsigned *, unsigned *, unsigned *, unsigned *);
void mutation(unsigned *);


void initialize()      /* 遺傳算法初始化 */
{
    /* 鍵盤輸入遺傳算法參數(shù) */
    initdata();
    /* 確定染色體的字節(jié)長(zhǎng)度 */
    chromsize = (lchrom/(8*sizeof(unsigned)));
    if(lchrom%(8*sizeof(unsigned))) chromsize++;
    /*分配給全局?jǐn)?shù)據(jù)結(jié)構(gòu)空間 */
    initmalloc();
    /* 初始化隨機(jī)數(shù)發(fā)生器 */
    randomize();
    /* 初始化全局計(jì)數(shù)變量和一些數(shù)值*/
    nmutation = 0;
    ncross = 0;
    bestfit.fitness = 0.0;
    bestfit.generation = 0;
    /* 初始化種群，并統(tǒng)計(jì)計(jì)算結(jié)果 */
    initpop();
    statistics(oldpop);
    initreport();
}

void initdata()           /* 遺傳算法參數(shù)輸入 */
{
   char  answer[2];
   popsize=30;
   if((popsize%2) != 0)
   {
	fprintf(outfp, "種群大小已設(shè)置為偶數(shù)\n");
	popsize++;
   };
   lchrom=22;
   printstrings=1;
   maxgen=300;
   pcross=0.8;
   pmutation=0.005;
}

void initpop()           /* 隨機(jī)初始化種群 */
{
    int j, j1, k, stop;
    unsigned mask = 1;
    for(j = 0; j < popsize; j++)
    {
        for(k = 0; k < chromsize; k++)
        {
            oldpop[j].chrom[k] = 0;
            if(k == (chromsize-1))
                stop = lchrom - (k*(8*sizeof(unsigned)));
            else
                stop =8*sizeof(unsigned);
            for(j1 = 1; j1 <= stop; j1++)
            {
               oldpop[j].chrom[k] = oldpop[j].chrom[k]<<1;
               if(flip(0.5))
                  oldpop[j].chrom[k] = oldpop[j].chrom[k]|mask;
            }
        }
        oldpop[j].parent[0] = 0;     /* 初始父?jìng)€(gè)體信息 */
        oldpop[j].parent[1] = 0;
        oldpop[j].xsite = 0;
        objfunc(&(oldpop[j]));       /* 計(jì)算初始適應(yīng)度*/
    }
}

void initreport()               /* 初始參數(shù)輸出 */
{
    void   skip();
    skip(outfp,1);
    fprintf(outfp,"             基本遺傳算法參數(shù)\n");
    fprintf(outfp," -------------------------------------------------\n");
    fprintf(outfp,"    種群大小(popsize)     =   %d\n",popsize);
    fprintf(outfp,"    染色體長(zhǎng)度(lchrom)    =   %d\n",lchrom);
    fprintf(outfp,"    最大進(jìn)化代數(shù)(maxgen)  =   %d\n",maxgen);
    fprintf(outfp,"    交叉概率(pcross)      =   %f\n",pcross);
    fprintf(outfp,"    變異概率(pmutation)   =   %f\n",pmutation);
    fprintf(outfp," -------------------------------------------------\n");
    skip(outfp,1);
    fflush(outfp);
}

void generation()
{
  int mate1, mate2, jcross, j = 0;
  /*  每代運(yùn)算前進(jìn)行預(yù)選 */
  preselect();
  /* 選擇, 交叉, 變異 */
  do
    {
      /* 挑選交叉配對(duì) */
      mate1 = select();
      mate2 = select();
      /* 交叉和變異 */
      jcross = crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom, newpop[j+1].chrom);
      mutation(newpop[j].chrom);
      mutation(newpop[j+1].chrom);
      /* 解碼, 計(jì)算適應(yīng)度 */
      objfunc(&(newpop[j]));
      /*記錄親子關(guān)系和交叉位置 */
      newpop[j].parent[0] = mate1+1;
      newpop[j].xsite = jcross;
      newpop[j].parent[1] = mate2+1;
      objfunc(&(newpop[j+1]));
      newpop[j+1].parent[0] = mate1+1;
      newpop[j+1].xsite = jcross;
      newpop[j+1].parent[1] = mate2+1;
      j = j + 2;
    }
  while(j < (popsize-1));

}

void initmalloc()              /*為全局?jǐn)?shù)據(jù)變量分配空間 */
{
  unsigned nbytes;
  char  *malloc();
  int j;
  /* 分配給當(dāng)前代和新一代種群內(nèi)存空間 */
  nbytes = popsize*sizeof(struct individual);
  if((oldpop = (struct individual *) malloc(nbytes)) == NULL)
    nomemory("oldpop");
  if((newpop = (struct individual *) malloc(nbytes)) == NULL)
    nomemory("newpop");
  /* 分配給染色體內(nèi)存空間 */
  nbytes = chromsize*sizeof(unsigned);
  for(j = 0; j < popsize; j++)
    {
      if((oldpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL)
	nomemory("oldpop chromosomes");
      if((newpop[j].chrom = (unsigned *) malloc(nbytes)) == NULL)
	nomemory("newpop chromosomes");
    }
  if((bestfit.chrom = (unsigned *) malloc(nbytes)) == NULL)
    nomemory("bestfit chromosome");

}

void freeall()               /* 釋放內(nèi)存空間 */
{
  int i;
   for(i = 0; i < popsize; i++)
    {
      free(oldpop[i].chrom);
      free(newpop[i].chrom);
    }
  free(oldpop);
  free(newpop);
  free(bestfit.chrom);
   }

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

void report()                /* 輸出種群統(tǒng)計(jì)結(jié)果 */
{
    void  repchar(), skip();
    void  writepop(), writestats();
    repchar(outfp,"-",80);
    skip(outfp,1); 
    if(printstrings == 1)
    {
        repchar(outfp," ",((80-17)/2));
        fprintf(outfp,"模擬計(jì)算統(tǒng)計(jì)報(bào)告  \n");
        fprintf(outfp, "世代數(shù) %3d", gen);
        repchar(outfp," ",(80-28));
        fprintf(outfp, "世代數(shù) %3d\n", (gen+1));
        fprintf(outfp,"個(gè)體  染色體編碼");
        repchar(outfp," ",lchrom-5);
        fprintf(outfp,"適應(yīng)度    父?jìng)€(gè)體 交叉位置  ");
        fprintf(outfp,"染色體編碼 ");
        repchar(outfp," ",lchrom-5);
        fprintf(outfp,"適應(yīng)度\n");
        repchar(outfp,"-",80);
        skip(outfp,1);
        writepop(outfp);
        repchar(outfp,"-",80);
        skip(outfp,1);
     }
    fprintf(outfp,"第 %d 代統(tǒng)計(jì): \n",gen);
    fprintf(outfp,"總交叉操作次數(shù) = %d, 總變異操作數(shù) = %d\n",ncross,nmutation);
    fprintf(outfp," 最小適應(yīng)度：%f 最大適應(yīng)度：%f  平均適應(yīng)度 %f\n", min,max,avg);
    fprintf(outfp," 迄今發(fā)現(xiàn)最佳個(gè)體 =>  所在代數(shù)： %d  ", bestfit.generation);
    fprintf(outfp," 適應(yīng)度：%f  染色體：", bestfit.fitness);
    writechrom((&bestfit)->chrom);
    fprintf(outfp," 對(duì)應(yīng)的變量值: %f", bestfit.varible);
    skip(outfp,1);
    repchar(outfp,"-",80);
    skip(outfp,1);  
}

void writepop()
{
    struct individual *pind;
    int j;
    for(j=0; j<popsize; j++)
    {
        fprintf(outfp,"%3d)  ",j+1);
        /* 當(dāng)前代個(gè)體 */
        pind = &(oldpop[j]);
        writechrom(pind->chrom);
        fprintf(outfp,"  %8f | ", pind->fitness);
        /* 新一代個(gè)體 */
        pind = &(newpop[j]);
        fprintf(outfp,"(%2d,%2d)   %2d   ",
        pind->parent[0], pind->parent[1], pind->xsite);
        writechrom(pind->chrom);
        fprintf(outfp,"  %8f\n", pind->fitness);
    }
}

void writechrom(chrom)           /* 輸出染色體編碼 */
unsigned *chrom;
{
    int j, k, stop;
    unsigned mask = 1, tmp;
    for(k = 0; k < chromsize; k++)
    {
        tmp = chrom[k];
        if(k == (chromsize-1))
            stop = lchrom - (k*(8*sizeof(unsigned)));
        else
            stop =8*sizeof(unsigned);
        for(j = 0; j < stop; j++)
        {
            if(tmp&mask)
                fprintf(outfp,"1");
            else
                fprintf(outfp,"0");
            tmp = tmp>>1;
        }
    }
}

void preselect()
{
    int j;
    sumfitness = 0;
    for(j = 0; j < popsize; j++) sumfitness += oldpop[j].fitness;
}

int select()                    /* 輪盤賭選擇*/
{
    extern float randomperc();
    float sum, pick;
    int i;
    pick = randomperc();
    sum = 0;
    if(sumfitness != 0)
    {
        for(i = 0; (sum < pick) && (i < popsize); i++)
            sum += oldpop[i].fitness/sumfitness;
    }
    else
        i = rnd(1,popsize);
    return(i-1);
}

void statistics(pop)  /* 計(jì)算種群統(tǒng)計(jì)數(shù)據(jù) */
struct individual *pop;
{
    int i, j;
    sumfitness = 0.0;
    min = pop[0].fitness;
    max = pop[0].fitness;
    /* 計(jì)算最大、最小和累計(jì)適應(yīng)度 */
    for(j = 0; j < popsize; j++)
    {
        sumfitness = sumfitness + pop[j].fitness;            
        if(pop[j].fitness > max) max = pop[j].fitness;        
        if(pop[j].fitness < min) min = pop[j].fitness;         
        /* new global best-fit individual */
        if(pop[j].fitness > bestfit.fitness)