aa.cpp

遗传算法 遗传算法简称GA(Genetic Algorithm)

#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include"stdio.h"
#include"stdlib.h"

//随机数的定义
#define rdint(i) (rand()%(int)(i))
#define rdft() (float)((double)rdint(16384)/(16383.0))
#define rnd(a,b) (rdint((int)(b)-(int)(a)+1)+(int)(a))

struct individual             //定义个体
{
 unsigned   chrom[5];      //个体拥有的染色体
 double     fitness;       //个体适应度
 double     varible;   //个体对应的变量值
 int        xsite;     //交叉位置
    int        parent[1];     //父个体
 int        *utinity;      //特定数据指针变量
};

struct  bestever
{
 unsigned    chrom[5];     //最佳个体染色体
 double      fitness;      //最佳个体适应度
 double      varible;  //最佳个体对应的变量值
 int         generation;   //最佳个体生成代
};

/////////////////////////////////////////////////////////
struct  individual  oldpop[20];    //当前代种群
struct  individual  newpop[20];    //新一代种群

struct  bestever    bestfit;   //最佳个体
double  sumfitness;            //种群中个体适应度累计
double  max;                   //种群中个体最大适应值
double  avg;                   //种群中个体平均适应值
double  min;                   //种群中个体最小适应值 
float   pcross;                //交叉率    
float   pmutation;             //变异率       
int     popsize;               //种群大小     
int     lchrom;                //染色体长度    
int     chromsize;             //存储一染色体所需字节数       
int     gen;                   //当前世代 
int     maxgen;                //最大世代数    
int     run;                   //当前运行次数 
int     maxruns;               //总运行次数
int     ncross;                //总交叉次数
int     nmutation;             //总变异次数
int     idum=-1;               //随机数系数
//////////////////////////////////////////////////////////////////
//函数定义
void     initpop();                                         
void     objfunc(struct individual *);          
int      select();                           
int      crossover(unsigned *parent1,unsigned *parent2,unsigned *child1,unsigned *child2);
void     mutation(unsigned *child);      //变异操作   
void     generation();                   //生成下一代 
void     sumfit();                       //种群适应度求和
void     statistics(struct individual *pop);   
/////////////////////////////////////////////////////////////////// 
void initialize()        //遗传算法初始化 
{
 //输入种群个体总数
    popsize=20;
 if(popsize%2!=0)
 {
  popsize++;
  cout<<"popsize已设为偶数";
 }

 //输入染色体长度
    lchrom=64;
 //确定染色体的字节长度 
    chromsize = (lchrom/(8*sizeof(unsigned)));
    if(lchrom%(8*sizeof(unsigned))) 
 {
  chromsize++;
 }

 //输入最大世代数
 //cout<<"输入最大世代数maxgen(100～300)";
 //cin>>maxgen;
    maxgen=300;

 //输入交叉率和变异率
 //cout<<"输入交叉率pcross(0.2～0.9)";
 //cin>>pcross;
    pcross=0.8;

 //cout<<"输入变异率pmutation(0.01～0.1)";
 //cin>>pmutation;
    pmutation=0.05;

 //初始化全局计数变量和一些数值
    nmutation = 0;
    ncross = 0;
    bestfit.fitness = 0.0;
    bestfit.generation = 0;

 //初始化种群，并统计计算结果
    initpop();
}

void  initpop()          //随机化初始种群
{
 int        i,j,k=0,stop=0;
 unsigned int mask=1; 
 for(i=0;i<popsize;i++)         //个体染色体初始化
 {
  for(j=0;j<chromsize;j++)
  {
   oldpop[i].chrom[j]=0;
   if(j==(chromsize-1))
   {
    stop=lchrom-(j*(8*sizeof(unsigned)));
   }
   else
   {
    stop=8*sizeof(unsigned);
   }
   for(k=1;k<=stop;k++)
   {
    oldpop[i].chrom[j]=oldpop[i].chrom[j]<<1;
    if(rdft()<=0.5)
    {
     oldpop[i].chrom[j]=oldpop[i].chrom[j]|mask;
    }
   }
  }
  oldpop[i].parent[0]=0;        //初始化父个体信息
  oldpop[i].parent[1]=0;
  oldpop[i].xsite=0;
  objfunc(&(oldpop[i]));        //计算个体适应度
 }
} 


/////////////////////////////////////////////////////////////
//计算适应度                       
void objfunc(struct individual *critter)            // 计算适应度函数值
{ 
 unsigned mask=1;
 unsigned bitpos;
 unsigned tp;
 double   pow(),bitpow;
 int j,k,stop;
 critter->varible=0.0;
 for(k=0;k<chromsize;k++)
 {
  if(k==(chromsize-1))
  {
   stop=lchrom-(k*(8*sizeof(unsigned)));
  }
  else
  {
   stop=k*(8*sizeof(unsigned));
  }
  tp=critter->chrom[k];
  for(j=0;j<stop;j++)
  {
   bitpos=j+(8*sizeof(unsigned))*k;
   if((tp&mask)==1)
   {
    bitpow=powl(2.0,(double)bitpos);
    critter->varible=critter->varible+bitpow;
   }
   tp=tp>>1;
  }
 }
 critter->varible=-1+3*critter->varible/(powl(2.0,(double)lchrom)-1);
 critter->fitness=critter->varible*sin(critter->varible*10*atan(1)*4)+2.0;
}


int select()              //新个体选择程序
{
 double sum,pick;
 int i;
 pick=rdft();
 sum=0;
 if(sumfitness!=0)
 {
  for(i=0;(sum<pick)&&(i<popsize);i++)
  {
   sum+=oldpop[i].fitness/sumfitness;
  }
 }
 else
 {
  i=int(rdft()*double(popsize));
 }
 return(i-1);
}


//由两个父个体产生两个子个体
int crossover(unsigned *parent1,unsigned *parent2,unsigned *child1,unsigned *child2)
{
 int j,k;
 unsigned jcross;
 unsigned mask,temp;
 if(rdft()<=pcross)         //产生随机数小于交叉率时执行交叉操作
 {
  jcross=rnd(1,lchrom-1); //交叉位置在1～l-1之间
  ncross++;
  for(k=1;k<=chromsize;k++)
  {
   if(jcross>=(k*(8*sizeof(unsigned))))
   {
    child1[k-1]=parent1[k-1];
    child2[k-1]=parent2[k-1];
   }
   else
   {
    if((jcross<(k*8*sizeof(unsigned)))&&(jcross>((k-1)*8*sizeof(unsigned))))
    {
     mask=1;
     for(j=1;j<=(int)(jcross-1-(k-1)*(8*sizeof(unsigned)));j++)
     {
      temp=1;
      mask=mask<<1;
      mask=mask|temp;
     }
     child1[k-1]=((parent1[k-1])&mask)|((parent2[k-1])&(~mask));
     child2[k-1]=((parent1[k-1])&(~mask))|((parent2[k-1])&mask);
    }
    else
    {
        child1[k-1]=parent2[k-1];
        child2[k-1]=parent1[k-1];
    }
   }
  }
 }
 else
 {
  for(k=0;k<chromsize;k++)
  {
      child1[k]=parent1[k];
      child2[k]=parent2[k];
  }
  jcross=0;
 }
 return(jcross);
}

void mutation(unsigned * child)    //变异操作
{
 int j,k,stop;
 unsigned mask,temp=1;
 for(k=0;k<chromsize;k++)
 {
  mask=0;
  if(k==chromsize-1)
  {
   stop=lchrom-(k*(8*sizeof(unsigned)));
  }
  else
  {
   stop=8*sizeof(unsigned);
  }
  for(j=0;j<stop;j++)
  {
   if(rdft()<=pmutation)
   {
    mask=mask|(temp<<j);
    nmutation++;
    child[k]=(child[k])^(mask);
   } 
  }  
 }
}

void generation()
{
 int mate1,mate2,jcross,j=0;
 sumfit();
 do
 {
  mate1=select();
  mate2=select();
  jcross=crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,newpop[j].chrom,newpop[j+1].chrom);
  mutation(newpop[j].chrom);
  mutation(newpop[j+1].chrom);
  objfunc(&(newpop[j]));
  newpop[j].parent[0]=mate1+1;
  newpop[j].xsite=jcross;
  newpop[j].parent[1]=mate2+1;
  objfunc(&(newpop[j+1]));
  newpop[j+1].parent[0]=mate1+1;
  newpop[j+1].xsite=jcross;
  newpop[j+1].parent[1]=mate2+1;
  j=j+2;
 }while(j<(popsize-1));
}


void sumfit()
{
 int j=0;
 sumfitness=0;
 for(j=0;j<popsize;j++)
 {
  sumfitness=sumfitness+oldpop[j].fitness;
 }
}

void main()  //主程序
{ 
 struct individual temp[20];
 //cout<<"输入遗传算法执行次数(1～5)"<<endl;
 //cin>>maxruns;
    maxruns=10;
 max=0;
 for(run=1;run<=maxruns;run++)
 {
  initialize();
  for(gen=0;gen<maxgen;gen++)
  {
   generation();
   for(int i=0;i<20;i++)
   {
    temp[i]=oldpop[i];
       oldpop[i]=newpop[i];
       newpop[i]=temp[i];
       if(max<oldpop[i].fitness)
    {
                    max=oldpop[i].fitness;     
    }
   }
  }
 }
 for(int i=0;i<20;i++)
 {    
	 
	 for(int j=0;j<chromsize;j++)
	 {
	      cout<<oldpop[i].chrom[j]<<" ";
	 }
     cout<<"oldpop["<<i<<"].fitness="<<oldpop[i].fitness<<endl;
 }
 cout<<"\n oldpop.fitness max="<<max<<"\n";
}