relearningscheme.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 "relearningscheme.h"

//Apportment of credit routines
ReLearningScheme::ReLearningScheme(int rand, int type, int maxpop)
{	
	matchset = new int[MAX_POP_SIZE];
	actset = new int[MAX_POP_SIZE];
	random = new Random();
	random->setSeed(rand);
	rep_type = type;
	maxpopsize = maxpop;
	num_cover = 0;
	beta = BETA_MIN;
}


void ReLearningScheme::setFastLearningRate(int level)
{
	if(level == TRUE)
		beta = BETA_MAX;
	else
		beta = BETA_MIN;
}
void ReLearningScheme::adaptLearningRate(double current_error, double previous_error)
{
	double delta = (current_error - previous_error)/REWARD;
	double beta1;
	if(delta > 0) //Performance decrease
	{
		beta1 = BETA_MIN + (BETA_MAX - BETA_MIN) * exp(((delta-1)/delta)*ALPHA1);
	}
	else
	{
		beta1 = BETA_MIN;
	}
	beta = (beta + beta1)/2;
}
int ReLearningScheme::getXCSOutput(Population *pop, input_t *input)
{
	int output;
	
	getMatchSet(pop,  input);
	getPredictionArray(pop);
	output = getActionWinner(pop );
	return output;
}

int ReLearningScheme::performanceComponent(GA *ga, Population *pop, input_t *input)
{
	int output;
	getMatchSet(pop,  input);
	getPredictionArray(pop);
	output =getRandomAction(pop);
	return output;
}

int ReLearningScheme::formMatchSet(Population *pop,  input_t *input)
{
	//reset values
	nmset = 0;
	int i;
	
	for(i = 0; i < pop->getNumMacro(); i++)
	{	
		if(pop->getClassifierC(i)->matchInput(input) == TRUE)
		{		
			matchset[nmset] = i;
			nmset ++;
		}
	}
	return nmset;
}

int ReLearningScheme::formActionSet(Population *pop, int action)
{
	naset = 0;
	// Obtain the action set
	for(int j = 0; j < nmset; j++)
	{
		if(pop->getClassifierC(matchset[j])->getAction() == action)
		{
			actset[naset] = matchset[j];
			naset ++;
		}
	}
	return naset;
}


int ReLearningScheme::getMatchSet(Population *pop, input_t *input)
{
	int loop = TRUE;
	int i;
	int coveredAction[NACTION+1];
	int num_covered_action = 0;
	
	formMatchSet(pop, input);
	while(loop == TRUE)
	{
		num_covered_action = 0;
		for(i = 0; i < NACTION; i++)
			coveredAction[i] = 0;
		for(i = 0; i < nmset; i++)
		{
			int action = pop->getClassifierC(matchset[i])->getAction();
			if(coveredAction[action] == 0)
			{
				coveredAction[action] = 1;
				num_covered_action ++;
			}
		}
		if(num_covered_action < THETA_MNA)
		{
			for(i = 0; i < NACTION; i++)
			{
				if(coveredAction[i] == 0)
				{
					Classifier *cl = covering(pop,input, i, STANDARD_COVER);
					pop->addClassifier(cl);
				}
			}
		}
		loop = FALSE;
		int popsize = pop->getPopSize();
		while(popsize > maxpopsize)
		{
			pop->deleteFromPopulation();
			popsize = pop->getPopSize();
			loop = TRUE;
		}
		formMatchSet(pop, input);
	}
	return nmset;
}
// Get the prediction array using fitness-weighted average of the predictions 
void ReLearningScheme::getPredictionArray( Population *pop)
{
	double farray[NACTION];
	double fitness, prediction;
	
	for(int j = 0; j < NACTION; j++)
	{
		parray[j] = 0;
		farray[j] = 0;
	}
	for(int i = 0; i < nmset; i++)
	{
		fitness = pop->getClassifierC(matchset[i])->getFitness();
		prediction = pop->getClassifierC(matchset[i])->getPrediction();
		int action = pop->getClassifierC(matchset[i])->getAction();
		
		parray[action] += prediction * fitness;
		farray[action] += fitness;
		
	}
	//Divide the sum of the predictions by the sum of the fitnesses
	for(int k = 0; k < NACTION; k++)
	{
		if(farray[k] != 0)
		{
			parray[k] = parray[k]/farray[k];
			if(parray[k] == 0)
				parray[k] = 0.0000001;
		}
		else
			parray[k] = 0;
	}
}
//Covering occurs if the number of actions present in [M] is < threashold
//A classifier is created whose condition matches the input and contain # with 
// probability P. The classifier's action is chosen randomly from among thost not presented in M

//Deterministic action selection in parray
int ReLearningScheme::getActionWinner(Population *pop)
{
	//char * action = new char[NACTION];
	int action =2;
	int temp = -1;
	double max = 0.0;
	
    for(int i = 0; i <NACTION; i++)
	{
		if(parray[i] > max)
		{
			max = parray[i];
			action = i;
		}
		if(parray[i] == max)
		{
			if(random->flip(0.5))
			{
				max = parray[i];
				action = i;
			}
		}
	}
	formActionSet(pop, action);
	return action;
}

int ReLearningScheme::getRandomAction(Population *pop)
{
	int action =2;
	int temp = -1;
	double max = 0.0;
	
	action = random->nextInt(NACTION);
	formActionSet(pop, action);
	return action;
}

Classifier * ReLearningScheme::covering(Population *pop,input_t *input, int action, int cover_type)
{
	num_cover++;
	Classifier *c = new Classifier(rep_type);
	c->getInterval()->action = action;
	double threshold;
#ifdef INT
	for(int i = 0; i < COND_OFFSET; i++)
	{
		if(random->flip(0.5))
		{
			int number = 0;
			while(number == 0)
				number = random->nextInt(COVER_THRESHOLD);
			c->getInterval()->point1[i] =	input->attrs[i] - 
				random->nextInt(COVER_THRESHOLD);
			
			c->getInterval()->point2[i] =	input->attrs[i] + number;
		}
		else
		{
			
			int number = 0;
			while(number == 0)
				number = random->nextInt(COVER_THRESHOLD);
			c->getInterval()->point1[i] =	input->attrs[i] + number;
			c->getInterval()->point2[i] =	input->attrs[i] -
				random->nextInt(COVER_THRESHOLD);
		}
		
	}
#endif
	
#ifdef REAL
	threshold = SPREAD_THRESHOLD; //
	
	for(int i = 0; i < COND_OFFSET; i++)
	{
		
		if(rep_type == CENTER_SPREAD )
		{
			c->getInterval()->point1[i] = input->attrs[i];
			c->getInterval()->point2[i] = random->nextDouble(threshold);
		}
		else if(rep_type == MIN_MAX)
		{
			if(random->flip(0.5))
			{
				c->getInterval()->point1[i] =	input->attrs[i] - 
					random->nextDouble(threshold);
				c->getInterval()->point2[i] =	input->attrs[i] +
					random->nextDouble(threshold);
			}
			else
			{
				c->getInterval()->point1[i] =	input->attrs[i] +
					random->nextDouble(threshold);
				c->getInterval()->point2[i] =	input->attrs[i] -
					random->nextDouble(threshold);
			}
		}
		else if(rep_type == CENTER_PERCENTAGE)
		{
			c->getInterval()->point1[i] = input->attrs[i];
			c->getInterval()->point2[i] = random->nextDouble(threshold);
		}
		else if(rep_type == MIN_PERCENTAGE)
		{
#ifdef SYM_COVER
			double range = random->nextDouble(threshold);
			double p1 =	input->attrs[i] - range;
			double p2 = input->attrs[i] + range;
			if(p2 > 1) p2 = 1;
			if(p1<0) p1 = 0;
			
			c->getInterval()->point2[i] = (p2-p1)/(UPPER_BOUND - p1);
			c->getInterval()->point1[i] = p1;
#else
			double p1 = input->attrs[i] - random->nextDouble(threshold);
			if(p1 < 0)
				p1 = 0;
			double p2 = input->attrs[i] + random->nextDouble(threshold);
			if(p2 > 1)
				p2 = 1;
			c->getInterval()->point2[i] = (p2 - p1)/(UPPER_BOUND - p1);
			c->getInterval()->point1[i] = p1;
#endif
		}
#ifdef NOISE_AT_ALLELE
		c->getInterval()->noise[i] = random->nextDouble(SPREAD_THRESHOLD);
#endif
	}
#endif
	
	return c;
}

//update fitness, prediction , prediction error, 
void ReLearningScheme::adjustActionSet(Population *pop,  double reward)
{
	double P, prediction, prediction_error, as;
	int my_exp;
	int setsize = 0;
	double maxP = 0;
	//	cout<<"Update the matchset"<<endl;
	
	for(int j = 0; j <naset; j++)
	{
		pop->getClassifierC(actset[j])->increaseExp();
		setsize += pop->getClassifierC(actset[j])->getNum();
	}
	//max value in prediction array
	for(int k = 0; k < NACTION; k++)
	{
		if(parray[k] > maxP)
			maxP = parray[k];	
	}
	P = reward + GAMMA * maxP; // maxP = 0 -> no previous action set
	
	for(int i   = 0; i < naset; i++)
	{	
		prediction_error = pop->getClassifierC(actset[i])->getPredictionError();
		prediction = pop->getClassifierC(actset[i])->getPrediction();
		as = pop->getClassifierC(actset[i])->getAS();//number of action set
		my_exp = pop->getClassifierC(actset[i])->getExp();// number of experience
		if( my_exp < 1/beta){
			
			prediction +=(P - prediction)/my_exp;
			prediction_error +=  (((double)fabs(P-prediction)-prediction_error)/my_exp);
			as += (setsize - as)/my_exp;
		}
		else{	
			prediction += beta * (P - prediction);
			prediction_error += beta * (fabs(P-prediction)-prediction_error);
			as += beta * (setsize - as);
		}
		pop->getClassifierC(actset[i])->setPrediction(prediction);
		pop->getClassifierC(actset[i])->setPredictionError(prediction_error);
		pop->getClassifierC(actset[i])->setAS(as);
	}
	
	updateFitness(pop);
	
}
//Update fitness of an action set
void ReLearningScheme::updateFitness(Population *pop)
{
	double accuracy, powersub, ksum = 0, fitness;
	//compute each classifier's accuracy
	for(int i = 0; i < naset; i++)
	{
		Classifier *c = pop->getClassifierC(actset[i]);
		if(c->getPredictionError() <= EPSILON0)
			accuracy  = 1.0;
		else
		{
			powersub = c->getPredictionError()/EPSILON0;
			accuracy = powersub;
			for(int j = 2; j < NU; j++)
				accuracy *= powersub;
			accuracy = ALPHA * (1/accuracy);
			
		}
		c->setAccuracy(accuracy) ;
		ksum += accuracy * c->getNum();	
	}
	
	// Update the finesses of the population  using relative accuracy
	for(int j = 0; j < naset; j++)
	{
		Classifier *temp = pop->getClassifierC(actset[j]);
		fitness = temp->getFitness();
		fitness = fitness + beta * (temp->getAccuracy()* temp->getNum()/ksum - fitness);
		temp->updateFitness(fitness);
	}
}
int ReLearningScheme::returnActionSet(int *set)
{
	for(int i = 0; i < naset; i++)
	{
		set[i] = actset[i];
	}
	return naset;
}

double ReLearningScheme::getAvgSystemError(int action, double reward)
{
	return (double)fabs(reward - parray[action]);
}