stack.cc

来自「标准的GP源代码,由Andy Singleton维护」· CC 代码 · 共 554 行

// stack.cc   File to demonstrate evolution of stack, build with GPQUICK-2.1
// W. Langdon cs.ucl.ac.uk
#define Version "12 Dec 1994 $Revision: 1.19 $"

// Includes main function


//Modifications
// WBL 15 Mar 96 Add calling DisplayDupStats

// WBL 13 Mar 96 Add command line handling, restore r1.13 (keep pTraceStatic)
//               Add pTraceDStats, pTracePStats and pTraceStatic

// WBL 28 Feb 96 Add crossfile

// WBL 26 Feb 96 Make compatible with new (ha 2years old) AddF
//               Ensure pMaxTreeExpr is ignored

// WBL 14/12/94 Load seed from command line

// WBL 25/5/94 Add write_Aux

//requires MULTREE to be defined

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

#include <assert.h>
//extern double difftime (time_t t2, time_t t1 );


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

ofstream temp("");
ofstream& crossfile = temp;

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

Problem* ThisProblem;

class stack : public Problem {
public:
	stack(ChromeParams* p=NULL);   // Initialize primitives,
	void WriteTreeName(int tree, ostream& ostr = cout );
	                               // parameters, and data
	float fitness(Chrome* chrome); // GP fitness function

	void AddFall(Function* f);
};//end class

//**************************************************************************
// static variables that make up the evaluation environment
// Build your environment here as statics
// where the evaluation functions can get to the data

#define Num_test_seq       4
#define num_tests        160
//#define max_fitness      160 moved to stack.h
#define Max_tests        (num_tests+Num_test_seq+1)

#define test_stack_limit  10
#define Max               10
#define store_limit       64

retval Arg1, Aux, store[store_limit];

BOOL memory_error;

int get_address()
{
int address = (EVAL)+(store_limit/2);

if ( address <= 0 || address >= store_limit )
  {
	memory_error = TRUE;
	return 0;             //safe buffer area
  }
else
	return address;

}//end get_address

//**************************************************************************
/////////////////// Problem specific functions and terminals
// Use the OPDEF,EVAL,IP and CURCHROME defines
// and the code will recompile for different eval methods

// Problem Specific Terminals
OPDEF(zeroEval) {return 0;}
OPDEF(oneEval) {return 1;}
OPDEF(MaxEval) {return Max;}
OPDEF(Arg1Eval) {return Arg1;}
OPDEF(AuxEval) {return Aux;}
OPDEF(inc_AuxEval) {return ++Aux;}
OPDEF(dec_AuxEval) {return --Aux;}

//Problem specific Functions
OPDEF(readEval) {int address = get_address(); return store[address];}
OPDEF(writeEval) {
       int address = get_address(); 
       retval old = store[address];
       store[address] = EVAL;
       return old;                // copy what Tesler does
}
OPDEF(write_AuxEval) {
       retval old = Aux;
       Aux = EVAL;
       return old;                // copy what write (ie Tesler) does
}
//**************************************************************************
///////////////////////// PROBLEM definition

void stack::AddFall(Function* f )
{
AddF(f);
for ( int i = 0; i < NUM_TREES; i++ )
	addtofuncbag(i, f);
}

stack::stack(ChromeParams* p) : Problem()
{
	AddF(new ConstFunc(0));    // REQUIRED as function 0

	// Add some standard primitives
	AddFall(new AddFunc(100));
	AddFall(new SubFunc(100));

	// Add the problem specific primitives
	AddFall(new Function(0,0,100,zeroEval,"0"));
	AddFall(new Function(0,0,100,oneEval,"1"));
	AddFall(new Function(0,0,100,MaxEval,"max"));
	AddFall(new Function(0,0,100,Arg1Eval,"arg1"));
	AddFall(new Function(0,0,100,AuxEval,"aux"));
	AddFall(new Function(0,0,100,inc_AuxEval,"inc_aux"));
	AddFall(new Function(0,0,100,dec_AuxEval,"dec_aux"));

	AddFall(new Function(1,0,100,readEval,"read"));
	AddFall(new Function(2,0,100,writeEval,"write"));
	AddFall(new Function(1,0,100,write_AuxEval,"write_Aux"));


	// Set some parameters
	p->params[pPopSize]=1000;
	p->params[pGenerateLimit]=100000;
	p->params[pMaxExpr]=250;	// Nb hold NUM_TREES trees
	p->params[pMaxTreeExpr]=0;      // NOT USED
	p->params[pRepeatEval]=0;	// Dont test again if copy chrome
	p->params[pMuteShrinkWt]=0;	// No shrink mutation
	p->params[pMuteWt]=0;	        // No muation
	p->params[pCrossWt]=90;         // Use Koza value
	p->params[pMuteRate]=0;         // No mutations
	p->params[pAnnealCrossWt]=0;	// No annealing
	p->params[pAnnealMuteWt]=0;
	p->params[pTournSize]=4;	// try and see
	p->params[pKillTourn]=4;	// try and see
	p->params[pMateRadius]=0;	// whole population
	p->params[pMaxAge]=0;     	// no age limit
//	p->params[pFitnessCases]=;	// ?
//	p->params[pTrace]=31;     	// everybody

	// If you need to load problem specific data for evaluation
	// Or load an environment (a map, a scenario)
	// Do it here
}
//store for test cases


enum{makenull,top,pop,push,empty,start_test,end_tests};

int test[Max_tests];
retval argument[Max_tests];
retval ans[Max_tests];

int sp;
retval correct_stack [test_stack_limit];

BOOL set_answer (int i)
{
ans [i] = 0;
argument [i] = 0;

switch(test[i])
{
 case makenull:
	sp = 0;
	break;

 case top:
	if (sp<=0)
		return FALSE; //force new tested to be selected
	else
		ans [i] = correct_stack [sp];
	break;

 case pop:
	if (sp<=0)
		return FALSE; //force new tested to be selected
	else
		{      ans [i] = correct_stack [sp];
		       --sp;
	       }
	break;

 case push:
	if (sp>=test_stack_limit)
		return FALSE; //force new tested to be selected
	else
		{      argument [i] = rnd(2000)-1000;
		       correct_stack [++sp] = argument [i];
	       }
	break;

 case empty:
	ans [i] = (sp==0);
	break;

 default:
	return FALSE; //force new tested to be selected
	break;
}//end case

return TRUE;

}//end set_answer()

void	generate_tests()
{
int i = 0;
cout << "Generating test data\n";

for (int j = 0; j < Num_test_seq; j++ )
{
test[i++] = start_test;
for (int k=0; k<(Max_tests/Num_test_seq-1); k++)
	{
	do {
		test[i] = makenull;
		if (k != 0) 
		  {       const int probablities [Num_test_seq][(empty+1)] =
	                                       {  1, 20, 34, 25, 20,
                                                 30, 10, 10, 40, 10,
                                                 10, 10, 20, 30, 30,
                                                 10, 40, 20, 20, 10 };
#define ptotal 100

			  int r = rnd(ptotal);
			  for ( int m = makenull; m <= empty; m++)
				  if (r <= probablities [j][m])
				   {      test [i] = m;
			                  break;
				   }
				  else 
					  r -= probablities [j][m];
		  }

	   } while (set_answer(i)==FALSE);
	i++;
	}//endloop k
}//endloop j
test[i++] = end_tests;
}//end generate_tests()

void write_tests ( ostream& fout = cout )
{
fout<<"Test cases\n";
int test_cases [empty+1] = {0, 0, 0, 0, 0};

{for (int i = 0; test[i] != end_tests; i++)
   {  if ( test [i] == start_test )
	      fout << "\nstart_test\n";
      else
	     {test_cases [test[i]]++;
	      ThisProblem->WriteTreeName(test[i], fout);
	      fout<< "(" << argument[i] << ")  \t" << ans[i] << endl;
             }
   }
}
{for ( int j = 0; j <= empty; j++ )
	{
	ThisProblem->WriteTreeName(j, fout);
	fout<<" tested " << test_cases [ j ] << " times";
	if ((j == pop ) || ( j == empty ))
		fout<<endl;
        else
		fout<<", ";
        }
}
fout<<"Min expected score " <<
        test_cases [ makenull ] + test_cases [ push ];
fout<<" Good score " <<
        test_cases [ makenull ] + test_cases [ push ] + test_cases [ empty ];
fout<<" Top score " <<
        test_cases [ makenull ] + test_cases [ top ] + test_cases [ pop ] +
        test_cases [ push ]     + test_cases [ empty ];
fout<<endl;
}//end write_tests()


void stack::WriteTreeName(int tree, ostream& ostr) //= cout) gcc 2.6.3 patch
{switch(tree)
	 {
	 case makenull: ostr<< "makenul"; break;

	 case top:      ostr<< "top"; break;

	 case pop:      ostr<< "pop"; break;

	 case push:     ostr<< "push"; break;

	 case empty:    ostr<< "empty"; break;

	 default:       ostr<< "ERROR321"; break;
	 }
}//end stack::WriteTreeName()

void update_score(int& score,
		  int test_done, int actual_answer, int required_ans )
{
switch(test_done)
{
 case makenull:
	score++;
	break;

 case top:
	if ( actual_answer == required_ans ) score++;
	break;

 case pop:
	if ( actual_answer == required_ans ) score++;
	break;

 case push:
	score++;
	break;

 case empty:
	if ( (actual_answer>0) == required_ans ) score++;
	break;

 default:
	assert (0==1);   //catch internal error and terminate gp run
        break;
}//end case

}//end update_score()



void display_run (Chrome* chrome, ostream& fout = cout )
// fitness function.
{
int i;
int score = 0;

chrome->SetupEval();

for(i=0; test[i] != end_tests; i++)
{
if (test[i] == start_test)
	{fout<<"Initialise everything for new test\n";
	 memory_error = FALSE;
	 Aux = 0;
	 memset(store,0,sizeof(store));
        }
else
	{retval answer;

	 Arg1 = argument[i];
	 answer = chrome->evalAll ( test[i] );
	 if (memory_error)   { break;  }

         update_score( score, test[i], answer, ans[i]);
	 fout<<"Test ["<<i<<"] ";
	 ThisProblem->WriteTreeName(test[i], fout);
	 fout<< "(" << argument[i] << ")  \tresult " << answer;
	 fout << " (expected " << ans[i] << ")\n";
        }//end if
fout<<"score = " << score;
fout<<" Aux = " << Aux <<endl;;
for (int j = 0; j < store_limit; j++)
   {
	if ( store[j] != 0 )
	   {
	   fout<<"store " << j-(store_limit/2) << " = " << store [j] << endl;
           }
   }
}//end loop

fout<<"Final score = " << score << endl;

assert (chrome->nfitness->fvalue == float (score)); //it should be!

}//end display_run()


float stack::fitness(Chrome* chrome)
// fitness function.
{
int i;
int score = 0;

//cout << "Fitness of "<< chrome << flush;

for(i=0; test[i] != end_tests; i++)
{
if (test[i] == start_test)
	{//initialise everything for new test
	 memory_error = FALSE;
	 Aux = 0;
	 memset(store,0,sizeof(store));
        }
else
	{retval answer;
	 Arg1 = argument[i];
	 answer = chrome->evalAll ( test[i] );
	 if (memory_error)   { break;  }

         update_score( score, test[i], answer, ans[i]);
        }//end if
}//end loop

chrome->nfitness->fvalue= float (score);

//cout<<"Final score = " << score << endl;

return score;

}//end stack::fitness



//**************************************************************************
int do_gens (Pop* pop, int number) //return if complete or not
{    cout<<"Running, gpquick_seed "<<gpquick_seed<<endl;

     pop->go_until(0,number,max_fitness);

     // Display the best so far
     cout << "\n\nAfter " << pop->gencount;
     cout << " generates, BestFitness = ";
     cout << pop->BestFitness->fvalue << "\n";

     pop->pop[pop->BestMember]->write(PRETTY_NONE,cout);
     cout << endl;

     pop->DisplayStats();
     if ( pop->params->params[pTrace] & pTraceDStats ) pop->DisplayDStats();
     if ( pop->params->params[pTrace] & pTracePStats ) pop->DisplayPStats();
     else                                      pop->DisplayLPStats();

     pop->DisplayDupStats();

     //	generate_tests(); //make sure its not learning the tests
     // write_tests();

//     display_run(pop->best()); //show what it does

     return (pop->BestFitness->fvalue >=max_fitness);

}//end do_gens()
///////////////////////////////  MAIN

int main(int argc, char * argv[])
// Run stack

{
	time_t start, end;

	cout << "\nGP Program to evolve a Stack, version "<<Version;
	time (&start);
	cout << ", " << ctime(&start) <<endl;


	ChromeParams* params = new ChromeParams();
	ThisProblem=new stack(params);
	Pop* pop;

	generate_tests();    //Must be done before create pop or change seed
	write_tests();

        for(int i=0; i<argc;i++) {
		params->Load(argv[i]); }
	if ( params->params[pPopSeed] > 0 )
		gpquick_seed = params->params[pPopSeed];  //dirty I know
	else
	      { rndomize();  //Cheat, use seed=1 to create tests but
			     //randomise population
		params->params[pPopSeed] = gpquick_seed; //record seed used
	      }

	int pop_size = params->params[pPopSize];
	int gen_max  = params->params[pGenerateLimit];

	cout << "Creating new population of " << pop_size<< " individuals\n";
	pop = new Pop(ThisProblem,params,pop_size);
	cout << "new Pop -- completed\n";

	params->Save();

	cout << "Setting each fitness value\n";
	int done = do_gens (pop, pop_size-1);

	cout << "Initial fitness values calculated,\n";
	if ( params->params[pTrace] & pTraceStatic )
		{  cout << "\n\nInitial Population";
		   pop->Write();
	   }
	cout << "Creating a total of " << gen_max << " individuals\n";

	                         // kbhit IS NOT PORTABLE (Borland specific)
	while (pop->gencount<gen_max && !done && !kbhit())  
	{
		done = do_gens (pop, pop_size);
		if ( params->params[pTrace] & pTraceStatic )
			{  cout << "\n\nCurrent Population";
			   pop->Write();
		   }
	}


	// Display the best
	cout << "\n\nFINAL RESULTS. After " << pop->gencount;
        cout << " generates, BestFitness = ";
        cout << pop->BestFitness->fvalue << "\n";

	// Display the final population
	if ( params->params[pTrace] & pTraceStatic )
	  {  cout << "\n\nFINAL Population";
	     pop->Write();
          }

	pop->pop[pop->BestMember]->write(PRETTY_NONE,cout);

        display_run(pop->best()); //show what it does

	time (&end);
	cout << "\nGP Stack Finished "<< ctime(&end);
//	cout << " took "<< difftime(end, start) <<" seconds elapse, ";
//	cout << clock() << " ticks cpu";
	cout << endl;

	delete pop;
	delete ThisProblem;
	delete params;
	return done? 1 : 0;
}