chrome.cxx

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

{
        return pop[BestMember];
}
#endif
#endif

void Pop::select_candidates(	int target, int tourn_size,
				Chrome* candidates[], int slots[],
				BOOL best)
{
int  dw, pw, offset;
UINT region;

region = params->params[pMateRadius];
dw = params->params[pDemeWidth];
pw = params->params[pPopWidth];

if (region == 0 || region > popsize) region = popsize;

if (dw==0 || pw==0)
{	dw = 1;
	pw = 1;
}

#ifdef ORIGINAL_DEME
offset=popsize+target-dw/2-region*pw/dw/2;
#else
offset=popsize+target-dw/2-pw*(region/dw/2);
#endif /*ORIGINAL_DEME*/

const int Elitist = params->params[pElitist];

int endstop = 0;
for (int i=0;  i<tourn_size; endstop++)
{	assert(endstop<1000);		//could happend with small demes
	int r = rnd(region);		//select from within deme
	int x = r/dw*pw + r%dw;		//convert from deme to pop index
	slots [i]     = (x+offset)%popsize;
	if ( best || (Elitist==0) || 
	     (!pop[slots[i]]->nfitness->unique_best())) {
		candidates[i] = pop[slots[i]];
		i++;
	}
}
}//end Pop::select_candidates

enum {docross,domutate,doanneal,docrossanneal,docopy};

Chrome* Pop::selectParent(int target)
{                                                                               // target identifies selection region in pop
// select one parent. Return pointer to selected parent
        int ts;
        Chrome* best;

        ts = params->params[pTournSize];
        // Only tournament selection is implemented in GPQUICK.
        // Add your own methods to taste
        if (params->params[pSelectMethod] == ETournament)
        {
//		Chrome* candidates [ts];
//		int     slot      [ts];
		Chrome* candidates [10];
		int     slot      [10];
		int	index;
		select_candidates(target,ts,candidates,slot,TRUE);
		best = problem->Bestof(candidates,ts,&index,target);
#ifdef CROSSFILE
		if(crossfile) {	crossfile<<"P "<<slot[index]<<" "<<flush;}
#endif
        }
        return best;
}

#ifdef MULTREE
Chrome* Pop::generate(int tree) //tree to crossover on, < 0 do at random
#else
Chrome* Pop::generate()
#endif
// generate a single new chrome.  Return fitness.
// This implements a one processor, steady stage GA
// Its reproductive operators are Copy, Subtree Crossover, and Node Mutation
// It uses tournament selection to select parents
// It selects in a one dimensional local region
// It uses global tournament anti-selection to select a member for replacement

// Virtual - add your own GA here if desired

{
#ifndef STACK_LIB
#ifdef MULTREE
	if ( tree < 0 ) tree = rnd ( NUM_TREES ); //defualt
#endif //MULTREE
#endif

        gencount++;

        if (initeval)                 // still on initial evaluations?
                                                        // don't generate. Finish evaluating initial pop.
        {
          Fitness(pop[nexteval]);
          InsertMember(nexteval,pop[nexteval],TRUE);
	  int target=nexteval;
          nexteval++;
          if (nexteval>=popsize)
                initeval=FALSE;
	  return pop[target];
          }

        int target;
//        int i,region,ts,offset;
        int newchrome = FALSE;
        int prob,wheel;
        int dowhat;

        Chrome* best;
        Chrome* secondbest;
        Chrome* trial;
                // decide what to do - Cross, Mutate, Copy
        
              prob=rnd(params->params[pCrossWt]+params->params[pMuteWt]+params->params[pCopyWt]+params->params[pAnnealMuteWt]+params->params[pAnnealCrossWt]);
                wheel=params->params[pCrossWt];
                if (prob<wheel)
                        dowhat=docross;
                else if (prob<(wheel += params->params[pMuteWt]))
                        dowhat=domutate;
                else if (prob<(wheel += params->params[pCopyWt]))
                        dowhat=docopy;
                else if (prob<(wheel += params->params[pAnnealMuteWt]))
                        dowhat=doanneal;
                else
                        dowhat=docrossanneal;
           
                // Perform reproduction
                switch (dowhat)
                {
                case docross:
                        target=GetTarget();                     // Find a member to replace
                        best=selectParent(target);
                        secondbest=selectParent(target);
#ifdef MULTREE
#ifdef DIRECTEDXOVER
        		if ((params->params[pDirCrossWt] != 0)      &&
			    (rnd(100) < params->params[pDirCrossWt])   )
				tree = best->ChooseCrossTree(secondbest);
#endif
			num_crosses[tree]++;
                        trial=best->CrossTree(secondbest, tree);
#else
                        trial=best->CrossTree(secondbest);
#endif
                        newchrome = TRUE;
                break;
                case domutate:
                        target=GetTarget();                     // Find a member to replace
                        best=selectParent(target);
                        trial = best->Copy();
                        prob=rnd(params->params[pMuteNodeWt]+params->params[pMuteConstWt]+params->params[pMuteShrinkWt]+params->params[pMuteSubTreeWt]);
                        wheel=params->params[pMuteNodeWt];
                        if (prob<wheel)
                             trial->Mutate();
                        else if (prob<(wheel += params->params[pMuteConstWt]))
                             trial->MutateC();
                        else if (prob<(wheel += params->params[pMuteShrinkWt]))
                             trial->MutateShrink();
                        else 
                             trial->MutateSubTree();
                        newchrome = TRUE;
                 break;
                 case doanneal:
                        target=GetAnnealTarget();
                        trial = pop[target]->Copy();
                        prob=rnd(params->params[pMuteNodeWt]+params->params[pMuteConstWt]+params->params[pMuteShrinkWt]+params->params[pMuteSubTreeWt]);
                        wheel=params->params[pMuteNodeWt];
                        if (prob<wheel)
                            trial->Mutate();
                        else if (prob<(wheel += params->params[pMuteConstWt]))
                                trial->MutateC();
                        else if (prob<(wheel += params->params[pMuteShrinkWt]))
                             trial->MutateShrink();
                        else 
                             trial->MutateSubTree();

                        Fitness(trial);
                                // test whether mutated chome is fitter
                        if (trial->nfitness->IsBetter(pop[target]->nfitness))
                        {
                                InsertMember(target,trial);
                                newchrome = TRUE;
                        }
                        else
#ifdef GENERATIONAL
			  if(params->params[pGenerational]) { gencount--;}
#endif
                                delete trial;
                  break;
                  case docrossanneal:
                        target=GetAnnealTarget();
                        best=selectParent(target);
#ifdef MULTREE
                        trial=pop[target]->CrossTree(best, tree);
#else
                        trial=pop[target]->CrossTree(best);
#endif
                        Fitness(trial);
                        // test whether chome is fitter
                        if (trial->nfitness->IsBetter(pop[target]->nfitness))
                        {
                                InsertMember(target,trial);
                                newchrome = TRUE;
                        }
                        else
#ifdef GENERATIONAL
			  if(params->params[pGenerational]) { gencount--;}
#endif
                                delete trial;
                  break;

                  case docopy:
                        target=GetTarget();                     // Find a member to replace
                        best=selectParent(target);
                        trial=best->Copy();
                        newchrome = (params->params[pRepeatEval]? TRUE: FALSE);
                  }//endswitch

                      // Update the pop array
                  if ((dowhat!=doanneal) && (dowhat!=docrossanneal))
                  {

                       // fitness?
                       if (newchrome)
                       {
                            Fitness(trial);
                        }
#ifdef CROSSFILE
		       if(crossfile) {
			 crossfile<<"off ";
			 crossfile<<gencount<<" ";
			 crossfile<<trial->nfitness->fvalue<<endl;
		       }
#endif
                        InsertMember(target,trial);
                  }

        return trial;
}

#ifdef MULTREE
Chrome* Pop::go_until(time_t max_time, int maxevals, float maxfitness,
	              int tree) //default random tree
#else
Chrome* Pop::go_until(time_t max_time, int maxevals, float maxfitness)
#endif
// generate until time max_time, evals maxevals, or fitness maxfitness
// Do this to run the GA in a bigger event loop

{
        //int done = FALSE;
        int didevals = 0;
#ifndef GENERATIONAL
#ifdef MULTREE
        Chrome* lastchrome=generate(tree);
#else
        Chrome* lastchrome=generate();
#endif //MULTREE
        didevals++;
#else
        Chrome* lastchrome=NULL;
#endif //GENERATIONAL

        //while(maxevals == 0 || didevals<maxevals)
        while ((max_time == 0 || time(NULL) < max_time) &&
        (maxevals == 0 || didevals<maxevals) &&
        ( lastchrome==NULL || (lastchrome->nfitness->fvalue < maxfitness))
        &&!Aborted())
        {
#ifdef GENERATIONAL 
#ifndef PARETO
	       if((gencount+1)%popsize==0 && 
		  (!initeval)             && params->params[pGenerational]) {
		 BestFitness = NULL;
		 if(params->params[pElitist] != 0) {
		   cout<<"Copying BestMember of pop ("<<BestMember;
		   cout<<") to newpop 0 "<<gencount<<endl;
		   gencount++;
		   didevals++;
		   Chrome* newchrome = pop[BestMember]->Copy();
		   InsertMember(0,newchrome);
		 }
	       }
#endif
#endif

#ifdef MULTREE
               lastchrome = generate(tree);
#else
               lastchrome = generate();
#endif
               didevals++;
#ifdef GENERATIONAL
	       if((gencount+1)%popsize==0 && 
		  gencount > popsize  && params->params[pGenerational] ) {
		 cout<<"Copying newpop to pop, at "<<gencount<<endl;
		 for(int s=0; s<popsize; s++) {
		   delete pop[s];
		   pop[s] = newpop[s];
		 }
	}
#endif //GENERATIONAL
        }
        return lastchrome;
}

#ifdef MULTREE
void Pop::reinitialise(BOOL change_flags[NUM_TREES])
{
#ifdef PARETO
clear_rank();
#else
BestFitness=NULL;
#endif

for ( UINT i = 0; i < popsize; i++ ) {
	pop[i]->reinit_trees(change_flags);
	Fitness(pop[i]);
	InsertMember(i,pop[i],TRUE);
	}
}//end reinitialise
#endif

#ifdef STACK_LIB
int Pop::GetTarget()
// Tournament anti-selection for replacement.  Usually size 1 (random selection) or 2
// Will select a target that is too old, even if more fit.
{
        int target = rnd(popsize);
        int i,winner;
        if (params->params[pKillTourn]>1 && 
	    (params->params[pMaxAge] == 0 ||
	     (gencount - pop[target]->birth) <= params->params[pMaxAge]))
        // pick a target to replace
        for (i=1;i<params->params[pKillTourn];i++)
        {
                winner=rnd(popsize);
                if (params->params[pMaxAge] != 0 &&
		    (gencount - pop[winner]->birth) > params->params[pMaxAge])
                	return winner;

		if (pop[target]->nfitness->IsBetter(pop[winner]->nfitness))
                        target = winner;
        }
#ifdef CROSSFILE
	if(crossfile) {crossfile<<"T "<<target<<" "<<flush;}
#endif
        return target;
}
#else
int Pop::GetTarget()
// Tournament anti-selection for replacement.  Usually size 1 (random selection) or 2
{
#ifdef GENERATIONAL
  if(params->params[pGenerational]) return gencount % popsize;
#endif
//	Chrome* candidates [params->params[pKillTourn]];
//	int     slot       [params->params[pKillTourn]];
	Chrome* candidates [10];
	int     slot       [10];

        // pick a target to replace

        int s=rnd(popsize); //chose any deme in pop
#ifdef QUEUE_LIB
	slot[0] = s;
	candidates[0] = pop[s];

	select_candidates(s, params->params[pKillTourn] - 1,
			  &candidates[1], &slot[1], FALSE ); //chose from same deme
#else /*QUEUE_LIB*/
	select_candidates(s, params->params[pKillTourn],  //chose from same
			  candidates, slot, FALSE );      //deme
#endif /*QUEUE_LIB*/
	int index;
	problem->Worstof(candidates, params->params[pKillTourn], gencount, 
                         &index, s);
#ifdef CROSSFILE
	if(crossfile) {crossfile<<"T "<<slot[index]<<flush;}
#endif
        return slot[index];
}
#endif

int Pop::GetAnnealTarget()
{
#ifdef GENERATIONAL
  if(params->params[pGenerational]) return gencount % popsize;
#endif
// target identifies selection region in pop
// select one parent. Return pointer to selected parent
        int ts, i;
        int best,trial;

        ts = params->params[pTournSize];
        // Only tournament selection is implemented in GPQUICK.
        // Add your own methods to taste
        if (params->params[pSelectMethod] == ETournament)
        {
                best=rnd(popsize);
        for (i=1;i<ts;i++)
                {
                        trial=rnd(popsize);
                        if (pop[trial]->nfitness->IsBetter(pop[best]->nfitness))
                                best=trial;
                }
        }
        return best;
}

void Pop::Write(ostream & fout, BOOL binary) //WBL
{
for ( UINT i = 0; i < popsize; i++ )
    if(!binary)
      { fout << endl << i ;
#ifdef TRACE
	pop[i]->write_trace(); //fix some time. Problem with const
#endif //TRACE
	pop[i]->write(PRETTY_N