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 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
00112
00113 Tree* hometree = (Tree*) state->getGenotypes()[genotypeId_].get();
00114 state_ = state;
00115
00116
00117 if(!hometree->primitiveSet_)
00118 initializeFirst(hometree);
00119
00120
00121 this->primitiveSet_ = hometree->primitiveSet_;
00122 initMaxDepth_ = hometree->initMaxDepth_;
00123 initMinDepth_ = hometree->initMinDepth_;
00124 maxDepth_ = hometree->maxDepth_;
00125 minDepth_ = hometree->minDepth_;
00126
00127
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
00146 hometree->primitiveSet_ = (PrimitiveSetP) (new PrimitiveSet);
00147 hometree->primitiveSet_->initialize(state_);
00148 this->primitiveSet_ = hometree->primitiveSet_;
00149
00150
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
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
00173 Primitives::terminal_type currentType = Primitives::Double;
00174 type_iter typeIter;
00175
00176
00177 std::stringstream tNames;
00178 sptr = getParameterValue(state_, "terminalset");
00179 tNames << *((std::string*) sptr.get());
00180
00181 while(tNames >> name)
00182 {
00183
00184 typeIter = primitiveSet_->mTypeNames_.find(name);
00185 if(typeIter != primitiveSet_->mTypeNames_.end()) {
00186 currentType = typeIter->second;
00187 continue;
00188 }
00189
00190
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
00203
00204 if(name[0] == '[' || name[0] == '{') {
00205
00206 std::string ercValues = "";
00207
00208
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
00240 erc->setName(ercValues);
00241 erc->initialize(state_);
00242 primitiveSet_->addTerminal(erc);
00243
00244 continue;
00245 }
00246
00247
00248
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
00265
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
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
00545 PrimitiveP prim = primitiveSet_->getPrimitiveByName(primitiveStr);
00546 if(prim != PrimitiveP()) {
00547 node->setPrimitive(prim);
00548 this->addNode(node);
00549 continue;
00550 }
00551
00552
00553
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
00599 this->update();
00600 }
00601
00602 }