chrome.cpp

用VC++编写的遗传算法源程序

					{
						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;i<funccount && rval<0;i++)
		if (strcmpi(funcname,funclist[i]->name)==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];
		funcbag = new CSelector(EStraight,256);
	varlist = new retval[CONSTARRAYSIZE];
	constlist = new retval[CONSTARRAYSIZE];
	funccount = 0;
	// set up constant table (not implemented)
	for (i=0;i<CONSTARRAYSIZE;i++) constlist[i]=i-(CONSTARRAYSIZE/2);
}

Problem::~Problem()
{
	int i;
	delete[] constlist;
	delete[] varlist;

	for (i=0;i<funccount;i++) delete funclist[i];
    delete funcbag;
	delete[] funclist;
}

FitnessValue* Problem::GetFitnessObj()
{
	FitnessValue* fv = new FitnessValue;
	if (fv==NULL) NoMoreMem();		// Out of memory?
	fv->fvalue=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;i<funccount;i++)
		funcbag->add(funclist[i]->weight/(2+funclist[i]->argnum),i);
	return funcbag;
}

float Problem::fitness(Chrome* chrome)
// This is just a stub.  You must add your own virtual fitness function

{
	float f=0;
	// clear variables if required
	// call the installed fitness function
	chrome->nfitness->fvalue = f;
	return f;
}



//**************************************************************************
//// Pop Functions /////////////////////////////////////////////////

Pop::Pop(Problem* prob,ChromeParams* par,UINT size)
// set up a population for a particular problem
// Creates <size> new Chromes
// evaluates the first Chrome.  The rest will be evaluated in the first
// Size-1 calls to generate

{
	UINT i;
		CSelector* fbag = prob->getfuncbag();
	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];
	if (pop==NULL) NoMoreMem();		// Out of memory?
	for (i=0;i<size;i++)
	{
		pop[i]=new Chrome(params,fbag,prob,prob->getfuncs(),prob->getconsts());
		if (pop[i]==NULL) NoMoreMem();		// Out of memory?
	}
	// now eval 1 guy
	initeval=TRUE;
	nexteval=1;
	Fitness(pop[0]);
	InsertMember(0,pop[0],TRUE);
}

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;


	if (!nodelete)
		 {
	// replace the chrome in this slot
	    delete pop[slot];
		pop[slot]=NewChrome;
	 }
	 // 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);
		BestMember=0;
		BestFitness=pop[0]->nfitness;
		UINT i;
		for (i=1;i<endpop;i++)
		{
			if (pop[i]->nfitness->IsBetter(BestFitness))
			{
				BestMember = i;
				BestFitness=pop[i]->nfitness;
			}
		}

	}
	NewChrome->birth=gencount;
}


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-10000000000000;
	// BestFitness->fvalue=1-MAXFLOAT;
}


Pop::~Pop()
{
		int i;
		for (i=0;i<popsize;i++) delete pop[i];
	delete[] pop;
}

Chrome* Pop::best()
{
	return pop[BestMember];
}

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 region, ts, offset, i;
	Chrome* best;
	Chrome* trial;

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

Chrome* Pop::generate()
// 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;
	


	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 (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);
		trial=best->CrossTree(secondbest);
		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 (prob<wheel)
	    trial->Mutate();
				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 (prob<wheel)
	    trial->Mutate();
		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);
		trial=pop[target]->CrossTree(best);
		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];
}

Chrome* Pop::go_until(time_t max_time, int maxevals, float maxfitness)
// 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;

	lastchrome=generate();
	didevals++;
		//while(maxevals == 0 || didevals<maxevals)
		while ((max_time == 0 || time(NULL) < max_time) &&
			(maxevals == 0 || didevals<maxevals) &&
			( lastchrome->nfitness->fvalue < maxfitness)
			&&!Aborted())
		{
				lastchrome = generate();
				didevals++;
	}
	return lastchrome;
}

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 && gencount- pop[target]->birth < params->params[pMaxAge])
	// pick a target to replace
	for (i=1;i<params->params[pKillTourn];i++)
	{
		winner=rnd(popsize);
		if (gencount - pop[winner]->birth > params->params[pMaxAge])
		{
			i=1000;
			target = winner;
		} else if (pop[target]->nfitness->IsBetter(pop[winner]->nfitness))
			target = winner;
	}
	return target;
}


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;i<ts;i++)
		{
			trial=rnd(popsize);
			if (pop[trial]->nfitness->IsBetter(pop[best]->nfitness))
				best=trial;
		}
	}
    return best;
}

//************************************************************************
//////////////////////ChromeParams methods

ChromeParams::ChromeParams()
//Set default parameters here in the constructor
{
	varcount = 0;
	funccount = 0;

	int x;
	for (x=0;x<PARAM_COUNT;x++)
		params[x]=0;

		params[pMaxExpr] = 50;         // Maximum expression size in nodes
		params[pInitExpr] = 6;          // Maximum initial expression depth
		params[pMuteRate] = 100;        // Node Mutation rate per 1000
		params[pCrossSelf] = 1;         // enable cross with self
		params[pUnRestrictWt] = 70;        // any point crossover out of 100
		params[pCrossWt] = 100;       // Crossover weight
		params[pMuteWt] = 30;        // overall Mutation weight
		params[pAnnealCrossWt] = 0;   // Crossover Annealing Weight
		params[pAnnealMuteWt] = 0;   // Mutate Annealing weight
		params[pCopyWt] = 10;        // Copy weight
		params[pMuteNodeWt] = 100;   // Node Mutate weight
		params[pMuteConstWt] = 100;    // MutateC weight
		params[pMuteShrinkWt] = 100;   // MutateShrink weight
		params[pSelectMethod] = ETournament;  // Selection method = Tournament
		params[pTournSize] = 7;         // Tournament size
		params[pMateRadius] = 500;       // Mating radius
		params[pGaussRegion] = 0;         // Guassian mate selection 0 disable 1 enable
		params[pRepeatEval] = 0;         // Repeat eval on copy? 0 no 1 yes
		params[pKillTourn] = 2;         // Size of "Kill Tournament" for replacement
		params[pMaxAge] = 2000;      // Maximum age before replaced even if better
		params[pParsimony] = 0;         // Parsimony factor
		params[pFitnessCases] = 20;        // # fitness cases
}


ChromeParams::~ChromeParams()
{
}

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