ga.cpp

- XCS for Dynamic Environments + Continuous versions of XCS + Test problem: real multiplexer +

/*	XCSR_DE1.0
*	--------------------------------------------------------
*	Learning classifier system based on accuracy in dynamic environments
*
*	by  Huong Hai (Helen) Dam
*	[e-mail]
*	UNSW @ ADFA, Canberra Australia
*	Artificial Life and Adaptive Robotics Laboratory
*	http://www.itee.adfa.edu.au/~alar
*
*	Last modified: 24-11-2005
*
*/
#include "ga.h"

GA::GA(int randomseed, int pop, double c, double m, int type)
{
	random = new Random();
	random->setSeed(randomseed);
	maxpopsize = pop;
	crate = c;
	mrate = m;
	rep_type = type;
}

GA::~GA(){
	delete random;
}

double GA::getAvgTime(Population *pop, int *actset, int naset){
	double sumTime = 0.0;
	double sumN = 0.0;
	for(int i = 0; i < naset; i++)
	{
		sumTime +=	pop->getClassifierC(actset[i])->getTimeStamp() * 
			pop->getClassifierC(actset[i])->getNum();
		sumN += pop->getClassifierC(actset[i])->getNum();
	}
	return (sumTime/sumN);
}
void GA::discoveryComponent(Population *pop, int *actset, int naset, int time)
{
	
	int m1, m2;
	int nclassifiers = pop->getNumMacro();
	
	double settime = getAvgTime(pop, actset, naset);
	//Check against THETA_GA
	if(time - settime  < THETA_GA)
		return;
	if(naset == 0)
		return;
	
	for(int i = 0; i < naset; i++)
		pop->getClassifierC(actset[i])->setTimeStamp(time);
	
	m1= tournamentSelection(pop,  actset, naset, -1);
	m2= tournamentSelection(pop,  actset, naset, m1);
	if(m1 != -1 && m2 != -1)
	{
		Classifier *mate1 = pop->getClassifierC(m1);
		Classifier *mate2 = pop->getClassifierC(m2);
		Classifier *child1 = new Classifier(rep_type);
		Classifier *child2 = new Classifier(rep_type);
		child1->classifiercpy(mate1);
		child2->classifiercpy(mate2);
		
		child1->setExp(0);
		child1->setNum(1);
		child2->setExp(0);
		child2->setNum(1);
		child1->updateFitness(mate1->getFitness()/mate1->getNum());
		child2->updateFitness(mate2->getFitness()/mate2->getNum());
		if(random->nextDouble() < crate)
		{
			crossover(CROSS_TWO	, mate1, mate2, child1, child2);//crossover 
			
			//children inherit average of parental strength values
			double newfitness = (	(double)mate1->getFitness()/mate1->getNum() + 
				(double)mate2->getFitness()/mate2->getNum() )/2;
			double prediction =	((double)mate1->getPrediction() + 
				(double)mate2->getPrediction())/2;
			double prediction_error=((double)mate1->getPredictionError() + 
				(double)mate2->getPredictionError())/2;
			child1->updateFitness(newfitness); //* fitnessReduction); //set new fitness for the child
			child2->updateFitness(newfitness);// * fitnessReduction);
			child1->setPrediction(prediction);
			child2->setPrediction(prediction);
			child1->setPredictionError(prediction_error);
			child2->setPredictionError(prediction_error);
			
		}
		child1->updateFitness(child1->getFitness()*0.1);
		child2->updateFitness(child2->getFitness()*0.1);
		mutation(child1->getInterval());
		mutation(child2->getInterval());
		GASubsumes(pop, child1, mate1, mate2);
		GASubsumes(pop, child2, mate1, mate2);
		
		int popsize = pop->getPopSize();
		while(popsize > maxpopsize)
		{
			pop->deleteFromPopulation();
			popsize = pop->getPopSize();
			
		}
		
	}
	
}
void GA::GASubsumes( Population *pop, Classifier *child, Classifier* parent1, Classifier *parent2)
{
    if(subsumes(child, parent1))
    {
        parent1->increaseNum();
        delete child;
    }
	
	else if(subsumes(child, parent2))
	{
		
		parent2->increaseNum();
		delete child;
	}
	else
	{
        insertInPopulation(pop, child);
	}
	
}
int GA::subsumes(Classifier *child, Classifier *parent)
{
	int check = TRUE;
	
	int cact = child->getAction();
	int pact = parent->getAction();
	if(cact != pact)
		check = FALSE;
	if(parent->getExp() < THETASUB || parent->getAccuracy() < 1)
		check = FALSE;
	if(isMoreGeneral( parent, child)== FALSE) 
		check = FALSE;	
	return check;
}

//Check if parent is more general than children.
//Return TRUE if it is, otherwise FALSE

int GA::isMoreGeneral(Classifier *parent, Classifier *child)
{
	int check = TRUE;
	for(int i = 0; i < COND_OFFSET; i++)
	{
		if((child->getIntervalMin(i) < parent->getIntervalMin(i)) ||
			(child->getIntervalMax(i) > parent->getIntervalMax(i)))
		{
			check = FALSE;
			break;
		}
	}
	return check;
}
void GA::insertInPopulation(Population *pop, Classifier *child){
	
	int	check= TRUE;
	int i;
	int len = 0;
	//Check if the child is identical in condition and action with any classifiers
	for( i = 0; i < pop->getNumMacro(); i++)
	{
		if(child->matchClassifier(pop->getClassifierC(i)))
		{
			check = FALSE;
			pop->getClassifierC(i)->increaseNum();	
			break;
		}	
	}	
	//Identical classifier
	if(check == TRUE)
		pop->addClassifier(child);
	else
		delete child;
}


// Select a single individual according to strength (random)
//Roulette wheel selection
int GA::rouletteWheelSelection(Population *pop,  int *actset, int naset)
{
	double rand, partsum, randomNumber, sumF=0;
	int i = 0, count=0;
	int nclassifiers = pop->getNumMacro();
	partsum = 0;
	randomNumber = random->nextDouble();
	
	for(int j = 0; j < naset; j++)
	{
		sumF += pop->getClassifierC(actset[j])->getFitness();
		count ++;
	}
	rand = randomNumber * sumF;
	if(count > 0)
	{
		do{
			partsum += pop->getClassifierC(actset[i])->getFitness();
			i++;
		}while((partsum <= rand)&&(i < naset));
		return (i-1);
	}
	else
		return -1;
}

//Tournamnt selection
int GA::tournamentSelection(Population *pop,  int *actset, int naset, int selected)
{
	int selection = -1;
	double fitnessMax = 0.;
	int sel[MAX_POP_SIZE];
	int i,j, asize = 0, setsum = 0;
	for(i = 0; i < MAX_POP_SIZE; i++)
		sel[i] = 0;
	for(i = 0; i < naset; i++)
	{
		setsum += pop->getClassifierC(actset[i])->getNum();
	}
	
	int size = (int)(TNMSIZE * setsum);
	if(size < 1)
		size = 1;
	
	for(i = 0; i < size; i++)
	{
		int choice = random->nextInt(setsum);
		sel[choice] = 1;	
	}
	
	if(naset < 2){
		selection = actset[0];
	}
	else
	{
		int total = 0;
		for(i = 0; i < naset; i++)
		{
			
			int numcp = pop->getClassifierC(actset[i])->getNum();
			double fitness = pop->getClassifierC(actset[i])->getFitness()/numcp;
			for(j = 0; j < numcp; j++)
			{
				if(sel[total + j] == 1)
				{
					if(fitness > fitnessMax)
					{
						fitnessMax = fitness;
						selection = actset[i];
						break;
					}
				}
			}
			total += numcp;
		}
	}
	return selection;
}

void GA::mutation(d_interval_t *interval)
{
	int i;
	int action = interval->action;
	if(random->nextDouble() < mrate) //flip with a biased coin
	{
		action = (action +1)%2;
	}
	interval->action = action;
	
	for(i = 0; i < COND_OFFSET; i++)
	{
#ifdef REAL
		if(random->nextDouble() < mrate) 
		{
			
			if(random->flip(0.5))
				interval->point1[i] +=random->nextDouble(MUTATION_THRESHOLD);
			else
				interval->point1[i] -= random->nextDouble(MUTATION_THRESHOLD);
		}
		
		if(random->nextDouble() < mrate) 
		{
			if(random->flip(0.5))
				interval->point2[i] += random->nextDouble(MUTATION_THRESHOLD);
			else
				interval->point2[i] -= random->nextDouble(MUTATION_THRESHOLD);
		}
#else
		if(random->nextDouble() < mrate)
		{
			
			if(random->flip(0.5))
				interval->point1[i] +=random->nextInt(MUTATION_THRESHOLD);
			else
				interval->point1[i] -= random->nextInt(MUTATION_THRESHOLD);
		}
		
		if(random->nextDouble() < mrate)
		{
			if(random->flip(0.5))
				interval->point2[i] += random->nextInt(MUTATION_THRESHOLD);
			else
				interval->point2[i] -= random->nextInt(MUTATION_THRESHOLD);
		}
		
#endif
	}
}
void GA::crossover(int ctype, 	Classifier *mate1, Classifier *mate2, 
				   Classifier *child1, Classifier *child2)
{
	
	int i,p1, p2;
	
	switch(ctype)
	{
	case CROSS_ONE:
		p1 = random->nextInt(COND_OFFSET *2+1); //crossover point 
		
		if((p1 % 2)==0)
		{
			
			for (i = p1/2; i < COND_OFFSET; i++)
			{
				child1->getInterval()->point1[i]= mate2->getInterval()->point1[i];
				child1->getInterval()->point2[i]=mate2->getInterval()->point2[i];
				
				child2->getInterval()->point1[i]=mate1->getInterval()->point1[i];
				child2->getInterval()->point2[i]=mate1->getInterval()->point2[i];
			}
		}
		else
		{
			
			i = p1/2;
			child1->getInterval()->point2[i]=mate2->getInterval()->point2[i];
			child2->getInterval()->point2[i]=mate1->getInterval()->point2[i];
			for (i = p1/2 +1; i < COND_OFFSET; i++)
			{
				child1->getInterval()->point1[i]= mate2->getInterval()->point1[i];
				child1->getInterval()->point2[i]=mate2->getInterval()->point2[i];
				
				child2->getInterval()->point1[i]=mate1->getInterval()->point1[i];
				child2->getInterval()->point2[i]=mate1->getInterval()->point2[i];
			}
		}
		
		break;
		
	case CROSS_TWO:
		//				int p1temp;
		p1 = random->nextInt(COND_OFFSET *2+1); //crossover point 
		p2 = random->nextInt(COND_OFFSET *2+1);
		if(p1> p2)
		{
			int temp = p2;
			p2 = p1;
			p1 = temp;
		}
		
		i = 0;
		do{
			if(p1 <= i && i < p2)
			{
				if(i%2 == 1)
				{
					child1->getInterval()->point1[(int)i/2] = mate2->getInterval()->point1[(int)i/2];
					child2->getInterval()->point1[(int)i/2] = mate1->getInterval()->point1[(int)i/2];
				}
				else
				{
					child1->getInterval()->point2[(int)i/2 - 1] = mate2->getInterval()->point2[(int)i/2-1];
					child2->getInterval()->point2[(int)i/2 - 1] = mate1->getInterval()->point2[(int)i/2-1];
				}
			}
			i++;
		}while(i < p2);
		
		break;
	case CROSS_TWO_WITHIN:
		p1 = random->nextInt(COND_OFFSET +1); //crossover point 
		p2 = random->nextInt(COND_OFFSET +1);
		if(p1> p2)
		{
			int temp = p2;
			p2 = p1;
			p1 = temp;
		}
		
		do{
			if(p1 <= i && i <= p2-1)
			{
				
				
				child1->getInterval()->point2[i] = mate2->getInterval()->point2[i];
				child2->getInterval()->point2[i] = mate1->getInterval()->point2[i];
				
				child1->getInterval()->point1[i+1] = mate2->getInterval()->point1[i+1];
				child2->getInterval()->point1[i+1] = mate1->getInterval()->point1[i+1];
				
				
				
			}
			i++;
		}while(i <= p2-1);
		break;
		
	}
	
				   }