ga.cpp

用GA求函数的极小值群体大小为15

//console application
/*这里是对应求解y=x*sin(1/x)在[0.05，0.5]中的极小值（这里确切说是局部最小值）
设实数编码，基因长度为3，上下限为[0.15,0],这样评估函数就设为0.5-((三个基因的和+0.05)sin（1/(三个基因的和+0.05)）),
评估函数的值阈[0，1]，其最大值就是最好的适应度
*/

#include "stdafx.h"
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define POPSIZE 15               /* 种群大小 */
#define MAXGENS 1000             /* 最大代数 */
#define NVARS 3                  /* 编码的长度*/
#define PXOVER 0.8               /* 交叉概率 */
#define PMUTATION 0.01           /* 变异概率 */
#define TRUE 1
#define FALSE 0

int generation;                  /* 当前代数 */
int cur_best;                    /* 当前最佳个体 */
FILE *galog;                     /* 输出文件 */

struct genotype              /* 代表一个个体的结构体 */
{
  double gene[NVARS];        /* 编码 */
  double fitness;            /* 适应度 */
  double upper[NVARS];       /* 编码上限 */
  double lower[NVARS];       /* 编码下限 */
  double rfitness;           /* 此个体相对种群的适应度 */
  double cfitness;           /*  种群中个体适应度累计 */
};
//下面+1的目的是为了存储最优值keep_the_best()
struct genotype population[POPSIZE+1];    /* population */
struct genotype newpopulation[POPSIZE+1]; /* 下一代 */


/* 函数声明 */

void initialize(void);
double randval(double, double);
void evaluate(void);
void keep_the_best(void);
void elitist(void);
void select(void);
void crossover(void);
void Xover(int,int);
void swap(double *, double *);
void mutate(void);
void report(void);

/***********************************************************/
/* 初始化函数 */
/***********************************************************/
void initialize(void)
{
FILE *infile;
int i, j;
double lbound, ubound;

if ((infile = fopen("inputdata.txt","r"))==NULL)
      {
      fprintf(galog,"\nCannot open input file!\n");
      exit(1);
      }
for (i = 0; i < NVARS; i++)    //每维编码都有上下限
      {
      fscanf(infile, "%lf",&lbound);      //好象是实数编码啊
      fscanf(infile, "%lf",&ubound);

      for (j = 0; j < POPSIZE; j++)  //初始化
           {
           population[j].fitness = 0;    //这里会重复赋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]);   //每维随机赋初值
           }
      }

fclose(infile);
}

/***********************************************************/
/*  随机产生low和high之间的一个任意数 */
/***********************************************************/

double randval(double low, double high)
{
double val;
val = ((double)(rand()%1000)/1000.0)*(high - low) + low;
return(val);
}

/*************************************************************/
/* 评估函数,这儿是： */
/* 0.5-((三个基因的和+0.05)sin（1/(三个基因的和+0.05)）)*/
/*************************************************************/
void evaluate(void)
{
int mem;
int i;
double xx,anti_xx;
double x[NVARS+1];
double fit;
for (mem = 0; mem < POPSIZE; mem++)
      {
      for (i = 0; i < NVARS; i++)
            x[i+1] = population[mem].gene[i];
	  xx=x[1]+x[2]+x[3]+0.05;
	  anti_xx=1/xx;
	  //printf("%f\n",xx*sin(anti_xx));
	  fit=population[mem].fitness=0.5-xx*sin(anti_xx);
	  //if(fit<0.5)
	  //printf("fitness is %f\n",fit);
      }
}

/***************************************************************/
/* Keep_the_best function: 保证最优的存活  */
/***************************************************************/

void keep_the_best()
{
int mem;
int i;
cur_best = 0; 

for (mem = 0; mem < POPSIZE; mem++)
      {
      if (population[mem].fitness > population[POPSIZE].fitness)
            {
            cur_best = mem;
            population[POPSIZE].fitness = population[mem].fitness;
            }
      }
for (i = 0; i < NVARS; i++)									//保存当前最优基因
      population[POPSIZE].gene[i] = population[cur_best].gene[i];
}

/***************************************************************/
/* 如果上一代的最优基因优于当前一代的最优基因， */
/* 就用上一代的最优基因代替当前的最差基因 */
/***************************************************************/
void elitist()
{
int i;
double best, worst;            
int best_mem, worst_mem;

best = population[0].fitness;
worst = population[0].fitness;
for (i = 0; i < POPSIZE - 1; ++i)   //一次循环记录最优值与最差值
      {
      if(population[i].fitness > population[i+1].fitness)
            {     
            if (population[i].fitness >= best)
                  {
                  best = population[i].fitness;
                  best_mem = i;
                  }
            if (population[i+1].fitness <= worst)
                  {
                  worst = population[i+1].fitness;
                  worst_mem = i + 1;
                  }
            }
      else
            {
            if (population[i].fitness <= worst)
                  {
                  worst = population[i].fitness;
                  worst_mem = i;
                  }
            if (population[i+1].fitness >= best)
                  {
                  best = population[i+1].fitness;
                  best_mem = i + 1;
                  }
            }
      }
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;
    }
}

/**************************************************************/
/* 赌轮法产生下一代的所有个体 */
/**************************************************************/
void select(void)
{
int mem, i, j, k;
double sum = 0;
double p;

/* find total fitness of the population */
for (mem = 0; mem < POPSIZE; mem++)
      {
      sum += population[mem].fitness;
      }

/* calculate relative fitness */
for (mem = 0; mem < POPSIZE; mem++)   //计算每个个体相对种群的适应度
      {
      population[mem].rfitness =  population[mem].fitness/sum;       //赌轮
      }
population[0].cfitness = population[0].rfitness;

/* calculate cumulative fitness */
for (mem = 1; mem < POPSIZE; mem++)                   //适应度累积
      {
      population[mem].cfitness =  population[mem-1].cfitness +      
                          population[mem].rfitness;
      }

/* finally select survivors using cumulative fitness. */
//赌轮法产生下一代的所有个体
for (i = 0; i < POPSIZE; i++)
      {
      p = rand()%1000/1000.0;                             //p位于0到1之间
      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];      //更新    
}

/***************************************************************/
/* 交叉操作,选择两个进行交叉的染色体*/
/***************************************************************/
void crossover(void)
{
int i, mem, one;
int first  =  0; /* count of the number of members chosen */
double x;

for (mem = 0; mem < POPSIZE; ++mem)
      {
      x = rand()%1000/1000.0;
      if (x < PXOVER)                //PXOVER是交叉的概率，可以交叉
            {
            ++first;
            if (first % 2 == 0)             //first是偶数
                  Xover(one, mem);
            else
                  one = mem;				//奇数时不交换
            }
      }
}
/**************************************************************/
/* 具体实施交叉操作 */
/**************************************************************/

void Xover(int one, int two)
{
int i;
int point; /* crossover point */

/* select crossover point */
if(NVARS > 1)
   {
   if(NVARS == 2)
         point = 1;
   else
         point = (rand() % (NVARS - 1)) + 1;

   for (i = 0; i < point; i++)   //交换前point个基因 
        swap(&population[one].gene[i], &population[two].gene[i]);

   }
}

/*************************************************************/
/* 交换 */
/*************************************************************/

void swap(double *x, double *y)
{
double temp;

temp = *x;
*x = *y;
*y = temp;

}

/**************************************************************/
/* 变异，变异后重新随机赋值  */
/**************************************************************/
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)					//可以变异
                  {
                  /* find the bounds on the variable to be mutated */
                  lbound = population[i].lower[j];
                  hbound = population[i].upper[j]; 
                  population[i].gene[j] = randval(lbound, hbound);   //所谓的变异就是重新赋值
                  }
            }
}

/***************************************************************/
/* 输出当前一代的情况 */
/***************************************************************/
void report(void)
{
int i;
double best_val;            /* best population fitness */
double avg;                 /* avg population fitness */
double stddev;              /* std. deviation of population fitness */
double sum_square;          /* sum of square for std. calc */
double square_sum;          /* square of sum for std. calc */
double sum;                 /* total population fitness */

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 * POPSIZE;
stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1));  //方差或什么的
best_val = population[POPSIZE].fitness;

fprintf(galog, "\n%5d,      %6.3f, %6.3f, %6.3f ", generation,
                                      best_val, avg, stddev);
}

/**************************************************************/
/* 主函数 */
/**************************************************************/

void main(void)
{
int i;
double xx=0.05;
if ((galog = fopen("galog.txt","w"))==NULL)
      {
      exit(1);
      }
generation = 0;

fprintf(galog, "\n generation  best  average  standard \n");
fprintf(galog, " number      value fitness  deviation \n");

initialize();
evaluate();
keep_the_best();
while(generation<MAXGENS)
      {
      generation++;
      select();
      crossover();
      mutate();
      report();
      evaluate();
      elitist();
      }
fprintf(galog,"\n\n Simulation completed\n");
fprintf(galog,"\n Best gene: \n");

for (i = 0; i < NVARS; i++)
   {
   fprintf (galog,"\n var(%d) = %3.3f",i,population[POPSIZE].gene[i]);
   xx+=population[POPSIZE].gene[i];
   }
   fprintf(galog,"\n对应的x值是：%f",xx);
fprintf(galog,"\n\n 区间中的局部最小值 = %3.3f",0.5-population[POPSIZE].fitness);
fclose(galog);
printf("Success\n");
}
/***************************************************************/