antprob.cxx

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

// Copyright Andy Singleton, 1993,1994
// This code is released for non-commercial use only
// For questions or upgrades contact:
// Andy Singleton, Creation Mechanics Inc.
// PO Box 248, Peterborough, NH 03458
// Internet: [e-mail]
// Compuserve 73313,757
// Phone: [phone]

// W.Langdon cs.ucl.ac.uk $Revision: 1.6 $

#define Version "Artificial Ant Problem. $Revision: 1.6 $"

//Modifications (reverse order):
// WBL 10 Feb 1997  Allow use as close as poss to GP1 page 147-155
// WBL  7 Feb 1997  Allow use within rest of GP frame work
// WBL 21 Nov 1995  Make compatible with MULTREE = True

 
// GPQUICK
// sample GP problem file
// Compatible with problem DLL's for the GP-GIM professional GP system
// ANTPROB Artificial Ant traversing a trail of food
// Implementation by Georg Fuellen
// Includes main function
// This problem requires the file SANTAFE.TRL or equivalent 32x32 ascii trail file

// The ARTIFICIAL ANT problem was originally created by Jefferson and Collins et al
// as part of their experiments in evolution using a 64K processor CM2.
// They created the "Santa Fe Trail" and used a binary string GA to evolve
// a finite automata that could traverse the trail.
// John Koza adapted this problem to genetic programming and reported his
// results at the A-LIFE II conference.  This problem attempts to be a
// faithful reproduction of Koza's experiment.  For more information, see
// the Koza article in A-LIFE II or the Koza "GENETIC PROGRAMMING" book.
// The artificial ant problem is a popular benchmark of the
// GA learning mechanism.
// The artificial ant problem is a fairly easy problem because the trail
// never changes.  This is another reason it makes for a convenient experiment.
// You can make it harder, however, by designing trails with less food.
// For real extra credit, try moving the trail around between evals.

#include "pch.h"
#include "chrome.h"
#include "primitiv.h"

extern char scratch[100];
#ifdef FASTEVAL
	extern evalnode* IpGlobal;
	extern Chrome* ChromeGlobal;
#endif


//**************************************************************************
// Define your Problem class

#ifdef WITHIN_GP
#include <assert.h>
#include "ant.h"
#include "gp.h"
#include "test.h"
#else
class AntProb : public Problem {
#ifdef MULTREE
void	AddFall(Function* f);
#endif
public:
	AntProb(ChromeParams* p);               // initialize functions, parameters, and data
	float fitness(Chrome* chrome);  // Driving ingredient - GP fitness function
};


//**************************************************************************
// static variables that make up the evaluation environment
// Build your environment here as statics
// where the evaluation functions can get to the data
#define Grid_Horizontal 32
#define Grid_Vertical  32
#endif


unsigned char Grid[Grid_Horizontal][Grid_Vertical];
unsigned char LoadedGrid[Grid_Horizontal][Grid_Vertical];
#ifdef KOZA_ANT
#define START_ENERGY 600
//GP1 says 400 but given solution requires more!
#else
#define START_ENERGY 600
#endif
int energy=START_ENERGY;
int direction=0;
int xx=0; //position of the ant
int yy=0;

//**************************************************************************
// Data handling functions

retval FoodAhead()
{
	retval rval=0;
	switch(direction)
	{
#ifdef KOZA_ANT		
		case 0:           /* is food on the right ?? */
		  rval=(Grid[(xx+1)%Grid_Horizontal][yy]                =='8');
		  break;
		case 1:        /* is food up  ?? */
		  rval=(Grid[xx][(yy+Grid_Vertical-1)%Grid_Vertical]    =='8');
		  break;
		case 2:    /* is food on the left ?? */
		  rval=(Grid[(xx+Grid_Horizontal-1)%Grid_Horizontal][yy]=='8');
		  break;
		case 3:  /* is food down ?? */
		  rval=(Grid[xx][(yy+1)%Grid_Vertical]                  =='8');
		  break;
#else
		case 0:           /* is food on the right ?? */
			rval=( ( xx < Grid_Horizontal-1 ) && ( Grid[xx+1][yy] == '8' ) );
		break;
		case 1:        /* is food up  ?? */
			rval=( ( yy > 0 ) && ( Grid[xx][yy-1] == '8' ) );
		break;
		case 2:    /* is food on the left ?? */
			rval=( ( xx > 0 ) && ( Grid[xx-1][yy] == '8' ) );
		break;
		case 3:  /* is food down ?? */
			rval=( ( yy < Grid_Vertical-1 ) && ( Grid[xx][yy+1] == '8' ) );
		break;
#endif
	}
    	return rval;
}

int Reset()
{
	energy=START_ENERGY;
	direction=0;
    	xx=0;
	yy=0; //position of the ant
    	return 0;
}

int CopyGrid()
{
	int i,j;

	for (i=0; i<Grid_Horizontal; i++)
	{
		for (j=0; j<Grid_Vertical; j++)
		{
			Grid[i][j]=LoadedGrid[i][j];
		}
	}

	return 0;
}

// Load a GRID_HORIZONTAL column by GRID_VERTICAL row trail (usually 32x32)
// '8' marks the food pieces
BOOL LoadFromFile(char* filename = "santafe.trl")
{
	int i,j;
	char ch;
    	int rval=TRUE;
	ifstream inf(filename);
	if (!inf)
	{
		 cerr<<"cannot open"<<filename;
		 rval=FALSE;
	}
    	else {
		for (i=0; i<Grid_Vertical; i++)
		{
			for (j=0; j<Grid_Horizontal; j++)
			{
				inf.get(ch); while (ch =='\n' || ch == '\r') inf.get(ch);
				LoadedGrid[j][i]=ch;
			}
		}
    }
	CopyGrid();
	return rval;
    
}

//**************************************************************************
//////////////////////////  Problem specific functions

// Use the OPDEF,EVAL,IP and CURCHROME defines
// and the code will recompile for different eval methods


OPDEF(IfFoodEval)
{
		  retval rval;
		  if (FoodAhead())
		  {
					 rval=EVAL;
					 IP++;           // Jump the second expression
					 TRAVERSE();
					 IP--;           // And back up one (since EVAL increments)
		  }
		  else {
					 IP++;
					 TRAVERSE();    // Jump the first expression
					 IP--;                                   // Back up for EVAL
					 rval=EVAL;
		  }
		  return rval;
}

class IfFoodAhead : public Function {       
public:
	IfFoodAhead() {strcpy(name,"IFFOODAHEAD");argnum=2;varnum=0;weight=100;
	evalfunc=IfFoodEval;};

};
				//
#ifdef KOZA_ANT
OPDEF(Progn2) {return (EVAL + EVAL);}
#endif
OPDEF(Progn3) {return (EVAL + EVAL + EVAL);}

				//
OPDEF(Left)
{
	retval rval;
	rval=0;
	if ( energy != 0 )
	{
		direction = ( direction + 1 ) % 4;
		energy--;
    }
	return rval;

}

				// 
OPDEF(Right) 
{
	retval rval;
	rval=0;
	if ( energy != 0 )
	{
		direction = ( direction + 3 ) % 4;
		energy--;
    }
	return rval;

}
				//
OPDEF(Move)
{
	retval rval=0;
	if ( energy == 0 ) {
		rval=0;
	}
    	else {
		switch ( direction )
		{
#ifdef KOZA_ANT
			case 0:  //right
			    xx = (xx+1)%Grid_Horizontal;                 break;
			case 1:  //up
			    yy = (yy+Grid_Vertical-1)%Grid_Vertical;     break;
			case 2: //left
			    xx = (xx+Grid_Horizontal-1)%Grid_Horizontal; break;
			case 3: //down
			    yy = (yy+1)%Grid_Vertical;                   break;
#else
			case 0:  //right
				{
					if ( xx < Grid_Horizontal-1 ) xx++;
				break;
				} 
			case 1:  //up
				{
					if ( yy > 0) yy--;
				break;
				} 
			case 2: //left
				{
					if ( xx > 0) xx--;
				break;
				} 
			case 3: //down
			{
					if ( yy < Grid_Vertical-1) yy++;
				break;
			} 
#endif
		}
    	}
	energy--;
	if ( Grid[xx][yy] == '8' )      /* Note spaces will not be seen as they == 2 */
	{
		Grid[xx][yy] = '+';          /* Eats Food */
		rval = 1;
	}
	else {
		{if (((Grid[xx][yy])=='+')||(Grid[xx][yy]=='*'))
		{Grid[xx][yy] = '*';}
		else {Grid[xx][yy]= '-';}}
		rval= 0;
	}
    return rval;
}


//**************************************************************************
///////////////////////// PROBLEM definition

#ifdef MULTREE
#ifdef WITHIN_GP
void gp::AddFall (Function* f )
#else
void AntProb::AddFall (Function* f )
#endif
{
AddF(f);
for ( int i = 0; i < NUM_TREES; i++ )
	addtofuncbag(i, f);
}
#endif

#ifdef WITHIN_GP
gp::gp() : Problem()
{
	ProbVersion = Version;
	assert ( NUM_TREES >= NUM_OPERATIONS );
#else
AntProb::AntProb(ChromeParams* p) : Problem()
{
#endif
#ifdef MULTREE
	AddFall(new ConstFunc(0));                         // Required for GPQUICK, but zero weight

	// Problem specific functions
	AddFall(new Function(2,0,100,IfFoodEval,"IfFoodAhead"));
#ifdef KOZA_ANT
	AddFall(new Function(2,0,100,Progn2,"Prog2"));
	AddFall(new Function(3,0,100,Progn3,"Prog3"));
#else
	AddFall(new Function(3,0,150,Progn3,"Prog3"));
#endif
	AddFall(new Function(0,0,100,Left,"Left"));
	AddFall(new Function(0,0,100,Right,"Right"));
	AddFall(new Function(0,0,100,Move,"Move"));
#else
	AddF(new ConstFunc(0));                         // Required for GPQUICK, but zero weight

	// Problem specific functions
	AddF(new Function(2,0,100,IfFoodEval,"IfFoodAhead"));
	AddF(new Function(3,0,150,Progn3,"Prog3"));
	AddF(new Function(0,0,100,Left,"Left"));
	AddF(new Function(0,0,100,Right,"Right"));
	AddF(new Function(0,0,100,Move,"Move"));
#endif

#ifndef WITHIN_GP
	// Set some parameters
    	p->params[pRepeatEval]=0;                   // no need to repeat, same case each time
	p->params[pMuteConstWt]=0;                      // no constants
   	 // Get to Koza type parameters
#ifdef MULTREE
   	 p->params[pMuteWt]=0; //not implemented by MULTREE
	p->params[pAnnealMuteWt]=0;
	p->params[pAnnealCrossWt] = 0;
#else
   	 p->params[pMuteWt]=15;                              // less mutation
	p->params[pAnnealMuteWt]=15;                    // disable annealing
	p->params[pAnnealCrossWt] = 0;
#endif
#endif //not WITHIN_GP

	// If you need to load problem specific data for evaluation
	// Or load an environment (a map, a scenario)
	// Do it here
	LoadFromFile("santafe.trl");
}

#ifdef WITHIN_GP
float gp::fitness(Chrome* chrome)  // fitness function.
{
  tests_run++;
  tests_apparently_run++;
#else
float AntProb::fitness(Chrome* chrome)
{
#endif
	int x,y,stop;
	float f = 0;
	CopyGrid();
	Reset();
	retval answer=0;
#ifdef TIMINGS
	int evals = 0;
#endif
	while ( energy > 0 )
	{
#ifdef TIMINGS
		evals++;
#endif
#ifdef MULTREE
		answer+= chrome->evalAll(0);
#else
		answer+= chrome->evalAll();
#endif
	}
	f=answer;
	chrome->nfitness->fvalue=f;
#ifdef TIMINGS
	ptrmyfitnessvalue(chrome->nfitness)->cpu_time = 
	  float(START_ENERGY - energy) / float(evals);
#endif
	return f;
}


#ifndef WITHIN_GP
//**************************************************************************
///////////////////////////////  MAIN

//int main(int, char **)
int EvolveAnt()
// Run with a population of size 2000
// Run for 80,000 evals, or until it finds the answer
// DOS version will exit on keyboard hit
// Every 5 seconds or 1000 evals, print the best answer so far

{
	ChromeParams* params = new ChromeParams();
	Problem* prob=new AntProb(params);
	Pop* pop;

   	cout << "\nGPQUICK Artificial Ant Problem\n";

	rndomize();
#ifdef KOZA_ANT
	pop = new Pop(prob,params,500);
#else
	pop = new Pop(prob,params,2000);                // population of size 2000
#endif
	int done = 0;

#ifdef KOZA_ANT
	while (pop->gencount<25500 && !done)
#else
	// Do for 80,000 iterations, or until we find the right answer
	while (pop->gencount<20000l && !done)  // Portable version - not interruptible
	//while (pop->gencount<25000l && !done && !kbhit())  // kbhit IS NOT PORTABLE (Borland specific)
#endif
	{
		// go for 5 seconds, 1000 evals, or until we get a right answer
		pop->go_until(time(NULL)+5,1000,89);

		// Display the best so far
		cout << "\n\nAfter " << pop->gencount << " generates, #food found = " << pop->BestFitness->fvalue << "\n";
		pop->pop[pop->BestMember]->write(PRETTY_NONE,cout);
		cout.flush();
		
		done = (pop->BestFitness->fvalue >=89);
	}


	// Display the best
	ofstream of("RESULT.TXT",ios::out | ios::app);
	cout << "\n\nFINAL RESULTS...";
	cout << "\nAfter " << pop->gencount << " generates, #food found = " << pop->BestFitness->fvalue << "\n";
	pop->pop[pop->BestMember]->write(PRETTY_NONE,cout);
	cout.flush();
			cout<<"****";pop->pop[pop->BestMember]->SetupEval();
    
			int x,y,stop;
			float f = 0;

	    // Get the track of the best ant
			CopyGrid();
			Reset();
			retval answer=0;
			while ( energy > 0 )
			{
#ifdef MULTREE
				answer+= pop->pop[pop->BestMember]->evalAll(0);
#else
				answer+= pop->pop[pop->BestMember]->evalAll();
#endif
			}

	    // Show the track
			f=answer;
			cout << '\n';
			of << '\n';
				for (y=0; y<Grid_Vertical; y++)
				{
					for (x=0; x<Grid_Horizontal; x++)
					{
						cout<<Grid[x][y];
			of<<Grid[x][y];
					}
					cout<<"\n";
		    of<<"\n";
				}

		of<< "\nLegend: (8)=Uneaten Food (+)=Eaten food (-)=Tracks (*)=Multiple Tracks";

			cout<<"\nFitness="<<f << " After " << pop->gencount << " generates";
			of<<"\nFitness="<<f << " After " << pop->gencount << " generates";

			cout<<"\n";pop->pop[pop->BestMember]->write(PRETTY_NONE,cout);
			of<<"\n";pop->pop[pop->BestMember]->write(PRETTY_NONE,of);

			cout << "\nResult in RESULT.TXT";

			of.close();
	delete pop;
	delete prob;
	delete params;
	return done? 1 : 0;
}

int main(int, char **)
{
	int i;
	BOOL done=FALSE;
	// remove comments to collect statistics
//      for (i=0;i<100 && !done;i++)
//    {
		EvolveAnt();
//              done=kbhit();
//      }
	return done? 0 : 1;
}
	
#endif // not WITHIN_GP