ga2.cpp

利用数论中的佳点集的理论和方法

/***求f(X)=100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1) -2.048<=xi<=2.048的最大值*****/
#include <iostream.h>
#include <time.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
/****常量声明,遗传算法的系统参数*********/
const int N=2;  //变量的个数
const int LENGTH=5;  //每个变量的编码位数
const int CHROMLENGTH=LENGTH*N; //染色体长度
const int popsize=4;  //种群中个体个数
const int maxgeneration=200; //最大进化代数
const double pc=0.6; //交叉概率
const double pm=0.01; //变异概率
const double Umin=-2.048; //变量范围的最小数
const double Umax=2.048; //变量范围的最大数
/***类声明***/
class individual{
public: 
	 char chrom[CHROMLENGTH+1]; //最后一位放'\0'
	 double X[N]; //存放每个变量的实数值
	 double fitness; //每个个体的适应值
};						   

/*******全局变量声明**********/
int generation;
//int best_index;
//int worst_index;
class individual bestindividual;
//class individual worstindividual;
class individual currentindividual;
class individual population[popsize];
class individual newpopulation[popsize];
class individual nextpopulation[popsize];
double fitness_sum;

void GenerateInitialPopulation()
{
    srand((unsigned)   time   (NULL));   

	 for(int i=0;i<popsize;i++)
	 {
	    for(int j=0;j<CHROMLENGTH;j++)
		{
			population[i].chrom[j]=(rand()%2==0)?'0':'1';
		}
		population[i].chrom[CHROMLENGTH]='\0';
	 }
	 for(i=0;i<popsize;i++)
			 cout<<population[i].chrom<<" ";
	 cout<<endl;
}

double decodechromesome(char a[],int i,int j)
{
    double y=0;
	for(int k=i;k<j;k++)
	{
	   y+=(int(a[k])-48)*pow(2,j-k-1);
	}
	y=Umin+y*(Umax-Umin)/(pow(2,LENGTH)-1);
	return y;
}

void calculatevalue() //计算每个变量的值
{
   for(int i=0;i<popsize;i++)
   {
      int count=0;
	  for(int j=0;j<CHROMLENGTH;)
	  {
	     population[i].X[count++]=decodechromesome(population[i].chrom,j,j+LENGTH);
	     j=j+LENGTH;
	  }
   }
}

double F(double X[],int N)
{
   return (100*(X[0]*X[0]-X[1])*(X[0]*X[0]-X[1])+(1-X[0])*(1-X[0]));
}
void calculatefitness()
{
    calculatevalue();
	fitness_sum=0.0;
	
	for(int i=0;i<popsize;i++)
	{  //for(int j=0;j<N;j++)
	     // cout<<"X=("<<population[i].X[j]<<"  ";
	   population[i].fitness=F(population[i].X,N);
       fitness_sum+=population[i].fitness;
	}
}

void FindBestIndividual()
{
   calculatefitness();
   bestindividual=population[0];
   
   for(int i=1;i<popsize;i++)
   {
     if(population[i].fitness>bestindividual.fitness)
	 {
	    bestindividual=population[i];
	 }
   }
   currentindividual=bestindividual;
   
}

void EvaluatePopulation()
{
   FindBestIndividual();
   cout<<"当前最好的个体是"<<currentindividual.chrom;
   cout<<"   其适应度为"<<currentindividual.fitness;
}

double ps[popsize];
int number[popsize];
void selectoperation() //取整数后，再取小数
{
	int i;
	double except_num[popsize];
	int count=0; double max=0.0;
    double fraction[popsize];
   
  /*for(i=0;i<popsize;i++)
  {
     population[i]=newpopulation[i];
  }*/
  for( i=0;i<popsize;i++)
   {
      ps[i]=population[i].fitness/fitness_sum;
      number[i]=0;
	  except_num[i]=ps[i]*popsize;
   }
 
   for(i=0;i<popsize;i++)
   {
       //srand((unsigned)   time   (NULL));   
      number[i]=int(except_num[i]);
	  count+=number[i];
	  fraction[i]=except_num[i]-number[i];
   }
    while(count!=4)
	  {  int flag; max=0.0;
	     for(int j=0;j<popsize;j++)
		 {
		    if(max<fraction[j])
			{
			   max=fraction[i];flag=j;
			}
		 }//for
		 number[flag]++;
		 count++;
	  }
   count=0;
   for(i=0;i<popsize;i++)
   {
     int num=number[i];
      while(num>0)
	  {
		  newpopulation[count++]=population[i];
	      num--;
	  }
   }
}


int crossoverindividual[popsize];
int crossoverpoint[popsize];
void crossoveroperation() 
{//每个染色体都有个随机产生的交叉概率,若小于给定的交叉概率,则进行交叉,否则不进行
  for(int i=0;i<popsize;i++)
  {
	 population[i]=newpopulation[i];
     crossoverindividual[i]=-1;
  }
   
   for(i=0;i<popsize;i++) 
  {
	  	 
	   if(crossoverindividual[i]==-1)
	  {
	     // srand((unsigned)   time   (NULL));   

		  int k=rand()%popsize;
		  for(int r=0;r<popsize;r++)
		  {
		    if(crossoverindividual[r]==k||i==k) 
			{
				k=rand()%popsize;
				r=0;
			}
		  }
		 crossoverindividual[i]=k;
		 crossoverindividual[k]=i;
		 
		 double p=rand()%99/100.0;
		 if(p<=pc)
		 {  //进行交叉
		    crossoverpoint[i]=crossoverpoint[k]=rand()%CHROMLENGTH;
		    for(int j=crossoverpoint[i];j<CHROMLENGTH;j++)
			{
			   char temp=population[i].chrom[j];
			   population[i].chrom[j]=population[k].chrom[j];
			   population[k].chrom[j]=temp;
			}
		 }//if
		 else crossoverpoint[i]=crossoverpoint[k]=-1;
	 }//if
	  nextpopulation[i]=population[i];  //nextpopulation为交叉表中的子代
  }//for
}

char isMutate[popsize];  //是否变异
int mutatepoint[popsize];//变异的位置
void mutationoperation() 
{
  for(int i=0;i<popsize;i++)
  {
	 //srand((unsigned)   time   (NULL));    
	 mutatepoint[i]=-1;	 
     population[i]=nextpopulation[i];
	 newpopulation[i]=population[i];
	 population[i]=nextpopulation[i];
	 double p=rand()%99/100.0;
	 if(p<=pm)
	 {
	    isMutate[i]='Y';
		int k=rand()%CHROMLENGTH;
        mutatepoint[i]=k;
		newpopulation[i].chrom[k]=(newpopulation[i].chrom[k]=='0')?'1':'0';
	 }//if
	 else isMutate[i]='N';
	
  }//for
}


void outputselect()
{
   cout<<"第"<<generation<<"代选择情况"<<endl;
   cout<<"序号    种群        适应值    选择概率    选中次数"<<endl;
   for(int i=0;i<popsize;i++)
   {
     cout<<i<<"  "<<population[i].chrom<<"       "<<population[i].fitness<<"      "
		 <<ps[i]<<"       "<<number[i]<<endl;
   }
}

void outputcrossover()
{
   cout<<"第"<<generation<<"代种群交叉情况"<<endl;
   cout<<"序号   种群     交叉个体   交叉值  子代  "<<endl;
   for(int i=0;i<popsize;i++)
   {
      cout<<i<<" "<<population[i].chrom<<"  "<<crossoverindividual[i]
		  <<"  "<<crossoverpoint[i]<<"  "<<nextpopulation[i].chrom<<endl;
   }
}

void outputmutation()
{
  cout<<"第"<<generation<<"代种群变异情况"<<endl;
  cout<<"序号   种群   是否变异  变异值   新种群"<<endl;
  for(int i=0;i<popsize;i++)
  {
    cout<<i<<"  "<<population[i].chrom<<"  "<<isMutate[i]<<"  "<<mutatepoint[i]
		<<" "<<newpopulation[i].chrom<<endl;
  }
  for(i=0;i<popsize;i++)
     population[i]=newpopulation[i];
}

void GenerateNextPopulation()
{
  selectoperation();
  outputselect();
  crossoveroperation();
  outputcrossover();
  mutationoperation();
  outputmutation();
}



void main()
{
   generation=0;
   GenerateInitialPopulation();
   calculatevalue();
   calculatefitness();
   FindBestIndividual();
   EvaluatePopulation();
   while(generation<maxgeneration)
   {
	   GenerateNextPopulation();
	   EvaluatePopulation();
	  // PerformEvaluation();
	  // OutputReport();
	   generation++;
   }
   cout<<"函数的最大值为"<<currentindividual.fitness<<endl;
  cout<<"最优解为X=(";
  for(int i=0;i<N;i++)
	  cout<<currentindividual.X[i]<<"  ";
  cout<<")"<<endl;
  cout<<endl;
  cin>>generation;
}