遗传算法的一个实现程序

来源：互联网   发布日期：2011-09-29 15:39:06   浏览：8146次  

智能算法的经典——遗传算法的一个实现程序 (2008-09-10 14:58:22)

标签： 智能算法 遗传算法 ga 程序 it 分类： 技术分享

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define POPSIZE 50 //种群大小,可以自定义
#define MAXGENS 1000
#define NVARS 3
#define PXOVER 0.8 //交叉概率
#define PMUTATION 0.2 //变异概率
#define TRUE 1 
#define FALSE 0

int generation;
int cur_best;
FILE*gaout;
struct genotype            
{
 double gene[NVARS];    
 double fitness;      //定义适应值
 double upper[NVARS];   //可行解的上界
 double lower[NVARS];   //可行解的下界
 double rfitness;       //相对概率
 double cfitness;       //累加概率
};
struct genotype pop[POPSIZE+1]; //population当前种群
struct genotype newpop[POPSIZE+1];//new population新种群,即子代

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

void main()
{
 int i;
 clock_t start,end;
 start=clock();
 if((gaout=fopen("gaout.txt","w"))==NULL)//打开同一目录下的文件
 {
  printf("can not open the gaout.txt!\n");
   
   exit(1);
 }

 generation=0;
 fprintf(gaout,"\n generation  best   average  standard  \n");
 fprintf(gaout,"\n number     value  fitness  deviation\n");
 
 initialize();
 evaluate();
 keep_the_best();

 while(generation<MAXGENS)
 {
     report();
  generation++;

  gaselect();
  crossover();
  mutate();
  
  evaluate();
  elitist();
 }
 fprintf(gaout,"\n \nSimulation completed\n");
 fprintf(gaout,"\n Best  member:\n");

 for(i=0;i<NVARS;i++)
  fprintf(gaout,"\n var(%d)=%3.3f",i,pop[POPSIZE].gene[i]);
 
 fprintf(gaout,"\n\nBest fitness=%3.3f",pop[POPSIZE].fitness);
 end=clock();
 fprintf(gaout,"\nthe time it takes %lf:",1.0*(end-start)/CLK_TCK);

 fclose(gaout);
 printf("Success!\n");
 
}

void initialize(void)
{
 FILE*infile;
 int i,j;
 double lbound,ubound;

 if((infile=fopen("gadata.txt","r"))==NULL)
 {
  fprintf(gaout,"\n找不到初始文件!\n");
  exit(1);
 }

 //initialize variables within the bounds;
 
 for(i=0;i<NVARS;i++)
 {
  fscanf(infile,"%lf",&lbound);
  fscanf(infile,"%lf",&ubound);
        fprintf(gaout,"The lower bound of var[%d]=%lf\n",i,lbound);
     fprintf(gaout,"The upper bound of var[%d]=%lf\n",i,ubound);

  for(j=0;j<POPSIZE;j++)
  {
   pop[j].fitness=0;
   pop[j].rfitness=0;
   pop[j].cfitness=0;
   pop[j].lower[i]=lbound;
   pop[j].upper[i]=ubound;
   pop[j].gene[i]=randval(pop[j].lower[i],pop[j].upper[i]);
   
  
  }
 }

  fclose(infile);  
 
}

double randval(double low,double high)
{
 double val;
 val=((double)(rand()%1001)/1000.0)*(high-low)+low;//产生从上界到下界之间的随机数
 return(val);

}

void evaluate(void)
{
 int mem;
 int i;
 double x[NVARS+1];
 fprintf(gaout,"gen=%d\n\n",generation);

 for(mem=0;mem<POPSIZE;mem++)
 {
  for(i=0;i<NVARS;i++)
  {
  x[i+1]=pop[mem].gene[i];
  //fprintf(gaout,"pop[%d].gene[%d]=%lf\n",mem,i,pop[mem].gene[i]);
  }
  pop[mem].fitness=(x[1]*x[1])-(x[1]*x[2])+x[3];
  
  //fprintf(gaout,"pop[%d].fitness=%lf\n\n",mem,pop[mem].fitness);
 }
}
void keep_the_best(void)
{
 int mem;
 int i;
 cur_best=0;//stores the index of the best individule;
 
    pop[POPSIZE].fitness=0;
 for(mem=0;mem<POPSIZE;mem++)
 {
  if(pop[mem].fitness>pop[POPSIZE].fitness)
  {
   cur_best=mem;
   
  }
 }
 pop[POPSIZE].fitness=pop[cur_best].fitness;

 //copy the best;
 for(i=0;i<NVARS;i++)
  pop[POPSIZE].gene[i]=pop[cur_best].gene[i];

 //fprintf(gaout,"The best of 0 = %d\n",cur_best);
}
//the best member of the previous generation is stored as the last in the array; if the best of the current
//generation is worse than the best of the previous ,the latter one would replace the forer.
void elitist(void)
{
 int i;
 double best,worst;
 int best_mem,worst_mem;

 best=pop[0].fitness;
 worst=pop[0].fitness;

 for(i=0;i<POPSIZE-1;i++)
 {
  if(pop[i].fitness>pop[i+1].fitness)
  {
   if(pop[i].fitness>=best)
   {
    best=pop[i].fitness;
    best_mem=i;
   }
   if(pop[i+1].fitness<=worst)
   {
    worst=pop[i+1].fitness;
    worst_mem=i+1;
   }
  }
  else
  {
   
    if(pop[i].fitness<=worst)
    {
    worst=pop[i+1].fitness;
    worst_mem=i;
    }

      if(pop[i+1].fitness>=best)
      {
    best=pop[i+1].fitness;
    best_mem=i+1;
      }
  }
 }

 if(best>=pop[POPSIZE].fitness)
 {
  for(i=0;i<NVARS;i++)
  pop[POPSIZE].gene[i]=pop[best_mem].gene[i];
 pop[POPSIZE].fitness=pop[best_mem].fitness;
 }
 else
 {
  for(i=0;i<NVARS;i++)
  pop[worst_mem].gene[i]=pop[best_mem].gene[i];
  pop[worst_mem].fitness=pop[best_mem].fitness;
 }

}
void gaselect(void)
{
 int mem,i,j;
 double sum=0;
 double p;
 
    //the total fitness;
 for(mem=0;mem<POPSIZE;mem++)
 {
  sum+=pop[mem].fitness;
 }

    //rfitness;
 pop[0].cfitness=pop[0].rfitness;
 for(mem=0;mem<POPSIZE;mem++)
 {
  pop[mem].rfitness=pop[mem].fitness/sum;
 }

    //cfitness;
 
 for(mem=1;mem<POPSIZE;mem++)
 {
  pop[mem].cfitness=pop[mem-1].cfitness+pop[mem].rfitness;
 }
 

 for(i=0;i<POPSIZE;i++)
 {
  p=rand()%1000/1000.0;
  if(p<pop[0].cfitness)
  {
   //if(generation==10)
   // fprintf(gaout,"newpop[i] is pop[0]!\n",i);
   newpop[i]=pop[0];
  }
  else
  {  
   for(j=0;j<POPSIZE-1;j++)
   {
   if(p>=pop[j].cfitness&&p<=pop[j+1].cfitness)
   {
    newpop[i]=pop[j+1];
   break;
   }
   
   }
   //if(generation==10)
   // fprintf(gaout,"newpop[%d] is pop[%d]!\n",i,j+1);//
  }

       
 }

 //copy the newpop;
 for(i=0;i<POPSIZE;i++)
 {
  pop[i]=newpop[i];
 }

}
//a single point crossover;
void crossover(void)
{
 int mem,one;
 int first=0; //count the number of members chosen;
 double x;

 for(mem=0;mem<POPSIZE;++mem)
 {
  x=rand()%1000/1000.0;
  if(x<PXOVER)
  {
   ++first;
   if(first%2==0)//当有两个个体的交叉概率p满足条件以后，就将其进行交叉
    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(&pop[one].gene[i],&pop[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)
   {
   //found the bounds on the variable to be mutated;
   lbound=pop[i].lower[j];
   hbound=pop[i].upper[j];
   pop[i].gene[j]=randval(lbound,hbound);//给出一个新的直；

   }
  }
}

 

void report(void)
{
 int i;
 double best_val;
 double avg;
 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; 
 sum=0.0;
 sum_square=0.0;

 for(i=0;i<POPSIZE;i++)
 {
  sum+=pop[i].fitness;
  sum_square+=pop[i].fitness*pop[i].fitness;
 }

 avg=sum/(double)POPSIZE;
 square_sum=avg*avg*(double)POPSIZE;
 stddev=sqrt((sum_square-square_sum)/(POPSIZE-1));
 best_val=pop[POPSIZE].fitness;

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

分享

顶

阅读┊ ┊ ┊┊ ┊打印┊

已投稿到：

排行榜 圈子

加载中，请稍候......

前一篇：解放思想的一个任务是消除“文革心理”

后一篇：中秋月，美在岳麓山

评论 重要提示：警惕虚假中奖信息       在插画中找寻曾经的美好       关注每日最热门博客 

评论加载中，请稍候...

发评论 旅游行摄，轻品日本       是谁改变了你的博客？       关注每日最热门博客

登录名： 密码： 找回密码 注册

昵   称：

   

验证码： 请点击后输入验证码

以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

< 前一篇解放思想的一个任务是消除“文革心理”

后一篇 >中秋月，美在岳麓山

赞助本站