demo2.cpp

一个实现基因表达式编程来解决函数发现问题的小程序

#include<stdio.h>
#include<time.h>
#include<iostream.h>
#include<math.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#include <C:\MATLAB6p5\extern\include\engine.h >

#define selectrange 100
#define Rand_Max 32767.0
//全局变量
int m_GepNum;
int nCurGepNum;
int m_nGroupSize;
int m_nNextGroupSize;
int m_nNumOfGenes;
int m_nHeadSize;
float m_PMutation;
float m_PRecombination;
int nLengthOfTail;
int nLengthOfGene;
int nLength;
const int nArity=2;
int m_nIdVariNum;
int nGepCrossNum;
int m_ConstantNum=10;
int m_LowerBound;
int m_UpperBound;
int nRow;
int nColumn;
int nCurConNum=0;//现在指向的常数个数
int asize=0;
double ** trainingset;
FILE *in_fp,*out_fp;

struct individual {
   double fitness;
   double *constants;
   char *GeneSerial;
};
struct bestever{
   double fitness;
   double *constants;
   char *GeneSerial;
   int generation;
};
struct binarytreenode{
   char element;
   binarytreenode *lchild;
   binarytreenode *rchild;
};


struct individual **oldpop;
struct individual *newpop;
struct bestever *bestfit;
binarytreenode* *binarytree;
double * midresult;
double TotalF=0;
double max;
double avg;
double min;
double *data;
char functionset[4]={'+','-','*','/'};
char *terminalset;
char *fandt;
char **infixmid;
char *infixfinal;
int *infixlength;
char *infixstring;
  /*
void nomemory(char *string)
{ 
	fprintf(out_fp,"mallocL:out of memory making %s!!\n",string);
    exit(-1);
}
*/

int RandomInt(int m,int n)
{ int k,rd;  
  rd=rand();
  k=rd%(n-m+1)+m; 
  return k;
}

double RandomFloat(int m,int n)
{  
  double k; 
  int	rd;
  rd=rand();
  k=(rd/Rand_Max)*(n-m)+m;  
  return k;
}

void initmemory()
{   
    
	bestfit=new bestever;
    bestfit->fitness=0.0;
    bestfit->generation=0;
	bestfit->constants=new double[m_ConstantNum];
	bestfit->GeneSerial=new char[nLength];
    oldpop=new individual *[m_GepNum+1];
    for(int i=0;i<=m_GepNum;i++)
        oldpop[i]=new individual[m_nGroupSize];
    for(i=0;i<=m_GepNum;i++)
		for(int j=0;j<m_nGroupSize;j++)
		{ 
		  oldpop[i][j].constants=new double[m_ConstantNum];
		  oldpop[i][j].GeneSerial=new char[nLength];
		}
    newpop=new individual[m_nNextGroupSize];
	for(i=0;i<m_nNextGroupSize;i++)
	{
		newpop[i].constants=new double[m_ConstantNum];
		newpop[i].GeneSerial=new char[nLength];
	}
    binarytree=new binarytreenode*[nLengthOfGene];
	for(i=0;i<nLengthOfGene;i++)
		binarytree[i]=new binarytreenode;
    midresult=new double[m_nNumOfGenes];
    data=new double[nColumn];
	infixmid=new char *[m_nNumOfGenes+1];
	for(i=0;i<=m_nNumOfGenes;i++)
		infixmid[i]=new char[nLengthOfGene+2*m_nHeadSize];
	infixfinal=new char[(m_nNumOfGenes+1)*(nLengthOfGene+2*m_nHeadSize)];
    infixlength=new int[m_nNumOfGenes+1];
}

void evaluate(struct individual &chromosome1,struct individual &chromosome2)
{
	int i;
	chromosome1.fitness=chromosome2.fitness;
    strcpy(chromosome1.GeneSerial,chromosome2.GeneSerial);
	for(i=0;i<m_ConstantNum;i++)
	{
		chromosome1.constants[i]=chromosome2.constants[i];
	}
}

void swap(struct individual &chromosome1,struct individual &chromosome2)
{
	struct individual *exchange=new individual;
	exchange->GeneSerial=new char[nLength];
	exchange->constants=new double[m_ConstantNum];
	exchange->fitness=chromosome1.fitness;
    strcpy(exchange->GeneSerial,chromosome1.GeneSerial);
	for(int i=0;i<m_ConstantNum;i++)
		exchange->constants[i]=chromosome1.constants[i];
	chromosome1.fitness=chromosome2.fitness;
	strcpy(chromosome1.GeneSerial,chromosome2.GeneSerial);
    for(i=0;i<m_ConstantNum;i++)
	   chromosome1.constants[i]=chromosome2.constants[i];
	evaluate(chromosome1,chromosome2);
	chromosome2.fitness=exchange->fitness;
    strcpy(chromosome2.GeneSerial,exchange->GeneSerial);
	for(i=0;i<m_ConstantNum;i++)
		chromosome2.constants[i]=exchange->constants[i];
    delete exchange;
}

int select()
{ double sum,pick;
  int i;
  pick=RandomFloat(0,1);
  sum=0;
  if(TotalF!=0)
  { 
    for(i=0;(sum<pick)&&(i<m_nGroupSize);i++)
       sum+=oldpop[nCurGepNum][i].fitness/TotalF;
  }
  else i=RandomInt(1,m_nGroupSize);
  return (i-1);
}



void mutation(struct individual chromosome)
{    
    int mutationpos;
    double pm=0.0;
    for(int h=0;h<nLengthOfGene*m_nNumOfGenes;h++)
    {
          pm=RandomFloat(0,1);
          if(pm<m_PMutation)
           {  
              if(h%nLengthOfGene<m_nHeadSize)
              mutationpos=RandomInt(0,sizeof(functionset)+m_nIdVariNum);
              else mutationpos=RandomInt(0,m_nIdVariNum);
              chromosome.GeneSerial[h]=fandt[mutationpos];
           }
    }
   for(;h<sizeof(chromosome.GeneSerial);h++)
   {  
          pm=RandomFloat(0,1);
          if(pm<m_PMutation)
           {  
              if(h%nLengthOfGene<m_nHeadSize)
              mutationpos=RandomInt(m_nIdVariNum,nColumn+sizeof(functionset)+m_nNumOfGenes);
              else mutationpos=RandomInt(sizeof(functionset)+m_nIdVariNum,m_nIdVariNum);
              chromosome.GeneSerial[h]=fandt[mutationpos];
           }

    }
}

int isoperator(char ch)
{
  switch(ch)
  {
     case '+':
     case '-':
     case '*':
     case '/': return 1;
               break;
     default: return 0;
             
   }
}

binarytreenode * buildatree(char *array,int left,int right)
{ 
  int parent,child;
  int leaf,non_leaf;
  for(int i=0;i<(right-left);i++)
   { 
     if(array[left+i]=='?')
	 {
        binarytree[i]->element='a'+nCurConNum;
		nCurConNum++;
	 }
     else  binarytree[i]->element=array[left+i];
     binarytree[i]->lchild=NULL;
     binarytree[i]->rchild=NULL;
   }
  
  parent=0,child=1;
  leaf=0,non_leaf=0;
   while(child<right&&(leaf!=non_leaf+1))
  {
    if(isoperator(binarytree[parent]->element))    //是运算符
      { 
        binarytree[parent]->lchild=binarytree[child++];
        binarytree[parent]->rchild=binarytree[child++];
        parent++;
        non_leaf++;
        
      } 
    else if(isupper(binarytree[parent]->element))  //是大写字母，表示自变量
        {
         binarytree[parent]->lchild=NULL;
         binarytree[parent]->rchild=NULL;
         parent++;
         leaf++;
	}
         else if(binarytree[parent]->element=='?')  //是小写字母，表示是常数
         { 
          
          binarytree[parent]->lchild=NULL;
          binarytree[parent]->rchild=NULL;
		  parent++;
          leaf++;
         }
             else /*printf("cannot figure out it!");*/
			 {                                           //是数字，在上一层会出现
			 
              binarytree[parent]->lchild=NULL;
              binarytree[parent]->rchild=NULL;
              parent++;
              leaf++;
			 }
    }  
  return binarytree[0];
}

double fitnessfunc2(binarytreenode *root,struct individual chromosome)
{
  if(isoperator(root->element))
   {
     if(root->element=='+')
      return fitnessfunc2(root->lchild,chromosome)+fitnessfunc2(root->rchild,chromosome);
     if(root->element=='-')
      return fitnessfunc2(root->lchild,chromosome)-fitnessfunc2(root->rchild,chromosome);
     if(root->element=='*')
      return fitnessfunc2(root->lchild,chromosome)*fitnessfunc2(root->rchild,chromosome);
     if(root->element=='/')
      { if(fitnessfunc2(root->rchild,chromosome)==0.0)
         return 0; 
        else return fitnessfunc2(root->lchild,chromosome)+fitnessfunc2(root->rchild,chromosome);
      }
    }
   else if(isalpha(root->element))
        {
          if(isupper(root->element))
          return data[root->element-'A'];
          else return chromosome.constants[(root->element-'a')%m_ConstantNum];
         }
        else return midresult[root->element-'1'];
}

double fitnessfunc1(struct individual chromosome,int left,int right)
{ 
   buildatree(chromosome.GeneSerial,left,right);
   return fitnessfunc2(binarytree[0],chromosome);
}


double fitnessfunc(struct individual chromosome)
{ 
   double finalfit=0.0;
   
   int i,j;
   for(i=0;i<nRow;i++)
   {  nCurConNum=0; 
      for(j=0;j<nColumn;j++)
      data[j]=trainingset[i][j];
      for(j=0;j<m_nNumOfGenes;j++)
      midresult[j]=fitnessfunc1(chromosome,j*nLengthOfGene,(j+1)*nLengthOfGene);
      finalfit=finalfit+selectrange-fabs(fitnessfunc1(chromosome,j*nLengthOfGene,nLength)-data[nColumn-1]);
    }
   return finalfit;
}

void sort1(struct individual *pop,int size)    //按适应值从大到小排列
{  
   cout<<"line "<<__LINE__<<endl;
   for(int i=0;i<size-1;i++)
   {
     int upperindex=i;
     for(int j=size-1;j>i;j--)
	 {
		 if(pop[j].fitness>pop[upperindex].fitness)
         upperindex=j;
	 }
	if(i!=upperindex)
      {
		 swap(pop[i],pop[upperindex]);
      }
   }

}

void initialize()
{  
     initmemory();
     int i,j,nSerialPos;
     char *terminalset=new char [m_nIdVariNum+1];
     terminalset[0]='?';
     for(i=1;i<=m_nIdVariNum;i++)
     terminalset[i]='A'+i-1;
     fandt=new char[nColumn+sizeof(functionset)+m_nNumOfGenes];
     strcpy(fandt,terminalset);
     for(j=0;j<sizeof(functionset);j++)
		 fandt[m_nIdVariNum+1+j]=functionset[j];
	 for(i=nColumn+sizeof(functionset);i<(nColumn+sizeof(functionset)+m_nNumOfGenes);i++)
     fandt[i]='1'+i-(nColumn+sizeof(functionset));
     for (i=0;i<m_nGroupSize;i++)
     {  
        for(int j=0;j<m_nNumOfGenes;j++)
        {
            for(int k=0;k<m_nHeadSize;k++)
           {  
             nSerialPos=RandomInt(0,sizeof(functionset)+m_nIdVariNum);
             oldpop[0][i].GeneSerial[k+j*nLengthOfGene]=fandt[nSerialPos];
           }
            for(;k<nLengthOfGene;k++)
           {
            nSerialPos=RandomInt(0,m_nIdVariNum);
            oldpop[0][i].GeneSerial[k+j*nLengthOfGene]=terminalset[nSerialPos];
           }
        }
       for(int k=0;k<m_nHeadSize;k++)
       {
          nSerialPos=RandomInt(nColumn,nColumn+sizeof(functionset)+m_nNumOfGenes-1);
          oldpop[0][i].GeneSerial[k+j*nLengthOfGene]=fandt[nSerialPos];
         }