queue2.cc

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

// queue.cc   File to demonstrate evolution of queue, build with GPQUICK-2.1
// W. Langdon cs.ucl.ac.uk 25 June 1994
//                     based upon queue.cc 24 Jun 1994,c Revision: 1.6.1.4
#define main_version "29 Nov 1994 $Revision: 1.58 $"

// Includes main function


//Modifications (in reverse order)

//WBL 31 Mar 97  Make compatible with GPxxx framework (but dont intergrate)
//               (Also restore r1.56 ie 320 tests rather than 32000)
//               Make compatible with DEC ALPHA C

//WBL 29 Nov 94  Add command line handling

//WBL 25 Nov 94  Comment out all calls to test_all_adf1.
//               Display location and scores of all "best" progs in pop

//WBL 23 Nov 94  Display all non-zero results from Is_adf1_minc rather >= 10

//WBL 23 Nov 94  Make Is_adf1_minc return length of cycle, rather than total

//WBL 22 Nov 94  Rule out answers < -15 or >15 in Is_adf1_minc. Plus bugfix

//WBL 22 Nov 94  Restore version 21 Oct 1994  ??
//               Add Is_adf1_minc() and test_all_adf1

//WBL 21 Oct 94  Same test sequence as before
//               Gather and display Adf1 cache statistics

//WBL 20a Oct 94 Ensure updates to store by Adf1 are recorded in store_written

//WBL 20 Oct 94  Add results cache to Adf1 (speed and better adf1ver display)

//WBL 19 Oct 94  Reduce size of numbers enqueued by 5/15.7
//               Count only store[] elements written to when counting mem used
//               Remove memory component of fitness
//               Add calling queue::Fitness before display_run if gp.load

//WBL 15aOct 94  Facility to load one chrome. Add TreeNameMatch

//WBL 15 Oct 94  Revert to 1.38 (ie restore empty)
//               To reduce file size: Remove display of average test passes

// WBL 13 Oct 94 Make static_check() forbid poor functions, do more checks,
//               Change check so all inputs must return different output
//               Treat adf1 as semantic variability of Adf1 instead of bad flag

// WBL 13 Sep 94 Make static_check() and write() maintain adf1

// WBL 13 Sep 94 Make compilable by solaris gcc

// WBL 13 Sep 94 Reimplement static_check to simply compare answers.
//               Remove memory_penalty, arg1_used and arg1_side_effect

// WBL 13 Sep 94 Remove Aux3 and Inc_Aux<n>

// WBL 7B Sep 94 Remove ADF1 from makenul

// WBL 7A Sep 94 Reduce store size from 63 to 31 cells

// WBL 7 Sep 94  Discarded version 6 Sep 94. Implement via last_var_used insted
//               Retain Dont allow fron and empty to call Adf

// WBL 1 Sep 94  Remove (use of) MInc<n>

// WBL 31b Aug 94 Make MIncN consistent with Mod (ie for -ve)

// WBL 31a Aug 94 Remove again..Restore write_tests every gen
//               Dont allow set_auxN, except in Makenull
//               Dont allow IncN, DecN or write in Empty or Front
//               Add MInc1, MInc2 and MInc3 (If it wont learn; tell it)

// WBL 29 Aug 94 For test 5 scale proability of enqueue according to q length
//               and adjust priorities to get even spread of tests by qlen
//               DONT Call write_tests every gen
//               Correct wordsused() and its usage. Move mem_penalty_bot to Q.h

// WBL 27 Aug 94 Half way for enqueue(number)
//               Remove Prog3 and Qrog3
//               1st 5 tests(add Last_test_seq, replace num_tests by test_total
//               Move write_tests to end of run, display number of passes etc


// WBL 25 Aug 94 Remove abort on memory out of range.
//               Restrict which primitives can be in which tree
//               Add Aux3, allow dequeue to call front, remove aux1--, aux2--
//               Increase number of enqueue(small number)
//               Comment per gen display of best

// WBL 24 Aug 94 Move to class queue to queue.h Add passed and if passed all 
//               setting score = max_fitness

// WBL 23 Aug 94 Move to Pareto tournament selection. Add queue.h
//               Move hits from Chrome to new Problem specific class
//               FitnessValue. Make ThisProblem of type queue*.
//               Add wordsused() and use it. Use fitptr inplace of chr..->nfi..

// WBL 16 Aug 94 Add Prog2, Prog3, Qrog2 and Qrog4

// WBL 15 Aug 94 Undo 7 Aug 94 (quick and dirty). Move setting max_fitness
//               to generate_tests, move score(), move display of fitness
//               targets from write_tests to main.
//               Keep record of how many tests we pass.

// WBL  5 Aug 94 Boost penalty from .2 to 2

// WBL  5 Aug 94 Add penalty for using more than 15 memory cells

// WBL  4 Aug 94 Increase 5th test from 80 to 160 tests

// WBL 3b Aug 94 Remove makenull from 5th test and boost chance of enqueue
//               Correct comparison of probabilities when choosing test

// WBL  3 Aug 94 Fix calculation of modulus again. See test program
//               mod_test.cc and its output file mod_final_test.
//               Nb retro fit 1.12 ontop of 1.9

// WBL 31 Jul 94 Increase chance of using small integers
//               Add 5th test sequence
//               FIXBUG in 30 Jul so display "start_test" correctly

// WBL 31 Jul 94 Add display of elapsed time

// WBL 30 Jul 94 Make number of test sequences to skip configurable
//               and restore all four.
//               Replace Write_Aux(n) with Set_Aux(n)
//               Remove Arg2 from function list (never non-zero)

// WBL  7 Jul 94 Skip first three test sequences

// WBL  6 Jul 94 Add ADF code from queue.cc version 2.6
//               But only allow adf1 to be called.
//               Add check NUM_TREES is correct

// WBL 30 Jun 94 Make calling  DisplayDstats() depend on pTrace bit 2 only

// WBL 28 Jun 94 Make calling  DisplayDstats() depend on pTrace
//               Give empty score of 1 rather than .25
//               Give front and dequeue score of 1 for correct

// WBL 27 Jun 94 Restore DisplayDstats()

// WBL 25 Jun 94 Make Dequeue return answer. Test on same basis as Front.
//	         Remove directing crossover. (25a correct Good score)

// WBL 24 Jun 94 Based on version 1.6 ie skip version which add ADFS
//               But add tidy ups.
//               Direct which tree will contain crossover points.

// WBL 19 Jun 94 Make all function scores parmaterisable. Make front score use
//               recipricol difference and sign, use empty_score rather than 1
//               use gencount+1 when deciding to stop or not

// WBL 17 Jun 94 Use same test lengths as stack.cc version 25 May 1994,3

// WBL 16 Jun 94 Add using pPopSeed and pTestSeed. Move Pop::Write()
//               Comment out Pop::DisplayDstats()

// WBL 14 Jun 94 Add calling Load() and Save() and drawing pop_size and 
//               gen_max from params.
//               Add calling Pop::DisplayDStats(), Pop::Write()

// WBL 13 Jun 94 Make empty == 0 => TRUE, rather than >0

//requires MULTREE to be defined

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

#include "queue2.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

const float sign_score      = 0.0; //front & dequeue
const float magnitude_score = 1.0; //front & dequeue
const float empty_score     = 1.0;
const float makenull_score  = 0.05;
//          dequeue_score -- as front
const float enqueue_score   = 0.05;
      float max_fitness     = 0.0; // Calculated by write_tests
const float mem_penalty     = 0.0; // No longer used was 2.0;
//const int mem_penalty_bot = 16;

//**************************************************************************

// Define your FitnessValue class

void myfitnessvalue::write(ostream& fout)
{	fout << fvalue;
        int total = 0;
	fout << " {";
	for (int i=0; i <= empty; i++)
		{ total += hits[i];
		  fout << hits[i];
		  if (i < empty ) fout << ",";
	        }
	fout << "}= " << total;
	fout << " memory " << mem_used;
	fout << " adf1ver " << adf1;
}//end myfitnessvalue::write

queue* ThisProblem;
ChromeParams* ThisParams = new ChromeParams();

//**************************************************************************
// 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       5
#define Last_test_seq      5
//#define num_tests        320
#define Max_tests        (320+Num_test_seq+1)

#define test_queue_limit  10
#define Max               10
#define store_limit       32

retval Arg1, Arg2, Aux1, Aux2, Aux3, store[store_limit];

BOOL store_written[store_limit];

#define Vnone (-4)
#define Vaux3 (-3)
#define Vaux2 (-2)
#define Vaux1 (-1)
//else store[x]
int last_var_used = Vnone;

int calls [ NUM_TREES]; //used to prevent recursive calls

BOOL memory_error;
BOOL recurse_error;

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

if ( address <= 0 || address >= store_limit )
  {
	memory_error = TRUE;
	store[0] = 0;         //Prevent using buffer area (depends on write)
	return 0;             //safe buffer area
  }
else
  {	return address;
  }
}//end get_address
//**************************************************************************

class retval_cache
{
 private:
	retval* answerptr;
	int     cache_size /*= 0*/;
	/*const int magic = -50505050;*/ enum {magic = -50505050};
//statistics
	int     calls;
	int     hits;
	int     magic_hits;
	retval  min;
	retval  max;
 public:
	int cache_used /*= 0*/;
	retval_cache( int size ): cache_used(0) 
		{ 
//cout<<"retval_cache"<<endl;//debug
		  answerptr   = new retval [ size ]; 
	          cache_size  = size;
                  stats_init();
	        };
	~retval_cache() 
		{ 
//cout<<"deleting retval_cache"<<endl;//debug
		  delete[] answerptr;
	        }
	void init()
                { 
//cout<<"init cache"<<endl;//debug
                  cache_used = 0;
                  for (int i = 0; i < cache_size; i++)
			  answerptr[i] = magic;
                };
        BOOL held( retval input, retval* output )
                { calls++;
                  if ( input >= (0-cache_size/2) && input < cache_size/2 )
		      {
			      if ( answerptr[input+cache_size/2] == magic )
				      {return FALSE;};
			      hits++;
//cout<<"heldFound "<<input<<". Returning ";
//cout<<answerptr[input+cache_size/2]<<flush;
                              *output = answerptr[input+cache_size/2];
//cout<<" returned value="<<*output<<endl;
			      return TRUE;
		      }
//cout<<"held "<<input<<" outside cache "<<endl;
		  return FALSE;
                };
	void add( retval input, retval answer )
		{   if (input < min) min = input;
                    if (input > max) max = input;
//cout<<"Add "<<input<<","<<answer<<flush;
                    if ( input >= (0-cache_size/2) && input < cache_size/2 )
			   { if (answer==magic)
				  {  magic_hits++;}
			     else
				  {  answerptr[input+cache_size/2] = answer;
//cout<<". Slots in use "<<cache_used<<flush;
				      cache_used++;
			          }
		           }
//cout<<endl;//debug
	        };
	void stats_init();
	void write( ostream& fout = cout )
		{   fout << "Cache used "<< calls << " times, hits " << hits;
		    fout << " (" << float(hits)/float(calls) << ").";
		    fout << " Least input " << min;
		    fout << " highest input " << max;
		    fout << " magic number " << magic;
		    fout << " hit " << magic_hits << endl;
		};
};//end retval_cache
	
void retval_cache::stats_init()
{
	calls = 0;
	hits  = 0;
	magic_hits = 0;
	min   = MAXINT;
	max   = -MAXINT;
}

retval_cache adf1_cache(1000);

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

// Problem Specific Terminals

// gcc refuses to accept these in primitiv So stuff em here!

OPDEF(Prog2Eval) {EVAL; return EVAL;}
//OPDEF(Prog3Eval) {EVAL;EVAL; return EVAL;}
OPDEF(Qrog2Eval) {retval first_eval=EVAL;
                  int    save_last_var_used = last_var_used;
		  EVAL;
		  last_var_used = save_last_var_used;
		  return first_eval;}
//OPDEF(Qrog3Eval) {retval first_eval=EVAL;EVAL;EVAL; return first_eval;}

OPDEF(zeroEval) {return 0;}
OPDEF(oneEval) {return 1;}
OPDEF(MaxEval) {return Max;}
OPDEF(modEval) { //see workbook III 10 June 1994
                 //    workbook IV  3 August 1994
       retval a = EVAL;
       retval b = abs(EVAL);
       if (b!=0) return (a % b + b) % b;
       else      return a;
}
OPDEF(Arg1Eval) {return Arg1;}
OPDEF(Arg2Eval) {return Arg2;}
OPDEF(Aux1Eval) {last_var_used=Vaux1; return Aux1;}
OPDEF(Aux2Eval) {last_var_used=Vaux2; return Aux2;}
OPDEF(Aux3Eval) {last_var_used=Vaux3; return Aux3;}
OPDEF(inc_Aux1Eval)  {last_var_used=Vaux1; return ++Aux1;}
OPDEF(Minc_Aux1Eval) {last_var_used=Vaux1; 
                      return Aux1 = ((++Aux1)%Max+Max)%Max;}
OPDEF(dec_Aux1Eval)  {last_var_used=Vaux1; return --Aux1;}

OPDEF(inc_Aux2Eval)  {last_var_used=Vaux2; return ++Aux2;}
OPDEF(Minc_Aux2Eval) {last_var_used=Vaux2;
                      return Aux2 = ((++Aux2)%Max+Max)%Max;}
OPDEF(dec_Aux2Eval)  {last_var_used=Vaux2; return --Aux2;}

OPDEF(inc_Aux3Eval)  {last_var_used=Vaux3; return ++Aux3;}
OPDEF(Minc_Aux3Eval) {last_var_used=Vaux3;
                      return Aux3 = ((++Aux3)%Max+Max)%Max;}
OPDEF(dec_Aux3Eval)  {last_var_used=Vaux3; return --Aux3;}

//Problem specific Functions
OPDEF(readEval) {
       int address = get_address();
       last_var_used = address;
       return store[address];
}
OPDEF(writeEval) {
       int address = get_address(); 
       retval old = store[address];
       store[address] = EVAL;
       store_written[address] = TRUE;
       last_var_used = address;
       return old;                // copy what Tesler does
}
//OPDEF(write_Aux1Eval) {
//       retval old = Aux1;
//       Aux1 = EVAL;
//       return old;                // copy what write (ie Tesler) does
//}
//OPDEF(write_Aux2Eval) {
//       retval old = Aux2;
//       Aux2 = EVAL;
//       return old;                // copy what write (ie Tesler) does
//}
OPDEF(set_Aux1Eval) {
       Aux1 = EVAL;
       last_var_used = Vaux1;
       return Aux1;                // Nb simplier than Tesler
}
OPDEF(set_Aux2Eval) {
       Aux2 = EVAL;
       last_var_used = Vaux2;
       return Aux2;                // Nb simplier than Tesler
}
OPDEF(set_Aux3Eval) {
       Aux3 = EVAL;
       last_var_used = Vaux3;
       return Aux3;                // Nb simplier than Tesler
}
retval calleval (int numarg, int tree, retval_cache* cache = NULL )
{
	retval result;

	int save_arg1 = Arg1;
	int save_arg2 = Arg2;
	int save_var_used = last_var_used;

	int t1 = 0;
	int t2 = 0;
	int var_used = Vnone;

	if ( numarg > 0 )
		{ last_var_used = Vnone; 
		  t1 = EVAL;
		  var_used = last_var_used;
	        }
	if ( numarg > 1 ) t2 = EVAL;
	assert ( numarg <= 2 ); 

	Arg1 = t1;
	Arg2 = t2;

	if ( calls [ tree ]++ > 1 )
	      { recurse_error = TRUE;
	        result = 0;
	      }
	else  { 
		if (cache==NULL || cache->held(Arg1,&result)==FALSE)
		{
			evalnode* save_ip = IP;
			result = CHROMEP->evalAll ( tree );
			IP = save_ip;
			if (cache!=NULL) cache->add(Arg1,result);
	        }
//cout<<"calleval updating "<<last_var_used<<" to "<<result<<endl;
		switch(last_var_used)
			{
			case Vnone:
				break;
			case Vaux1:
				Aux1 = result;
				break;
			case Vaux2:
				Aux2 = result;
				break;
			case Vaux3:
				Aux3 = result;
				break;
			default:
				if ( last_var_used > 0 &&
				     last_var_used < store_limit)
				    {
					store[last_var_used]         = result;
					store_written[last_var_used] = TRUE;