//*******************************個體變異*****************************
void peoplemutate(struct pp *pp1,int k)
{
  int i;
  randomize();
  i=random(lchrom);
  if(flip(0))
  { if(pp1[k].chromX[i])
	pp1[k].chromX[i]=0;
  }
  i=random(lchrom);
  if(flip(0))
  { if(pp1[k].chromY[i])
        pp1[k].chromY[i]=0;
  }
}


//****************************產生下一代種群*******************************
void generation()                  //產生下一代種群
{ unsigned int j,mate1,mate2;
  int flag=1;                               //交叉或競爭的標志
  j=0;
  do
  {mate1=select();                    //找出兩個體進行交叉競爭
   mate2=select();
   //以某種概率留部分頂級種群
   flag=crossover_compete(oldpop[mate1].chromX,oldpop[mate2].chromX,oldpop[mate1].chromY,oldpop[mate2].chromY,j);
   if(flag)
   {
   peoplemutate(newpop,j);
   peoplemutate(newpop,j+1);
   newpop[j].x=(float)decode(newpop[j].chromX,Xmin,Xmax);
   newpop[j].y=(float)decode(newpop[j].chromY,Ymin,Ymax);
   newpop[j].fitness=objfitness(newpop[j].x,newpop[j].y);
   newpop[j].parent1=mate1;
   newpop[j].parent2=mate2;
   newpop[j].xsite=jcross;
   newpop[j+1].x=(float)decode(newpop[j+1].chromX,Xmin,Xmax);
   newpop[j+1].y=(float)decode(newpop[j+1].chromY,Ymin,Ymax);
   newpop[j+1].fitness=objfitness(newpop[j+1].x,newpop[j+1].y);
   newpop[j+1].parent1=mate1;
   newpop[j+1].parent2=mate2;
   newpop[j+1].xsite=jcross;
   j=j+2;
   }
   else                                 //以一定的概率兩兩競爭，留下一個個體
   {
     if(oldpop[mate1].fitness<oldpop[mate2].fitness)
     newpop[j]=oldpop[mate2];
     else
     newpop[j]=oldpop[mate1];
     peoplemutate(newpop,j);
     j=j+1;
   }
  }while (j<popsize);
  newpop[popsize-1]=oldpop[popsize-1];  //直接繼承最大適應度值的個體
}

//**********************************對種群進行選擇***************************************


int select()                      //對種群進行選擇,選出兩個個體進行交叉或競爭或和諧共處
{                                       //用改進的輪轉賭輪法
  double rand1,partsum;
  int j;
  float a,b,pgen;     
   pgen=(float)(1.0*gen/maxgen);                       //進行適應度調整的兩參數
  partsum=0.0;
  j=0;
  rand1=random1()*sumfitness;
  if (pgen<=0.3)                  //對不同時期的種群進行不同的適應度調整
  {a=0.1; b=0.9*avgfitness;}
  else if(0.3<pgen<=0.7)
  {a=1;b=0;}
  else
  {
   a=2;b=-1*avgfitness;
   if ((a*min+b)<=0)
    {a=1;b=0;}
  }
  while(((a*partsum+b)<rand1)&&(j<popsize))
  {
    partsum=partsum+oldpop[j].fitness;
    j=j+1;
  }
  return j-1;
}


int flip(float probability)          //對某概率的樣本進行隨機的選取,選到返回1,否則返回0
{
 float ppp;
 ppp=random(20001)/20000.0;
 if(ppp<=probability) return 1;
 return 0;
}

//*********************************求個體的適應度***************************************

double objfitness(float x1,float x2)   //求個體的適應度
{ float y;
  y=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);
  return y;
}

//********************************對種群進行統計*****************************************

void statistics(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;
    }
  }
 avgfitness=sumfitness/(float)popsize; /*求出平均適應度值*/

}

//**************************求當前的交叉概率*******************************


float now_pcross()             //求當前的交叉概率
{
 float p,pgen;
 pgen=(float)(gen*1.0/maxgen);
 if(pgen<=0.3)
 p=pcross;
 else if(0.3<pgen<=0.6)
 p=pcross;
 else if(0.6<pgen<=0.95)
 p=0.8;
 else
 p=0.5;
 return p;
}


//****************************求當前的變異概率********************************

float now_pmutation()          //求當前的變異概率
{
 float p,pgen;
 pgen=(float)(gen*1.0/maxgen);//注意這里要乘以1.0 用來化為float型!!!!!!!!!重要!!!!!!!!
 if(pgen<=0.2)
 p=0.4;
 else if(0.2<pgen<=0.3)
 p=pmutation;
 else if(0.3<pgen<=0.8)
 p=0.3;
 else if(0.5<pgen<=0.8)
 p=pmutation;
 else
 p=0.01;
 return p;
}

//**************************************解碼操作**********************************************
double decode(unsigned char *pp,float xmin,float xmax) //把值定義在一個區間內的二進制數轉化為十進制數,即解碼操作
{
 int j;
 double power;//各位的權重
 double value;
 power=1.0;
 value=0.0;
 for(j=lchrom-1;j>-1;j--)//十進制變二進制
 { if(pp[j]) value=value+power;
   power=2.0*power;
 }
 value=(value/(pow(2,lchrom)-1))*(xmax-xmin)+xmin;
//把二進制值映射到[xmin,xmax]區間上
 return value;
}

float random1()
{
 jrand=jrand+1;
 if (jrand>=lchrom)
  {jrand=0;
   randomize1();
  }
 return oldrand[jrand];
}


void randomize1()                    /*randomize again*/
 {
  int i;
  randomize();
  for(i=0;i<lchrom;i++)
    oldrand[i]=random(30001)/30000.0;
  jrand=0;
 }

void initpop()                       //初始化種群
{
 int j,j1;
 for(j=0;j<popsize;j++)
  { randomize();
    for (j1=0;j1<lchrom;j1++)
   { 
    oldpop[j].chromX[j1]=(int)(random(20000)/10000.0);     /*隨機產生由0/1組成的染色體*/
    oldpop[j].chromY[j1]=(int)(random(20000)/10000.0); ;     /*隨機產生由0/1組成的染色體*/
   }
   oldpop[j].x=(float)decode(oldpop[j].chromX,Xmin,Xmax);
   oldpop[j].y=(float)decode(oldpop[j].chromY,Ymin,Ymax);
   oldpop[j].fitness=objfitness(oldpop[j].x,oldpop[j].y);
   oldpop[j].parent1=0;
   oldpop[j].parent2=0;
   oldpop[j].xsite=0;
  }
}



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


void CoBox(int x,int y,int l,int h,int color)
{
  setfillstyle(1,8);
  bar(x,y,x+l,y+h);
  setfillstyle(1,color);
  bar(x+2,y+2,x+l-2,y+h-2);
  setcolor(15);
  line(x,y,x+l,y);
  line(x,y,x,y+h);
  line(x+1,y+1,x+l-1,y+1);
  line(x+1,y+1,x+1,y+h-1);
}



void CoReBox(int x,int y,int l,int h,int color)
{
  setfillstyle(1,8);
  bar(x,y,x+l,y+h);
  setfillstyle(1,color);
  bar(x+2,y+2,x+l-2,y+h-2);
  setcolor(15);
  line(x,y+h,x+l,y+h);
  line(x+l,y+h,x+l,y);
  line(x+1,y+h-1,x+l-1,y+h-1);
  line(x+l-1,y+h-1,x+l-1,y+1);
}



void clearscreen()
{
  setfillstyle(1,15);
  bar(330,50,630,250);
  setlinestyle(0,0,3);
  setcolor(4);
  line(325,250,630,250);
  line(630,250,620,240);
  line(630,250,620,260);
  line(330,255,330,45);
  line(330,45,320,55);
  line(330,45,340,55);
  setfillstyle(1,15);
  bar(375,265,585,475);
  setcolor(4);
  setlinestyle(0,0,3);
  rectangle(375,265,585,475);
}


void drawgraph(int gen,float oldmax)
{
  int Gx,Gy,Gx1,Gy1;
  int Px,Py;
  int j;
  Gy=(int)(max*200/4000);
  Gx=(int)(gen*300.0/maxgen);
  Gy1=(int)(oldmax*200/4000);
  Gx1=(int)((gen-1)*300.0/maxgen);

  setlinestyle(0,0,1);
  setcolor(2);
  line(330+Gx1,250-Gy1,330+Gx,250-Gy);
  for (j=0;j<popsize;j++)
  {
   Px=(int)(newpop[j].x*50+480);
   Py=(int)(370-newpop[j].y*50);
   line(Px-3,Py,Px+3,Py);
   line(Px,Py-3,Px,Py+3);
  }

}

void resetmenu()
{
  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");
}





void report()
{
   int k;
   setfillstyle(1,0);
   bar(0,0,getmaxx(),100);
   gotoxy(10,1);
   printf("Population Report\n");
   for(k=0;k<79;k++) printf("*");
   printf("\n");
   printf("RESULT: ");
   printf("avgfitness=%8.4f  MIN=%8.4f  MAX=%8.4f\n",avgfitness,min,max);
   printf("x=%8.4f  y=%8.4f  \n",oldpop[maxpp].x,oldpop[maxpp].y);
   printf("         ncross=%d   nmutation=%d\n",ncross,nmutation);
   free(p1);
   free(oldpop);
   free(newpop);

}