#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>//把日期和時間轉(zhuǎn)換為字符串
using namespace std;
//Parametes setting           
#define POPSIZE 200   //population size 
#define MAXGENS 1000  //max number of generation 
#define NVARS 2     //no of problem variables 
#define PXOVER  0.75 //probalility of crossover 
#define PMUTATION 0.15 //probalility of mutation 
#define TRUE 1
#define FALSE 0
#define LBOUND 0    
#define UBOUND 12   
#define STOP 0.001
int generation;     //current generation no
int cur_best;      //best individual
double diff;      
FILE *galog;      //an output file
struct genotype
{
   double gene[NVARS];   //a string of variables基因變量
   double upper[NVARS];  //individual's variables upper bound 基因變量取值上確界
   double lower[NVARS];  //individual's batiables lower bound 基因變量取值下確界
   double fitness;     //individual's fitness個體適應值
   double rfitness;    //relative fitness個體適應值占種群適應值比例
   double cfitness;    //curmulation fitness個體適應值的累加比例
 };
struct genotype population[POPSIZE+1]; 
//population 當前種群 population[POPSIZE]用于存放個體最優(yōu)值并假設最優(yōu)個體能存活下去
//在某些遺傳算法中最優(yōu)值個體并不一定能夠存活下去
struct genotype newpopulation[POPSIZE+1]; //new population replaces the old generation 子種群
 /*Declaration of procedures used by the gentic algorithm*/
 void initialize(void);          //初始化函數(shù)
 double randval(double,double);      //隨機函數(shù)
 double funtion(double x1,double x2);  //目標函數(shù)
 void evaluate(void);          //評價函數(shù)
 void keep_the_best(void);        //保留最優(yōu)個體
 void elitist(void);            //當前種群與子代種群最優(yōu)值比較
 void select(void);
 void crossover(void);          //基因重組函數(shù)
 void swap(double *,double *);      //交換函數(shù)
 void mutate(void);            //基因突變函數(shù)
 double report(void);          //數(shù)據(jù)記錄函數(shù)
void initialize(void)
 {
  int i,j;
   for(i=0;i<NVARS;i++)
   {
    for(j=0;j<POPSIZE+1;j++)
    {
       if(!i)
       {
        population[j].fitness=0;
        population[j].rfitness=0;
        population[j].cfitness=0;
       }
      population[j].lower[i]=LBOUND;
      population[j].upper[i]=UBOUND;
      population[j].gene[i]=randval(population[j].lower[i],population[j].upper[i]);
     }
   }
 }
//***************************************************************************
//Random value generator:generates a value within bounds
//***************************************************************************
 double randval(double low,double high)
 {
   double val;
   val=((double)(rand()%10000)/10000)*(high-low)+low;
  return val;
 }
//目標函數(shù)
 double funtion(double x,double y)
{
  double result1=sqrt(x*x+y*y)+sqrt((x-12)*(x-12)+y*y)+sqrt((x-8)*(x-8)+(y-6)*(y-6));
  return result1;
}
 //***************************************************************************
 //Evaluation function:evaluate the individual's fitness.評價函數(shù)給出個體適應值
//Each time the function is changes,the code has to be recompl
 //***************************************************************************
 void evaluate(void)
 {
  int mem;
  int i;
  double x[NVARS];
  for(mem=0;mem<POPSIZE;mem++)
   {

    for(i=0;i<NVARS;i++)
    x[i]=population[mem].gene[i];
    population[mem].fitness=funtion(x[0],x[1]);//將目標函數(shù)值作為適應值
  }
 }
 //***************************************************************************************
 //Keep_the_best function:This function keeps track of the best member of the population.
//找出種群中的個體最優(yōu)值并將其移動到最后
//***************************************************************************************
 void keep_the_best()
 {
   int mem;
   int i;
   cur_best=0;
   for(mem=0;mem<POPSIZE;mem++)//找出最高適應值個體
  {
     if(population[mem].fitness<population[cur_best].fitness)
     {
       cur_best=mem;      
    }
  }
  //將最優(yōu)個體復制至population[POSIZE]
   if(population[cur_best].fitness<=population[POPSIZE].fitness||population[POPSIZE].fitness<1)//防止出現(xiàn)種群基因退化 故保留歷史最優(yōu)個體
  {
    population[POPSIZE].fitness=population[cur_best].fitness;
    for(i=0;i<NVARS;i++)
    population[POPSIZE].gene[i]=population[cur_best].gene[i];
  }  
}
 //***************************************************************************
 //last in the array.If the best individual from the new populatin is better
//than the best individual from the previous population ,then copy the best
 //from the new population;else replace the worst individual from the current
 //population with the best one from the previous generation.防止種群最優(yōu)值退化
//***************************************************************************
 void elitist()
{
   int i;
  double best,worst;//適應值
  int best_mem,worst_mem;//序號
  best_mem=worst_mem=0;
  best=population[best_mem].fitness;//最高適應值初始化
  worst=population[worst_mem].fitness;//最低適應值初始化
  for(i=1;i<POPSIZE;i++)//找出最高和最低適應值 算法有待改進
   {    
     if(population[i].fitness<best)
     {
       best=population[i].fitness;
      best_mem=i;
     }
    if(population[i].fitness>worst)
     {
       worst=population[i].fitness;
      worst_mem=i;
    }  
   }
  if(best<=population[POPSIZE].fitness)//賦值
   {
    for(i=0;i<NVARS;i++)
       population[POPSIZE].gene[i]=population[best_mem].gene[i];
    population[POPSIZE].fitness=population[best_mem].fitness;
   }
   else
  {
     for(i=0;i<NVARS;i++)
       population[worst_mem].gene[i]=population[POPSIZE].gene[i];
     population[worst_mem].fitness=population[POPSIZE].fitness;
   }
}
 //***************************************************************************
 //Select function:Standard proportional selection for maximization problems
//incorporating elitist model--makes sure that the best member survives.篩選函數(shù)并產(chǎn)生子代
//***************************************************************************
 void select(void)
 {
   int mem,i,j;
   double sum=0;
   double p;
   for(mem=0;mem<POPSIZE;mem++)//所有適應值求和
  {
     sum+=population[mem].fitness;
   }
   for(mem=0;mem<POPSIZE;mem++)
   {
    population[mem].rfitness=population[mem].fitness/sum;//個人認為還不如建一個種群類 把sum看成類成員
  }
  population[0].cfitness=population[0].rfitness;
  for(mem=1;mem<POPSIZE;mem++)
  {
    population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;
  }
   for(i=0;i<POPSIZE;i++)
  {
     p=rand()%1000/1000.0;
     if(p<population[0].cfitness)
    {
       newpopulation[i]=population[0];
     }
     else
    {
      for(j=0;j<POPSIZE;j++)
         if(p>=population[j].cfitness&&p<population[j+1].cfitness)
           newpopulation[i]=population[j+1];
     }
   }
   for(i=0;i<POPSIZE;i++)//子代變父代
     population[i]=newpopulation[i];
}
//***************************************************************************
 //Crossover:performs crossover of the selected parents.
 //***************************************************************************
void Xover(int one,int two)//基因重組函數(shù)
{
   int i;
  int point;
  if(NVARS>1)
  {
     if(NVARS==2)
      point=1;
    else
      point=(rand()%(NVARS-1))+1;//兩個都重組嗎?
    for(i=0;i<point;i++)//只有第一個基因發(fā)生重組有待改進
      swap(&population[one].gene[i],&population[two].gene[i]);
   }
 }
//***************************************************************************
//Swapp: a swap procedure the helps in swappling 2 variables
//***************************************************************************
 void swap(double *x,double *y)
 {
  double temp;
  temp=*x;
  *x=*y;
  *y=temp;
}
 //***************************************************************************
 //Crossover function:select two parents that take part in the crossover.
 //Implements a single point corssover.雜交函數(shù)
 //***************************************************************************
void crossover(void)
 {
   int mem,one;
   int first=0;
   double x;
  for(mem=0;mem<POPSIZE;++mem)
  {
    x=rand()%1000/1000.0;
    if(x<PXOVER)
     {
       ++first;
      if(first%2==0)//選擇雜交的個體對 雜交有待改進 事實上往往是強者與強者雜交 這里沒有考慮雌雄與雜交對象的選擇
        Xover(one,mem);
      else
         one=mem;
 }
  }
 }
//***************************************************************************
 //Mutation function:Random uniform mutation.a variable selected for mutation
 //變異函數(shù) 事實基因的變異往往具有某種局部性
 //is replaced by a random value between lower and upper bounds of the variables.
 //***************************************************************************
 void mutate(void)
 {
   int i,j;
   double lbound,hbound;
   double x;
   for(i=0;i<POPSIZE;i++)
     for(j=0;j<NVARS;j++)
     {
       x=rand()%1000/1000.0;
       if(x<PMUTATION)
      {
         lbound=population[i].lower[j];
         hbound=population[i].upper[j];
         population[i].gene[j]=randval(lbound,hbound);
       }
     }
 }
//***************************************************************************
 //Report function:Reports progress of the simulation.
 //***************************************************************************
 double report(void)
 {
  int i;
  double best_val;//種群內(nèi)最優(yōu)適應值
  double avg;//平均個體適應值
   //double stddev;
  double sum_square;//種群內(nèi)個體適應值平方和
  //double square_sum;
  double sum;//種群適應值
  sum=0.0;
  sum_square=0.0;
  for(i=0;i<POPSIZE;i++)
   {
     sum+=population[i].fitness;
     sum_square+=population[i].fitness*population[i].fitness;
   }
  avg=sum/(double)POPSIZE;
   //square_sum=avg*avg*(double)POPSIZE;
   //stddev=sqrt((sum_square-square_sum)/(POPSIZE-1));
  best_val=population[POPSIZE].fitness;
  fprintf(galog,"%6d %6.3f %6.3f %6.3f %6.3f %6.3f\n",generation,best_val,population[POPSIZE].gene[0],population[POPSIZE].gene[1],avg,sum);
  return avg;
 }
 //***************************************************************************
//main function:Each generation involves selecting the best members,performing
 //crossover & mutation and then evaluating the resulting population,until the
//terminating condition is satisfied.
 //***************************************************************************
 void main(void)
 {
   int i;
   double temp;
   double temp1;
   if((galog=fopen("data.txt","w"))==NULL)
  {
    exit(1);
   }
  generation=1;
  srand(time(NULL));//產(chǎn)生隨機數(shù)
  fprintf(galog,"number value  x1   x2   avg   sum_value\n");
  printf("generation best average standard\n");
  initialize();
  evaluate();
  keep_the_best();
  temp=report();//記錄,暫存上一代個體平均適應值  
   do
   {      
     select();//篩選
     crossover();//雜交
     mutate();//變異
     evaluate();//評價
     keep_the_best();//elitist();
     temp1=report();
     diff=fabs(temp-temp1);//求浮點數(shù)x的絕對值
     temp=temp1;
     generation++;
   }while(generation<MAXGENS&&diff>=STOP);
   //fprintf(galog,"\n\n Simulation completed\n");
   //fprintf(galog,"\n Best member:\n");
   printf("\nBest member:\ngeneration:%d\n",generation);
   for(i=0;i<NVARS;i++)
   {
     //fprintf(galog,"\n var(%d)=%3.3f",i,population[POPSIZE].gene[i]);
     printf("X%d=%3.3f\n",i,population[POPSIZE].gene[i]);
   }
   //fprintf(galog,"\n\n Best fitness=%3.3f",population[POPSIZE].fitness);
   fclose(galog);
   printf("\nBest fitness=%3.3f\n",population[POPSIZE].fitness);
 }