• Main Page
  • Modules
  • Classes
  • Files
  • File List

D:/Projekt/ECF_trunk/ECF/xcs/AlgXCS.cpp

00001 #include "../ECF_base.h"
00002 #include "../SelRandomOp.h"
00003 #include "../SelFitnessProportionalOp.h"
00004 #include "../SelWorstOp.h"
00005 #include "../ECF_macro.h"
00006 
00007 #include "AlgXCS.h"
00008 #include "math.h"
00009 #include "time.h"
00010 #include "../Logger.h"
00011 #include <string>
00012 //
00013 //#undef XCS_STEP_DEBUG
00014 //#undef XCS_DEBUG
00015 
00016 #pragma region Intro comments
00017 //References:
00018 //      [1] An algorithmic Description of XCS, Martin V. 
00019 //          Butz and Stewart W. Wilson
00020 //      [2] Rule-Based Evolutionary Online Learning Systems
00021 //          Martin V. Butz
00022 
00023 /*System characteristics:
00024     - single-step problems
00025     - multi-step problems
00026 */
00027 #pragma endregion
00028 
00029 //Compare function used for sorting classifier by fitness value
00030 bool cmp (ClassifierP a, ClassifierP b){
00031     return a->ind->fitness->getValue() > b->ind->fitness->getValue();
00032 }
00033 using namespace std;
00034 
00035 XCS::XCS()
00036 {
00037     name_ = "XCS";
00038     
00039     //TODO: izbacit randomOp i worstOp
00040     selRandomOp = static_cast<SelectionOperatorP> (new SelRandomOp);
00041     selFitPropOp = static_cast<SelectionOperatorP> (new SelFitnessProportionalOp);
00042     selWorstOp = static_cast<SelectionOperatorP> (new SelWorstOp);
00043 
00044     params = static_cast<XCSParamsP> ( new XCSParams(name_));
00045 }
00046 
00047 
00048 //Method for registering algorithm parameters
00049 void XCS::registerParameters(StateP state)
00050 {
00051     params->registerParams(state->getRegistry());
00052     
00053     //Defining aditional genotype used for storing classifier parameters
00054     ClassifierParamsP params = static_cast<ClassifierParamsP> (new ClassifierParams(0,0,0));
00055     state->addGenotype(params);
00056     
00057 }
00058 bool XCS::initialize(StateP state)
00059 {
00060     if (!Classifier::checkState(state)) {
00061         throw ("");
00062     }
00063 
00064     selRandomOp->initialize(state);
00065     selWorstOp->initialize(state);
00066     selFitPropOp->initialize(state);
00067     
00068     params->readParams(state->getRegistry());
00069 
00070     time = 0;
00071 
00072     ClassifierParamsP clParams = static_cast<ClassifierParamsP> (new ClassifierParams(0,0,0));
00073     clParams->setGenotypeId(3);
00074     clParams->initialize(state);
00075     params->initF_ = clParams->F_;
00076 
00077     //Environment initialization
00078     environment = boost::dynamic_pointer_cast<Environment> (evalOp_);
00079     
00080     if (!environment->checkState(state)) {
00081         throw ("");
00082     }
00083 
00084     try {
00085         if (!environment->initialize()){
00086             throw (std::string("failed to initialize"));
00087         }
00088     }catch (std::string text){
00089         ECF_LOG_ERROR(state, "Environment error: "+text);
00090         throw ("");
00091     }
00092 
00093     return true;
00094 }
00095 void XCS::printPopulation(){
00096     //sort(populationSet.begin(), populationSet.end(), cmp);
00097     for (uint i = 0; i < populationSet.size(); i++)
00098         populationSet[i]->print();
00099 }
00100 
00101 bool XCS::advanceGeneration(StateP state, DemeP deme) { 
00102     
00103     if (state->getGenerationNo() == 0){
00104         
00105         //creating population set [P]
00106         ClassifierP classP;
00107         PopulationP pop = state->getPopulation();
00108 
00109         for (uint i = 0; i < pop->size(); i++){
00110             for (uint j = 0; j < pop->at(i)->size(); j++){
00111                 classP = static_cast<ClassifierP> 
00112                     (new Classifier(params, time, pop->at(i)->at(j), state));
00113                 populationSet.push_back(classP);
00114             }
00115         }
00116 
00117         for (uint i = 0; i < deme->size(); i++)
00118             deme->at(i)->fitness->setValue(params->initF_);
00119         environment->reset();
00120     }
00121 
00122     std::vector<ClassifierP> lastActionSet;  //[A]-1
00123     double lastReward = 0;
00124     GenotypeP lastInput;
00125 
00126     //main generation loop
00127     do {
00128         
00129 #ifdef XCS_STEP_DEBUG
00130         std::cout << "Press any key to continue..." << std::endl;
00131         std::cin.get();
00132 #endif
00133         time++;
00134         std::vector<ClassifierP> matchSet; //[M]
00135         std::vector<ClassifierP> actionSet;//[A]
00136     
00137         //Getting input from environment
00138         GenotypeP input = environment->getInput();
00139 
00140 #ifdef XCS_DEBUG
00141         std::cout << "Input value: ";
00142         Classifier::printBitString(boost::dynamic_pointer_cast<BitString::BitString> (input));
00143         std::cout << std::endl;
00144 #endif
00145         //Generate match set [M]
00146         matchSet = generateMatchSet(state, deme, input); //[M]
00147     
00148 #ifdef XCS_DEBUG
00149         std::cout << "Match set [M]: "<< std::endl;
00150         for (uint i = 0; i < matchSet.size(); i++)
00151             matchSet[i]->print();
00152 #endif
00153         
00154         //creating prediction array PA
00155         std::map<int, double> PA = generatePA(matchSet);    
00156         //selecting action id
00157         
00158         int actionId = selectActionId(state, PA);
00159 #ifdef XCS_DEBUG
00160         std::cout << "action id = " << actionId<< std::endl;
00161 #endif
00162 
00163         //generating action set [A]
00164         actionSet = generateActionSet(matchSet, actionId);
00165 
00166 #ifdef XCS_DEBUG
00167         std::cout << "\nAction set [A]: "<< std::endl;
00168         for (uint i = 0; i < actionSet.size(); i++)
00169             actionSet[i]->print();
00170 #endif
00171 
00172         //executing selected action
00173         IndividualP ind = static_cast<IndividualP> (new Individual);
00174         ind->push_back(input);
00175         ind->push_back(actionSet[0]->getAction());
00176         
00177         //getting reward from environment
00178         evaluate(ind);
00179         double reward = ind->fitness->getValue();
00180 
00181 #ifdef XCS_DEBUG
00182         std::cout << "Reward: " << reward << std::endl;
00183 #endif      
00184         
00185         if (!lastActionSet.empty()){
00186             double P = lastReward + params->gama_ * getMaxFromPA(PA).second;
00187 
00188             updateActionSet(lastActionSet, deme,  P, state);
00189             if (!environment->isExploit()) {
00190                 runGA(lastActionSet, lastInput, deme, state);
00191             }
00192         }
00193         if (environment->isOver()) {
00194             
00195             if (!environment->isExploit()) {
00196                 updateActionSet(actionSet, deme, reward, state);
00197                 
00198                 runGA(actionSet, input, deme, state);
00199                 lastActionSet.clear();
00200             }
00201 
00202         } else {
00203             lastActionSet = actionSet;
00204             lastReward = reward;
00205             lastInput = input;
00206         }       
00207     } while (!environment->isOver());
00208         
00209     environment->nextTrial();
00210 
00211 #ifdef XCS_DEBUG
00212     std::cout << "Classifiers:" << std::endl;
00213     printPopulation();
00214     std::cout << " ===== advanceGeneration end ====="<< std::endl;
00215 #endif
00216 
00217     return true;
00218 }
00219 
00220 std::vector<ClassifierP> XCS::generateMatchSet(StateP state, DemeP deme, GenotypeP input) {
00221 
00222     //(!) napomena mora vrijediti deme->at(i) == vClassifier[i].ind
00223     std::vector<ClassifierP> matchSet;
00224 
00225     while(matchSet.empty()){
00226 
00227         for (uint i = 0; i < populationSet.size(); ++i){
00228             if (populationSet[i]->doesMatch(input))
00229                 matchSet.push_back(populationSet[i]);
00230         }
00231 
00232         uint noDiffActions = (uint) getActionsFromMs(matchSet).size();
00233         if (noDiffActions < params->mna_){
00234                 
00235             ClassifierP coverCl = cover(state, deme, input, matchSet);
00236             deleteFromPopulation(state, deme);
00237             matchSet.clear();
00238         }
00239     }
00240 
00241     return matchSet;
00242 } 
00243 
00244 std::set<int> XCS::getActionsFromMs (std::vector<ClassifierP> matchSet){
00245 
00246     std::set<int> actions;
00247     for (uint i = 0; i < matchSet.size(); ++i){
00248         actions.insert(matchSet[i]->getActionId());
00249     }
00250     return actions;
00251 }
00252 
00253 //Creates cover classifier according to input value
00254 //and inserts it in populationSet and deme
00255 ClassifierP XCS::cover (StateP state, DemeP deme, GenotypeP input, std::vector<ClassifierP> matchSet){
00256     
00257     IndividualP newInd = static_cast<IndividualP> (new Individual(state));
00258     
00259     ClassifierP newClassifier = static_cast<ClassifierP> (new 
00260         Classifier (params,time, newInd, state));
00261     
00262     //classifier must match input so that it can be added in [M]
00263     newClassifier->cover(getActionsFromMs(matchSet), input, state);
00264     newInd->index = (uint)deme->size();
00265     
00266     populationSet.push_back(newClassifier);
00267     deme->push_back(newInd);
00268 
00269         assert(deme->size() == populationSet.size());
00270 
00271     return newClassifier;
00272 }
00273 
00274 //Generates prediction array from match set
00275 std::map<int, double> XCS::generatePA(std::vector<ClassifierP> matchSet){
00276     std::map<int, double> PA;
00277     std::map<int, double> fsa; //fitness sum array
00278 
00279         for (uint i = 0; i < matchSet.size(); ++i){
00280 
00281             ClassifierP cl = matchSet[i];
00282             double fitness = cl->getFitness();
00283             int action = cl->getActionId();
00284         
00285             if(PA[action] == NULL) {
00286                 PA[action] = cl->getPrediction() * fitness;
00287                 fsa[action] = 0;
00288             } else 
00289                 PA[action] += cl->getPrediction() * fitness;
00290             fsa[action] += fitness;
00291         }
00292         for (std::map<int, double>::iterator it = PA.begin(); it != PA.end(); ++it){
00293             PA[it->first] /= (fsa[it->first] == 0 ? 1 : fsa[it->first]);
00294         }
00295     return PA;
00296 }
00297 
00298 
00299 int XCS:: selectActionId(StateP state, std::map<int, double> PA){
00300     double rnd = state->getRandomizer()->getRandomDouble();
00301     int actionId = PA.begin()->first;
00302 
00303     //if it is exploit experiment
00304     if (environment->isExploit())
00305         return getMaxFromPA(PA).first;
00306 
00307     if (rnd < params->p_explore_) {
00308         //exploration
00309         rnd = state->getRandomizer()->getRandomDouble();
00310         int i = 1;
00311         for (std::map<int, double>::const_iterator it = PA.begin(); it != PA.end(); ++it){
00312             if (i > PA.size() * rnd){
00313                 actionId = it->first;
00314                 break;
00315             }
00316             i++;
00317         }
00318     }else {
00319         //exploitation
00320         actionId = getMaxFromPA(PA).first;  
00321     }
00322     return actionId;
00323 }
00324 
00325 std::vector<ClassifierP> XCS::generateActionSet(std::vector<ClassifierP> matchSet, int actionId){
00326     std::vector<ClassifierP> actionSet;
00327     for (uint i = 0; i < matchSet.size(); i++)
00328         if (matchSet[i]->getActionId() == actionId)
00329             actionSet.push_back(matchSet[i]);
00330     return actionSet;
00331 }
00332 
00333 void XCS::updateActionSet(std::vector<ClassifierP> actionSet, DemeP deme, double reward, StateP state){
00334     
00335     ClassifierP cl;
00336     double sum = 0;
00337     std::vector<double> accuracy;
00338     
00339     int numSum = 0;
00340     for (uint i = 0; i < actionSet.size(); ++i)
00341         numSum += actionSet[i]->getNumerosity();
00342 
00343     //update exp, eps, p and as
00344     for (uint i = 0; i < actionSet.size(); ++i){
00345         cl = actionSet[i];
00346         
00347         double exp = cl->getExperience() + 1;
00348         cl->setExperience(exp);
00349 
00350         double eps = cl->getError();
00351         double p = cl->getPrediction();
00352         double as = cl->getActSetSize();
00353 
00354         if (exp < 1 / params->beta_) {
00355             p += (reward - p) / exp;
00356             eps += (fabs(reward - p) - eps) / exp;
00357             as += (numSum - as) / exp;
00358         } else {
00359             p += params->beta_ * (reward - p);
00360             eps += params->beta_ * (fabs(reward - p) - eps);
00361             as += params->beta_ * (numSum - as);
00362         }
00363 
00364         if (eps < params->eps0_)
00365             accuracy.push_back(1);
00366         else 
00367             accuracy.push_back( params->alpha_ * pow(eps / params->eps0_, -params->accExp_) );
00368         
00369         sum += accuracy[i] * cl->getNumerosity();
00370 
00371         cl->setPrediction(p);
00372         cl->setError(eps);
00373         cl->setActSetSize(as);
00374     }
00375 
00376     //update fitness
00377     for (uint i = 0; i < actionSet.size(); ++i){
00378         
00379         cl = actionSet[i];
00380 
00381         double F = cl->getFitness();
00382         F += params->beta_ * (accuracy[i] * cl->getNumerosity() / sum - F) ;
00383         cl->setFitness(F);
00384     }
00385 
00386     actionSetSubsumption(&actionSet, deme, state);
00387     
00388 }
00389 
00390 double XCS::getAsTimeSum(std::vector<ClassifierP> as) {
00391 
00392     double sumNum = 0, sumTsNum = 0;
00393     for (uint i = 0; i < as.size(); ++i){
00394         sumTsNum += as[i]->getTimeStamp() * as[i]->getNumerosity();
00395         sumNum += as[i]->getNumerosity();
00396     }
00397     
00398     return sumTsNum / sumNum;
00399 }
00400 
00401 void XCS::runGA(std::vector<ClassifierP> actionSet, GenotypeP genInput, DemeP deme, StateP state){
00402 
00403     if (time - getAsTimeSum(actionSet) < params->thresholdGA_) return;
00404 
00405     std::vector<IndividualP> tournament, vActionSet;
00406 
00407     for (uint i = 0; i < actionSet.size(); i++) {
00408         if (!actionSet[i]->valid) continue;
00409         vActionSet.push_back(actionSet[i]->ind);
00410         actionSet[i]->setTimeStamp(time);
00411     }
00412     if (vActionSet.size() < 1) return;
00413 
00414     IndividualP parent[2];
00415     parent[0] = selFitPropOp->select(vActionSet);
00416     parent[1] = selFitPropOp->select(vActionSet);
00417 
00418     ClassifierP clParent[2];
00419     clParent[0] = populationSet[parent[0]->index];
00420     clParent[1] = populationSet[parent[1]->index];
00421 
00422     assert(clParent[0]->getActionId() == clParent[1]->getActionId());
00423     ClassifierP clChild[2];
00424 
00425     for (int i = 0; i < 2; ++i) {
00426 
00427         clChild[i] = static_cast<ClassifierP> (new Classifier(clParent[i]));
00428 
00429         clChild[i]->setNumerosity(1);
00430         clChild[i]->setExperience(0);
00431 
00432         double f = clChild[i]->getFitness();
00433 
00434         if (state->getRandomizer()->getRandomDouble() < params->pCrossover_) {
00435             mate(parent[0], parent[1], clChild[i]->ind);
00436             
00437             clChild[i]->setAction(clParent[0]->getAction());
00438 
00439             assert(clChild[i]->getActionId() == clParent[i]->getActionId());
00440 
00441             clChild[i]->setPrediction((clParent[0]->getPrediction() + clParent[1]->getPrediction()) / 2);
00442             clChild[i]->setError((clParent[0]->getError() + clParent[1]->getError()) / 2);
00443 
00444             f = (clParent[0]->getFitness() + clParent[1]->getFitness()) / 2;
00445         }
00446 
00447         clChild[i]->setFitness( 0.1 * f);
00448 
00449         clChild[i]->mutateRule(genInput, state);
00450         clChild[i]->mutateAction(state);
00451 
00452         if (clParent[0]->doesSubsume(clChild[i])) {
00453             clParent[0]->setNumerosity(clParent[0]->getNumerosity() + 1);
00454         } else if (clParent[1]->doesSubsume(clChild[i])) {
00455             clParent[1]->setNumerosity(clParent[1]->getNumerosity() + 1);
00456         } else {
00457             clChild[i]->ind->index = (uint)deme->size();
00458             populationSet.push_back(clChild[i]);
00459             deme->push_back(clChild[i]->ind);
00460         }
00461             assert(deme->size() == populationSet.size());
00462 
00463         deleteFromPopulation(state, deme);
00464     }   
00465 }
00466 
00467 std::pair<int, double> XCS::getMaxFromPA(std::map<int, double> PA){
00468     
00469     if (PA.empty()) return std::make_pair(-1, -1.);
00470 
00471     std::pair<int, double> maxPA = *PA.begin();
00472     for (std::map<int, double>::iterator it = PA.begin(); it != PA.end(); ++it){
00473         if (it->second > maxPA.second)
00474             maxPA = *it;
00475     }
00476     return maxPA;
00477 }
00478 
00479 void XCS::deleteFromPopulation(StateP state, DemeP deme) {
00480 
00481     int sumNum = 0;
00482     double sumFit = 0;
00483 
00484     for ( uint i = 0; i < populationSet.size(); ++i) {
00485         sumNum += populationSet[i]->getNumerosity();
00486         sumFit += populationSet[i]->getFitness();
00487     }
00488     if (sumNum <= (int) params->popSize_) return;
00489 
00490     double avFitInPop = sumFit / sumNum;
00491     double sumVote = 0;
00492 
00493     for ( uint i = 0; i < populationSet.size(); ++i) {
00494         sumVote += populationSet[i]->getDeletionVote(avFitInPop);
00495     }
00496     double choicePoint = state->getRandomizer()->getRandomDouble() * sumVote;
00497     sumVote = 0;
00498     for ( uint i = 0; i < populationSet.size(); ++i) {
00499         ClassifierP cl = populationSet[i];
00500         sumVote += cl->getDeletionVote(avFitInPop);
00501         if (sumVote > choicePoint) {
00502             int n = cl->getNumerosity();
00503             if (n > 1){
00504                 cl->setNumerosity(n-1);
00505             } else {
00506                 removeFromPopSet(cl, deme);
00507             }
00508             return;
00509         }
00510     }
00511     assert(deme->size() == populationSet.size());
00512 
00513 }
00514 
00515 void XCS::removeFromPopSet(ClassifierP cl, DemeP deme){
00516     
00517     IndividualP lastInd = deme->at(deme->size()-1);
00518     ClassifierP lastCl = populationSet[populationSet.size()-1];
00519 
00520     lastInd->index = cl->ind->index;
00521 
00522     populationSet[cl->ind->index] = lastCl;
00523     populationSet.erase(populationSet.begin() + populationSet.size() - 1);
00524 
00525     deme->at(cl->ind->index) = lastInd;
00526     deme->erase(deme->begin() + deme->size() - 1);
00527     
00528     assert(deme->size() == populationSet.size());
00529     cl->valid = false;
00530 }
00531 
00532 void XCS::actionSetSubsumption(std::vector<ClassifierP> *actionSet, DemeP deme, StateP state){
00533     ClassifierP cl;
00534     bool clSet = false;
00535     
00536     for (uint i = 0; i < actionSet->size(); ++i){
00537         
00538         ClassifierP c = actionSet->at(i);
00539         if (c->couldSubsume()){
00540 
00541             int clDcb = c->numOfDCBits();
00542             double rnd = state->getRandomizer()->getRandomDouble();
00543             if (!clSet || clDcb > cl->numOfDCBits() || (clDcb == cl->numOfDCBits() && rnd < 0.5 )) {
00544                 cl = c;
00545                 clSet = true;
00546             }
00547         }
00548     }
00549     if (clSet) {
00550         for (uint i = 0; i < actionSet->size(); ++i){
00551             ClassifierP c = actionSet->at(i);
00552             if (cl->isMoreGeneral(c)){
00553                 cl->setNumerosity(cl->getNumerosity() + c->getNumerosity());
00554                 actionSet->erase(actionSet->begin() + i);
00555                 removeFromPopSet(c,deme);
00556             }
00557         }
00558     }
00559 }

Generated on Tue Nov 4 2014 13:04:31 for ECF by  doxygen 1.7.1