EvolvingObjects
eoParseTreeDepthInit.h
00001 // -*- mode: c++; c-indent-level: 4; c++-member-init-indent: 8; comment-column: 35; -*-
00002 
00003 //-----------------------------------------------------------------------------
00004 // eoParseTreeDepthInit.h : initializor for eoParseTree class
00005 // (c) Maarten Keijzer 2000  Jeroen Eggermont 2002
00006 /*
00007     This library is free software; you can redistribute it and/or
00008     modify it under the terms of the GNU Lesser General Public
00009     License as published by the Free Software Foundation; either
00010     version 2 of the License, or (at your option) any later version.
00011 
00012     This library is distributed in the hope that it will be useful,
00013     but WITHOUT ANY WARRANTY; without even the implied warranty of
00014     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015     Lesser General Public License for more details.
00016 
00017     You should have received a copy of the GNU Lesser General Public
00018     License along with this library; if not, write to the Free Software
00019     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00020 
00021     Contact: todos@geneura.ugr.es, http://geneura.ugr.es
00022              mak@dhi.dk
00023              jeggermo@liacs.nl
00024 
00025  */
00026 //-----------------------------------------------------------------------------
00027 
00028 #ifndef eoParseTreeDepthInit_h
00029 #define eoParseTreeDepthInit_h
00030 
00031 #include <EO.h>
00032 #include <gp/eoParseTree.h>
00033 #include <eoInit.h>
00034 #include <eoOp.h>
00035 #include <eoPop.h>
00036 
00037 using namespace gp_parse_tree;
00038 
00044 // eoGpDepthInitializer is defined for backward compatibility
00045 #define eoGpDepthInitializer eoParseTreeDepthInit
00046 
00047 template <class FType, class Node>
00048 class eoParseTreeDepthInit : public eoInit< eoParseTree<FType, Node> >
00049 {
00050     protected:
00051         // a binary predicate for sorting
00052         // hopefully this will work with M$VC++ 6.0
00053         struct lt_arity:public std::binary_function<Node,Node,bool>
00054         {
00055                 bool operator()(const Node &_node1, const Node &_node2) { return (_node1.arity() < _node2.arity());};
00056         };
00057 
00058     public :
00059 
00060     typedef eoParseTree<FType, Node> EoType;
00061 
00069         eoParseTreeDepthInit(
00070         unsigned _max_depth,
00071         const std::vector<Node>& _initializor,
00072         bool _grow = true,
00073         bool _ramped_half_and_half = false)
00074             :
00075             eoInit<EoType>(),
00076                         max_depth(_max_depth),
00077                         initializor(_initializor),
00078                         grow(_grow),
00079                         ramped_half_and_half(_ramped_half_and_half),
00080                         current_depth(_max_depth)
00081     {
00082       if(initializor.empty())
00083       {
00084         throw std::logic_error("eoParseTreeDepthInit: uhm, wouldn't you rather give a non-empty set of Nodes?");
00085       }
00086       // lets sort the initializor std::vector according to  arity (so we can be sure the terminals are in front)
00087       // we use stable_sort so that if element i was in front of element j and they have the same arity i remains in front of j
00088       stable_sort(initializor.begin(), initializor.end(), lt_arity());
00089     }
00091         virtual std::string className() const { return "eoParseTreeDepthInit"; };
00092 
00096     void operator()(EoType& _tree)
00097         {
00098         std::list<Node> sequence;
00099         generate(sequence, current_depth);
00100 
00101         parse_tree<Node> tmp(sequence.begin(), sequence.end());
00102         _tree.swap(tmp);
00103 
00104         if(ramped_half_and_half)
00105         {
00106                 if(grow)
00107                 {
00108                         if (current_depth > 2)
00109                                 current_depth--;
00110                         else
00111                                 current_depth = max_depth;
00112                 }
00113                 // change the grow method from 'grow' to 'full' or from 'full' to 'grow'
00114                 grow = !grow;
00115         };
00116 
00117         }
00118    private :
00119     void generate(std::list<Node>& sequence, int the_max, int last_terminal = -1)
00120     {
00121             if (last_terminal == -1)
00122             { // check where the last terminal in the sequence resides
00123             typename std::vector<Node>::iterator it;
00124                     for (it = initializor.begin(); it != initializor.end(); ++it)
00125                     {
00126                             if (it->arity() > 0)
00127                                     break;
00128                     }
00129 
00130                     last_terminal = it - initializor.begin();
00131             }
00132 
00133             if (the_max == 1)
00134             { // generate terminals only
00135                     typename std::vector<Node>::iterator it = initializor.begin() + rng.random(last_terminal);
00136                     it->randomize();
00137                     sequence.push_front(*it);
00138                     return;
00139             }
00140 
00141             typename std::vector<Node>::iterator what_it;
00142 
00143             if (grow)
00144             {
00145                     what_it = initializor.begin() + rng.random(initializor.size());
00146             }
00147             else // full
00148             {
00149                     what_it = initializor.begin() + last_terminal + rng.random(initializor.size() - last_terminal);
00150             }
00151 
00152         what_it->randomize();
00153 
00154             sequence.push_front(*what_it);
00155 
00156             for (int i = 0; i < what_it->arity(); ++i)
00157                     generate(sequence, the_max - 1, last_terminal);
00158     }
00159 
00160 
00161 
00162         unsigned max_depth;
00163         std::vector<Node> initializor;
00164         bool grow;
00165         bool ramped_half_and_half;
00166         unsigned current_depth;
00167 };
00168 
00178 template <class FType, class Node>
00179 void  eoInitRampedHalfAndHalf(eoPop< eoParseTree<FType,Node> > &pop, unsigned int population_size, unsigned int init_max_depth, std::vector<Node> &initializor)
00180 {
00181         typedef eoParseTree<FType,Node> EoType;
00182         typedef eoPop< EoType > Pop;
00183 
00184         unsigned int M = init_max_depth - 1;
00185         unsigned int part_pop_size = population_size / (2*M);
00186         unsigned int m=0;
00187 
00188         std::cerr << "EO WARNING: Ramped Half and Half Initialization is now supported by eoParseTreeDepthInit." << std::endl;
00189         std::cerr << "            This function is now obsolete and might be removed in the future so you should"<< std::endl;
00190         std::cerr << "            update your code to use: " << std::endl << std::endl;
00191         std::cerr << "            eoParseTreeDepthInit( _max_depth, _initializer, bool _grow, bool _ramped_half_and_half)" << std::endl << std::endl;
00192 
00193         pop.clear();
00194 
00195         // initialize with Depth's (D) -> 2
00196         for(m=init_max_depth; m >= 2; m--)
00197         {
00198                 eoParseTreeDepthInit<FType, Node> grow_initializer(m, initializor, true);
00199                 Pop grow(part_pop_size, grow_initializer);
00200                 pop.insert(pop.begin(), grow.begin(), grow.end());
00201 
00202                 eoParseTreeDepthInit<FType, Node> full_initializer(m, initializor, false);
00203                 Pop full(part_pop_size, full_initializer);
00204                 pop.insert(pop.begin(), full.begin(), full.end());
00205         }
00206 
00207         bool g = true;
00208         while (pop.size() < population_size)
00209         {
00210                 eoParseTreeDepthInit<FType, Node> initializer(init_max_depth, initializor, g);
00211                 Pop p(1, initializer);
00212                 pop.insert(pop.begin(), p.begin(), p.end());
00213                 g= !g;
00214         }
00215 }
00216 
00217 
00218 #endif
 All Classes Namespaces Files Functions Variables Typedefs Friends