非佳点集算法.cpp

理解普通的遗传算法和佳点集遗传算法的基本思想和不同点,用遗传算法测试一标准函数。佳点集算法测试一标准函数,理解普通的遗传算法和佳点集遗传算法的基本思想和不同点

//求解f(X)=x1*x1+x2*x2+x3*x3的最大值 -5.12<=xi<=5.12
#include <iostream.h>
#include <time.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
const int N=3;  //变量的个数
const int LENGTH=8;  //每个变量的编码位数
const int CHROMLENGTH=LENGTH*N; //染色体长度
const int popsize=4;  //种群中个体个数
const int maxgeneration=10; //最大进化代数
const double pc=0.8; //交叉概率
const double pm=0.2; //变异概率
const double Umin=-5.12; //变量范围的最小数
const double Umax=5.12; //变量范围的最大数
/***类声明***/
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 (X[0]*X[0]+X[1]*X[1]+X[2]*X[2]);
}
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]<<"  ";
	}
	cout<<")";*/
	   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<<endl;
   cout<<"当前最好的个体是"<<currentindividual.chrom;
   cout<<"   其适应度为"<<currentindividual.fitness;
   cout<<endl;
}

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++)
   {
      ps[i]=population[i].fitness/fitness_sum;//适应度除以适应度之和：选择概率！
      number[i]=0;//选中次数
	  except_num[i]=ps[i]*popsize;//计算期望次数
   }
 
   for(i=0;i<popsize;i++)
   {   
      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[j];flag=j;
			   fraction[j]=-1;
			}
		 }//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];
	 nextpopulation[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=nextpopulation[i].chrom[j];
			   nextpopulation[i].chrom[j]=nextpopulation[k].chrom[j];
			   nextpopulation[k].chrom[j]=temp;  //nextpopulation为交叉表中的子代
			}
		 }//if
		 else crossoverpoint[i]=crossoverpoint[k]=-1;
	 }//if
	  //nextpopulation[i]=population[i];  
  }//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<<endl;
	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<<endl; 
  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<<endl;
	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;
  int jixu;
  cout<<"是否继续（1/0）：";
  cin>>jixu;
  if (jixu==1) {main();}
  else  exit(0);
}