// chrome.cxx version to support stack.cc, from GPQUICK-2.1 // W.Langdon cs.ucl.ac.uk $Revision: 1.7 $ //Modifications (reverse order): // WBL 15 Oct 1994 Make chrome::Load() work with MULTREE // NB I have not implemented constants // WBL 14 Oct 1994 Call static_check when creating entirely new chrome // WBL 13 Sep 1994 Make compilable by solaris gcc // WBL 9 Sep 1994 UNDO part of 17 Aug 1994: ``InsertMember nolonger // places worse child into pop'' // WBL 8 Sep 1994 Make crosstree call static_check // WBL 25 Aug 1994 Make funcbag and array, add funcbagcount. // Replace getfuncbag by addtofuncbag // WBL 24 Aug 1994 Add Problem::Bestof and Worstof and use it in place // of IsBetter tournaments. Add Pop::select_candidates // WBL 23 Aug 1994 Remove copying hits and write_hits() (to problem // specific file). Replace call of write_hits by // write(nfitness*). Use this inplace of fout< //for DisplayStats #include #include "pch.h" #include "chrome.h" #include "suit.h" SUIT_object progdisp1,progdisp2,progdisp3,progdisp4,progdisp5,progdisp6; // Global variables char scratch[100]; extern boolean displayrect, displaytext, showeval; int gpquick_seed = 1; #ifdef FASTEVAL // Global evaluation variables. Eliminates parameter passing // If you can get IpGlobal into a register, you will run near the speed // limit for S-expression evaluation Chrome * ChromeGlobal; // currently evaluating Chrome evalnode ExprGlobal[EXPRLEN]; // expression expanded to evalnodes evalnode * IpGlobal; // Current instruction pointer #ifdef FASTEVAL evalnode* fast_tree_starts [NUM_TREES]; // start of each tree //#ifdef INTERFACE int my_fast_tree_starts[NUM_TREES]; //#endif #endif #endif //************************************************************************** //////////////////////////////////// Utility functions int min(int value1, int value2) { return ( (value1 < value2) ? value1 : value2); }; int max(int value1, int value2) { return ( (value1 > value2) ? value1 : value2); }; // Comment out if included in your implementation (e.g. Borland) // upper case string char* strupr(char* s) { int i=0; while (s[i]) if (s[i]>='a' && s[i]<='z') s[i]=s[i]-32; i++; return s; } // compare strings without case sensitivity int strcmpi(char* s1, char* s2) // only checks equality { int mismatch=0; while (*s1 && *s2 && !mismatch) { if (*s1>='a' && *s1<='z' && *s2<='Z') mismatch = *s1-32 != *s2; else if (*s1>='A' && *s1<='Z' && *s2>='a') mismatch = *s1+32 !=*s2; else mismatch = *s1!=*s2; s1++;s2++; } return mismatch || *s1 || *s2; } //************************************************************************** //////////////Function member function (separated for use in a DLL) char* Function::getprint(Chrome* chrome) { // NUMBER has its own getprint to write the correct number // This is fancy footwork for other functions with operands // these are written as _ if (varnum) sprintf(scratch,"%s_%-d",name,VARNUM(chrome->expr[chrome->ip])); return (varnum? scratch : name); } //************************************************************************** /// Chrome functions /////////////////////////////////////////// Chrome::Chrome(ChromeParams* p,Problem* pr,Function** f,retval* c,BOOL doinit) { // initialize a expr using the functions in array f //cout << "Chrome::Chrome\n"; int depth = p->params[pInitExpr]; // funcbag=cf; params = p; probl = pr; funclist = f; constlist = c; MaxExpr=params->params[pMaxExpr]; ExprBytes=MaxExpr*sizeof(node); expr=new node[MaxExpr]; ip=0; ep=0; funccount = params->funccount; // how many primitives? birth = 0; nfitness = probl->GetFitnessObj(); // allocates a FitnessValue object; GetFitnessObj calls new if (doinit) { #ifdef MULTREE for (int t = 0; t < NUM_TREES; t++ ){ tree_starts[t] = ip; do { ip = tree_starts[t]; //discard earlier attempt at tree #endif // DO "ramped half and half from 2 to depth" if (depth > 0) { SubInit(probl->funcbag[t],1,rnd(depth-1)+1,rnd(2), TRUE); // go to some depth less than max, full or half full } else SETNODE(expr[ip],0,0); // stick in a stub constant #ifdef MULTREE }while (probl->static_check(this,t)>rnd(100)); }//end for each tree #endif } } Chrome* Chrome::Copy() { Chrome* nw=new Chrome(params,probl,funclist,constlist,FALSE); nw->Dup(this); return nw; } void Chrome::Dup(Chrome* source) // make a copy nondestructively { #ifdef TRACE source->num_children++; mum.birth = source->birth; #endif #ifdef MULTREE memcpy (tree_starts, source->tree_starts, sizeof(tree_starts)); #endif // funcbag=source->funcbag; params=source->params; funclist=source->funclist; funccount=source->funccount; constlist=source->constlist; memcpy(expr,source->expr,ExprBytes); nfitness->Copy(source->nfitness); ip=0; } #ifdef MULTREE retval Chrome::evalAll(int tree) // eval the whole expression anew #else retval Chrome::evalAll() // eval the whole expression anew #endif { #ifndef FASTEVAL #ifdef MULTREE ip= tree_starts[tree]-1; #else ip=-1; #endif return eval(); #else #ifdef MULTREE IP=fast_tree_starts[tree]; #ifdef INTERFACE ep = my_fast_tree_starts[tree]; #endif #else IP=ExprGlobal; #endif //cout<<"FUNC="<< IP->op; return (IP->ef)(); #endif } void Chrome::SetupEval() { #ifdef FASTEVAL // expand stack into evalnodes in global eval stack int args; node* spp=expr; evalnode* ip=ExprGlobal; #ifdef MULTREE for (int t = 0; t < NUM_TREES; t++ ){ fast_tree_starts[t] = ip; #endif args=1; while (args > 0) { SETEVALNODE(ip,spp->op,spp->idx); args=args+PARGNUM(spp)-1; ip++; spp++; } // set global eval pointers #ifdef MULTREE }//end for each tree #endif ChromeGlobal=this; #endif } //D.Raithatha #ifdef INTERFACE double Chrome::zoomtext(double scale_factor) { if (scale_factor < 0.1) { return 36.0; } else if (scale_factor < 0.5) {return 24;} else if (scale_factor < 1.0) {return 6.0;} return 0.0; } void Chrome::tree_display(int whichtree) { SUIT_viewport temp_vp1; /* The active Viewport */ rectangle recvView; /* The rectangle used to define the */ /* drawing area */ double offset_h = 0.0; double offset_v = 0.0; double scaling_factor = 1.0; double wxmin,wxmax,wymin,wymax; double fontsize; GP_pushGraphicsState(); for (int t = 0; tGetTreeName(t)); break; case 1: temp_vp1 = SUIT_getViewport(progdisp2, VIEWPORT); offset_h = SUIT_getDouble(SUIT_getChild(progdisp2,0), CURRENT_VALUE); offset_v = SUIT_getDouble(SUIT_getChild(progdisp2,1),CURRENT_VALUE); scaling_factor = atof(SUIT_getText(SUIT_getChild(progdisp2,5),LABEL)); SUIT_setText(SUIT_getChild(progdisp2,2),LABEL,probl->GetTreeName(t)); break; case 2: temp_vp1 = SUIT_getViewport(progdisp3, VIEWPORT); offset_h = SUIT_getDouble(SUIT_getChild(progdisp3,0),CURRENT_VALUE); offset_v = SUIT_getDouble(SUIT_getChild(progdisp3,1),CURRENT_VALUE); scaling_factor = atof(SUIT_getText(SUIT_getChild(progdisp3,5),LABEL)); SUIT_setText(SUIT_getChild(progdisp3,2),LABEL,probl->GetTreeName(t)); break; case 3: temp_vp1 = SUIT_getViewport(progdisp4, VIEWPORT); offset_h = SUIT_getDouble(SUIT_getChild(progdisp4,0),CURRENT_VALUE); offset_v = SUIT_getDouble(SUIT_getChild(progdisp4,1),CURRENT_VALUE); scaling_factor = atof(SUIT_getText(SUIT_getChild(progdisp4,5),LABEL)); SUIT_setText(SUIT_getChild(progdisp4,2),LABEL,probl->GetTreeName(t)); break; case 4: temp_vp1 = SUIT_getViewport(progdisp5, VIEWPORT); offset_h = SUIT_getDouble(SUIT_getChild(progdisp5,0),CURRENT_VALUE); offset_v = SUIT_getDouble(SUIT_getChild(progdisp5,1),CURRENT_VALUE); scaling_factor = atof(SUIT_getText(SUIT_getChild(progdisp5,5),LABEL)); SUIT_setText(SUIT_getChild(progdisp5,2),LABEL,probl->GetTreeName(t)); break; case 5: temp_vp1 = SUIT_getViewport(progdisp6, VIEWPORT); offset_h = SUIT_getDouble(SUIT_getChild(progdisp6,0),CURRENT_VALUE); offset_v = SUIT_getDouble(SUIT_getChild(progdisp6,1),CURRENT_VALUE); scaling_factor = atof(SUIT_getText(SUIT_getChild(progdisp6,5),LABEL)); SUIT_setText(SUIT_getChild(progdisp6,2),LABEL,probl->GetTreeName(t)); break; default: break; } recvView.bottom_left.x = temp_vp1.bottom_left.x ; recvView.bottom_left.y = temp_vp1.bottom_left.y +25; recvView.top_right.x = temp_vp1.top_right.x -25 ; recvView.top_right.y = temp_vp1.top_right.y - 2; GP_setViewport(recvView); GP_setClipRectangle(recvView); scaling_factor = scaling_factor/100.0; wxmin = 0.0 + offset_h; wxmax = 2.0 + offset_h; wymin = 0.0 + offset_v; wymax = 2.0+offset_v; float centre_of_x = ((wxmin) + (wxmax))/2.0; //find centre of x value float centre_of_y = ((wymin) + (wymax))/2.0; //same for y wxmin = (wxmin - centre_of_x)*scaling_factor + centre_of_x; wxmax = (wxmax - centre_of_x)*scaling_factor + centre_of_x; wymin = (wymin - centre_of_y)*scaling_factor + centre_of_y; wymax = (wymax - centre_of_y)*scaling_factor + centre_of_y; GP_setWindow(GP_defRectangle(wxmin,wymin,wxmax,wymax)); GP_setColor(SUIT_getColor(progdisp1,BACKGROUND_COLOR)); GP_fillRectangleCoord(wxmin,wymin,wxmax,wymax); GP_setColor(GP_defColor("black",TRUE)); ip = tree_starts[t] - 1; depth = 0; fontsize = zoomtext(scaling_factor); if (fontsize != 0.0) GP_setFont(GP_defFont("courier","bold",fontsize)); double *bluff; if (fontsize != 0.0) bluff = suitsubwrite(0.0,1.95,1); else bluff = subtree_display(0.0,1.95,0); } } //draw tree recursively GP_popGraphicsState(); } double* Chrome::subtree_display(double minx,double ymax,int isfont) { int args, i; ep++; // cout << inter_vals[ep] << "ep " << ep << " "; ip++; // cout << "ip value " << inter_vals[ip] << "ip " << ip< 0) { depth++; switch(args) { case 1: ptr2 = subtree_display(minx,(ymax-0.15),isfont); xvals2[minimumx]= *ptr2++; xvals2[recx]= *ptr2; if (displayrect) GP_rectangleCoord((xvals2[recx]- 0.15),(ymax-0.09),(xvals2[recx]),ymax); GP_lineCoord((xvals2[recx]-0.075),(ymax-0.15),(xvals2[recx]-0.075),(ymax-0.09)); help = help+1; *help-- = xvals2[recx]; if (displaytext && (isfont != 0)) GP_justifyTextInRectangle(funclist[FUNCNUM(expr[temptr])]->getprint(this),JUSTIFY_CENTER,GP_defRectangle((xvals2[recx]-0.15),(ymax-0.09),(xvals2[recx]),ymax)); if(showeval) GP_justifyTextInRectangle(sprintf(buffer,"%d",inter_vals[temptr]),JUSTIFY_CENTER,GP_defRectangle((xvals2[recx]-0.15),(ymax-0.09),(xvals2[recx]),ymax)); //cout << " value temp " << inter_vals[temptr] <<" actual temp " << temptr << endl; // cout << temptr; // if (temptr > 255) // { // cout << "ERRORgetprint(this),JUSTIFY_CENTER,GP_defRectangle(x1,(ymax-0.09),(x1+0.15),ymax)); if(showeval) GP_justifyTextInRectangle(sprintf(buffer,"%d",inter_vals[temptr]),JUSTIFY_CENTER,GP_defRectangle(x1,(ymax-0.09),(x1+0.15),ymax)); //cout << " value temp " << inter_vals[temptr] <<" actual temp" << temptr << endl; //cout << temptr; //if (temptr > 255) //cout << "ERROR< ERROR"; break; default: break; } } else { if (displayrect) GP_rectangleCoord(minx,(ymax - 0.09),(minx+0.15),ymax); if (displaytext && (isfont != 0)) GP_justifyTextInRectangle(funclist[FUNCNUM(expr[ip])]->getprint(this),JUSTIFY_CENTER,GP_defRectangle(minx,(ymax-0.09),(minx+0.15),ymax)); if(showeval) GP_justifyTextInRectangle(sprintf(buffer,"%d",inter_vals[ip]),JUSTIFY_CENTER,GP_defRectangle(minx,(ymax-0.09),(minx+0.15),ymax)); //cout << " actualterminal ip" << ip << " value " << inter_vals[ip] << endl; help = help + 1; *help-- = minx+0.15; minx = minx+0.16; *help = minx; return help; } minx = xvals2[minimumx]; *help = minx; return help; } #endif void Chrome::SubInit(CSelector* funcbag, int argstogo,int depth,int isfull, BOOL isstart) // Initialize a subtree half full { //cout <<"SubInit( " << argstogo << ", " << depth << ", " << isfull << //", " << isstart << " )\n"; int i; int maxargs,thisargs; maxargs = MaxExpr -(ip+argstogo); // max number of args to add assert(maxargs>=0); //can sometimes trip this WBL //cout <<"SubInit Calling roulette() 1\n"; i=funcbag->roulette(); //cout <<"SubInit roulette() 1, returned "<argnum>0) i=funcbag->roulette(); // node required else if (isfull || isstart) //support for MULTREE if (maxargs > 5) while (funclist[i]->argnum == 0) i=funcbag->roulette(); else // not enough room. // Take what you can get. // NB may cause prog to loop WBL // Hence added assert 25/8/94WBL while (funclist[i]->argnum>maxargs) i=funcbag->roulette(); // terminal allowed 50% of the time else if (rnd(2)) // terminal required while (funclist[i]->argnum>0) i=funcbag->roulette(); else // node required if (maxargs > 5) while (funclist[i]->argnum == 0) i=funcbag->roulette(); else // not enough room. Take what you can get. while (funclist[i]->argnum>maxargs) i=funcbag->roulette(); if (funclist[i]->varnum == 0) {SETNODE(expr[ip],i,0);} //WBL bug fix 001 12-May-94 else {SETNODE(expr[ip],i,rnd(funclist[i]->varnum));} ip++; thisargs=funclist[i]->argnum; argstogo += funclist[i]->argnum-1; for (i=0;i 0) { args=args+ARGNUM()-1; ip++; } } #ifdef INTERFACE retval Chrome::evalwithstore() { int temp_p = ep++; // ep = ep + 1; inter_vals[temp_p] = ((++IP)->ef)(); // cout << inter_vals[temp_p]; // cout << value; // return value; return inter_vals[temp_p]; } #endif void Chrome::TraverseGlobal() { // skip the next expression int args = 1; while (args > 0) { args=args+PARGNUM(IP)-1; IP++; } } // Write the next subexpression to a stream // pretty flag controls parentheses, indenting // PRETTY_NONE = no indenting, just a stream, with parens // PRETTY_NOPARENS = indented, one function per line, no parens // PRETTY_PARENS = indented, one function per line, parens void Chrome::SubWrite(ostream& ostr,int pretty) { int args,i; ip++; args = ARGNUM(); if (pretty) // indent? { ostr<< '\r' << '\n'; for (i=0;i0) { // write (FUNC args) if (pretty != PRETTY_NOPARENS) ostr << '('; ostr << funclist[FUNCNUM(expr[ip])]->getprint(this); depth++; while (args-- > 0) SubWrite(ostr,pretty); depth--; if (pretty != PRETTY_NOPARENS) ostr << ")"; } else { // write an atom ostr << funclist[FUNCNUM(expr[ip])]->getprint(this); } } #ifdef MULTREE Chrome* Chrome::CrossTree(Chrome* mate, int tree ) //work on one tree only #else Chrome* Chrome::CrossTree(Chrome* mate) #endif // Return a new Chrome that is a cross with mate { //debug//cout<<"\nSTART CrossTree, this="; //this->write(PRETTY_NONE,cout); //cout<<"\nCrossTree, mate="; //mate->write(PRETTY_NONE,cout); Chrome* newexpr = Copy(); #ifdef TRACE mate->num_children++; //this incremented by Copy() #endif int thislen; // total length of expression int thissubptr; // pointer to subexpression int thissublen; int matelen; int matesubptr; int matesublen; #ifdef MULTREE thislen=tree_starts[NUM_TREES-1] + SubLen(tree_starts[NUM_TREES-1]); matelen=mate->tree_starts[NUM_TREES-1] + mate->SubLen(mate->tree_starts[NUM_TREES-1]); #else thislen=SubLen(0); matelen=mate->SubLen(0); #endif do { if (rnd(101)>params->params[pUnRestrictWt]) { #ifdef MULTREE thissubptr=GetIntNode(tree); matesubptr=mate->GetIntNode(tree); #else thissubptr=GetIntNode(); matesubptr=mate->GetIntNode(); #endif } else { #ifdef MULTREE thissubptr=GetAnyNode(tree); matesubptr=mate->GetAnyNode(tree); #else thissubptr=GetAnyNode(); matesubptr=mate->GetAnyNode(); #endif } thissublen = SubLen(thissubptr); matesublen=mate->SubLen(matesubptr); //cout<<"\ntree="<write (fout); fout << " len " << tree_starts[NUM_TREES-1] + SubLen(tree_starts[NUM_TREES-1]); fout << " children " << num_children; if ( mum.birth >= 0 ) { fout << "\tmum=" << mum.birth; fout << "x" << mum.xpoint; } if ( dad.birth >= 0 ) { fout << ",dad=" << dad.birth; fout << "x" << dad.xpoint << ","; } #ifdef MULTREE if ( mum.birth >= 0 && mum.xtree >= 0 ) probl->WriteTreeName(mum.xtree); #endif }//end Chrome::write_trace() #endif TRACE #define EATSPACE c=istr.peek();while(isspace(c)||c==':') {istr.get();c=istr.peek();} #define GETTOK tp=0;c=istr.peek();while(c!=EOF && !isspace(c) && c!=':' && c!='(' && c!=')' &&tp<79) {scratch[tp++]=istr.get(); c=istr.peek();} scratch[tp]='\0' int Chrome::Load(istream& istr,int issource) // Load an expression from a stream // issource should always be TRUE { int x,tempop, tempidx; int rval=LOAD_OK; node* buf; //Get a new clean FitnessValue object delete nfitness; nfitness = probl->GetFitnessObj(); birth = 0; if (!issource) { for(x=0;x> tempop; //cout << tempop<<"hello"; expr[x].op =(unsigned) tempop; istr >> tempidx; expr[x].idx=(unsigned) tempidx; } } else // load a Source file { ip=0; buf=new node[MaxExpr]; #ifdef MULTREE char c; int tp; rval = LOAD_OK; for (int t = 0; t < NUM_TREES && rval == LOAD_OK; t++ ){ tree_starts[t] = ip; EATSPACE; GETTOK; int temp = probl->TreeNameMatch(t,scratch); //cout <=MaxExpr) { rval=LOAD_TOOLONG; } else if (istr.peek()=='(') // Get an expression and the close paren { istr >> c; rval = SubLoad(istr,buf); if (rval==LOAD_OK) { EATSPACE; istr >> c; if (c!=')') rval=LOAD_TOOMANY; } } else // Get an expression. Return if you hit a close paren. { GETTOK; if (strlen(scratch)==0) rval=LOAD_TOOFEW; else { //DIRTY FRIG - I DONT USE CONSTANTS (EXCEPT 0 and 1) // if (isdigit(scratch[0]) || scratch[0]=='-') // it's a number. Function 0 // { // func=atoi(scratch); // if (func>=0-CONSTARRAYSIZE/2 && func_operand s=strrchr(scratch,'_'); if (strchr("0123456789",s[1])) // it is an underscore followed by numbers { vnum=atoi(s+1); if (vnum>=0 && vnum <= CONSTARRAYSIZE) { s[0]='\0'; // found a valid function with variable number appended. Keep function name. } else vnum=0; } } func=FindFunc(scratch); if (func<0) rval=LOAD_BADFUNC; else { SETNODE(buf[ip],func,vnum); ip++; rval=LOAD_OK; // get the arguments args=funclist[func]->argnum; while(args>0 && rval==LOAD_OK) { rval=SubLoad(istr,buf); args--; } // if (rval == LOAD_TOOFEW) // ; // restore the token for the error message } } } } return rval; } //************************************************************************** int Chrome::FindFunc(char* funcname) // find a function index by name, or return -1 { int rval=-1; int i; for (i=0;iname)==0) rval=i; return rval; } Chrome::~Chrome() { delete[] expr; delete nfitness; } //************************************************************************** //// Generic Problem Functions ///////////////////////////////////// Problem::Problem() // Set up the tables // You add the primitive functions in your subclass constructor { int i; funclist = new Function*[FUNCARRAYSIZE]; for (i=0;ireset(); } varlist = new retval[CONSTARRAYSIZE]; constlist = new retval[CONSTARRAYSIZE]; funccount = 0; // set up constant table (not implemented) for (i=0;ifvalue=0; // fv has to be deleted by the Chrome Object return fv; } //CSelector* Problem::getfuncbag() // update the function selector and return its pointer //{ // int i; // funcbag->reset(); // for (i=0;iadd(funclist[i]->weight/(2+funclist[i]->argnum),i); // return funcbag; //} void Problem::addtofuncbag(int tree, Function* f ) //NB must be called in correct sequence, ie after AddF has funccount++ { funcbag[tree]->add(f->weight/(2+f->argnum),funccount-1); } float Problem::fitness(Chrome* chrome) // This is just a stub. You must add your own virtual fitness function { cout <<"Problem::fitness (stub)\n";//debug float f=0; // clear variables if required // call the installed fitness function chrome->nfitness->fvalue = f; return f; } Chrome* Problem::Bestof(Chrome* list[], int listsize, int* bestinlist) { //WBL if ( bestinlist == NULL ) {int dummy; bestinlist = &dummy;}//discard *bestinlist = 0; Chrome * best = list[0]; for (int i=1; infitness->IsBetter(best->nfitness)) { *bestinlist = i; best = list[i]; } } return best; }//end Problem::Bestof Chrome* Problem::Worstof(Chrome* list[], int listsize, int timenow, int* worstinlist ) //WBL { // Will select a target that is too old, even if more fit. *worstinlist = 0; for (int i=1; iparams->params[pMaxAge] != 0 && (timenow - list[i]->birth) > list[i]->params->params[pMaxAge]) { *worstinlist = i; break; } if (list[*worstinlist]->nfitness->IsBetter(list[i]->nfitness)) { *worstinlist = i; } } return list[*worstinlist]; ////////////////////////////////////////////////////////////////////// // // Nice Idea, but leads to even more dominance of population by best // WBL 17-Aug-94. Might be marginaly quicker? // if (target == BestMember) // target = winner; //avoid discarding best if can // // else ////////////////////////////////////////////////////////////////////// }//end Problem::Worstof //************************************************************************** //// Pop Functions ///////////////////////////////////////////////// Pop::Pop(Problem* prob,ChromeParams* par,UINT size) // set up a population for a particular problem // Creates new Chromes // evaluates the first Chrome. The rest will be evaluated in the first // Size-1 calls to generate { UINT i; isAborted=FALSE; problem = prob; gencount = 0; start=time(NULL); BestMember=0; BestFitness=NULL; params=par; par->funccount = prob->funccount; if (par->params[pMaxExpr] > EXPRLEN) par->params[pMaxExpr]=EXPRLEN; popsize=size; pop = new Chrome*[size]; for (i=0;iNewChrome(par); //cout << "Created Pop, Now testing pop[0]\n"; // now eval 1 guy initeval=TRUE; nexteval=1; Fitness(pop[0]); InsertMember(0,pop[0],TRUE); #ifdef INTERFACE previous_best = 0.0; previous_mean = 0.0; #endif } float Pop::Fitness(Chrome* chrome) // uses the problem to evalue the fitness of member X // performs setup on the Chrome // updates the BestMember and returns the fitness value { chrome->SetupEval(); return problem->fitness(chrome); } void Pop::InsertMember(int slot,Chrome* NewChrome,int nodelete) // uses the problem to evalue the fitness of member X // performs setup on the Chrome // updates the BestMember and returns the fitness value { UINT endpop; NewChrome->birth=gencount; // if (!nodelete && pop[slot]->nfitness->IsBetter(NewChrome->nfitness) ) // { // // Check NewChrome is not worse than existing //#ifdef TRACE // if ( params->params[pTrace] & pTraceDynamic ) // { cout << endl; // cout << "Discarding new "; // NewChrome->write_trace(); // cout << "\nRather than " << slot; // pop[slot]->write_trace(); // cout << endl; // } //#endif // delete NewChrome; // }//end discard NewChrome (Nb parents credited with child anyway // else { if (!nodelete) { // replace the chrome in this slot #ifdef TRACE if ( params->params[pTrace] & pTraceDynamic ) { cout << endl; cout << "Deleting " << slot; pop[slot]->write_trace(); } #endif delete pop[slot]; pop[slot]=NewChrome; }// end discard old chrome in this slot // Update Best Member if (BestFitness==NULL) { BestMember=slot; BestFitness=NewChrome->nfitness; } else if(NewChrome->nfitness->IsBetter(BestFitness)) { BestMember=slot; BestFitness=NewChrome->nfitness; } else if(slot==BestMember) { endpop = (initeval? nexteval : popsize); //cout<<"Scanning whole pop"<Bestof(pop,endpop,&BestMember); //cout<<" Updating BestFitness"<nfitness; } #ifdef TRACE if ( params->params[pTrace] & pTraceDynamic ) { cout << "\nInserting " << slot << " "; NewChrome->write_trace(cout); NewChrome->write(PRETTY_NONE, cout); cout << endl; } #endif TRACE }//end if add NewChrome to pop } Pop::Pop(Problem* prob,ChromeParams* par) // set up just the core of a population;; let a subclass allocate the members { isAborted=FALSE; problem = prob; gencount = 0; params=par; popsize=0; pop=NULL; BestMember=-1; BestFitness=prob->GetFitnessObj(); // allocates FitnessValue object on heap BestFitness->fvalue=1-MAXFLOAT; } Pop::~Pop() { int i; for (i=0;iparams[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; } offset=popsize+target-dw/2-region*pw/dw/2; for (int i=0; iparams[pTournSize]; // Only tournament selection is implemented in GPQUICK. // Add your own methods to taste if (params->params[pSelectMethod] == ETournament) { Chrome* candidates [ts]; int dummy [ts]; select_candidates(target,ts,candidates,dummy); best = problem->Bestof(candidates,ts); } 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 { int target; // int i,region,ts,offset; int newchrome = FALSE; int prob,wheel; int dowhat; Chrome* best; Chrome* secondbest; Chrome* trial; #ifdef MULTREE if ( tree < 0 ) tree = rnd ( NUM_TREES ); //defualt #endif MULTREE gencount++; if (initeval) // still on initial evaluations? // don't generate. Finish evaluating initial pop. { Fitness(pop[nexteval]); InsertMember(nexteval,pop[nexteval],TRUE); target=nexteval; nexteval++; if (nexteval>=popsize) initeval=FALSE; } else { // 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 (probparams[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 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]); wheel=params->params[pMuteNodeWt]; if (probMutate(); else if (prob<(wheel += params->params[pMuteConstWt])) trial->MutateC(); else trial->MutateShrink(); newchrome = TRUE; break; case doanneal: target=GetAnnealTarget(); trial = pop[target]->Copy(); prob=rnd(params->params[pMuteNodeWt]+params->params[pMuteConstWt]+params->params[pMuteShrinkWt]); wheel=params->params[pMuteNodeWt]; if (probMutate(); else if (prob<(wheel += params->params[pMuteConstWt])) trial->MutateC(); else trial->MutateShrink(); Fitness(trial); // test whether mutated chome is fitter if (trial->nfitness->IsBetter(pop[target]->nfitness)) { InsertMember(target,trial); newchrome = TRUE; } else 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 delete trial; break; case docopy: target=GetTarget(); // Find a member to replace best=selectParent(target); trial=best->Copy(); newchrome = (params->params[pRepeatEval]? TRUE: FALSE); } // Update the pop array if ((dowhat!=doanneal) && (dowhat!=docrossanneal)) { // fitness? if (newchrome) { Fitness(trial); } InsertMember(target,trial); } } // if not initeval return pop[target]; } #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; Chrome* lastchrome; #ifdef MULTREE lastchrome=generate(tree); #else lastchrome=generate(); #endif didevals++; //while(maxevals == 0 || didevalsnfitness->fvalue < maxfitness) &&!Aborted()) { #ifdef MULTREE lastchrome = generate(tree); #else lastchrome = generate(); #endif didevals++; } return lastchrome; } int Pop::GetTarget() // Tournament anti-selection for replacement. Usually size 1 (random selection) or 2 { Chrome* candidates [params->params[pKillTourn]]; int slot [params->params[pKillTourn]]; // pick a target to replace int s=rnd(popsize); //chose any deme in pop slot[0] = s; candidates[0] = pop[s]; select_candidates(s, params->params[pKillTourn] - 1, &candidates[1], &slot[1] ); //chose from same deme int index; problem->Worstof(candidates, params->params[pKillTourn], gencount, &index); return slot[index]; } int Pop::GetAnnealTarget() { // 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;infitness->IsBetter(pop[best]->nfitness)) best=trial; } } return best; } void Pop::Write(ostream & fout) //WBL { for ( UINT i = 0; i < popsize; i++ ) { fout << endl << i ; #ifdef TRACE pop[i]->write_trace(); #endif TRACE pop[i]->write(PRETTY_NONE, fout); fout << endl; } }//end Pop::Write //************************************************************************ //////////////////////ChromeParams methods ChromeParams::ChromeParams() //Set default parameters here in the constructor { varcount = 0; funccount = 0; int x; for (x=0;x> c; if ( c == EOF ) return FALSE;} while ( c == par[i++]){ in >> c; } if ( i != (strlen(par)+1) ) return FALSE; while ( c != ':' ) { in >> c; if ( c == EOF ) return FALSE;} in >> value; return TRUE; }//end Load_1 void ChromeParams::Load(istream& in ) { Load_1 ( in, "pPopSize", params[pPopSize] ); Load_1 ( in, "pGenerateLimit", params[pGenerateLimit] ); Load_1 ( in, "pPopSeed", params[pPopSeed] ); Load_1 ( in, "pTestSeed", params[pTestSeed] ); Load_1 ( in, "pTrace", params[pTrace] ); Load_1 ( in, "pMaxExpr", params[pMaxExpr] ); Load_1 ( in, "pInitExpr", params[pInitExpr] ); Load_1 ( in, "pMuteRate", params[pMuteRate] ); Load_1 ( in, "pCrossSelf", params[pCrossSelf] ); Load_1 ( in, "pUnRestrictWt", params[pUnRestrictWt] ); Load_1 ( in, "pCrossWt", params[pCrossWt] ); Load_1 ( in, "pMuteWt", params[pMuteWt] ); Load_1 ( in, "pMuteNodeWt", params[pMuteNodeWt] ); Load_1 ( in, "pMuteConstWt", params[pMuteConstWt] ); Load_1 ( in, "pMuteShrinkWt", params[pMuteShrinkWt] ); Load_1 ( in, "pAnnealMuteWt", params[pAnnealMuteWt] ); Load_1 ( in, "pAnnealCrossWt", params[pAnnealCrossWt] ); Load_1 ( in, "pCopyWt", params[pCopyWt] ); Load_1 ( in, "pSelectMethod", params[pSelectMethod] ); Load_1 ( in, "pTournSize", params[pTournSize] ); Load_1 ( in, "pPopWidth", params[pPopWidth] ); Load_1 ( in, "pDemeWidth", params[pDemeWidth] ); Load_1 ( in, "pMateRadius", params[pMateRadius] ); Load_1 ( in, "pGaussRegion", params[pGaussRegion] ); Load_1 ( in, "pRepeatEval", params[pRepeatEval] ); Load_1 ( in, "pKillTourn", params[pKillTourn] ); Load_1 ( in, "pMaxAge", params[pMaxAge] ); Load_1 ( in, "pParsimony", params[pParsimony] ); Load_1 ( in, "pFitnessCases", params[pFitnessCases] ); }//end ChromeParams::Load() void ChromeParams::Save(ostream& out) { out << "pPopSize : " << params[pPopSize] << endl; out << "pGenerateLimit : " << params[pGenerateLimit] << endl; out << "pPopSeed : " << params[pPopSeed] << endl; out << "pTestSeed : " << params[pTestSeed] << endl; out << "pTrace : " << params[pTrace] << endl; out << "pMaxExpr : " << params[pMaxExpr] << endl; out << "pInitExpr : " << params[pInitExpr] << endl; out << "pMuteRate : " << params[pMuteRate] << endl; out << "pCrossSelf : " << params[pCrossSelf] << endl; out << "pUnRestrictWt : " << params[pUnRestrictWt] << endl; out << "pCrossWt : " << params[pCrossWt] << endl; out << "pMuteWt : " << params[pMuteWt] << endl; out << "pMuteNodeWt : " << params[pMuteNodeWt] << endl; out << "pMuteConstWt : " << params[pMuteConstWt] << endl; out << "pMuteShrinkWt : " << params[pMuteShrinkWt] << endl; out << "pAnnealMuteWt : " << params[pAnnealMuteWt] << endl; out << "pAnnealCrossWt : " << params[pAnnealCrossWt] << endl; out << "pCopyWt : " << params[pCopyWt] << endl; out << "pSelectMethod : " << params[pSelectMethod] << endl; out << "pTournSize : " << params[pTournSize] << endl; out << "pPopWidth : " << params[pPopWidth] << endl; out << "pDemeWidth : " << params[pDemeWidth] << endl; out << "pMateRadius : " << params[pMateRadius] << endl; out << "pGaussRegion : " << params[pGaussRegion] << endl; out << "pRepeatEval : " << params[pRepeatEval] << endl; out << "pKillTourn : " << params[pKillTourn] << endl; out << "pMaxAge : " << params[pMaxAge] << endl; out << "pParsimony : " << params[pParsimony] << endl; out << "pFitnessCases : " << params[pFitnessCases] << endl; }//end ChromeParams::Save()