Skip to content
Snippets Groups Projects
Mathis Brede's avatar
Mathis Brede authored
2366b219

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.

  1. 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"
  1. 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 -
  1. 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);
  1. (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;
  1. 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);
            }
        }
    }
  1. 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).
  1. 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])

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.

  1. Stewart W. Wilson. Classier Fitness Based on Accuracy. Evolutionary Computation, 3(2):149175, 1995.

  2. BUTZ, Martin V.; WILSON, Stewart W. An algorithmic description of XCS. In: International Workshop on Learning Classifier Systems. Springer, Berlin, Heidelberg, 2000. S. 253-272.