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
00014
00015
00016 #pragma region Intro comments
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #pragma endregion
00028
00029
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
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
00049 void XCS::registerParameters(StateP state)
00050 {
00051 params->registerParams(state->getRegistry());
00052
00053
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
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
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
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;
00123 double lastReward = 0;
00124 GenotypeP lastInput;
00125
00126
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;
00135 std::vector<ClassifierP> actionSet;
00136
00137
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
00146 matchSet = generateMatchSet(state, deme, input);
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
00155 std::map<int, double> PA = generatePA(matchSet);
00156
00157
00158 int actionId = selectActionId(state, PA);
00159 #ifdef XCS_DEBUG
00160 std::cout << "action id = " << actionId<< std::endl;
00161 #endif
00162
00163
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
00173 IndividualP ind = static_cast<IndividualP> (new Individual);
00174 ind->push_back(input);
00175 ind->push_back(actionSet[0]->getAction());
00176
00177
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
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
00254
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
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
00275 std::map<int, double> XCS::generatePA(std::vector<ClassifierP> matchSet){
00276 std::map<int, double> PA;
00277 std::map<int, double> fsa;
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
00304 if (environment->isExploit())
00305 return getMaxFromPA(PA).first;
00306
00307 if (rnd < params->p_explore_) {
00308
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
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
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
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 }