Class XClassifierSet

java.lang.Object
  |
  +--XClassifierSet

All Implemented Interfaces:

java.io.Serializable

public class XClassifierSet

extends java.lang.Object

implements java.io.Serializable

This class handles the different sets of classifiers. It stores each set in an array. The array is initialized to a sufficient large size so that no changes in the size of the array will be necessary. The class provides constructors for constructing

• the initial population (random or empty),
• the match set, and
• the action set.

It executes a GA in a set and updates classifier parameters of a set. Moreover, it provides all necessary different sums and averages of parameters in the set. Finally, it handles addition, deletion and subsumption of classifiers.

Since:

JDK 1.3

See Also:

Serialized Form

Field Summary

private int	cllSize The actual number of macro-classifiers in the list (which is in fact equal to the number of entries in the array).
private XClassifier[]	clSet The classifier list (in form of an array)
private static XCSConstants	cons The cons parameter is necessary for all kinds of calculations in the set.
private int	nbAnswers number of answers collected during the communication process
private int	numerositySum The Sum of the numerosity in one set is always kept up to date!
private XClassifierSet	parentSet Each set keeps a reference to the parent set out of which it was generated.

Constructor Summary

XClassifierSet(int numberOfActions)
Creates a new, empty population initializing the population array to the maximal population size plus the number of possible actions.

XClassifierSet(int numberOfActions, int conLength)
Creates a new random population, initializing the population array to the maximal population size plus the number of possible actions.

XClassifierSet(java.lang.String state, XClassifierSet pop, int numberOfActions)
Constructs a match set out of the population, without covering.

XClassifierSet(java.lang.String state, XClassifierSet pop, int time, int numberOfActions)
Constructs a match set out of the population.

XClassifierSet(XClassifierSet matchSet, int action)
Constructs an action set out of the given match set.

XClassifierSet(XCSConstants cons)
Construct the list of classifier candidate for answering a question

Method Summary

void	addBestAnswerToPopulation(XClassifier cladd, XClassifierSet matchSet) Once a classifier has been selected after communication, it is added to the population of classifiers of the asking agent.
private void	addClassifier(XClassifier classifier) Adds a classifier to the set and increases the numerositySum value accordingly.
private void	addValues(XClassifier cl) Increases the numerositySum value with the numerosity of the classifier.
void	addXClassifierToPopulation(XClassifier cl) Adds the classifier to the population and checks if an identical classifier exists.
private double	computeDispersion() Computes the dispersion of classifiers in the population, that is the sum of variances along the X axis and variance along Y axis
double	computeMinDistance(Environment env, java.lang.String string, double averFit) Computes the minimum distance between a classifier and the centre of the competence of an agent
private double	computeVariance(int[] listCoord) Computes variance along one dimension (X or Y)
void	confirmClassifiersInSet() Updates the numerositySum of the set and deletes all classifiers with numerosity 0.
private int	containsClassifier(XClassifier cl) Returns the position of the classifier in the set if it is present and -1 otherwise.
private int	decode(char[] binary, int size) Turns a binary string into an integer
XClassifier	deleteFromPopulation() Deletes one classifier in the population.
private void	doActionSetSubsumption() Executes action set subsumption.
XClassifier	elementAt(int i) Returns the classifier at the specified position.
XClassifier[]	getAnswerSet() returns the array of answering classifiers
double	getAverageExperience() Returns the average experience of the classifier set
double	getAverageFitness() Returns the average Fitness of the classifier set
double	getAveragePerformance() Returns the average performance of the classifier set
double	getAveragePredictionError() Returns the average error of the classifier set
int	getCollAnsSize() returns the number of answers in the array used to pass the answers from one agent to another
private double	getExperienceSum() Returns the sum of experiences in the population of classifiers
double	getFitnessSum() Returns the sum of the fitnesses of all classifiers in the set.
private XClassifier	getIdenticalClassifier(XClassifier newCl) Looks for an identical classifier in the population.
int	getNumerositySum() Return the numerosity of the population of classifiers of one agent
private double	getPredictionErrorSum() Returns the sum of errors in the population of classifiers
private double	getPredictionSum() Returns the sum of the prediction values of all classifiers in the set.
int	getSize() Returns the number of macro-classifiers in the set.
double	getTimeStampAverage() Returns the average of the time stamps in the set.
private double	getTimeStampSum() Returns the sum of the time stamps of all classifiers in the set.
private void	increaseNumerositySum(int nr) Increases recursively all numerositySum values in the set and all parent sets.
void	increaseSize() update the size of the array of answers collected
private void	insertDiscoveredXClassifiers(XClassifier cl, XClassifier cl1P, XClassifier cl2P) Inserts one discovered classifier keeping the maximal size of the population and possibly doing GA subsumption.
private boolean	isActionCovered(int action) Returns if the specified action is covered in this set.
void	printCharacteristics(java.io.PrintWriter pW) print characteristics into a file
void	printSet() Prints the classifier set to the control panel.
void	printSet(java.io.PrintWriter pW) Prints the classifier set to the specified print writer (which usually refers to a file).
private boolean	removeClassifier(int pos) Removes the (possible macro-) classifier at the specified array position from the population.
private boolean	removeClassifier(XClassifier classifier) Removes the specified (possible macro-) classifier from the population.
void	runGA(int time, Environment env, java.lang.String state, int numberOfActions, double distLevelOne, double averFit) The Genetic Discovery in XCS takes place here.
private XClassifier	selectXClassifierRW(double fitSum) Selects one classifier using roulette wheel selection according to the fitnesses of the classifiers.
private void	setTimeStamps(int time) Sets the time stamp of all classifiers in the set to the current time.
private void	subsumeXClassifier(XClassifier cl) Tries to subsume a classifier in the current set.
private void	subsumeXClassifier(XClassifier cl, XClassifier cl1P, XClassifier cl2P) Tries to subsume a classifier in the parents.
boolean	testFitness(double averFit) Tests if the fitness of a classifier is above the average performance of the population of classifiers
boolean	testPerformance(double averPerf) Tests if the performance of a classifier is above the average performance of the population of classifiers
private void	updateFitnessSet() Special function for updating the fitnesses of the classifiers in the set.
void	updateSet(double maxPrediction, double reward) Updates all parameters in the current set (should be the action set).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

cons

private static XCSConstants cons

The cons parameter is necessary for all kinds of calculations in the set. Note that it is static, so that it is not reconstructed each time a new set is created.

See Also:

XCSConstants.XCSConstants()

numerositySum

private int numerositySum

The Sum of the numerosity in one set is always kept up to date!

parentSet

private XClassifierSet parentSet

Each set keeps a reference to the parent set out of which it was generated. In the population itself this pointer is set to zero.

clSet

private XClassifier[] clSet

The classifier list (in form of an array)

cllSize

private int cllSize

The actual number of macro-classifiers in the list (which is in fact equal to the number of entries in the array).

nbAnswers

private int nbAnswers

number of answers collected during the communication process

Constructor Detail

XClassifierSet

public XClassifierSet(int numberOfActions)

Creates a new, empty population initializing the population array to the maximal population size plus the number of possible actions.

Parameters:

numberOfActions - The number of actions possible in the problem

See Also:

XCSConstants.maxPopSize

XClassifierSet

public XClassifierSet(int numberOfActions,
                      int conLength)

Creates a new random population, initializing the population array to the maximal population size plus the number of possible actions.

Parameters:

numberOfActions - The number of actions possible in the problem

conLength - The length of the condition part of classifiers

See Also:

XCSConstants.maxPopSize, XClassifier.XClassifier(double, int, int, int)

XClassifierSet

public XClassifierSet(java.lang.String state,
                      XClassifierSet pop,
                      int numberOfActions)

Constructs a match set out of the population, without covering.

Parameters:

state - The current situation/problem instance.

numberOfActions - The number of actions possible in the environment.

See Also:

XClassifier.XClassifier(double,int,String,int), XCSConstants.maxPopSize, deleteFromPopulation()

XClassifierSet

public XClassifierSet(java.lang.String state,
                      XClassifierSet pop,
                      int time,
                      int numberOfActions)

Constructs a match set out of the population. After the creation, it is checked if the match set covers all possible actions in the environment. If one or more actions are not present, covering occurs, generating the missing action(s). If maximal population size is reached when covering, deletion occurs.

Parameters:

state - The current situation/problem instance.

time - The actual number of instances the XCS learned from so far.

numberOfActions - The number of actions possible in the environment.

See Also:

XClassifier.XClassifier(double,int,String,int), XCSConstants.maxPopSize, XClassifier.match(String), addClassifier(XClassifier), deleteFromPopulation(), removeClassifier(int)

XClassifierSet

public XClassifierSet(XClassifierSet matchSet,
                      int action)

Constructs an action set out of the given match set.

Parameters:

matchSet - The current match set

action - The chosen action for the action set.

See Also:

addClassifier(XClassifier)

XClassifierSet

public XClassifierSet(XCSConstants cons)

Construct the list of classifier candidate for answering a question

Parameters:

cons - The set of constants used in the XCS

See Also:

XCSConstants.maxPopSize

Method Detail

getCollAnsSize

public int getCollAnsSize()

returns the number of answers in the array used to pass the answers from one agent to another

getAnswerSet

public XClassifier[] getAnswerSet()

returns the array of answering classifiers

increaseSize

public void increaseSize()

update the size of the array of answers collected

containsClassifier

private int containsClassifier(XClassifier cl)

Returns the position of the classifier in the set if it is present and -1 otherwise.

isActionCovered

private boolean isActionCovered(int action)

Returns if the specified action is covered in this set.

Parameters:

action - The specified action

updateSet

public void updateSet(double maxPrediction,
                      double reward)

Updates all parameters in the current set (should be the action set). Essentially, reinforcement Learning as well as the fitness evaluation takes place in this set. Moreover, the prediction error and the action set size estimate is updated. Also, action set subsumption takes place if selected. As in the algorithmic description, the fitness is updated after prediction and prediction error. However, in order to be more conservative the prediction error is updated before the prediction.

Parameters:

maxPrediction - The maximum prediction value in the successive prediction array (should be set to zero in single step environments).

reward - The actual resulting reward after the execution of an action.

See Also:

XCSConstants.gamma, XClassifier.increaseExperience(), XClassifier.updatePreError(double), XClassifier.updatePrediction(double), XClassifier#updateActionSetSize(int), updateFitnessSet(), XCSConstants#doActionSetSubsumption(), doActionSetSubsumption()

updateFitnessSet

private void updateFitnessSet()

Special function for updating the fitnesses of the classifiers in the set.

See Also:

XClassifier#updateFitness()

runGA

public void runGA(int time,
                  Environment env,
                  java.lang.String state,
                  int numberOfActions,
                  double distLevelOne,
                  double averFit)

The Genetic Discovery in XCS takes place here. If a GA takes place, two classifiers are selected by roulette wheel selection, possibly crossed and mutated and then inserted. The GA is modified compared to Butz (2001) in that it checks if the offsprings are in the domain of competencies of the agent before to add them in the classifiers population.

Parameters:

time - The actual number of instances the XCS learned from so far.

state - The current situation/problem instance.

numberOfActions - The number of actions possible in the environment.

distLevelOne - Threshold distance from the central competences of the agent

averFit - The average fitness of the population of classifiers

See Also:

XCSConstants.theta_GA, selectXClassifierRW(double), XClassifier.twoPointCrossover(XClassifier), XClassifier.applyMutation(java.lang.String, int), XCSConstants.predictionErrorReduction, XCSConstants.fitnessReduction, insertDiscoveredXClassifiers(XClassifier, XClassifier, XClassifier), computeMinDistance(Environment, String, double)

selectXClassifierRW

private XClassifier selectXClassifierRW(double fitSum)

Selects one classifier using roulette wheel selection according to the fitnesses of the classifiers.

Parameters:

fitSum - the sum of the fitness of the classifiers in the set

See Also:

XCSConstants.drand()

insertDiscoveredXClassifiers

private void insertDiscoveredXClassifiers(XClassifier cl,
                                          XClassifier cl1P,
                                          XClassifier cl2P)

Inserts one discovered classifier keeping the maximal size of the population and possibly doing GA subsumption.

Parameters:

cl - The classifier generated by the GA.

cl1P - The first parent of the two new classifiers.

cl2P - The second classifier of the two new classifiers.

See Also:

XCSConstants.doGASubsumption, subsumeXClassifier(XClassifier, XClassifier, XClassifier), addXClassifierToPopulation(XClassifier), XCSConstants.maxPopSize, deleteFromPopulation()

subsumeXClassifier

private void subsumeXClassifier(XClassifier cl,
                                XClassifier cl1P,
                                XClassifier cl2P)

Tries to subsume a classifier in the parents. If no subsumption is possible it tries to subsume it in the current set.

Parameters:

cl - the newly generated classifier to be subsumed

cl1P - the first parent of the classifier

cl2P - the second parent of the classifier

See Also:

subsumeXClassifier(XClassifier)

subsumeXClassifier

private void subsumeXClassifier(XClassifier cl)

Tries to subsume a classifier in the current set. This method is normally called in an action set. If no subsumption is possible the classifier is simply added to the population considering the possibility that there exists an identical classifier.

Parameters:

cl - The classifier that may be subsumed.

See Also:

addXClassifierToPopulation(XClassifier)

doActionSetSubsumption

private void doActionSetSubsumption()

Executes action set subsumption. The action set subsumption looks for the most general subsumer classifier in the action set and subsumes all classifiers that are more specific than the selected one.

See Also:

XClassifier.isSubsumer(), XClassifier.isMoreGeneral(XClassifier)

addXClassifierToPopulation

public void addXClassifierToPopulation(XClassifier cl)

Adds the classifier to the population and checks if an identical classifier exists. If an identical classifier exists, its numerosity is increased.

Parameters:

cl - The to be added classifier.

See Also:

getIdenticalClassifier(XClassifier), addClassifier(XClassifier)

getNumerositySum

public int getNumerositySum()

Return the numerosity of the population of classifiers of one agent

getIdenticalClassifier

private XClassifier getIdenticalClassifier(XClassifier newCl)

Looks for an identical classifier in the population.

Parameters:

newCl - The new classifier.

Returns:

Returns the identical classifier if found, null otherwise.

deleteFromPopulation

public XClassifier deleteFromPopulation()

Deletes one classifier in the population. The classifier that will be deleted is chosen by roulette wheel selection considering the deletion vote. Returns the macro-classifier which got decreased by one micro-classifier.

See Also:

XClassifier.getDelProp(double, double)

confirmClassifiersInSet

public void confirmClassifiersInSet()

Updates the numerositySum of the set and deletes all classifiers with numerosity 0.

setTimeStamps

private void setTimeStamps(int time)

Sets the time stamp of all classifiers in the set to the current time. The current time is the number of exploration steps executed so far.

Parameters:

time - The actual number of instances the XCS learned from so far.

addClassifier

private void addClassifier(XClassifier classifier)

Adds a classifier to the set and increases the numerositySum value accordingly.

Parameters:

classifier - The to be added classifier.

See Also:

addValues(XClassifier)

addValues

private void addValues(XClassifier cl)

Increases the numerositySum value with the numerosity of the classifier.

Parameters:

cl - the considered classifier

increaseNumerositySum

private void increaseNumerositySum(int nr)

Increases recursively all numerositySum values in the set and all parent sets. This function should be called when the numerosity of a classifier in some set is increased in order to keep the numerosity sums of all sets and essentially the population up to date.

Parameters:

nr - the number by which numerosity should be increased

removeClassifier

private boolean removeClassifier(XClassifier classifier)

Removes the specified (possible macro-) classifier from the population. The function returns true when the classifier was found and removed and false otherwise. It does not update the numerosity sum of the set, neither recursively remove classifiers in the parent set. This must be done manually where required.

Parameters:

classifier - the considered classifier

removeClassifier

private boolean removeClassifier(int pos)

Removes the (possible macro-) classifier at the specified array position from the population. The function returns true when the classifier was found and removed and false otherwise. It does not update the numerosity of the set, neither recursively remove classifiers in the parent set. This must be done manually where required.

Parameters:

pos - the position of the classifier to be removed in the population array

addBestAnswerToPopulation

public void addBestAnswerToPopulation(XClassifier cladd,
                                      XClassifierSet matchSet)

Once a classifier has been selected after communication, it is added to the population of classifiers of the asking agent. In doing so, we make sure that the size of classifiers population remains stable. The classifer about which communication takes place is replaced by the best answer received and numerosity of the new macro-classifier is adapted to the maximum size of the population.

Parameters:

cladd - The (micro-)classifier to be added

matchSet - The classifier is added in the population set and in the match set

See Also:

XClassifier.XClassifier(XClassifier), XClassifier.setNumerosity(int), XClassifier.setFitness(double), XClassifier.setPredictionError(double), XClassifier.setPrediction(double), XClassifier.setTimeStamp(int), XClassifier.setExperience(int), XClassifier.setActionSetSize(int), XClassifier.getFitness(), XClassifier.getNumerosity(), removeClassifier(XClassifier), addClassifier(XClassifier)

getPredictionSum

private double getPredictionSum()

Returns the sum of the prediction values of all classifiers in the set.

See Also:

XClassifier.getPrediction(), XClassifier.getNumerosity()

getExperienceSum

private double getExperienceSum()

Returns the sum of experiences in the population of classifiers

See Also:

XClassifier.getExperience(), XClassifier.getNumerosity()

getPredictionErrorSum

private double getPredictionErrorSum()

Returns the sum of errors in the population of classifiers

See Also:

XClassifier.getPredictionError(), XClassifier.getNumerosity()

getFitnessSum

public double getFitnessSum()

Returns the sum of the fitnesses of all classifiers in the set.

See Also:

XClassifier.getFitness()

getTimeStampSum

private double getTimeStampSum()

Returns the sum of the time stamps of all classifiers in the set.

See Also:

XClassifier.getTimeStamp(), XClassifier.getNumerosity()

elementAt

public XClassifier elementAt(int i)

Returns the classifier at the specified position.

Parameters:

i - The position specified

getSize

public int getSize()

Returns the number of macro-classifiers in the set.

getTimeStampAverage

public double getTimeStampAverage()

Returns the average of the time stamps in the set.

printSet

public void printSet()

Prints the classifier set to the control panel.

See Also:

XClassifier.printXClassifier()

printSet

public void printSet(java.io.PrintWriter pW)

Prints the classifier set to the specified print writer (which usually refers to a file).

Parameters:

pW - The print writer that normally refers to a file writer.

See Also:

XClassifier.printXClassifier(PrintWriter)

getAveragePerformance

public double getAveragePerformance()

Returns the average performance of the classifier set

getAverageFitness

public double getAverageFitness()

Returns the average Fitness of the classifier set

getAverageExperience

public double getAverageExperience()

Returns the average experience of the classifier set

getAveragePredictionError

public double getAveragePredictionError()

Returns the average error of the classifier set

testPerformance

public boolean testPerformance(double averPerf)

Tests if the performance of a classifier is above the average performance of the population of classifiers

Parameters:

averPerf - The average performance of the population

testFitness

public boolean testFitness(double averFit)

Tests if the fitness of a classifier is above the average performance of the population of classifiers

Parameters:

averFit - The average fitness of the population

computeMinDistance

public double computeMinDistance(Environment env,
                                 java.lang.String string,
                                 double averFit)

Computes the minimum distance between a classifier and the centre of the competence of an agent

Parameters:

env - The problem space

string - The condition of the tested classifier

averFit - The average fitness of the population

See Also:

Square.computeDistance(String,String)

computeDispersion

private double computeDispersion()

Computes the dispersion of classifiers in the population, that is the sum of variances along the X axis and variance along Y axis

See Also:

decode(char[], int), computeVariance(int[])

decode

private int decode(char[] binary,
                   int size)

Turns a binary string into an integer

Parameters:

binary - The binary string

size - The length of the string

computeVariance

private double computeVariance(int[] listCoord)

Computes variance along one dimension (X or Y)

Parameters:

listCoord - The list of coordinates of which variance is computed

printCharacteristics

public void printCharacteristics(java.io.PrintWriter pW)

print characteristics into a file

Parameters:

pW - The print writer that normally refers to a file writer

See Also:

computeDispersion()