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

D:/Projekt/ECF_trunk/ECF/tree/Tree.cpp

00001 #include "../ECF_base.h"
00002 #include "Tree.h"
00003 #include <iostream>
00004 #include <sstream>
00005 #include <cmath>
00006 #include <sstream>
00007 
00008 // operators
00009 #include "TreeMutPermutation.h"
00010 #include "TreeMutGauss.h"
00011 #include "TreeMutNodeReplace.h"
00012 #include "TreeMutNodeComplement.h"
00013 #include "TreeMutHoist.h"
00014 #include "TreeMutShrink.h"
00015 #include "TreeMutSubtree.h"
00016 #include "TreeCrxSimple.h"
00017 #include "TreeCrxUniform.h"
00018 #include "TreeCrxContextPreserved.h"
00019 #include "TreeCrxSizeFair.h"
00020 #include "TreeCrxOnePoint.h"
00021 
00022 
00023 namespace Tree
00024 {
00025 
00026 Tree::Tree(void)
00027 {
00028     name_ = "Tree";
00029     startDepth_ = 0;
00030 }
00031 
00032 
00033 Tree::~Tree(void)
00034 {   }
00035 
00036 
00037 Tree* Tree::copy()
00038 {
00039     Tree *newObject = new Tree(*this);
00040 
00041     // create new nodes, copy primitives if necessary
00042     for(int i = 0; i < (int) this->size(); i++) {
00043         (*newObject)[i] = (NodeP) (new Node((*this)[i]));
00044     }
00045     return newObject;
00046 }
00047 
00048 
00049 std::vector<CrossoverOpP> Tree::getCrossoverOp()
00050 {
00051     std::vector<CrossoverOpP> crx;
00052     crx.push_back((CrossoverOpP) (new TreeCrxSimple));
00053     crx.push_back((CrossoverOpP) (new TreeCrxContextPreserved));
00054     crx.push_back((CrossoverOpP) (new TreeCrxUniform));
00055     crx.push_back((CrossoverOpP) (new TreeCrxSizeFair));
00056     crx.push_back((CrossoverOpP) (new TreeCrxOnePoint));
00057     return crx;
00058 }
00059 
00060 
00061 std::vector<MutationOpP> Tree::getMutationOp()
00062 {
00063     std::vector<MutationOpP> mut;
00064     mut.push_back((MutationOpP) (new TreeMutPermutation));
00065     mut.push_back((MutationOpP) (new TreeMutGauss));
00066     mut.push_back((MutationOpP) (new TreeMutNodeReplace));
00067     mut.push_back((MutationOpP) (new TreeMutNodeComplement));
00068     mut.push_back((MutationOpP) (new TreeMutHoist));
00069     mut.push_back((MutationOpP) (new TreeMutShrink));
00070     mut.push_back((MutationOpP) (new TreeMutSubtree));
00071     
00072     return mut;
00073 }
00074 
00075 
00080 bool Tree::addFunction(PrimitiveP func)
00081 {
00082     userFunctions_.push_back(func);
00083     return true;
00084 }
00085 
00086 
00091 bool Tree::addTerminal(PrimitiveP term)
00092 {
00093     userTerminals_.push_back(term);
00094     return true;
00095 }
00096 
00097 
00098 void Tree::registerParameters(StateP state)
00099 {
00100     registerParameter(state, "maxdepth", (voidP) (new uint(5)), ECF::UINT);
00101     registerParameter(state, "mindepth", (voidP) (new uint(1)), ECF::UINT);
00102     registerParameter(state, "initmaxdepth", (voidP) (new uint(5)), ECF::UINT);
00103     registerParameter(state, "initmindepth", (voidP) (new uint(1)), ECF::UINT);
00104     registerParameter(state, "functionset", (voidP) (new std::string), ECF::STRING);
00105     registerParameter(state, "terminalset", (voidP) (new std::string), ECF::STRING);
00106 }
00107 
00108 
00109 bool Tree::initialize(StateP state)
00110 {
00111     // 'hometree' is a Tree instance kept in the State;
00112     // we use it to link the PrimitiveSet to it and store the parameters
00113     Tree* hometree = (Tree*) state->getGenotypes()[genotypeId_].get();
00114     state_ = state;
00115 
00116     // if we are the first one to initialize
00117     if(!hometree->primitiveSet_) 
00118         initializeFirst(hometree);
00119 
00120     // in any case, read parameters from from hometree
00121     this->primitiveSet_ = hometree->primitiveSet_;
00122     initMaxDepth_ = hometree->initMaxDepth_;
00123     initMinDepth_ = hometree->initMinDepth_;
00124     maxDepth_ = hometree->maxDepth_;
00125     minDepth_ = hometree->minDepth_;
00126 
00127     // build tree (TODO: reimplement for ramped-half-and-half)
00128     if(state->getRandomizer()->getRandomInteger(0, 1) % 2 == 0)
00129         fullBuild(primitiveSet_);
00130     else
00131         growBuild(primitiveSet_);
00132 
00133     return true;
00134 }
00135 
00136 
00143 void Tree::initializeFirst(Tree* hometree)
00144 {
00145     // create and link PrimitiveSet to the hometree
00146     hometree->primitiveSet_ = (PrimitiveSetP) (new PrimitiveSet);
00147     hometree->primitiveSet_->initialize(state_);
00148     this->primitiveSet_ = hometree->primitiveSet_;
00149 
00150     // add user defined functions to primitiveSet
00151     for(int i = 0; i < (int) userFunctions_.size(); i++) {
00152         primitiveSet_->mAllPrimitives_[userFunctions_[i]->getName()] = userFunctions_[i];
00153         primitiveSet_->mAllPrimitives_[userFunctions_[i]->getName()]->initialize(state_);
00154     }
00155 
00156     // read function set from the configuration
00157     voidP sptr = getParameterValue(state_, "functionset");
00158     std::stringstream names;
00159     std::string name;
00160     names << *((std::string*) sptr.get());
00161     while(names >> name) {
00162         if(!primitiveSet_->addFunction(name)) {
00163             ECF_LOG_ERROR(state_, "Error: unknown function in function set (\'" + name + "\')!");
00164             throw("");
00165         }
00166     }
00167     if(primitiveSet_->getFunctionSetSize() == 0) {
00168         ECF_LOG_ERROR(state_, "Tree genotype: empty function set!");
00169         throw("");
00170     }
00171 
00172     // set default terminal type
00173     Primitives::terminal_type currentType = Primitives::Double;
00174     type_iter typeIter;
00175 
00176     // read terminal set from the configuration
00177     std::stringstream tNames;
00178     sptr = getParameterValue(state_, "terminalset");
00179     tNames << *((std::string*) sptr.get());
00180 
00181     while(tNames >> name)
00182     {
00183         // read current terminal type (if set)
00184         typeIter = primitiveSet_->mTypeNames_.find(name);
00185         if(typeIter != primitiveSet_->mTypeNames_.end()) {
00186             currentType = typeIter->second;
00187             continue;
00188         }
00189 
00190         // see if it's a user-defined terminal 
00191         uint iTerminal = 0;
00192         for(; iTerminal < userTerminals_.size(); iTerminal++)
00193             if(userTerminals_[iTerminal]->getName() == name)
00194                 break;
00195         if(iTerminal < userTerminals_.size()) {
00196             userTerminals_[iTerminal]->initialize(state_);
00197             primitiveSet_->addTerminal(userTerminals_[iTerminal]);
00198             continue;
00199         }
00200 
00201 
00202         // read ERC definition (if set)
00203         // ERC's are defined as interval [x y] or set {a b c}
00204         if(name[0] == '[' || name[0] == '{') {
00205 
00206             std::string ercValues = "";
00207 
00208             // name this ERC (ERC's name is its value!)
00209             PrimitiveP erc;
00210             switch(currentType) {
00211                 case Primitives::Double:
00212                     erc = (PrimitiveP) (new Primitives::ERCD); 
00213                     ercValues = DBL_PREFIX;
00214                     break;
00215                 case Primitives::Int:
00216                     erc = (PrimitiveP) (new Primitives::ERC<int>); 
00217                     ercValues = INT_PREFIX;
00218                     break;
00219                 case Primitives::Bool:
00220                     erc = (PrimitiveP) (new Primitives::ERC<bool>); 
00221                     ercValues = BOOL_PREFIX;
00222                     break;
00223                 case Primitives::Char:
00224                     erc = (PrimitiveP) (new Primitives::ERC<char>); 
00225                     ercValues = CHR_PREFIX;
00226                     break;
00227                 case Primitives::String:
00228                     erc = (PrimitiveP) (new Primitives::ERC<std::string>); 
00229                     ercValues = STR_PREFIX;
00230                     break;
00231             }
00232 
00233             while(name[name.size() - 1] != ']' && name[name.size() - 1] != '}') {
00234                 ercValues += " " + name;
00235                 tNames >> name;
00236             }
00237             ercValues += " " + name;
00238 
00239             // ERC ocekuje "D_ [<value> <value> ...]" kao ime prije initialize()
00240             erc->setName(ercValues);
00241             erc->initialize(state_);
00242             primitiveSet_->addTerminal(erc);
00243 
00244             continue;
00245         } 
00246 
00247 
00248         // otherwise, read terminal of current type
00249         PrimitiveP terminal;
00250         switch(currentType)
00251         {
00252             case Primitives::Double:
00253                 terminal = (PrimitiveP) (new Primitives::Terminal); break;
00254             case Primitives::Int:
00255                 terminal = (PrimitiveP) (new Primitives::TerminalT<int>); break;
00256             case Primitives::Bool:
00257                 terminal = (PrimitiveP) (new Primitives::TerminalT<bool>); break;
00258             case Primitives::Char:
00259                 terminal = (PrimitiveP) (new Primitives::TerminalT<char>); break;
00260             case Primitives::String:
00261                 terminal = (PrimitiveP) (new Primitives::TerminalT<std::string>); break;
00262         }
00263 
00264         // if the 'name' can be identified as a value of the 'currentType', then it's a _constant terminal_ (of that value)
00265         // otherwise, it's a regular terminal with 'name'
00266         std::istringstream ss(name);
00267         switch(currentType)
00268         {
00269             case Primitives::Double:
00270                 double dblValue;
00271                 ss >> dblValue;
00272                 if(ss.fail() == false) 
00273                     terminal->setValue(&dblValue);
00274                 break;
00275             case Primitives::Int:
00276                 int intValue;
00277                 ss >> intValue;
00278                 if(ss.fail() == false) 
00279                     terminal->setValue(&intValue);
00280                 break;
00281             case Primitives::Bool:
00282                 bool boolValue;
00283                 ss >> boolValue;
00284                 if(name == "true")
00285                     boolValue = true;
00286                 else if(name == "false")
00287                     boolValue = false;
00288                 if(ss.fail() == false || name == "true" || name == "false") {
00289                     if(boolValue)
00290                         name = "true";
00291                     else
00292                         name = "false";
00293                     terminal->setValue(&boolValue);
00294                 }
00295                 break;
00296             case Primitives::Char:
00297                 char charValue;
00298                 ss >> charValue;
00299                 if(ss.fail() == false) 
00300                     terminal->setValue(&charValue);
00301                 break;
00302             case Primitives::String:
00303                 std::string stringValue;
00304                 ss >> stringValue;
00305                 if(ss.fail() == false) 
00306                     terminal->setValue(&stringValue);
00307                 break;
00308         }
00309         terminal->setName(name);
00310         primitiveSet_->addTerminal(terminal);
00311         
00312     }
00313 
00314     if(primitiveSet_->getTerminalSetSize() == 0) {
00315         ECF_LOG_ERROR(state_, "Tree: Empty terminal set!");
00316         throw("");
00317     }
00318 
00319     // read tree depth constraints, store in hometree
00320     sptr = getParameterValue(state_, "maxdepth");
00321     hometree->maxDepth_ = *((uint*) sptr.get());
00322     sptr = getParameterValue(state_, "mindepth");
00323     hometree->minDepth_ = *((uint*) sptr.get());
00324     if(hometree->maxDepth_ < hometree->minDepth_ || hometree->maxDepth_ < 1) {
00325         ECF_LOG_ERROR(state_, "Tree genotype: invalid values for max and min tree depth!");
00326         throw("");
00327     }
00328 
00329     hometree->initMaxDepth_ = hometree->maxDepth_;
00330     if(isParameterDefined(state_, "initmaxdepth")) {
00331         sptr = getParameterValue(state_, "initmaxdepth");
00332         hometree->initMaxDepth_ = *((uint*) sptr.get());
00333     }
00334     hometree->initMinDepth_ = hometree->minDepth_;
00335     if(isParameterDefined(state_, "initmindepth")) {
00336         sptr = getParameterValue(state_, "initmindepth");
00337         hometree->initMinDepth_ = *((uint*) sptr.get());
00338     }
00339     if(hometree->initMaxDepth_ < hometree->initMinDepth_ || hometree->initMaxDepth_ < 1) {
00340         ECF_LOG_ERROR(state_, "Tree genotype: invalid values for initial max and min tree depth!");
00341         throw("");
00342     }
00343     if(hometree->initMaxDepth_ > hometree->maxDepth_) {
00344         ECF_LOG_ERROR(state_, "Tree genotype: initial max depth cannot be greater than evolution max depth!");
00345         throw("");
00346     }
00347 }
00348 
00349 
00356 void Tree::execute(void *result)
00357 {
00358     iNode_ = 0;
00359     this->at(iNode_)->primitive_->execute(result, *this);
00360 }
00361 
00362 
00363 void Tree::addNode(Node *node)
00364 {
00365     this->push_back(static_cast<NodeP> (node));
00366 }
00367 
00368 
00369 void Tree::addNode(NodeP node)
00370 {
00371     this->push_back(node);
00372 }
00373 
00374 
00376 uint Tree::fullBuild(PrimitiveSetP primitiveSet, int myDepth)
00377 {
00378     Node* node = new Node();
00379     node->depth_ = myDepth;
00380 
00381     if(node->depth_ < this->initMaxDepth_) {
00382         node->setPrimitive(primitiveSet->getRandomFunction());
00383         this->addNode(node);
00384     } else {
00385         node->setPrimitive(primitiveSet->getRandomTerminal());
00386         this->addNode(node);
00387     }
00388 
00389     for(int i = 0; i < node->primitive_->getNumberOfArguments(); i++ ) {
00390         node->size_ += fullBuild(primitiveSet, myDepth + 1);
00391     }
00392 
00393     return node->size_;
00394 }
00395 
00396 
00398 uint Tree::growBuild(PrimitiveSetP primitiveSet, int myDepth)
00399 {
00400     Node* node = new Node();
00401     node->depth_ = myDepth;
00402 
00403     if(node->depth_ < this->initMinDepth_) {
00404         node->setPrimitive(primitiveSet->getRandomFunction());
00405         this->addNode(node);
00406     }
00407     else if(node->depth_ < this->initMaxDepth_) {
00408         node->setPrimitive(primitiveSet->getRandomPrimitive());
00409         this->addNode(node);
00410     }
00411     else {
00412         node->setPrimitive(primitiveSet->getRandomTerminal());
00413         this->addNode(node);
00414     }
00415     
00416     for(int i = 0; i < node->primitive_->getNumberOfArguments(); i++) {
00417         node->size_ += growBuild(primitiveSet, myDepth + 1);
00418     }
00419 
00420     return node->size_;
00421 }
00422 
00423 
00429 void Tree::update()
00430 {
00431     this->at(0)->size_ = setSize(0);
00432 
00433     iNode_ = 0;
00434     for(int i = 0; i < this->at(0)->primitive_->getNumberOfArguments(); i++) {
00435         iNode_++;
00436         setDepth(startDepth_ + 1);
00437     }
00438     this->at(0)->depth_ = startDepth_;
00439 }
00440 
00441 
00445 uint Tree::setSize(int iNode)
00446 {
00447     int myNode = iNode;
00448     int mySize = 1;
00449     for(int i = 0; i < this->at(myNode)->primitive_->getNumberOfArguments(); i++) {
00450         int childSize = setSize(iNode + 1);
00451         mySize += childSize;
00452         iNode += childSize;
00453     }
00454     this->at(myNode)->size_ = mySize;
00455     return mySize;
00456 }
00457 
00458 
00462 void Tree::setDepth(int myDepth)
00463 {
00464     int index = iNode_;
00465     int nArgs = this->at( iNode_ )->primitive_->getNumberOfArguments();
00466     for(int i = 0; i < nArgs; i++) {
00467         iNode_++;
00468         setDepth(myDepth + 1);
00469     }
00470     this->at(index)->depth_ = myDepth;
00471 }
00472 
00473 
00477 void Tree::growBuild(PrimitiveSetP primitiveSet)
00478 {
00479     growBuild(primitiveSet, startDepth_);
00480 }
00481 
00482 
00486 void Tree::fullBuild(PrimitiveSetP primitiveSet)
00487 {
00488     fullBuild(primitiveSet, startDepth_);
00489 }
00490 
00491 
00498 void Tree::setTerminalValue(std::string name, void* value)
00499 {
00500     PrimitiveP term = primitiveSet_->getTerminalByName(name);
00501     if(term == PrimitiveP()) {
00502         ECF_LOG_ERROR(state_, "Tree genotype: invalid terminal name referenced in setTerminalValue()!");
00503         throw("");
00504     }
00505 
00506     term->setValue(value);
00507 }
00508 
00509 
00510 void Tree::write(XMLNode& xTree)
00511 {
00512     xTree = XMLNode::createXMLTopNode("Tree");
00513     std::stringstream sValue;
00514     sValue << this->size();
00515     xTree.addAttribute("size", sValue.str().c_str());
00516     
00517     sValue.str("");
00518     for(uint i = 0; i < this->size(); i++) {
00519         sValue << this->at(i)->primitive_->getName() << " ";
00520     }
00521     xTree.addText(sValue.str().c_str());
00522 }
00523 
00524 
00525 void Tree::read(XMLNode& xTree)
00526 {
00527     this->clear();
00528 
00529     XMLCSTR sizeStr = xTree.getAttribute("size");
00530     uint size = str2uint(sizeStr);
00531 
00532     XMLCSTR tree = xTree.getText();
00533     std::stringstream stream;
00534     stream << tree;
00535 
00536     std::vector<PrimitiveP>& primitives = primitiveSet_->primitives_;
00537     std::string primitiveStr;
00538     uint position = 0;
00539 
00540     for(uint iNode = 0; iNode < size; iNode++) {
00541         stream >> primitiveStr;
00542         Node* node = new Node();
00543 
00544         // 'regular' primitives
00545         PrimitiveP prim = primitiveSet_->getPrimitiveByName(primitiveStr);
00546         if(prim != PrimitiveP()) {
00547             node->setPrimitive(prim);
00548             this->addNode(node);
00549             continue;
00550         }
00551 
00552         // ERCs
00553         // (TODO: include user defined ERC types)
00554         PrimitiveP erc;
00555         std::string prefix = primitiveStr.substr(0, 2);
00556         std::string value = primitiveStr.substr(2);
00557         std::stringstream ss;
00558         ss << value;
00559         if(prefix == DBL_PREFIX) {
00560             erc = (PrimitiveP) (new Primitives::ERCD);
00561             double v;
00562             ss >> v;
00563             erc->setValue(&v);
00564         }
00565         else if(prefix == INT_PREFIX) {
00566             erc = (PrimitiveP) (new Primitives::ERC<int>);
00567             int v;
00568             ss >> v;
00569             erc->setValue(&v);
00570         }
00571         else if(prefix == BOOL_PREFIX) {
00572             erc = (PrimitiveP) (new Primitives::ERC<bool>);
00573             bool v;
00574             ss >> v;
00575             erc->setValue(&v);
00576         }
00577         else if(prefix == CHR_PREFIX) {
00578             erc = (PrimitiveP) (new Primitives::ERC<char>);
00579             char v;
00580             ss >> v;
00581             erc->setValue(&v);
00582         }
00583         else if(prefix == STR_PREFIX) {
00584             erc = (PrimitiveP) (new Primitives::ERC<std::string>);
00585             std::string v;
00586             ss >> v;
00587             erc->setValue(&v);
00588         }
00589         else {
00590             ECF_LOG_ERROR(state_, "Tree genotype: undefined primitive (" + primitiveStr + ")!");
00591             throw("");
00592         }
00593         erc->setName(primitiveStr);
00594         node->primitive_ = erc;
00595         this->addNode(node);
00596     }
00597 
00598     // set node depths and sizes
00599     this->update();
00600 }
00601 
00602 }

Generated on Fri Jul 5 2013 09:34:23 for ECF by  doxygen 1.7.1