00001 #include "../ECF_base.h"
00002 #include "Tree.h"
00003 #include <iostream>
00004 #include <sstream>
00005 #include <cmath>
00006 #include <sstream>
00007
00008
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
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 "maximum tree depth (default: 5)");
00102 registerParameter(state, "mindepth", (voidP) (new uint(1)), ECF::UINT,
00103 "minimum tree depth (default: 1)");
00104 registerParameter(state, "initmaxdepth", (voidP) (new uint(5)), ECF::UINT,
00105 "maximum initial tree depth (default: 5)");
00106 registerParameter(state, "initmindepth", (voidP) (new uint(1)), ECF::UINT,
00107 "minimum initial tree depth (default: 1)");
00108 registerParameter(state, "functionset", (voidP) (new std::string), ECF::STRING,
00109 "set of functional tree elements (mandatory)");
00110 registerParameter(state, "terminalset", (voidP) (new std::string), ECF::STRING,
00111 "set of terminal tree elements (mandatory)");
00112 }
00113
00114
00115 bool Tree::initialize(StateP state)
00116 {
00117
00118
00119 Tree* hometree = (Tree*) state->getGenotypes()[genotypeId_].get();
00120 state_ = state;
00121
00122
00123 if(!hometree->primitiveSet_)
00124 initializeFirst(hometree);
00125
00126
00127 this->primitiveSet_ = hometree->primitiveSet_;
00128 initMaxDepth_ = hometree->initMaxDepth_;
00129 initMinDepth_ = hometree->initMinDepth_;
00130 maxDepth_ = hometree->maxDepth_;
00131 minDepth_ = hometree->minDepth_;
00132
00133
00134 if(state->getRandomizer()->getRandomInteger(0, 1) % 2 == 0)
00135 fullBuild(primitiveSet_);
00136 else
00137 growBuild(primitiveSet_);
00138
00139 return true;
00140 }
00141
00142
00149 void Tree::initializeFirst(Tree* hometree)
00150 {
00151
00152 hometree->primitiveSet_ = (PrimitiveSetP) (new PrimitiveSet);
00153 hometree->primitiveSet_->initialize(state_);
00154 this->primitiveSet_ = hometree->primitiveSet_;
00155
00156
00157 for(int i = 0; i < (int) userFunctions_.size(); i++) {
00158 primitiveSet_->mAllPrimitives_[userFunctions_[i]->getName()] = userFunctions_[i];
00159 primitiveSet_->mAllPrimitives_[userFunctions_[i]->getName()]->initialize(state_);
00160 }
00161
00162
00163 voidP sptr = getParameterValue(state_, "functionset");
00164 std::stringstream names;
00165 std::string name;
00166 names << *((std::string*) sptr.get());
00167 while(names >> name) {
00168 if(!primitiveSet_->addFunction(name)) {
00169 ECF_LOG_ERROR(state_, "Error: unknown function in function set (\'" + name + "\')!");
00170 throw("");
00171 }
00172 }
00173 if(primitiveSet_->getFunctionSetSize() == 0) {
00174 ECF_LOG_ERROR(state_, "Tree genotype: empty function set!");
00175 throw("");
00176 }
00177
00178
00179 Primitives::terminal_type currentType = Primitives::Double;
00180 type_iter typeIter;
00181
00182
00183 std::stringstream tNames;
00184 sptr = getParameterValue(state_, "terminalset");
00185 tNames << *((std::string*) sptr.get());
00186
00187 while(tNames >> name)
00188 {
00189
00190 typeIter = primitiveSet_->mTypeNames_.find(name);
00191 if(typeIter != primitiveSet_->mTypeNames_.end()) {
00192 currentType = typeIter->second;
00193 continue;
00194 }
00195
00196
00197 uint iTerminal = 0;
00198 for(; iTerminal < userTerminals_.size(); iTerminal++)
00199 if(userTerminals_[iTerminal]->getName() == name)
00200 break;
00201 if(iTerminal < userTerminals_.size()) {
00202 userTerminals_[iTerminal]->initialize(state_);
00203 primitiveSet_->addTerminal(userTerminals_[iTerminal]);
00204 continue;
00205 }
00206
00207
00208
00209
00210 if(name[0] == '[' || name[0] == '{') {
00211
00212 std::string ercValues = "";
00213
00214
00215 PrimitiveP erc;
00216 switch(currentType) {
00217 case Primitives::Double:
00218 erc = (PrimitiveP) (new Primitives::ERCD);
00219 ercValues = DBL_PREFIX;
00220 break;
00221 case Primitives::Int:
00222 erc = (PrimitiveP) (new Primitives::ERC<int>);
00223 ercValues = INT_PREFIX;
00224 break;
00225 case Primitives::Bool:
00226 erc = (PrimitiveP) (new Primitives::ERC<bool>);
00227 ercValues = BOOL_PREFIX;
00228 break;
00229 case Primitives::Char:
00230 erc = (PrimitiveP) (new Primitives::ERC<char>);
00231 ercValues = CHR_PREFIX;
00232 break;
00233 case Primitives::String:
00234 erc = (PrimitiveP) (new Primitives::ERC<std::string>);
00235 ercValues = STR_PREFIX;
00236 break;
00237 }
00238
00239 while(name[name.size() - 1] != ']' && name[name.size() - 1] != '}') {
00240 ercValues += " " + name;
00241 tNames >> name;
00242 }
00243 ercValues += " " + name;
00244
00245
00246 erc->setName(ercValues);
00247 erc->initialize(state_);
00248 primitiveSet_->addTerminal(erc);
00249
00250 continue;
00251 }
00252
00253
00254
00255 PrimitiveP terminal;
00256 switch(currentType)
00257 {
00258 case Primitives::Double:
00259 terminal = (PrimitiveP) (new Primitives::Terminal); break;
00260 case Primitives::Int:
00261 terminal = (PrimitiveP) (new Primitives::TerminalT<int>); break;
00262 case Primitives::Bool:
00263 terminal = (PrimitiveP) (new Primitives::TerminalT<bool>); break;
00264 case Primitives::Char:
00265 terminal = (PrimitiveP) (new Primitives::TerminalT<char>); break;
00266 case Primitives::String:
00267 terminal = (PrimitiveP) (new Primitives::TerminalT<std::string>); break;
00268 }
00269
00270
00271
00272 std::istringstream ss(name);
00273 switch(currentType)
00274 {
00275 case Primitives::Double:
00276 double dblValue;
00277 ss >> dblValue;
00278 if(ss.fail() == false)
00279 terminal->setValue(&dblValue);
00280 break;
00281 case Primitives::Int:
00282 int intValue;
00283 ss >> intValue;
00284 if(ss.fail() == false)
00285 terminal->setValue(&intValue);
00286 break;
00287 case Primitives::Bool:
00288 bool boolValue;
00289 ss >> boolValue;
00290 if(name == "true")
00291 boolValue = true;
00292 else if(name == "false")
00293 boolValue = false;
00294 if(ss.fail() == false || name == "true" || name == "false") {
00295 if(boolValue)
00296 name = "true";
00297 else
00298 name = "false";
00299 terminal->setValue(&boolValue);
00300 }
00301 break;
00302 case Primitives::Char:
00303 char charValue;
00304 ss >> charValue;
00305 if(ss.fail() == false)
00306 terminal->setValue(&charValue);
00307 break;
00308 case Primitives::String:
00309 std::string stringValue;
00310 ss >> stringValue;
00311 if(ss.fail() == false)
00312 terminal->setValue(&stringValue);
00313 break;
00314 }
00315 terminal->setName(name);
00316 primitiveSet_->addTerminal(terminal);
00317
00318 }
00319
00320 if(primitiveSet_->getTerminalSetSize() == 0) {
00321 ECF_LOG_ERROR(state_, "Tree: Empty terminal set!");
00322 throw("");
00323 }
00324
00325
00326 sptr = getParameterValue(state_, "maxdepth");
00327 hometree->maxDepth_ = *((uint*) sptr.get());
00328 sptr = getParameterValue(state_, "mindepth");
00329 hometree->minDepth_ = *((uint*) sptr.get());
00330 if(hometree->maxDepth_ < hometree->minDepth_ || hometree->maxDepth_ < 1) {
00331 ECF_LOG_ERROR(state_, "Tree genotype: invalid values for max and min tree depth!");
00332 throw("");
00333 }
00334
00335 hometree->initMaxDepth_ = hometree->maxDepth_;
00336 if(isParameterDefined(state_, "initmaxdepth")) {
00337 sptr = getParameterValue(state_, "initmaxdepth");
00338 hometree->initMaxDepth_ = *((uint*) sptr.get());
00339 }
00340 hometree->initMinDepth_ = hometree->minDepth_;
00341 if(isParameterDefined(state_, "initmindepth")) {
00342 sptr = getParameterValue(state_, "initmindepth");
00343 hometree->initMinDepth_ = *((uint*) sptr.get());
00344 }
00345 if(hometree->initMaxDepth_ < hometree->initMinDepth_ || hometree->initMaxDepth_ < 1) {
00346 ECF_LOG_ERROR(state_, "Tree genotype: invalid values for initial max and min tree depth!");
00347 throw("");
00348 }
00349 if(hometree->initMaxDepth_ > hometree->maxDepth_) {
00350 ECF_LOG_ERROR(state_, "Tree genotype: initial max depth cannot be greater than evolution max depth!");
00351 throw("");
00352 }
00353 }
00354
00355
00362 void Tree::execute(void *result)
00363 {
00364 iNode_ = 0;
00365 this->at(iNode_)->primitive_->execute(result, *this);
00366 }
00367
00368
00369 void Tree::addNode(Node *node)
00370 {
00371 this->push_back(static_cast<NodeP> (node));
00372 }
00373
00374
00375 void Tree::addNode(NodeP node)
00376 {
00377 this->push_back(node);
00378 }
00379
00380
00382 uint Tree::fullBuild(PrimitiveSetP primitiveSet, int myDepth)
00383 {
00384 Node* node = new Node();
00385 node->depth_ = myDepth;
00386
00387 if(node->depth_ < this->initMaxDepth_) {
00388 node->setPrimitive(primitiveSet->getRandomFunction());
00389 this->addNode(node);
00390 } else {
00391 node->setPrimitive(primitiveSet->getRandomTerminal());
00392 this->addNode(node);
00393 }
00394
00395 for(int i = 0; i < node->primitive_->getNumberOfArguments(); i++ ) {
00396 node->size_ += fullBuild(primitiveSet, myDepth + 1);
00397 }
00398
00399 return node->size_;
00400 }
00401
00402
00404 uint Tree::growBuild(PrimitiveSetP primitiveSet, int myDepth)
00405 {
00406 Node* node = new Node();
00407 node->depth_ = myDepth;
00408
00409 if(node->depth_ < this->initMinDepth_) {
00410 node->setPrimitive(primitiveSet->getRandomFunction());
00411 this->addNode(node);
00412 }
00413 else if(node->depth_ < this->initMaxDepth_) {
00414 node->setPrimitive(primitiveSet->getRandomPrimitive());
00415 this->addNode(node);
00416 }
00417 else {
00418 node->setPrimitive(primitiveSet->getRandomTerminal());
00419 this->addNode(node);
00420 }
00421
00422 for(int i = 0; i < node->primitive_->getNumberOfArguments(); i++) {
00423 node->size_ += growBuild(primitiveSet, myDepth + 1);
00424 }
00425
00426 return node->size_;
00427 }
00428
00429
00435 void Tree::update()
00436 {
00437 this->at(0)->size_ = setSize(0);
00438
00439 iNode_ = 0;
00440 for(int i = 0; i < this->at(0)->primitive_->getNumberOfArguments(); i++) {
00441 iNode_++;
00442 setDepth(startDepth_ + 1);
00443 }
00444 this->at(0)->depth_ = startDepth_;
00445 }
00446
00447
00451 uint Tree::setSize(int iNode)
00452 {
00453 int myNode = iNode;
00454 int mySize = 1;
00455 for(int i = 0; i < this->at(myNode)->primitive_->getNumberOfArguments(); i++) {
00456 int childSize = setSize(iNode + 1);
00457 mySize += childSize;
00458 iNode += childSize;
00459 }
00460 this->at(myNode)->size_ = mySize;
00461 return mySize;
00462 }
00463
00464
00468 void Tree::setDepth(int myDepth)
00469 {
00470 int index = iNode_;
00471 int nArgs = this->at( iNode_ )->primitive_->getNumberOfArguments();
00472 for(int i = 0; i < nArgs; i++) {
00473 iNode_++;
00474 setDepth(myDepth + 1);
00475 }
00476 this->at(index)->depth_ = myDepth;
00477 }
00478
00479
00483 void Tree::growBuild(PrimitiveSetP primitiveSet)
00484 {
00485 growBuild(primitiveSet, startDepth_);
00486 }
00487
00488
00492 void Tree::fullBuild(PrimitiveSetP primitiveSet)
00493 {
00494 fullBuild(primitiveSet, startDepth_);
00495 }
00496
00497
00504 void Tree::setTerminalValue(std::string name, void* value)
00505 {
00506 PrimitiveP term = primitiveSet_->getTerminalByName(name);
00507 if(term == PrimitiveP()) {
00508 ECF_LOG_ERROR(state_, "Tree genotype: invalid terminal name referenced in setTerminalValue()!");
00509 throw("");
00510 }
00511
00512 term->setValue(value);
00513 }
00514
00515
00522 void Tree::getTerminalValue(std::string name, void* value)
00523 {
00524 PrimitiveP term = primitiveSet_->getTerminalByName(name);
00525 if(term == PrimitiveP()) {
00526 ECF_LOG_ERROR(state_, "Tree genotype: invalid terminal name referenced in getTerminalValue()!");
00527 throw("");
00528 }
00529
00530 term->getValue(value);
00531 }
00532
00533
00534
00535 void Tree::write(XMLNode& xTree)
00536 {
00537 xTree = XMLNode::createXMLTopNode("Tree");
00538 std::stringstream sValue;
00539 sValue << this->size();
00540 xTree.addAttribute("size", sValue.str().c_str());
00541
00542 sValue.str("");
00543 for(uint i = 0; i < this->size(); i++) {
00544 sValue << this->at(i)->primitive_->getName() << " ";
00545 }
00546 xTree.addText(sValue.str().c_str());
00547 }
00548
00549
00550 void Tree::read(XMLNode& xTree)
00551 {
00552 this->clear();
00553
00554 XMLCSTR sizeStr = xTree.getAttribute("size");
00555 uint size = str2uint(sizeStr);
00556
00557 XMLCSTR tree = xTree.getText();
00558 std::stringstream stream;
00559 stream << tree;
00560
00561 std::vector<PrimitiveP>& primitives = primitiveSet_->primitives_;
00562 std::string primitiveStr;
00563 uint position = 0;
00564
00565 for(uint iNode = 0; iNode < size; iNode++) {
00566 stream >> primitiveStr;
00567 Node* node = new Node();
00568
00569
00570 PrimitiveP prim = primitiveSet_->getPrimitiveByName(primitiveStr);
00571 if(prim != PrimitiveP()) {
00572 node->setPrimitive(prim);
00573 this->addNode(node);
00574 continue;
00575 }
00576
00577
00578
00579 PrimitiveP erc;
00580 std::string prefix = primitiveStr.substr(0, 2);
00581 std::string value = primitiveStr.substr(2);
00582 std::stringstream ss;
00583 ss << value;
00584 if(prefix == DBL_PREFIX) {
00585 erc = (PrimitiveP) (new Primitives::ERCD);
00586 double v;
00587 ss >> v;
00588 erc->setValue(&v);
00589 }
00590 else if(prefix == INT_PREFIX) {
00591 erc = (PrimitiveP) (new Primitives::ERC<int>);
00592 int v;
00593 ss >> v;
00594 erc->setValue(&v);
00595 }
00596 else if(prefix == BOOL_PREFIX) {
00597 erc = (PrimitiveP) (new Primitives::ERC<bool>);
00598 bool v;
00599 ss >> v;
00600 erc->setValue(&v);
00601 }
00602 else if(prefix == CHR_PREFIX) {
00603 erc = (PrimitiveP) (new Primitives::ERC<char>);
00604 char v;
00605 ss >> v;
00606 erc->setValue(&v);
00607 }
00608 else if(prefix == STR_PREFIX) {
00609 erc = (PrimitiveP) (new Primitives::ERC<std::string>);
00610 std::string v;
00611 ss >> v;
00612 erc->setValue(&v);
00613 }
00614 else {
00615 ECF_LOG_ERROR(state_, "Tree genotype: undefined primitive (" + primitiveStr + ")!");
00616 throw("");
00617 }
00618 erc->setName(primitiveStr);
00619 node->primitive_ = erc;
00620 this->addNode(node);
00621 }
00622
00623
00624 this->update();
00625 }
00626
00627 }