pareto.cc

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

// pareto.cc     File to perform pareto selection, build with GPQUICK-2.1
// W. Langdon cs.ucl.ac.uk 24 August 1994

//$Revision: 1.47 $

//Modifications (in reverse order)

//#define DEBUG

//WBL 31 Mar 97  restore QUEUE_LIB functionality
//               Make compatible with DEC ALPHA C

//WBL 13 Jun 96  Go back to S.Wales size problem

//WBL 22 May 96  Improve processing of schedule_counts when week=0

//WBL 18 May 96  Add schedule_counts

//WBL 10 Dec 95  Use only clear_rank to initialise data

//WBL 22 Sep 95  Replace list.h by prob.h
//               Various tweaks to cope with reduced pareto size
//               Make pareto_fitness take 2 args rather than one

//WBL 29 Aug 1995 BUGFIX 28-aug (remove -1s) cf gp.cc

//WBL 28 Aug 1995 Report num of items left in tournament group at each stage

//WBL 30 Apr 1995 Replace elite chain in myfitnessvalue with elite counts

//WBL 26 Apr 1995 Make elite chain a double chain

//WBL 19 Apr 1995 Make find_elite set count and best even if exceed listsize

//WBL  7 Apr 1995 To save diskspace comment out message on deleting elite

//WBL 14 Mar 1995 Add find_elite

//WBL 14 Mar 1995 Various efficiency improvemnts
//                Add pElitist etc

//WBL 12 Mar 1995 Replace constants (81,1) by pTournComp and pNicheSize

//WBL 26 Feb 1995 Add select_hits_by_niche etc

//WBL 25 Feb 1995 In select_hits, replace better_list_max by listsize

//WBL 18 Feb 1995 Add identical chromes and other other reporting data

//WBL 18 Feb 1995 Add reporting of identical scores. Fixit

//WBL 16 Feb 1995 Allow floating point scores

//WBL 13 Feb 1995 Dispite comments odes NOT retain identical scores.
//                On best identical are discarded as worse; on !best they are
//                treated as better and so displace originals from list.

//WBL 12 Feb 1995 Ok so now get it working again!

//WBL 23 Jan 1995 Start makeing problem independant
//                add gp.h, Primitives
//                HACK to make compile

//WBL 29 Nov 1994 Make compatible with boom gcc

//WBL 26 Nov 1994 In select_hits dont set bestinlist if select and numselect
//                arguments are give. NB avoids call to rnd

//WBL 25 Nov 1994 Add select and numselect arguments to select_hits

//WBL 13 Sep 1994 Make compilable by solaris gcc

//WBL  9 Sep 1994 Implement pMaxAge in Worstof

//WBL 7A Sep 1994 Dont discard identicals

//WBL 29 Aug 1994 Select on memory, but not on makenull or enqueue.
//                Expand top list to 50. 

//WBL 27 Aug 1994 Add discarding identicals. Scan whole list but keep only
//                top 10, rather than scanning only 1st ten.

//requires MULTREE to be defined

#include <assert.h>
#include <limits.h>

#include "pch.h"
#include "chrome.h"
#include "prob.h"
#ifdef QUEUE_LIB
#include "queue2.h"
#else
#include "Primitives.h"
#include "gp.h"
#endif /*QUEUE_LIB*/
#ifdef GRID_LIB
#define NW 54
//actual values (ie no +1)
#define NL_ 42
#endif

#ifndef QUEUE_LIB
extern Pop* ThisPop;
#endif

//**************************************************************************
int select_hits_called              = 0;
int select_hits_pop_comparisons     = 0;
int select_hits_identical_chrome    = 0;
int select_hits_identical_scores    = 0;
int select_hits_nondominated_scores = 0;
int select_hits_pop_nondominated    = 0;
int sum_select_hits_identical_chrome    = 0;
int sum_select_hits_identical_scores    = 0;
int sum_select_hits_nondominated_scores = 0;
int sum_select_hits_pop_nondominated    = 0;
int select_hits_pop_niche    = 0;
int select_hits_pop_nichesqr = 0;

void select_hits_write_stats(ostream& fout)
{
	fout<<select_hits_called<<" "
	    <<select_hits_identical_chrome<<" "
	    <<select_hits_identical_scores<<" "
	    <<select_hits_nondominated_scores<<" "
	    <<select_hits_pop_nondominated<<" "
            <<select_hits_pop_comparisons<<" "
	    <<sum_select_hits_identical_chrome<<" "
	    <<sum_select_hits_identical_scores<<" "
	    <<sum_select_hits_nondominated_scores<<" "
	    <<sum_select_hits_pop_nondominated<<" "
	    <<select_hits_pop_niche<<" "
	    <<select_hits_pop_nichesqr<<flush;
}

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

BOOL myfitnessvalue::IsBetter(FitnessValue* fv)
{
if( this->dominates(ptrmyfitnessvalue(fv)) >0 ) return TRUE;
                                                return FALSE;
}//end myfitnessvalue::IsBetter

#define MIN_SCORE INT_MIN

#ifndef QUEUE_LIB
scoretype best_hits [num_ellite_pareto];
int best_counts [num_ellite_pareto];
#endif /*QUEUE_LIB*/

#ifdef GRID_LIB
int schedule_counts[NW][NL_];

scoretype rare_schedule(const char schedule[NL_]) {
for (int l=0;l<NL_;l++) {if(schedule[l]>0 && schedule_counts[schedule[l]][l] < 100) return 1;}
return 0;
}

void display_schedule_counts(ostream& fout)
{
fout<<"schedule_counts\n";
for(int w=0;w<NW;w++) {
	fout<<w<<" ";
	for (int l=0;l<NL_;l++) fout<<schedule_counts[w][l]<<"\t";
	fout<<endl;
}
}

scoretype pareto_fitness(const ptrmyfitnessvalue x,const int i)
{
return (i<(NUM_OPERATIONS+NUM_OTHERS))? 
	(x->hits[i]) : rare_schedule(x->schedule);
}
#endif

#ifdef QUEUE_LIB
scoretype pareto_fitness(const ptrmyfitnessvalue x,const int i)
{
switch (i) {
  case 0: return x->hits[front];
  case 1: return x->hits[dequeue];
  case 2: return x->hits[empty];
  case 3: return (x->mem_used  <=  mem_penalty_bot)? 0: -x->mem_used;
  default:
          assert(0==1);
}//end switch
}
#else /*QUEUE_LIB*/

void clear_rank()
{
for (int i = 0; i<num_ellite_pareto ;i++) {
	best_hits[i] = MIN_SCORE;
	best_counts[i] = 0;
}
#ifdef GRID_LIB
memset(schedule_counts,0,sizeof(schedule_counts));
#endif

}//end clear_rank

void find_elite(Chrome* list[], const int listsize, int& output_size,
		scoretype best[num_ellite_pareto],int count[num_ellite_pareto])
{
output_size = 0;
memset(count,0,sizeof(int)*num_ellite_pareto);
for(UINT j=0;j<ThisPop->popsize;j++) {
	const ptrmyfitnessvalue p=ptrmyfitnessvalue(ThisPop->pop[j]->nfitness);
	BOOL placed_in_list = FALSE;
	for (int i = 0; i<num_ellite_pareto ;i++) {
//cout<<i<<" "<<p<<" "<<a[i]<<" "<<p->ptr_chrome<<" "<<endl;
                if(pareto_fitness(p,i)==best_hits[i]) {
			count[i]++;
			best[i] = pareto_fitness(p,i); 
			if ((!placed_in_list)&&(output_size<listsize)) {
				list[output_size++] = ThisPop->pop[j];
				placed_in_list = TRUE;
			}
		}//end if elite
	}//end for each pareto
}//scan whole population

for (int i = 0; i<num_ellite_pareto ;i++) {
if(best_counts[i] != count[i])
cout<<"find_elite: best_count["<<i<<"] != count["<<i<<"] "
    <<best_counts[i]<<" != "<<count[i]<<endl;
}//end sanity check

}//end find_elite


//void myfitnessvalue::unchain() 
//{
//cout<<"Uncahining "<<this<<endl;//debug
//
////should go looking for it but overhead is huge 
////assume will either be first thing in chain or not at all
//
//for (int i = 0; i<num_ellite_pareto;i++) {
//	if(best_head[i]==this) best_head[i] = chain[i];
//}//end for
//
//}//end unchain


myfitnessvalue::~myfitnessvalue() 
{
if(ThisPop != NULL && ThisPop->params->params[pElitist] != 0) {

//cout<<"Deleting myfitness "<<this<<flush;//debug
#ifdef GRID_LIB
{for (int l = 0; l<NL_;l++) --schedule_counts[schedule[l]][l];}
#endif
BOOL deleted_unique = FALSE;
BOOL update_required[num_ellite_pareto];
for (int i = 0; i<num_ellite_pareto;i++) {
	update_required[i] = FALSE;
        if(pareto_fitness(this,i)==best_hits[i]) {
//cout<<" Op "<<i<<" "<<a[i]<<flush;
                best_counts[i]--;
                if(best_counts[i] == 0) {
			deleted_unique = TRUE;
			update_required[i] = TRUE;
		}
        }
}

if(deleted_unique) { //now empty
//			cout<<" Deleting unique best, operation = "<<i
//			    <<" score = "<<a[i]<<flush;
//			    <<" scaning whole population"<<endl;
//Now go looking for new best(s) but overhead is huge 
	for(UINT j=0;j<ThisPop->popsize;j++) {
		for (int i = 0; i<num_ellite_pareto;i++) {
			if(update_required[i]) {
			best_hits[i] = MIN_SCORE;
			const ptrmyfitnessvalue p = ptrmyfitnessvalue(
						   ThisPop->pop[j]->nfitness);
			if(p != this) {//dont add ourselves backagain!
			if(pareto_fitness(p,i)>=best_hits[i]) {
				if(pareto_fitness(p,i) > best_hits[i]) {
					best_counts[i] = 0; //delete rest
					best_hits[i] = 
					    pareto_fitness(p,i); //update best
					}
				best_counts[i]++;
			}//end insert 
			}//end not object being deleted
			cout<<" new best "<<best_hits[i]<<endl;
			}//endif update_required
		}//endfor each pareto
        }//end scan whole pop
}//endif deleted unique best
//cout<<"End Deleting myfitness\n";//debug
}//endif pElite
}//end ~myfitnessvalue


void myfitnessvalue::update_rank() 
{
#ifdef GRID_LIB
{for (int l = 0; l<NL_;l++) ++schedule_counts[schedule[l]][l];}
#endif
for (int i = 0; i<num_ellite_pareto;i++) {
//if(i==0){
//cout<<this<<" Best_head "<<best_head[i]<<" Best_hits "<<best_hits[i]
//<<" chain "<<chain[i]<<" hits "<<a[i]<<endl;
//}
	if(pareto_fitness(this,i)>=best_hits[i]) {
		if(pareto_fitness(this,i) > best_hits[i]) {
			best_counts[i] = 0;  //delete rest
			best_hits[i] = pareto_fitness(this,i); //update best
		}
		//We should check has not already been added to chain.
		//This _used to happen because chrome copied old chromes rather
		//than create new ones from scratch.

		best_counts[i]++;
	}//end insert at begining of chain
//if(i==0){
//cout<<this<<"    _head "<<best_head[i]<<" Best_hits "<<best_hits[i]
//<<" chain "<<chain[i]<<" hits "<<a[i]<<endl;
//}
}//end for

}//end myfitnessvalue::update_rank


BOOL myfitnessvalue::unique_best() const
{
for (int i = 0; i<num_ellite_pareto;i++) {
	if((pareto_fitness(this,i) == best_hits[i]) &&
	   (best_counts[i] == 1) )
		return TRUE; //ie is only thing in best[i] chain
}
return FALSE;

}//end myfitnessvalue::unique_best

#endif /*QUEUE_LIB*/

//**************************************************************************
#define IDENTICAL -2

inline 
int myfitnessvalue::dominates(myfitnessvalue* target)
{
#ifdef DEBUG
//cout<<"dominates this="; write();cout<<"\tover? "; target->write();
#endif

BOOL dom = IDENTICAL;

for (int i = 0; i<num_pareto_components; i++)
{
	if      (pareto_fitness(this,i) > pareto_fitness(target,i))
	      { if (dom == -1) return 0;
		else dom = 1;
	      }
	else if (pareto_fitness(this,i) < pareto_fitness(target,i))
	      { if (dom == 1) return 0;
		else dom = -1;
	      }
};//end loop

return dom;

}//end myfitnessvalue::dominates;

#ifndef QUEUE_LIB
Chrome* any() {
#ifdef DEBUG
	int x = rnd(ThisPop->popsize);
//	cout<<" any compare with? "<<x<<flush;
	return ThisPop->pop[x];
#else
	return ThisPop->pop[rnd(ThisPop->popsize)];
#endif
} //end any //chrome in pop


enum {east,west,north,south};
int  radius_of_spiral, spiral_index, spiral_edge;

void setup_spiral() { //always use square demes for comparison
radius_of_spiral=0;
}//end setup_spiral

Chrome* spiral(const int offset) {
int x;
int pw = ThisPop->params->params[pPopWidth];
if (pw==0) {pw = 1;}

if(radius_of_spiral==0) {
	x = 0;
	radius_of_spiral = 1;