#include <float.h>
#include <time.h>
#include <math.h>
#include <graphics.h>
#include <stdlib.h>

#define maxpop 100
#define maxstring 64
struct pp
  {unsigned char chrom[maxstring];
   float x,fitness;
   unsigned int parent1,parent2,xsite;
   }
struct pp   *oldpop;
struct pp   *newpop;
struct pp   *p1;
unsigned int  popsize,lchrom,gen,maxgen,nmutation,ncross,jcross,maxpp,
              minpp,jrand;
float   pcross,pmutation,sumfitness,avg,max,min,seed,rj[maxpop],
        oldrand[maxpop];
double  coef;
float   objfunc(float);
void    statistics();
int     select();
int     flip(float);
int     crossover();
int     mutation();
void    generation();
void    initialize();
void    report();
void    initpop();
void    initdata();
void    initreport();
float   decode();
float   random1();
float   randomize1();

main()
{
 long int  gen,k,j;
float  oldmax;
int    oldmaxpp;
if(!(oldpop=(struct pp*)malloc(maxpop*sizeof(struct pp))))
    {printf("memory request failed!\n");exit(0);}
if(!(newpop=(struct pp*)malloc(maxpop*sizeof(struct pp))))
    {printf("memory request failed!\n");exit(0);}
if(!(p1=(struct pp*)malloc(maxpop*sizeof(struct pp))))
    {printf("memory request failed!\n");exit(0);}
for(k=0;k<maxpop;k++) oldpop[k].chrom[0]='\0';
for(k=0;k<maxpop;k++) newpop[k].chrom[0]='\0';
gen=0;
initialize();
clrscr();
p1=newpop;
newpop=oldpop;
statistics(newpop);
report(gen);
newpop=p1;
getch();
do{
   gen=gen+1;
   randomize();
   oldmax=max;
   oldmaxpp=maxpp;
   generation();
   statistics(newpop);
   if(max<oldmax)
      {for(j=0;j<lchrom;j++)
         newpop[minpp].chrom[j]=oldpop[oldmaxpp].chrom[j];
       newpop[minpp].x=oldpop[oldmaxpp].x;
       newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
       statistics(newpop);
      }
   report(gen);
   p1=oldpop;
   oldpop=newpop;
   newpop=p1;
   getch();
  }while (gen<maxgen);
  free(p1);
  free(oldpop);
  free(newpop);
  exit(0);
}

float objfunc(float x1)/*個體適應度計算*/
  {float y;
   y=3.1415926*x1;
   y=sin(2.0*y);
   return y*y;
  }

void statistics(pop) /*群體適應度計算*/
struct pp *pop;
  {int j;
   sumfitness=pop[0].fitness;
   min=pop[0].fitness;
   max=pop[0].fitness;
   minpp=0;
   maxpp=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/(float)popsize;
  }

void generation/*群體更新*/
  {unsigned int j,mate1,mate2;
   j=0;
   do{
      mate1=select();
      mate2=select();
      crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
      newpop[j].x=(float)decode(newpop[j].chrom);
      newpop[j].fitness=objfunc(newpop[j].x);
      newpop[j].parent1=mate1;
      newpop[j].parent2=mate2;
      newpop[j].xsite=jcross;
      newpop[j+1].x=(float)decode(newpop[j+1].chrom);
      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);
  }

void initdata()/*控制參數輸入*/
  {unsigned int ch,j;
   clrscr();
   printf("------------------------------\n");
   printf("A Simple Genetic Algorithm-SGA\n");
   printf("(c)X.F.CHEN JUNE 1994\n");
   printf("  All Rights Reserved\n");
   printf("------------------------------\n");
   pause();clrscr();
   printf("********SGA DATA ENTRY AND INITIALIZATION********\n");
   printf("\n");
   printf("Enter population size-------->\n");scanf("%d",&popsize);
   printf("Enter chromosome length-------->\n");scanf("%d",&lchrom);
   printf("Enter max.generation-------->\n");scanf("%d",&maxgen);
   printf("Enter crossover probability-------->\n");scanf("%d",&pcross);
   printf("Enter mutation probability-------->\n");scanf("%d",&pmutation);
   clrscr();
   randomize();
   randomize1();
   nmutation=0;
   ncross=0;
  }

void initreport()/*初始化信息輸出*/
  {int j,k;
   printf("------------------------------\n");
   printf("A Simple Genetic Algorithm-SGA\n");
   printf("(c)X.F.CHEN JUNE 1994\n");
   printf("  All Rights Reserved\n");
   printf("------------------------------\n");
   printf("SGA Parameters\n");
   printf("-----------------\n");
   printf("\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 probability(pcross)=%f\n",pcross);
   printf("Mutation probability(pmutation)=%f\n",pmutation);
   printf("-----------------\n");
   printf("\n");
   printf("Initial Popolation Maximum Fitness=%f\n",max);
   printf("Initial Popolation Average Fitness=%f\n",avg);
   printf("Initial Popolation Minimum Fitness=%f\n",min);
   printf("Initial Popolation Sam of Fitness=%f\n",sumfitness);
   pause();
  }

void initpop()/*生成初始群體*/
  {int j,j1;
   randomize();
   for(j=0;j<popsize;j++)
     {for(j1=0;j1<lchrom;j1++)
         oldpop[j].chrom[j1]=random(2);
      oldpop[j].x=(float)decode(oldpop[j].chrom);
      oldpop[j].fitness=objfunc(oldpop[j].x);
      oldpop[j].parent1=0;
      oldpop[j].parent2=0;
      oldpop[j].xsite=0;
     }
  }

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

void report(int gen)/*數據輸出*/
  {int k,j;
   for(j=0;j<79;j++) print("*");
   printf("\n");
   printf("                 Population Report\n");
   printf("                     Generation %3d\n",gen);
   printf("#parents xsite   string         x    fitness\n");
   for(j=0;j<79;j++) print("+");
   printf("\n");
   for(j=0;j<popsize;j++) 
      {printf("%2d)(%2d,",j,newpop[j].parent1)
       printf("%2d)%2d",newpop[j].parent2,newpop[j].xsite);
       for(k=0;k<lchrom;k++)
         printf("%d",newpop[j].chrom[k]);
       printf("%12.1f",newpop[j].x)
       printf("%6.4f-New.\n",newpop[j].fitness);
      }
   for(k=0;k<79;k++) print("*");
   printf("\n");
   printf("RESULT:GEN:%3d\n",gen);   
   printf("AVG=%8.4d MIN=%8.4f MAX=%8.4f\n",avg,min,max);
   printf("ncross=%4d nmutation=%4d\n",ncross,nmutation);
  }

float decode(unsigned char *pp)/*譯碼*/
  {int j;
   float tt,tt1;
   tt1=1.0;
   tt=0.0;
   for(j=lchrom-1;j>-1;j--)
     {if(pp[j]) tt=tt+tt1;
      tt1=2.0*tt1;
     }
   tt=tt/coef;
   return tt;
  }

pause()/*延時*/
  {int j,j1;
   int x1;
   x1=0;
   for(j=1;j<=25;j++)
     {for(j1=1;j1<2;j1++) x1=x1+1;}
   return x1;
  }

int select()/*選擇操作*/
 {double rand1,partsum;
  int j;
  partsum=0.0;
  j=0;
  rand1=random1()*sumfitness;
  do{
     partsum=partsum+oldpop[j].fitness;
     j=j+1;
  }while ((partsum<rand1)&&(j<popsize));
  return j-1;
 }

int mutation(ch)/*變異操作*/
unsigned char 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;
  }

int crossover(unsigned char *parent1,unsigned char *parent2,int k5)/*交叉操作*/
  {int i,j,j1;
   if(flip(pcross))
     {jcross=random(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])l
        }
      for(j=jcross;j<lchrom;j++)
        {newpop[k5].chrom[j]=mutation(parent2[j]);
         newpop[k5+1].chrom[j]-mutation(parent1[j])l
        }
     }
   else 
      {for(j=0;j<lchrom;j++)
        {newpop[k5].chrom[j]=mutation(parent1[j]);
         newpop[k5+1].chrom[j]-mutation(parent2[j])l
        }
      }
   return 1;
  }

void randomize1()/*重啟動隨機數發生器*/
  {int i;
   randomize();
   for(i=0;i<lchrom;i++)
     oldrand[i]=random(30001)/30000.0;
   jrand=0;
  }

float random1()/*隨機數發生器*/
  {jrand=jrand+1;
   if(jrand>=lchrom)
     {jrand=0;
      randomize1();
     }
   return oldrand[jrand];
  }

int flip(float probability)/*貝努力試驗*/
  {float ppp;
   ppp=random(20001)/20000.0;
   if(ppp<=probability)  return 1;
   return 0;
  }