list.cc

来自「标准的GP源代码,由Andy Singleton维护」· CC 代码 · 共 1,002 行 · 第 1/3 页

// list.cc   File to demonstrate evolution of queue, build with GPQUICK-2.1
// W. Langdon cs.ucl.ac.uk 24 Jan 1995
//                     based upon queue2.cc 24 Jan 1995 Revision: 1.??
#define list_version "list. $Revision: 1.87 $"

//#define DEBUG 

//Modifications (in reverse order)

//WBL  4 Apr 97  Easter 1997 Release. Restore r1.74 functionality (regarding
//               gp::gp(), static_check and final_score) retain bugfixes 
//               Remove update_rank (now done by InsertMember)
//               Make compatble with DEC UNIX Alpha C Compiler
//               Make compatible with MAXTREEDEPTH

//WBL 30 Aug 95  Disable syntax rules entirely

//WBL 30 Aug 95  Make syntax much less restrictive
//               Allow PROG2, forwhile, i0 in any tree (allow nested loop)
//               Allow aux1 everywhere but Next and Previous
//               Allow ARG1 and ARG2 in all _adfs where valid ie Insert_adf
//               Allow read, write, swap everywhere but end,first,next,prev
//               Allow print in Printlist
//               Allow End,First,Next,Previous to be calld by all but eachother
//               Allow Insert,Delete,Locate,Printlist to call own adf directly

//               Remove restriction on nested loops and print

//WBL  8 Aug 95  Add current_phase_reported

//WBL  8 Aug 95  BUGFIX ensure only call update_population_fitness() once

//WBL  8 Aug 95  BUGFIX replace constant NUM_TEST_PHASES by var num_phases

//WBL 27 Jun 95  Support multiple testing phases

//WBL 26 Jun 95  After 1st solution is found, remove cpu amd mem thresholds

//WBL 20 Jun 95  Add ProbLTStat

//WBL 29 May 95  Restore calling update_population_fitness once sol_found.
//               and remove fitness dependance on Memory_errors()

//WBL 28 May 95  Move write_problem_params into this file (from gp.cc)
//               add display of (new value of) cpu_penalty_bot

//WBL 27 May 95  Support op_ok

//WBL 26 May 95  BUGFIX minor chance of ChooseCrossTree not setting tree

//WBL 25 May 95  Make ChooseCrossTree part of Chrome and return its answer 

//WBL 23 May 95  Make ChooseCrossTree inactive untill pass more tests than fail

//WBL 22 May 95  Make ChooseCrossTree take into account those test which were
//               were not run (due to stop_on error)

//WBL 22 May 95  Change so max_fitness > max_passes rather than setting highest
//               fitness ever report to < max_passes. Should be cosmetic,
//               ie get printing ok

//WBL 14 May 95  BUGFIX(for 14 May) dont display gencount on initial pop

//WBL 14 May 95  BUGFIX(for 12 May) protect against cpu_time overflow

//WBL 14 May 95  Allow to run past solution. BUT DONT CHANGE FITNESS FUNCTION

//WBL 12 May 95  Add ProbLPStats

//WBL 12 May 95  Add support for memory_errors. Include them in memory fitness
//               penalty only after sol_found

//WBL 12 May 95  Report each new solution found internally, rather than
//               relying on gp.cc to report the whole population.
//               Remove perfect

//WBL 10 May 95  Allow run to continue passed 1st solution (see 9 May), 
//               passed solution with no memory or cpu penalties. Report 
//               solutions found which use less memory or less cpu. Add
//               update_population_fitness

//WBL  9 May 95  Add perfect()

//WBL  7 May 95  Remove second parent from consideration in ChooseCrossTree
//               since blurs distictions esp if cross with self-similar
//               Reduce tournament size from 7 to 3.

//WBL  7 May 95  Correct display of cache statistics.
//               Enlarge field used to print ok-nak

//WBL  3 May 95  Add STORE_FIT

//WBL  2 May 95  Add ChooseCrossTree

//WBL  2 May 95  Add TRACE_RUN

//WBL  1 May 95  Remove Ifeq (SUB works quite well!). 
//               Remove ARG1, ARG2 and next from ins_adf (reorder Adf1_xxx)

//WBL 30 Apr 95  Comment out chains

//WBL 23 Apr 95  Add Ntests_run and cpu penalty

//WBL 23 Apr 95  Add First and End caches

//WBL 22 Apr 95  Remove Iflte. Remove Aux1 from Next and Prev, xxx_adf,
//               Makenull, Retrieve, Locate and Printlist
//               Add next_cache and prev_cache

//WBL 20 Apr 95  Add IsLoop, TIMINGS

//WBL 18 Apr 95  Replace adf2 by swap

//WBL 17 Apr 95  More restrictive version of which primitives can be in which
//               tree and more checks by static_check. And more debug info

//WBL  8 Apr 95  Add insert_adf, delete_adf, locate_adf and printlist_adf

//WBL  7 Apr 95  Remove loops except from adf1 and other who calls who changes

//WBL 6  Apr 95  Replace arg1 and arg2 by ARG1 and ARG2 in insert, delete
//               and locate. Update static_check

//WBL 31 Mar 95  Add ForWhileEval and Prog2Eval etc

//WBL 23 Mar 95  Display fvalue in fixed field width

//WBL 22 Mar 95  Set chains to NULL

//WBL 14 Mar 95  Do clear inline

//WBL 11 Mar 95  Add static_tests to ensure use of arg1 and arg2

//WBL 21 Feb 95  Performance improvements. Inline update_score (nb move to
//               test.cc) Call cells_written only once.

//WBL 16 Feb 95  Fix bug in calculating amout of memory used.

//WBL 15 Feb 95  Used fixed feild width in outputing hits
//               Add update_passed

//WBL 13 Feb 95  Comment out TopEval and BotEval on the principle of
//               minimum change from queue.

//WBL 11 Feb 95  Add update_score and final_score

//WBL 24 Jan 95  New file

//requires MULTREE to be defined

#include <assert.h>
#include "pch.h"
#include "chrome.h"
#include "primitiv.h"
#include "list.h"
#ifdef TRACE_RUN
#include "trace.h"
#endif
#ifdef TIMINGS
#include "time.h"
#endif
#include "Primitives.h"
#include "gp.h"
#include "test.h"

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

extern Pop*  ThisPop;
extern test* ThisTest;

const int tree_arg_num[Printlist+1] = {0,1,2,1,0,0,1,1,1,0};
const BOOL tree_return_value[Printlist+1] = 
                       {TRUE,TRUE,FALSE,FALSE,TRUE,TRUE,TRUE,TRUE,TRUE,FALSE};

int num_sol_found = 0;//used to report solution to each test phase found
BOOL sol_found = FALSE;//used to report 1st total solution found
                       //Once found there are no thresholds on mem or cpu usage
BOOL current_phase_reported = FALSE;//Used by gen_gens
                       //should be in dumpfile but ignore this for time being
 
//**************************************************************************


void write_problem_params()
{
cout<<store_limit<<"["<<Array_bot<<".."<<Array_top<<"] ";
cout<<mem_penalty_bot<<" "<<F_tan_spread<<" "<<cpu_penalty_bot<<endl;
}

void missed(ptrmyfitnessvalue fitptr, int answer[NUM_TREES])
{//estimate number of time each tree would be run if stop_on error hadnt
 //prematurely aborted the tests. For Adfs etc this is pure guessing

ThisTest->not_run(fitptr, answer);

for(int t = NUM_OPERATIONS; t<NUM_TREES; t++) {
	const int mql = 3; //all a bit of a guess anyway

	answer[t] =   (t==Insert_adf)   ? answer[Insert]    * mql :
		      (t==Delete_adf)   ? answer[Delete]    * mql :
		      (t==Locate_adf)   ? answer[Locate]    * mql :
		      (t==Printlist_adf)? answer[Printlist] * mql :
			                  answer[Insert] + answer[Delete] + 
			                  answer[Locate] + answer[Printlist];
			      
}
}//end missed

BOOL Tree_OK(ptrmyfitnessvalue fitptr, int tree)
{
return	(tree==Insert_adf)   ? ThisTest->Operation_OK(fitptr,Insert)   :
	(tree==Delete_adf)   ? ThisTest->Operation_OK(fitptr,Delete)   :
	(tree==Locate_adf)   ? ThisTest->Operation_OK(fitptr,Locate)   :
	(tree==Printlist_adf)? ThisTest->Operation_OK(fitptr,Printlist):
		               ThisTest->Operation_OK(fitptr,tree);
}//end Tree_OK

// Define your FitnessValue class

void myfitnessvalue::write(ostream& fout)
{	{char buf[80]; sprintf(buf,"%4d",int(fvalue));
	 fout << buf;}
        scoretype total = 0;
	fout << " {";
	for (int i=first_op; i <= last_op; i++)
		{ total += hits[i];
		  char buf[80]; sprintf(buf,"%4.1f",hits[i]);
		  fout << buf << ",";
	        }
	fout << "[";
	for (i=0; i < NUM_OTHERS; i++)
		{ char buf[80]; sprintf(buf,"%4.1f",hits[i+last_op+1]);
		  fout << buf;
		  if (i < NUM_OTHERS-1 ) fout << ",";
	        }
	fout << "]}= " << total;
	fout << " mem " << int(mem_used)<<","<<Memory_errors();
#ifdef MINC_ADF
	fout << " adf1ver " << adf1;
#endif
#ifdef TIMINGS
	fout << " cpu " << cpu_time;
#endif
	fout << " tests " << Ntests_run;
#ifdef TRACE_RUN
	fout << " (";

	int notrun[NUM_TREES];
	missed(this, notrun);

	for (i=0; i < NUM_TREES; i++)
		{ char buf[80]; 
		  sprintf(buf,"%4d", ok(i)); fout << buf;
		  {if(Tree_OK(this,i))
			   fout<<"K"; else fout<<"-";}
		  sprintf(buf,"%-4d",nak(i)); fout << buf;
		  sprintf(buf,"%-4d",notrun[i]); fout << buf;		  
	        }
	fout << ")";
#endif
}//end myfitnessvalue::write

retval_cache   end_cache(1000);
retval_cache first_cache( 200);
retval_cache  next_cache(1000);
retval_cache  prev_cache( 200);

void cache_init()
{
	end_cache.init();
	first_cache.init();
	next_cache.init();
	prev_cache.init();
}

void cache_stats_init()
{
        end_cache.stats_init();
        first_cache.stats_init();
        next_cache.stats_init();
        prev_cache.stats_init();
}

void cache_stats()
{
	cout<<endl;
	cout<<"Size of end  cache " << end_cache.cache_used << endl;
	cout<<"Size of firstcache " << first_cache.cache_used << endl;
	cout<<"Size of next cache " << next_cache.cache_used << endl;
	cout<<"Size of prev cache " << prev_cache.cache_used << endl;
}

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


OPDEF(RetrieveEval) {return calleval (tree_arg_num[Retrieve],Retrieve);}
OPDEF(EndEval)      {return calleval (tree_arg_num[End],     End,     FALSE,-1,
                                      &end_cache);}
OPDEF(FirstEval)    {return calleval (tree_arg_num[First],   First,   FALSE,-1,
                                      &first_cache);}
OPDEF(NextEval)     {return calleval (tree_arg_num[Next],    Next,    TRUE,-1,
                                      &next_cache);}
OPDEF(PrevEval)     {return calleval (tree_arg_num[Previous],Previous,TRUE,-1,
                                      &prev_cache);}
OPDEF(Adf1_InsertEval)     {return calleval (2, adf1,FALSE,Insert_adf);}
OPDEF(Adf1_DeleteEval)     {return calleval (2, adf1,FALSE,Delete_adf);}
OPDEF(Adf1_LocateEval)     {return calleval (2, adf1,FALSE,Locate_adf);}
OPDEF(Adf1_PrintlistEval)  {return calleval (2, adf1,FALSE,Printlist_adf);}
//OPDEF(Adf2Eval)            {return calleval (2, adf2);}
OPDEF(FUNCEval)            {return calleval (1, Arg2);}

int Adf1_Insert_funcnum = -1;
int Adf1_Delete_funcnum = -1;
int Adf1_Locate_funcnum = -1;
int Adf1_Printlist_funcnum = -1;

OPDEF(Insert_adfEval)    {return calleval (1,Insert_adf);}
OPDEF(Delete_adfEval)    {return calleval (1,Delete_adf);}
OPDEF(Locate_adfEval)    {return calleval (1,Locate_adf);}
OPDEF(Printlist_adfEval) {return calleval (1,Printlist_adf);}

gp::gp():i0_funcnum(0),
         for_funcnum(0),
	 down_funcnum(0),
	 while_funcnum(0),
	 forwhile_funcnum(0),
 
	 arg1_funcnum(0),
	 arg2_funcnum(0),