/*lianzhouhui,Marth 2005,at NANJING
  GENETIC ALGORITHM
  determine the minimization of the problem :100*(x*x-y)^2+(1-x)^2
   recommonded parament pc=0.8,pm=0.05 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <float.h>
#include <graphics.h>
#include <math.h>
#include <conio.h>

#define maxpop 100
#define maxstring 64
#define Xmin   -2.048
#define Xmax   2.048
#define Ymin   -2.048
#define Ymax   2.048
struct pp
 {unsigned char chromX[maxstring],chromY[maxstring];
  float x,y,fitness;
  unsigned int parent1,parent2,xsite,class;
 };
/*以下變量均為全局變量*/
struct pp *oldpop,*newpop,*p1;
/*定義了 舊種群,新種群, 用來操作的種群*/
unsigned int popsize,lchrom,maxgen,nmutation,ncross,jcross,maxpp,minpp,jrand,gen;
/*定義了 種群個體數，染色體長度，最大代數，變異數，交叉數，交叉點，最大\最小適應度個體的位置，在隨機數組中取隨機數的位置*/
float pcross,pmutation,sumfitness,avgfitness,max,min,oldrand[maxpop],sumclass;
/*定義了 交叉概率,變異概率,適應度之和,適應度平均值,最大適應度,最小適應度,上次生成的隨機數組*/


void ga();                          //GA主函數
int crossover_compete(unsigned char *parentX1,unsigned char *parentX2,unsigned char *parentY1,unsigned char *parentY2,int k5);          //交叉競爭操作
int mutation(unsigned char ch);     //變異
void generation();                  //產生下一代種群
int select();                       //對種群進行選擇,選出兩個個體進行交叉或競爭或和諧共處
double objfitness(float x1,float x2);//求個體的適應度
void statistics(struct pp *pop);    //對種群的適應度進行統計

int flip(float probability);        //對某概率的樣本進行隨機的選取,選到返回1,否則返回0
float now_pcross();               //求當前的交叉概率
float now_pmutation();            //求當前的變異概率
double decode(unsigned char *pp,float xmin,float xmax); //把值定義在一個區間內的二進制數轉化為十進制數,即解碼操作
float random1();
void randomize1();
void initpop();                     //初始化種群
void initdata();                    //輸入參數
void pause();
void CoBox(int x,int y,int l,int h,int color);
void CoReBox(int x,int y,int l,int h,int color);
void clearscreen();
void drawgraph(int gen,float oldmax);
void resetmenu();
void report();
void peoplemutate(struct pp *pp1,int k);



main()
{
 char c1,c2;
 int gdriver=VGA,gmode=VGAHI,errorcode;

 initgraph(&gdriver, &gmode, "d:\\borlandc\\bgi");

   /* read result of initialization */
   errorcode = graphresult();

   if (errorcode != grOk)  /* an error occurred */
   {
      printf("Graphics error: %s\n", grapherrormsg(errorcode));
      printf("Press any key to halt:");
      getch();
      exit(1);             /* return with error code */
   }

  setbkcolor(15);
  setfillstyle(8,10);
  bar(0,0,getmaxx(),40);
  setcolor(4);
  settextstyle(1,0,4);
  outtextxy(0,1,"-------A GENETIC ALGORITHM-------");
  setfillstyle(8,10);
  bar(0,40,getmaxx()/2,getmaxy());
  settextstyle(0,0,1);
  outtextxy(20,50,"(c)lianzhouhui march 2005");
  setlinestyle(0,0,3);
  setcolor(0);
  line(320,getmaxy(),320,40);
  setcolor(9);
  settextstyle(0,0,1);
  CoBox(20,80+80,120,30,10);
  outtextxy(20,80+10+80," 1 SET");
  CoBox(20,170+40,120,30,10);
  outtextxy(20,170+10+40,"2 RESET");
  CoBox(180,80+80,120,30,10);
  outtextxy(180,80+10+80," 3 START");
  CoBox(180,170+40,120,30,10);
  outtextxy(180,170+10+40," 4 EXIT");
  setcolor(4);
  settextstyle(1,0,3);
  outtextxy(0,250,"  ********PARAMETRE********");
  settextstyle(0,0,1);
  outtextxy(10,285+3,"Enter population size-------->");
  outtextxy(10,285+38,"Enter chromosome length------>");
  outtextxy(10,285+38+38-3,"Enter max.generations-------->");
  outtextxy(10,285+38+38+38-8,"Enter crossover probability-->");
  outtextxy(10,285+38+38+38+38-10,"Enter mutation probability---->");
  outtextxy(0,140," attention:maxgen<=100  chromlength<=64");
  outtextxy(10,285+38+38+38+38+20,"Recommonded parametre:100,62,1000,0.8,0.05");
  settextstyle(1,0,3);
  /*  outtextxy(320,40,"****************GRAPH****************");*/
  clearscreen();
  setcolor(4);
  settextstyle(0,0,1);
  outtextxy(300,50,"4000");
  outtextxy(630,255,"maxgen");
  outtextxy(20,60+20,"**************OUTPUT**************");
  outtextxy(20,60+40,"gen=");
  outtextxy(160,60+40,"maxfitness=");
  outtextxy(20,100+20,"x=");
  outtextxy(160,100+20,"y=");
 if(!(oldpop=(struct pp *)malloc(maxpop*sizeof(struct pp))))   //分配空間oldpop,newpop,p1
	{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(sizeof(struct pp))))
	{printf("memory request failed!\n");  exit(0);}

 c1='1';
 c2='1';
  while(1)
  {
    switch(c1)
    {
      case '1':
      {
       resetmenu();
       CoReBox(20,80+80,120,30,10);
       outtextxy(20,80+10+80," 1 SET");
       break;
      }
      case '2':
      {
       resetmenu();
       CoReBox(20,170+40,120,30,10);
       outtextxy(20,170+10+40,"2 RESET");

       break;
      }
      case '3':
      {
       resetmenu();
      CoReBox(180,80+80,120,30,10);
      outtextxy(180,80+10+80," 3 START");
       break;
      }
      case '4':
      {
       resetmenu();
      CoReBox(180,170+40,120,30,10);
       outtextxy(180,170+10+40," 4 EXIT");
       break;
      }
      case '\r':
	{
	  if(c2=='1')
	  {
	   resetmenu();
           gotoxy(35,15+4);
           printf("     ");
           gotoxy(35,15+4);
           scanf("%d",&popsize);
           gotoxy(35,15+2+4);
	   printf("     ");
	   gotoxy(35,15+2+4);
           scanf("%d",&lchrom);
           gotoxy(35,15+2+2+4);
           printf("     ");
           gotoxy(35,15+2+2+4);
	   scanf("%d",&maxgen);
           gotoxy(35,15+2+2+2+4);
           printf("     ");
           gotoxy(35,15+2+2+2+4);
           scanf("%f",&pcross);
           gotoxy(35,15+2+2+2+2+4);
           printf("     ");
           gotoxy(35,15+2+2+2+2+4);
           scanf("%f",&pmutation);
	   c1='1';       
           CoReBox(20,80+80,120,30,10);
           outtextxy(20,80+10+80," 1 SET");
	  }
	  if(c2=='2')
	  {
          resetmenu();
          clearscreen();
	  c1='1';
          CoReBox(20,80+80,120,30,10);
          outtextxy(20,80+10+80," 1 SET");
	  }
          if(c2=='3')
	  {
	  nmutation=0;
	  ncross=0;
	  ga();
	  c1='1';
          CoReBox(20,80+80,120,30,10);
          outtextxy(20,80+10+80," 1 SET");
	  }
	  if(c2=='4')
	  { 
	  report();
	  getch();
	  exit(0);}
     }
    }
  c2=c1;
  c1=getch();
  }


}


//*********************************GA主函數**************************************

void ga()
{
  double oldmax;
  int oldmaxpp;
  int k,j;
  for(k=0;k<maxpop;k++) {oldpop[k].chromX[0]='\0';oldpop[k].chromY[0]='\0';}
  for(k=0;k<maxpop;k++) {newpop[k].chromX[0]='\0';newpop[k].chromY[0]='\0';}
  gen=0;
  initpop();
  p1=newpop;
  newpop=oldpop;
  statistics(newpop);
  newpop=p1;
  nmutation=0;ncross=0;
  resetmenu();
 do{
   gen=gen+1;
   randomize();
   oldmax=max;
   oldmaxpp=maxpp;
   generation();
   statistics(newpop);
   p1[0]=newpop[popsize-1];                   //保留最大適應度的個體,并放在一個固定的位置，避免其影響太大
   newpop[popsize-1]=newpop[maxpp];
   newpop[maxpp]=p1[0];
   maxpp=popsize-1;
   if(max<oldmax)                   
  {
    newpop[popsize-1]=oldpop[oldmaxpp];
    statistics(newpop);
    }
  setfillstyle(1,15);
  bar(375,265,585,475);
  setcolor(4);
  setlinestyle(0,0,1);
  rectangle(375,265,585,475);
  gotoxy(16-3,4+2+1);
  printf("      ");
  gotoxy(16-3,4+2+1);
  printf("%d",gen);
  gotoxy(16+20-3,4+2+1);
  printf("      ");
  gotoxy(16+20-3,4+2+1);
  printf("%8.4f",max);
  gotoxy(16-3-8,4+3+1);
  printf("      ");
  gotoxy(16-3-8,4+3+1);
  printf("%8.4f",newpop[maxpp].x);
  gotoxy(16+20-3-7,4+3+1);
  printf("      ");
  gotoxy(16+20-3-7,4+3+1);
  printf("%8.4f",newpop[maxpp].y);
  gotoxy(6+20,4+1);
  printf("      ");
  gotoxy(6+20,4+1);
  printf("%d,%d",maxpp,oldmaxpp);
  drawgraph(gen,oldmax);
  p1=oldpop;
  oldpop=newpop;
  newpop=p1;
  //delay(20);               //延時
 }while(gen<maxgen);
}

 //*****************************交叉競爭操作*******************************

int crossover_compete(unsigned char *parentX1,unsigned char *parentX2,unsigned char *parentY1,unsigned char *parentY2,int k5)          //交叉競爭操作
{
 int j;
 float npcross;
 npcross=now_pcross();
 if (flip(npcross))
  {jcross=random(lchrom-1);
   ncross=ncross+1;
   for(j=0;j<jcross;j++)
    {newpop[k5].chromX[j]=mutation(parentX2[j]);
     newpop[k5+1].chromX[j]=mutation(parentX1[j]);
     newpop[k5].chromY[j]=mutation(parentY2[j]);
     newpop[k5+1].chromY[j]=mutation(parentY1[j]);
    }
   for(j=jcross;j<lchrom;j++)
    {newpop[k5].chromX[j]=mutation(parentX1[j]);
     newpop[k5+1].chromX[j]=mutation(parentX2[j]);
     newpop[k5].chromY[j]=mutation(parentY1[j]);
     newpop[k5+1].chromY[j]=mutation(parentY2[j]);
    }
  return 1;
  }
 else if(flip(0.1*(1-npcross)))
  {
    for(j=0;j<lchrom;j++)
    {newpop[k5].chromX[j]=mutation(parentX1[j]);
     newpop[k5+1].chromX[j]=mutation(parentX2[j]);
     newpop[k5].chromY[j]=mutation(parentY1[j]);
     newpop[k5+1].chromY[j]=mutation(parentY2[j]);
    }
  return 1;
  }
 else
 {return 0;}
}

//*******************************變異*****************************

int mutation(unsigned char ch)                   //變異
{
 int mutate;
 float npmutation;
 npmutation=now_pmutation();
 mutate=flip(npmutation);
 if(mutate)
  {nmutation=nmutation+1;
   if(ch) ch=0;
   else ch=1;
  }
 if(ch) return 1;
 else return 0;
}