XCS Base
This project is a C++ based implementation of the XCS algorithm introduced by Wilson1. The implementation itself is based on the algorithmic description of Butz, Martin V. and Wilson2.
- Including the Modules:
- First all necessary modules have to be included. Those are XCS.hh and Random.hh, which are in the Headers directory.
//include the XCS library and the provided RandomNumberGenerator (can be replaced with own Generator)
#include "Headers/XCS.hh"
#include "Headers/Random.hh"
- In this project four different test environments are implemented. If you want to use one of these, the specific Header must be included from the Environments folder.
#include "Environments/Multiplexer.hh"
#include "Environments/MultiActionMultiplexer.hh"
#include "Environments/Woods1.hh"
#include "Environments/HiddenParity.hh"
- Init and config of XCSParameter:
- XCSParameter is a struct, which contains all user configurable parameters. These parameters, their function and their default value for the 6Multiplexer are given in the following table. The parameter possibleActionsPtr must be set to a vector filled with strings with all possible actions. The other parameters can be set, but default values are given. In the table below all parameters are listed with their description and default values. The only parameter that must be set is the possibleActionsPtr, which must be filled with all possible actions for the environment.
//init XCSParameter
XCSParameter parameter;
Parameter | Description | Default value |
---|---|---|
N | max PopulationSet size | 1000 |
pGeneral | probability for # as attribute in covering | 0.5 |
beta | learning rate | 0.2 |
alpha | parameter for calculation of fitness | 0.1 |
e0 | parameter for calculation of fitness | 1 |
nu | parameter for calculation of fitness | 5 |
thetaGA | threshold for average time period of action set to start the genetic algorithm procedure | 25 |
pCrossover | probability for crossover during genetic algorithm | 0.8 |
pMutation | probability for mutation during genetic algorithm | 0.04 |
thetaDel | deletion threshold;if experience of Classifier is greater than threshold, its fitness my be considered in probability of deletion | 20 |
delta | the fraction of the mean fitness in populationSet below which the fitness of a Classifier my be considered in probability of deletion | 0.1 |
initPrediction | value initial prediction parameter for new Classifier | 10 |
initError | value initial prediction error parameter for new Classifier | 0 |
initFitness | value initial fitness parameter for new Classifier | 0.01 |
pExplore | probability for doing an explore cycle (random action is chosen from prediction array) | 0.5 |
thetaMatching | threshold for unique actions in match set | 2 |
doGASubsumption | parameter if subsumption should be active in GA | true |
doActionSetSubsumption | parameter if subsumption should be active in action set | false |
thetaSub | experience a classifier needs to be a subsumer | 20 |
seed | seed for the RandomNumberGenerator | 20 |
GAInExploitation | parameter if GA should take place in exploitation cycles | false |
discountFactorPA | parameter to discount the reward of the previous iteration | 0.7 |
possibleActionsPtr | Ptr to all possible actions for the environment | - |
- Init RandomNumberGenerator, environment and XCS
- After setting the parameters for the algorithm, the RandomNumberGenerator, the Environment and XCS must be initialized.
- The provided environments and XCS are initialized with different RandomNumberGenerators to allow comparability between runs with different XCS configurations. The seed of the RandomNumberGenerator for the XCS algorithm can be set via the XCSParameter.
//RandomNumberGenerator for the environment
Random* RandomNumberGeneratorPtr = new Random(seed);
//init of 6Multiplexer
Multiplexer testEnv = Multiplexer(2,RandomNumberGeneratorPtr);
//init XCS with the values set
XCS xcs = XCS(parameter);
- (optional) MovingAvgTracker
- This XCS implementation provides a moving-average Tracker for the reward, which can be helpful for the performance tracking.
- To use the MovingAvgTracker you need to include the MovingAvgTracker.hh file from the Headers folder.
- ⚠️ ATTENTION ⚠️ Since the MovingAvgTracker uses the template class RingBuffer, the window is set to 2000. To change the size you need to change the value in the MovingAvgTracker.hh file. If you changed the window, make sure to initialize the specific RingBuffer in the RingBuffer.cc (some already used RingBuffers are initialized at the end of the file).
//init MovingAvgTracker
MovingAvgTracker tracker;
- Typical structure for use:
- The example below shows a typical example of how to use this implementation. You can either set a fixed iteration count, like in this example, or use a while-loop and check the performance value, if XCS has solved the given problem. At first, we give the xcs system the input generated by the testEnv. XCS then returns a struct with the proposed action and the information whether the action was selected in an exploration cycle. If the proposed action is right, xcs gets a payoff of '1000', if not a payoff of '0'. Usually the tracker only uses the reward of the exploitation cycles, so it is checked if the proposedAction was determined in such one.
- More example can be found in the possibleProfilingSituations directory with matching parameters.
//init variables for action and condition
returnAction proposedAction;
std::string condition;
unsigned i = 0;
while(i < CYCLE){
condition = testEnv.getCondition();
proposedAction = xcs.generateAction(condition);
if(proposedAction.action == testEnv.getAction()){
xcs.provideReward(1,1000);
if(proposedAction.isExploitation){
i++;
tracker.learn(1000);
}
}else{
xcs.provideReward(1,0);
if(proposedAction.isExploitation){
i++;
tracker.learn(0);
}
}
}
- XCS Settings
- In the constants.hh three different settings for the XCS algorithm can be adjusted.
- FITSUMPARAMETER: If set to 1 the sum of the fitness values of all classifiers in the populationSet is calculated by updating a parameter whenever the fitness value of one classifier changes. If set to 0, the sum is calculated by iterating over the populationSet.
- ALTERNATING_EXPLORE: If set to 1 exploit and exploring cycles are alternating (used to ensure reproducability). If set to 0 the type of cycle is determined randomly by using pExplore in the XCSParameters.
- BINARY_CONDITIONS: If set to 1 the conditions are represented as binary and not as string (if set to 0).
- Compilation & Execution
- It is suggested to use the following flags for compilation:
- -O3 (In case of the use of Binary Conditions the performance is only improving with highest compiler optimization)
- -std=c++17 (at least the C++17 standard must be used, since if constexpr is used; this if expressions are evaluated at compile-time)
- optional flag:
- -pg (needed for the profiling execution with gprof [gprof needs the debug information])
- It is suggested to use the following flags for compilation:
Example compilation & execution with main file from possibleProfilingSituations copied into the xcs directory:
g++ -O3 -std=c++17 ./xcs/**.cc ./xcs/Environments/**.cc -o ./xcs_example
# seed: set seed for environment
# xcsseed: set seed for xcs algorithm
# timeFile: set filename to save execution time in .csv file
# performanceFile: set filename to save performance in .csv file
# popsetFile: set filename to save last populationSet in .csv file
./xcs_example --seed=10 --xcsseed=20 --timeFile=xcs_example_time --performanceFile=xcs_example_performance --popsetFile=xcs_example_popset
The profiling_script_gprof file can help to better understand the compilation and executing.