chrome.cxx

标准的GP源代码,由Andy Singleton维护

// chrome.cxx  version to support stack.cc, from GPQUICK-2.1
// W.Langdon cs.ucl.ac.uk $Revision: 1.89 $

#define debug

//Modifications (reverse order):
// WBL  2 Apr 1997  Add ORIGINAL_DEME to allow queue2 to operate identically

// WBL 14 Mar 1997  BUGFIX Ensure only one individual per crossfile line 
//                  Ie copy clones to appear on own line.

// WBL 15 Feb 1997  BUGFIX (GENERATIONAL) ensure answer returned by generate 
//                  refers to chrome just created. Was going wrong if last
//                  chrome in the population was a copy. Improve layout of
//                  generate while about it.

// WBL 13 Feb 1997  Add pTournOff

// WBL 31 Dec 1996  Reduce number of warnings with newer C++ compilers,
//                  Make deleting newpop cleaner, 
//                  ensure lastchrome is initialised

// WBL 14 Dec 1996  Add pMaxDepth

// WBL 23 May 1996  Add pCPU

// WBL 16 May 1996  BUGFIX ensure MutateSubTree dont crash with depth==0

// WBL 26 Apr 1996  Add display of location of parents and offspring
//                  to crossfile. Trace deme bug
//                  BUGFIX correct calculation of offset in select_candidates
//                  further testing required

// WBL 12 Apr 1996  BUGFIX move update_rank to InsertMember so mutation and
//                  seeding work with pElitist. Nb remove other calls to it

// WBL 11 Apr 1996  Allow multiple seeds in gp.load
//                  Allow comments in gp.load (based on isscoment from test.cc)

// WBL  8 Apr 1996  Get mutation working

// WBL 21 Mar 1996  Add chrome differs from mum or dad to crossover log

// WBL 28 Feb 1996  Add logfile of crossover details

// WBL 27 Feb 1996  Disable static_check when used in stack problem
//                  Restore oldversion of GetTarget for STACK_LIB

// WBL 12 Dec 1995  Make Chrome::Chrome more robust to errors in the dumpfile

// WBL 10 Dec 1995  Ensure Pop::Pop calls clear_rank

// WBL 13 Jun 1995  Add binary save mode to Pop::Write 
//                  and input stream to Pop::Pop and Chrome::Chrome

// WBL 27 Jun 1995  Add reinitialise and reinit_trees

// WBL 23 May 1995  Add reporting which tree is used for crossover

// WBL  6 May 1995  Remove MaxExpr, ExprBytes, MaxTreeExpr, funccount,
//                  from Chrome. Replace with params pMaxExpr, pMaxTreeExpr
//                  and probl->funccount. Replace depth with new SubWrite arg

// WBL  4 May 1995  Restore copying fitnessvalue on crossover (see r1.29,1.28)
//                  in order to support STORE_FIT. Add call to update_rank
//                  Add pStoreFit

// WBL  2 May 1995  Add pDirCrossWt

// WBL 26 Apr 1995  Reduce size of chrome by removing idx from node
//                  since it is never used. Mainly done by redefining
//                  macros in chrome.h but minor change to load

// WBL 18 Apr 1995  Improve layout of debug info

// WBL 17 Apr 1995  Add optional last_tree argument to chrome::write
//                  Add and use pMaxTreeExpr

// WBL  8 Apr 1995  Add check function exists in tree. This also
//                  ensures we get right function where they are ambigious

// WBL  7 Apr 1995  Make gp.load case sensitive by chaning FindFunc

// WBL 23 Mar 1995  Move pElitist from Worstof to select_candidates

// WBL 23 Mar 1995  Add Chrome* optional parameter to GetFitnessObj

// WBL 22 Mar 1995  Dont call Copy when creating a new Chrome by crossover

// WBL 15 Mar 1995  Add pElitist

// WBL 12 Mar 1995  Add pTournComp and pNicheSize

// WBL 19 Feb 1995  Add passing target to Bestof and Worstof

// WBL 19 Feb 1995  Add call to static_check in chrome::Load

// WBL 28 Jan 1995  Add some debug traces to chrome::Load() and SubLoad()

// WBL 29 Nov 1994  Implement pnames, change Load and Saveto use it.
//                  add Load(char*)

// WBL 15 Oct 1994  Make chrome::Load() work with MULTREE 
//                  NB I have not implemented constants

// WBL 14 Oct 1994  Call static_check when creating entirely new chrome

// WBL 13 Sep 1994  Make compilable by solaris gcc

// WBL  9 Sep 1994  UNDO part of 17 Aug 1994: ``InsertMember nolonger
//                  places worse child into pop'' 

// WBL  8 Sep 1994  Make crosstree call static_check

// WBL 25 Aug 1994  Make funcbag and array, add funcbagcount.
//                  Replace getfuncbag by addtofuncbag

// WBL 24 Aug 1994  Add Problem::Bestof and Worstof and use it in place
//                  of IsBetter tournaments. Add Pop::select_candidates

// WBL 23 Aug 1994  Remove copying hits and write_hits() (to problem
//                  specific file). Replace call of write_hits by
//                  write(nfitness*). Use this inplace of fout<<fvalue.
//                  Make Pop::Pop call problem specific NewChrome.
//                  Add debug output to stub Problem::fitness

// WBL 17 Aug 1994  TRY AND COMMENT OUT GetTarget() avoid selecting BestMember
//                  InsertMember nolonger places worse child into pop (nb
//                  appears to be very CPU inensive, illusion of prog length?

// WBL 15 Aug 1994  Add write_hits(). 
//                  Make  Chrome::Dup() set mum and write_trace() trap xtree<0

// WBL  6 Jul 1994  Add two dimensional torridal demes. Add pPopWidth,
//		    pDemeWidth

// WBL 1  Jul 1994  Remove class stats, Pop::DisplayStats and
//                  Pop::DisplayDStats to new file stats.cc

// WBL 28 Jun 1994  Make nfit take average of cube rather than linear average
//                  Tidy displays in DisplayDStats

// WBL 27 Jun 1994  Correct display of gencount in DisplayStats
//                  Add class stats and make DisplayStats use it.
//                  Complete impementation of DisplayDStats

// WBL 24 Jun 1994  Direct crossover to a particular tree
//                  Protect sqrt from rounding errors

// WBL 14 Jun 1994  Add support for pPopSeed, pTestSeed and PTrace

// WBL 14 Jun 1994  Add ChromeParams::Save() and ChromeParams::Load()
//                  based upon gpcplus3.0 cpv.cc.
//                  Add Pop::DisplayDStats()
//		    Add Pop::Write()

// WBL 16 May 1994  Add Pop::DisplayStats(). Fix MULTREE CrossOver bug

// WBL 12 May 1994  fix % by zero error in rnd() on SETNODE if varnum==0,
//		    Probably only arises if you have the wrong compiler switch

// WBL  5 May 1994  Make pMaxAge = 0 disable age limit,
//		    Add support for P-M random numbers

// GPQUICK
// C++ prefix stack implementation
// Divides GP system into classes:
//    Chrome-Function  - representation of the genetic program
//    Pop - Runs the GA
//    Problem - fitness and primitive functions

//#include <math.h>	//for DisplayStats
#include <assert.h>
#include "pch.h"
#include "chrome.h"

//#define CROSSFILE true
#ifdef CROSSFILE
//#define crossfile cout
#endif

// Global variables
char scratch[100];

int gpquick_seed = 1;

#ifdef FASTEVAL
        // Global evaluation variables.  Eliminates parameter passing
        // If you can get IpGlobal into a register, you will run near the speed
        // limit for S-expression evaluation
        Chrome * ChromeGlobal;                  // currently evaluating Chrome
        evalnode ExprGlobal[EXPRLEN];   // expression expanded to evalnodes
        evalnode * IpGlobal;            // Current instruction pointer
#ifdef FASTEVAL
        evalnode* fast_tree_starts [NUM_TREES];     // start of each tree 
#endif
#endif


//**************************************************************************
//////////////////////////////////// Utility functions
int min(int value1, int value2)
   {
          return ( (value1 < value2) ? value1 : value2);
   }
int max(int value1, int value2)
   {
          return ( (value1 > value2) ? value1 : value2);
   }

// Comment out if included in your implementation (e.g. Borland)
        // upper case string
char* strupr(char* s)
{
        int i=0;
        while (s[i])
                if (s[i]>='a' && s[i]<='z') s[i]=s[i]-32;
        i++;
        return s;
}

        // compare strings without case sensitivity
int strcmpi(char* s1, char* s2)         // only checks equality
{
        int mismatch=0;
        while (*s1 && *s2 && !mismatch)
        {
                if (*s1>='a' && *s1<='z' && *s2<='Z')
                        mismatch = *s1-32 != *s2;               
                else if (*s1>='A' && *s1<='Z' && *s2>='a')
                mismatch = *s1+32 !=*s2;

                else
                        mismatch = *s1!=*s2;
                s1++;s2++;
        }
        return mismatch || *s1 || *s2;
}


//**************************************************************************
//////////////Function member function (separated for use in a DLL)
char* Function::getprint(Chrome* chrome)
{
        // NUMBER has its own getprint to write the correct number
        // This is fancy footwork for other functions with operands
        // these are written as <name>_<operand number>
        if (varnum) sprintf(scratch,"%s_%-d",name,VARNUM(chrome->expr[chrome->ip]));
        return (varnum? scratch : name);
}



//**************************************************************************
/// Chrome functions ///////////////////////////////////////////

Chrome::Chrome(ChromeParams* p,Problem* pr,Function** f,retval* c,BOOL doinit,
			     istream* fin )
#ifdef TRACE
                  :num_children (0)
#endif
{
// initialize a expr using the functions in array f

//cout << "Chrome::Chrome\n";
        int depth = p->params[pInitExpr];
//        funcbag=cf;
        params = p;
        probl = pr;
        funclist = f;
        constlist = c;
        expr=new node[params->params[pMaxExpr]];
        ip=0;
        birth = 0;
        nfitness  = probl->GetFitnessObj(this);
        // allocates a FitnessValue object;  GetFitnessObj  calls new

//cout<<"Size of chrome "<<sizeof(*this)<<" + "
//    <<sizeof(node)*params->params[pMaxExpr]<<endl;

        if (doinit)
        {
        if (fin!=NULL && *fin)
        {//load each line into a separate tree
	 //psuedo binary. 1 byte per opcode but in ascii
		int ip = 0;
#ifdef MULTREE
		for (int t = 0; t < NUM_TREES; t++ ) {
			tree_starts[t] = ip;
#endif
			char c;
			for(c=fin->get(); (c != '\n') && (c != EOF); ip++) {
//cout<<"`"<<c<<"'";debug
				assert(ip<params->params[pMaxExpr]);
				expr[ip].op = c-'A';
				c = fin->get();
			};//endfor each line
		if(c == EOF) {                                //sanity checks
			cout<<"Unexpected EOF on loading dumpfile\n";
			assert(c != EOF); }
		if( (ip-tree_starts[t]) <= 0) {
			cout<<"Empty tree in dumpfile\n";
			assert( (ip-tree_starts[t]) > 0 );}
		if( (ip-tree_starts[t]) != SubLen(tree_starts[t]) ) {
			cout<<"Corrupt tree in dumpfile\n";
			assert( (ip-tree_starts[t])==SubLen(tree_starts[t]));}
#ifdef MULTREE
//cout<<"end tree "<<t<<endl; debug
		int valid = probl->static_check(this,t);
		if (valid>0) cout<<"static_check reports "<<valid
				 <<" on tree "<<t<<endl;
		};//endfor all trees
#endif
	}
	else {
#ifdef MULTREE
	for (int t = 0; t < NUM_TREES; t++ ){
	        tree_starts[t] = ip;
#ifndef STACK_LIB
	do {
#endif
	        ip = tree_starts[t]; //discard earlier attempt at tree
#endif
                // DO "ramped half and half from 2 to depth"
                if (depth > 0)
                {
#ifdef MULTREE
                  SubInit(probl->funcbag[t],1,rnd(depth-1)+1,rnd(2), TRUE, t);
#else
                  SubInit(probl->funcbag[0],1,rnd(depth-1)+1,rnd(2), TRUE);       // go to some depth less than max, full or half full
#endif
                }
                else
                        SETNODE(expr[ip],0,0);    // stick in a stub constant
#ifdef MULTREE
#ifndef STACK_LIB
	}while (probl->static_check(this,t)>rnd(100));
#endif
	}//end for each tree
#endif
        }//end else fil
	}//end doinit
}

#ifdef MULTREE
void Chrome::reinit_trees(BOOL flag[NUM_TREES])
{
node* save = new node[params->params[pMaxExpr]];
memcpy(save,expr,params->params[pMaxExpr]*sizeof(node));

int save_starts[NUM_TREES+1];
for (int t = 0; t < NUM_TREES; t++) {
	save_starts[t] = tree_starts[t]; }
save_starts[NUM_TREES] = tree_starts[NUM_TREES-1] + 
				SubLen(tree_starts[NUM_TREES-1]);

        int depth = params->params[pInitExpr];

        ip=0;

	for (t = 0; t < NUM_TREES; t++ ){
		tree_starts[t] = ip;
//debug	if(tree_starts[t] != save_starts[t])
//		cout<<"New tree_starts["<<t<<"]="<<tree_starts[t]
//end debug	    <<" original="<<save_starts[t]<<endl;
	if(flag[t])
	do {
	        ip = tree_starts[t]; //discard earlier attempt at tree

                // DO "ramped half and half from 2 to depth"
                if (depth > 0)
                {
                  SubInit(probl->funcbag[t],1,rnd(depth-1)+1,rnd(2), TRUE, t);
                }
                else
                        SETNODE(expr[ip],0,0);    // stick in a stub constant
	}while (probl->static_check(this,t)>rnd(100));
	else {
		ip = tree_starts[t] + save_starts[t+1]-save_starts[t];
		if(ip>=params->params[pMaxExpr]) {
			cout<<"reinit_trees OUTOFSPACE on tree "<<t<<endl;
			assert(0==1);
		}
		memcpy(&(expr[tree_starts[t]]),&(save[save_starts[t]]),
		       save_starts[t+1]-save_starts[t]                 );
	}
	}//end for each tree

delete[] save;

}//end reinit_trees
#endif

Chrome* Chrome::Copy()
{
        Chrome* nw=new Chrome(params,probl,funclist,constlist,FALSE);
        nw->Dup(this);
        return nw;
}

void Chrome::Dup(Chrome* source)                // make a copy nondestructively
{
#ifdef TRACE
	source->num_children++;
	mum.birth = source->birth;
#endif
#ifdef MULTREE
	memcpy (tree_starts, source->tree_starts, sizeof(tree_starts));
#endif
//        funcbag=source->funcbag;
        params=source->params;
        funclist=source->funclist;
        constlist=source->constlist;
        
        memcpy(expr,source->expr,params->params[pMaxExpr]*sizeof(node));
        nfitness->Copy(source->nfitness);
#ifdef ORIGINAL_RANK
        nfitness->update_rank();
#endif
        ip=0;
}

#ifdef MULTREE
retval Chrome::evalAll(int tree) // eval the whole expression anew
#else