pareto.cc

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

	spiral_edge = east;
	spiral_index = 0;
}
else {
	if(spiral_index >= (2*radius_of_spiral)) { 
		spiral_index=0;
		spiral_edge++;
		if(spiral_edge>south) {spiral_edge=east; radius_of_spiral++;};
	}
	
	switch (spiral_edge) {
	case east:
		x =  spiral_index    - radius_of_spiral*pw - radius_of_spiral;
		break;
	case north:
		x =  spiral_index*pw - radius_of_spiral*pw + radius_of_spiral;
		break;
	case west:
		x = -spiral_index    + radius_of_spiral*pw + radius_of_spiral;
		break;
	case south:
		x = -spiral_index*pw + radius_of_spiral*pw - radius_of_spiral;
		break;
	default:
		assert (1==0);
		break;
	}//end case	
	spiral_index++;
};//endif

#ifdef DEBUG
//	cout<<"\nspiral ("<<radius_of_spiral<<") compare with? "<<x
//	    <<" "<<(x+offset)%ThisPop->popsize;
#endif
return ThisPop->pop[(x+offset)%ThisPop->popsize];

}

void select_by_niche(const BOOL best, const int target,
	             const PtrChrome  list[], const int listsize,
		     int better[], int& listhead, int& numbetter )
{
//int niche[listsize];
//memset(niche,0,sizeof(niche));
int* niche = new int[listsize];
memset(niche,0,listsize*sizeof(int));

setup_spiral(); //just in case needed

const int TournComp = list[0]->params->params[pTournComp];
const int PopWidth  = list[0]->params->params[pPopWidth];
const int NicheSize = list[0]->params->params[pNicheSize];

for (int k=1; (numbetter>1) && (k<=TournComp); k++) {
	select_hits_pop_comparisons++;
	Chrome* comparitor;
	BOOL unique;
	do {   comparitor = (PopWidth==0)? any() : spiral(target);
	       unique = TRUE;
	       for (int i = 0; (i<listsize) && unique; i++)
		       {if(list[i]==comparitor) unique = FALSE;}
	} while (!unique);

	{for (int i = listhead; i >= 0; i = better[i]) {
		int d = ptrmyfitnessvalue(comparitor->nfitness)->dominates(
                        ptrmyfitnessvalue(list[i]->nfitness)               );
#ifdef DEBUG
//		cout<<" niche_ans("<<"?"<<","<<i<<")="<<d<<flush;
#endif
		//niche holds the number better than i. Those that are
                //close to i are counted against it to spread the population
		//out in fitness space. For the timebeing pNicheSize is
		//treated as a simple flag; 0 => not used, <> 0 means are in
		//the same niche if they have identical fitness. These are
		//intended for use if using pareto fitness.

		if ((d > 0) || 
		    ((d==IDENTICAL) && (NicheSize!=0)))
		    niche[i]++;
	}};//end compare with each left in tournament


	{int old_i = -1;
	 for (int i = listhead;  i >= 0 ; i = better[i]) {
	 int old_j = i;
	 for (int j = better[i]; j >= 0 ; j = better[j]) {
		 int diff = (niche[i] - niche[j]);
		 int dsq  = diff*diff;
		 if((dsq>=4) && (dsq>=4*(niche[i]+niche[j]))) { //2SD
#ifdef DEBUG
			 {cout<<endl<<"Removing "<<i<<" or "<<j<<" niches";
			 for (int i = listhead; i >= 0; i = better[i]) {
				 cout<< " [" <<i<< "]=" <<niche[i]<<flush;
			 }
			 cout<<endl;}
#endif
			 numbetter--;
			 if((best&&(diff<0))||((!best)&&(diff>0))){//remove j 
				  if ( old_j >= 0 ) better[old_j] = better[j];
				  else              listhead      = better[j];
			 }
			 else {//remove i
				  if ( old_i >= 0 ) better[old_i] = better[i];
				  else              listhead      = better[i];
				  goto end_loop_i;
			 }
		 }//remove from list;
		 else {
			 old_j = j;}
	 }//end for j
	 old_i = i;
end_loop_i: ;
	 }}//end for i

	 }//end for k

	//ok if havent differentiated so far, relax the 2SD requirement
	{int old_i = -1;
	 for (int i = listhead;  i >= 0 ; i = better[i]) {
	 int old_j = i;
	 for (int j = better[i]; j >= 0 ; j = better[j]) {
		 int diff = (niche[i] - niche[j]);
		 if(diff!=0) { 
#ifdef DEBUG
			 {cout<<endl<<"Remove2 "<<i<<" or "<<j<<" niches";
			 for (int i = listhead; i >= 0; i = better[i]) {
				 cout<< " [" <<i<< "]=" <<niche[i]<<flush;
			 }
			 cout<<endl;}
#endif
			 numbetter--;
			 if((best&&(diff<0))||((!best)&&(diff>0))){//remove j 
				  if ( old_j >= 0 ) better[old_j] = better[j];
				  else              listhead      = better[j];
			 }
			 else {//remove i
				  if ( old_i >= 0 ) better[old_i] = better[i];
				  else              listhead      = better[i];
				  goto end_loop_i2;
			 }
		 }//remove from list;
		 else {
			 old_j = j;}
	 }//end for j
	 old_i = i;
end_loop_i2: ;
	 }}//end for i

#ifdef DEBUG
	 {cout<<"by_niche "<<numbetter<<" choices left" <<flush;
	  for (int i = listhead;  i >= 0 ; i = better[i]) {
		  cout<< "[" <<i<< "]=" <<niche[i]<<" "<<flush;
	 }}
#endif
         if(numbetter>1) {//stats on how occupied niches are
		 select_hits_pop_niche    += niche[listhead];
                 select_hits_pop_nichesqr += niche[listhead]*niche[listhead];
	 }
delete[] niche;
}//end select_by_niche

#endif /*QUEUE_LIB*/

Chrome* select_hits (const PtrChrome  list[], const int listsize,
                     const int target, int* bestinlist, const BOOL best, 
	             int* select, int* num_duplicates, int* select_size)
{

//int better [listsize]; //use static array to hold dynmic list of candidates;
//int same   [listsize];
//int nchrome[listsize];
int* better = new int [listsize];//newer versions of C require it to be dynamic
int* same   = new int [listsize];
int* nchrome= new int [listsize];
int listhead  = -1;     //ie empty
int numbetter = 0;      //ie empty too!
int numbetter_max = 0;  //Indicates potential group overrruns
#ifdef QUEUE_LIB
const int better_list_max = 50;
#endif /*QUEUE_LIB*/

#ifdef DEBUG
cout<<(best? "BEST " : "WORSE")<<endl;
{for (int i = 0; i<listsize; i++) {
	cout<<i<<" "<<flush;
//\\        list[i]->write_trace(); fix some tiem
	cout<<endl;
}
}
#endif

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

for (int i = 0; i<listsize; i++)
{
int old_j = -1;
for (int j = listhead; j >= 0; j = better[j])
{
#ifndef QUEUE_LIB
	if ( (!best) && (Elitist !=0) &&
	     ptrmyfitnessvalue(list[i]->nfitness)->unique_best()) { 
		goto discard_list_element; } //remove i from consideration

	if (list[i]==list[j]) { nchrome[j]++;
		goto discard_list_element; } //remove i from consideration
#endif /*QUEUE_LIB*/

	int d = ptrmyfitnessvalue(list[i]->nfitness)->dominates(
                ptrmyfitnessvalue(list[j]->nfitness)           );
#ifdef DEBUG
//	cout<<" ans("<<i<<","<<j<<")="<<d<<flush;
#endif
#ifndef QUEUE_LIB
	if (d==IDENTICAL) { same[j]++;
		goto discard_list_element; } //remove i from consideration
#endif /*QUEUE_LIB*/
	if (!best) d = -d;
	if ( d > 0 )
	{//remove j from candidates
		if ( old_j >= 0 ) better[old_j] = better[j];
		else              listhead      = better[j];
	        numbetter--;
	        numbetter_max--;
	}
        else if ( d < 0 )
	{//remove i from consideration
		goto discard_list_element;
	}
	else
	{
		old_j = j;
        }
};//end scan better

#ifdef QUEUE_LIB
if (numbetter<=better_list_max)
#else
if (numbetter<=listsize)
#endif /*QUEUE_LIB*/
	{
		better[i] = listhead; //add i to candidates
		nchrome[i]= 1;
		same[i]   = 1;
		listhead  = i;
		numbetter++;
        }
numbetter_max++;

discard_list_element: ;
};//end scan list

if (numbetter<numbetter_max)
	{
#ifdef QUEUE_LIB
	cout<< "select_hits reduced parento group to " << better_list_max;
#else
	cout<< "select_hits reduced parento group to " << listsize;
#endif
	cout<< " (upper limit not more than) " << numbetter_max << endl;
        }

#ifdef DEBUG
cout<<" final list: size " << numbetter <<" "<<flush;
{int j = 0;
for (i = listhead; (j<numbetter); j++, i = better[i]) {
        cout<<i<<" nchrome "<<nchrome[i]<<" same "<<same[i]<<". "<<flush;}}
#endif

if (select != NULL && select_size != NULL && num_duplicates != NULL ){
//gather display info for gp.cc
	int j = 0;
        for (i = listhead; (j<numbetter)&&(j<*select_size); j++, i=better[i]) {
		select[j] = i;
		num_duplicates[j] = same[i];
	}
        *select_size = j;
}
else { //actual in pop selection
       {BOOL identical_chrome = FALSE;
	BOOL identical_scores = FALSE;

        for (i = listhead; i >= 0; i = better[i]) {
		if(nchrome[i]>1){
			identical_chrome = TRUE;
			sum_select_hits_identical_chrome+= nchrome[i]; }
		if(same[i]   >1) {
			identical_scores = TRUE;
			sum_select_hits_identical_scores+= same[i]; }
	}
        select_hits_called++;
	if(identical_chrome)
                select_hits_identical_chrome++;
	if (identical_scores)
                select_hits_identical_scores++;
        if (numbetter > 1) {
                select_hits_nondominated_scores++;
                sum_select_hits_nondominated_scores     += numbetter; }
}

#ifndef QUEUE_LIB
       //if more than one choice left; chose least/most popular in population
	if (numbetter > 1) {
		select_by_niche( best, target, list, listsize, better, 
				 listhead, numbetter );
	}
#endif /*QUEUE_LIB*/

        if (numbetter > 1) {
                select_hits_pop_nondominated++;
                sum_select_hits_pop_nondominated        += numbetter; }

	int chosen = rnd (numbetter);
        for (i = listhead; chosen > 0; i = better[i]) chosen--;

#ifdef DEBUG
        select_hits_write_stats();
        cout<<" select_hits: chosing " << i<<" "<<flush;
//\\        list[i]->write_trace(); fix const cometime
#endif

        *bestinlist = i;
}

#ifdef DEBUG
cout<<endl;
#endif

delete[] nchrome;
delete[] same;
delete[] better;

return list[i];

}//end select_hits;


#ifdef QUEUE_LIB
Chrome* queue::Bestof(const PtrChrome  list[], const int listsize,
#else
Chrome* gp::Bestof(const PtrChrome  list[], const int listsize,
#endif
	           int* bestinlist, const int target )
{
if ( bestinlist == NULL ) {int dummy; bestinlist = &dummy;}//discard

return select_hits (list, listsize, target, bestinlist);
}//end Bestof


#ifdef QUEUE_LIB
Chrome* queue::Worstof(const PtrChrome list[], const int listsize,
#else
Chrome* gp::Worstof(const PtrChrome list[], const int listsize,
#endif
	            const int timenow, int* worstinlist, const int target)
{
// Will select a target that is too old, even if more fit.

const int MaxAge = list[0]->params->params[pMaxAge];

if(MaxAge!=0) {
for (int i=0; i<listsize; i++)
{
	if ((timenow - list[i]->birth) > MaxAge)
	     {	*worstinlist = i;
	        return list[i];
	     }
}}


//return select_hits (list, listsize, target, worstinlist, FALSE );

Chrome* c = select_hits (list, listsize, target, worstinlist, FALSE );

#ifndef QUEUE_LIB
if (ptrmyfitnessvalue(c->nfitness)->unique_best()) {
	cout<<"Worstof selected unique_best, from "<<endl;
        for (int i=0; i<listsize; i++) {
		if(c==list[i])
			cout<<"=> "; 
		else
			cout<<"   ";
		if(ptrmyfitnessvalue(c->nfitness)->unique_best())
			cout<<"U ";
		else
			cout<<"ok";
		list[i]->nfitness->write();
		cout<<endl;
	     }
}
#endif /*QUEUE_LIB*/
return c;

}//end Worstof