queue2.cc

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

	 Arg1 = argument[i];
	 Arg2 = 0;
	 memset(calls,0,sizeof(calls));
	 calls [ test[i] ] = 1; //should be in evalAll, but avoid chrome.cxx
	 answer = chrome->evalAll ( test[i] );
	 if (memory_error)  fout<< "MEMORY ERR\t";
//         else
         if (recurse_error) fout<< "RECURSE ERR\t";
         else
         if ( update_score( score, test[i], answer, ans[i]) )
	       { fout<<"passed\t\t";
		 passed++;
	       }
	 else
		 fout<<"FAILED\t\t";
	 fout<<"Test ["<<i<<"] ";
	 ThisProblem->WriteTreeName(test[i], fout);
	 fout<< "(" << argument[i] << ")  \tresult " << answer;
	 fout << " (expected " << ans[i] << ")\n";
        }//end if
fout<<"score = " << score;
fout<<" Aux1 = " << Aux1;
fout<<" Aux2 = " << Aux2;
fout<<" Aux3 = " << Aux3;
fout<<" lvusd  " <<last_var_used <<endl;
for (int j = 0; j < store_limit; j++)
   {
	if ( store[j] != 0 )
	   {
	   fout<<"store " << j-(store_limit/2) << " = " << store [j] << endl;
           }
   }
//if (memory_error||recurse_error) break;
if (recurse_error) break;
}//end loop

int written = 0;
for (int j = 1; j < store_limit; j++ )
{
	if (store_written[j])
	    {   if((j-store_limit/2)%10 == 0) fout << "W"; else fout << "w";
		written++;
	    }
	else
		if((j-store_limit/2)%10 == 0) fout << "_"; else fout << " ";
}
fout << ": " << written;
fout << " size of adf1 cache " << adf1_cache.cache_used << endl;

fout<<"Final score = " << score << ". Passed " << passed << " tests.\n";

if  ( passed < test_total ) //NB fvalue frigged to stop chrome
	assert (chrome->nfitness->fvalue == float (score)); //it should be!

}//end display_run()


float queue::fitness(Chrome* chrome)
// fitness function.
{
int i;
int passed = 0;
float score = 0;
memset(store_written,0,sizeof(store_written));

tests_run++;

const float r = float(ThisParams->params[pPopSize]-1) / 
                float(ThisParams->params[pPopSize]);
for (i=first_test; test[i] != end_tests; i++)
        tests_avg_passed[i] *=r;

ptrmyfitnessvalue fitptr = ptrmyfitnessvalue (chrome->nfitness);

//NB clearing whole of myfitnessclass cause gcc produced code to crash
memset(fitptr->hits,0,sizeof(fitptr->hits));
fitptr->mem_used = 0;

adf1_cache.init();

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

for(i=first_test; test[i] != end_tests; i++)
{
if (test[i] == start_test)
	{
//initialise everything for new test
	 memory_error = FALSE;
	 recurse_error= FALSE;
	 Aux1 = 0;
	 Aux2 = 0;
	 Aux3 = 0;
	 memset(store,0,sizeof(store));
        }
else
	{retval answer;
	 Arg1 = argument[i];
	 Arg2 = 0;
	 memset(calls,0,sizeof(calls));
	 calls [ test[i] ] = 1; //should be in evalAll, but avoid chrome.cxx
	 answer = chrome->evalAll ( test[i] );
//	 if (memory_error)   { break;  }
	 if (recurse_error)  { break;  }

         if (update_score( score, test[i], answer, ans[i]))
	       { fitptr->hits[test[i]]++;
		 passed++;
		 tests_avg_passed[i]+= 1.0/float(ThisParams->params[pPopSize]);
	       }

        }//end if
}//end loop

for (int j = 1; j < store_limit; j++ )
{	if (store_written[j])
		fitptr->mem_used++;
}
fitptr->adf1 = adf1_cache.cache_used;

if ( passed >= test_total ) score = max_fitness; //stop chrome

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

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

return score;

}//end queue::fitness

int static_check_loop = 0; //detect loops

int queue::static_check(Chrome* chrome, int tree)
// Perform static analysis of new chromsome. Just changed in tree
// Crude but should demonstrate if the idea is worth pursuing
// Only checks Adf1
{

const int good = 0;
const int recurse_penalty = 100;
const int poor_function_penalty = 100;
//const int memory_penalty = 20;

//store_written - not used directly by static_check

if (tree!=adf1) return good;

static_check_loop++;
if(static_check_loop > 1000)
{   cout<<"static_check looping! ("<<static_check_loop<<")"<<endl;
    static_check_loop = 0;
    chrome->write(PRETTY_NONE,cout); cout<<endl;
    return good;               //stop it looping
}

const int num_checks = 2*(Max + 1);

//cout<<"static_check (ADF1) "<<static_check_loop<<flush; //debug

retval ans [num_checks];

ptrmyfitnessvalue fitptr = ptrmyfitnessvalue (chrome->nfitness);

fitptr->adf1   = 0; //assume the worst
BOOL follow    = FALSE;
BOOL new_value = FALSE;
int  k         = -1;
for (int i = 0; (k<Max) && (i<num_checks); i++)
       {//start call adf1 loop
	 int input;
	 if (!follow && new_value && (ans[i-1] < 0 || ans[i-1] > Max) )
         {  input = ans[i-1];
	    follow = TRUE;
         }
	 else
         {  input  = ++k;
	    follow = FALSE;
         }

	 //initialise everything to be consistent with queue::fitness

	 memory_error = FALSE;
	 recurse_error= FALSE;
	 Aux1 = 0;
	 Aux2 = 0;
	 Aux3 = 0;
	 memset(store,0,sizeof(store));

	 Arg1 = input;
	 Arg2 = 0;
	 memset(calls,0,sizeof(calls));
	 calls [ tree ] = 1; //should be in evalAll, but avoid chrome.cxx

	 chrome->SetupEval();
	 ans [i] = chrome->evalAll ( tree );

//if(recurse_error)cout<<" RECURSE_ERROR";
//if(memory_error) cout<<" MEMORY_ERROR";
//cout<<" "<<Arg1<<"=>"<<ans[i]<<" "<<flush;

//cout<<" "<<last_var_used<<" "<<arg1_used<<" "<<arg1_side_effect<<" ";

	 if (recurse_error)  return recurse_penalty;

         new_value = TRUE;
	 for (int j = 0; j < i; j++)
	 {
		 if (ans[i] == ans[j]) new_value = FALSE;
	 }
	 if (new_value) fitptr->adf1++;

	if (ans[i] == i) return poor_function_penalty; //identity
        };//end run adf1 to test it loop


if (fitptr->adf1 <= 1)
	return poor_function_penalty; //ie its a constant
else
  {
//chrome->write(PRETTY_NONE,cout); cout<<endl; //debug
        static_check_loop = 0;
	return good;
  }
}//end queue::static_check



int Is_adf1_minc(Chrome* chrome)

// Call adf1 repeatedly, untill either it returns an answer it has
// already given before or one that is not a legal memory address.
// If adf1 falls into a cycle return the cycle length

{

retval ans [store_limit+2];
ans[0] = 0;

chrome->SetupEval();

for (int i = 0; i <= store_limit; i++)
       {
	 Arg1 = ans[i];
	 ans [i+1] = chrome->evalAll ( adf1 );

	 if ((ans[i+1]+(store_limit/2) <= 0) || (ans[i+1] >= store_limit/2))
		 return 0;

	 for (int j = 0; j <= i; j++)
		 {if (ans[i+1] == ans[j]) return i+1-j;}

        };//end run adf1 to test it loop

assert(1==0); //should never fall out of loop
return 0; //keep compiler quiet
}//end Is_adf1_minc

void test_all_adf1(Pop* pop, int lower)
{
int v, x, y;

if (ThisParams->params[pPopWidth] == 0)
   for (x=0;x<ThisParams->params[pPopSize];x++) {
	v = Is_adf1_minc(pop->pop[x] );
	if (v >= lower) {
		cout<< x << " " << v;
//		pop->pop[x]->write(PRETTY_NONE,cout);
		cout<<endl;
	}
   }
else
   for ( y=0; y <= (ThisParams->params[pPopSize] / 
		    ThisParams->params[pPopWidth]); y++) 
   for ( x=0; (x < ThisParams->params[pPopWidth]) && 
	      ((x+y*ThisParams->params[pPopWidth]) < 
		      ThisParams->params[pPopSize]);   x++) {
	v = Is_adf1_minc(pop->pop[x+y*ThisParams->params[pPopWidth]] );
	if (v >= lower) {
		cout<< x << " " << y << " " << v;
//		pop->pop[x+y*ThisParams->params[pPopWidth]]->
//			write(PRETTY_NONE,cout);
		cout<<endl;
	}
   }
}//end test_all_adf1;

void display_all_best(Pop* pop, int popsize, int popwidth)
{
int i, dummy;
int outputsize = 50;
int output[50 /*outputsize*/];
int duplicates[50 /*outputsize*/];

select_hits(
pop->pop, popsize, 0, &dummy, TRUE, output, duplicates, &outputsize);

cout<<"Best ("<<outputsize<<") in population "<<endl;

for (i=0; i<outputsize; i++){
	if (popwidth == 0) {
		cout<< output[i] << " ";
		pop->pop[output[i]]->nfitness->write();
	}
	else {
		cout<< output[i] % popwidth << " " 
		    << output[i] / popwidth << " ";
		pop->pop[output[i]]->nfitness->write();
	}
	cout<<endl;
}//end display best in pop

}//end display_all_best();

//void write_fitness_summary()
//{
//
//};//end write_fitness_summary




//**************************************************************************
int do_gens (Pop* pop, int number, int tree) //return if complete or not
{    
     cout << "Running, gpquick_seed " << gpquick_seed
          << " at " <<pop->gencount+1 << ". ";
     if ( tree >= 0 )
	  {  cout << "Crossover in ";
             ThisProblem->WriteTreeName(tree);
          }
     else
	     cout << "Random crossover tree\n";

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

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

#ifdef TRACE
     cout << pop->BestMember;
     pop->pop[pop->BestMember]->write_trace();
//   pop->pop[pop->BestMember]->write(PRETTY_NONE,cout);
     cout << endl;
#endif

//     write_tests();
     display_all_best(
	 pop, ThisParams->params[pPopSize], ThisParams->params[pPopWidth]);
     pop->DisplayStats();
     if ( ThisParams->params[pTrace] & pTraceDStats ) pop->DisplayDStats();

//     display_run(pop->best()); //show what it does
//     test_all_adf1(pop, 1);
     return (pop->BestFitness->fvalue >=max_fitness);

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

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

{
	time_t start, end;

	cout << "\nGP to evolve a Queue2, "<<main_version;
	time (&start);
	cout << ", " << ctime(&start) <<endl;

	ThisProblem=new queue(ThisParams);
	for(int i=0; i<argc;i++) {
		ThisParams->Load(argv[i]); }
	Pop* pop;


	if ( ThisParams->params[pTestSeed] > 0 ) 
		gpquick_seed = ThisParams->params[pTestSeed]; //dirty I know
	else
	      { rndomize(); //use random seed
		ThisParams->params[pTestSeed] = gpquick_seed; //record seed
	      }

	generate_tests();    //Must be done before create pop
	cout<<"Number of tests " << test_total;
	cout<<". Min expected score " << 0;
	cout<<" Good score " << max_fitness - 
                        ((test_cases [ front ] + test_cases [ dequeue ]) *
                         (sign_score + magnitude_score));
	cout<<" Top score " << max_fitness;
	cout<<endl<<endl;

	if ( ThisParams->params[pPopSeed] > 0 )
		gpquick_seed = ThisParams->params[pPopSeed];  //dirty I know
	else
	      { rndomize(); //use random seed
		ThisParams->params[pPopSeed] = gpquick_seed; //record seed used
	      }

	ifstream gpLoad ("gp.load");
	if ( gpLoad )
	     { cout << "Loading from one chrome from gp.load\n";
	       ThisParams->params[pPopSize]=1;
	       ThisParams->params[pGenerateLimit]=1;
             }

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

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

	ThisParams->Save();

	int done;
	if ( gpLoad )
	     { cout << "Overwritting with file gp.load\n";
	       int rval = pop->pop[0]->Load(gpLoad, TRUE);
	       if (rval != 0)
		       cout<<"Load error - "<<rval<<endl;
	       else
		   {   pop->pop[0]->SetupEval();
		       ThisProblem->fitness(pop->pop[0]);
		       pop->pop[0]->write_trace();
		       pop->pop[0]->write(PRETTY_NONE,cout);
		       adf1_cache.stats_init();
		       display_run (pop->pop[0]);
//		       test_all_adf1(pop, 0);
	           }
	       gpLoad.close();
	       done = TRUE;
        }
else
{
	cout << "Setting each fitness value\n";
	done = do_gens (pop, pop_size-1, -1); //no crossover on init pop
	

	cout << "Initial fitness values calculated,\n";
	cout << "Creating a total of " << gen_max << " individuals\n";

	                         // kbhit IS NOT PORTABLE (Borland specific)
	while ( (pop->gencount+1) < gen_max && !done && !kbhit() )  
	{
		done = do_gens (pop, pop_size, -1);
	}


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

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

	cout << "BestMember ";
#ifdef TRACE
	cout << pop->BestMember;
        pop->pop[pop->BestMember]->write_trace();
#endif
	pop->pop[pop->BestMember]->write(PRETTY_NONE,cout);

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

}//if not loading from file

	adf1_cache.write();

	time (&end);
	cout << "\nGP Queue2 took " << end - start << " secs. Finished at ";
	cout << ctime(&end);
//	cout << clock() << " ticks cpu";
	cout << endl;

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