Source Code for Module buildtree

  1  """ 
  2  buildtree 
  3  ========= 
  4  Contains strongly-typed versions of Koza-based tree building methods. 
  5  The buildTree() method is the constructor for a tree and contains the 
  6  relevant functions. 
  7   
  8  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
  9  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 10  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 11  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 12  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
 13  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 
 14  THE SOFTWARE. 
 15   
 16  @author: by Mehdi Khoury 
 17  @version: 1.20 
 18  @copyright: (c) 2009 Mehdi Khoury under the mit license 
 19  http://www.opensource.org/licenses/mit-license.html 
 20  @contact: mehdi.khoury at gmail.com 
 21   
 22   
 23   
 24  """ 
 25  import random 
 26  import settings 
 27  from collections import deque 
 28  import psyco 
 29  import timeit 
 30   
 31   
 32  # Exceptions related to tree building 
 33 -class TreeBuildingError(Exception): pass 
 34 -class NoTerminalSet(TreeBuildingError): pass 
 35 -class NoFunctionSet(TreeBuildingError): pass 
 36 -class EmptyOrderedSet(TreeBuildingError): pass 
 37   
 38   
 39  # class that contains methods to build a random tree 
 40   
 41  psyco.profile() 
 42   
 43   
 44   
 45 -class buildTree(): 
 46      """ 
 47      implement tree building methods described in Koza I/II. 
 48      The buildTree() method is the constructor for a tree and contains the 
 49      relevant functions. 
 50       
 51      """ 
 52           
 53 -    def setRandomLeafChild(self,parent,child_nb): 
 54          """ 
 55          Function:  setRandomLeafChild 
 56          ============================= 
 57           
 58          Set the a random leaf node 
 59           
 60          @param parent: the parent node (generally a root node) e.g. (0,2,'root') 
 61          @param child_nb: the child node position (0 for first, 1 for second and so on...) 
 62          @return: the random leaf child node e.g. (3,0,'x') 
 63          """  
 64          random_leaf_child=[] 
 65          try: 
 66              random_leaf_child=random.choice(settings.treeRules[parent[2]][child_nb][1]) 
 67          except: 
 68              raise NoTerminalSet, "Empty terminal set! This parent has no leaf node to choose from!" 
 69              exit 
 70          return random_leaf_child 
 71   
 72   
 73   
 74 -    def setRandomBranchChild(self,parent,child_nb): 
 75          """ 
 76          Function:  setRandomBranchChild 
 77          =============================== 
 78           
 79          Set the a random branch node 
 80    
 81          @param parent: the parent node (generally a root node) e.g. (0,2,'root') 
 82          @param child_nb: the child node position (0 for first, 1 for second and so on...) 
 83          @return: the random branch child node e.g. (1,2,'*') 
 84          """  
 85          random_branch_child=[] 
 86          try: 
 87              random_branch_child = random.choice(settings.treeRules[parent[2]][child_nb][0]) 
 88          except: 
 89              raise NoFunctionSet, "Empty function set! This parent has no branch node to choose from!" 
 90              exit 
 91          return random_branch_child 
 92   
 93   
 94   
 95 -    def setRandomBranchWithTerminalSet(self,parent,child_nb): 
 96          """ 
 97          Function:  setRandomBranchWithTerminalSet 
 98          ========================================= 
 99           
100          Set an random branch child node which has terminals 
101    
102          @param parent: the parent node (generally a root node) e.g. (0,2,'root') 
103          @param child_nb: the child node position (0 for first, 1 for second and so on...) 
104          @return: the branch child node e.g. (1,2,'*') 
105          """  
106          constraints = settings.treeRules 
107          if not constraints[parent[2]][child_nb][0]: 
108              raise NoFunctionSet, "Empty function set! Root node has no function to choose from!" 
109              exit 
110          initial = constraints[parent[2]][child_nb][0] 
111          try: 
112              #filter functions (take aways those who don't have a terminal set) 
113              initial = [ x for x in initial if constraints[x[2]][child_nb][1] ] 
114              return random.choice(initial)  
115          except: 
116              # if there are no functions with terminal set, use the other ones 
117              return random.choice(settings.treeRules[parent[2]][child_nb][0]) 
118   
119   
120 -    def setRandomBranchWithFunctionSet(self,parent,child_nb): 
121          """ 
122          Function:  setRandomBranchWithTerminalSet 
123          ========================================= 
124           
125          Set an random branch child node which has terminals 
126    
127          @param parent: the parent node (generally a root node) e.g. (0,2,'root') 
128          @param child_nb: the child node position (0 for first, 1 for second and so on...) 
129          @return: the branch child node e.g. (1,2,'*') 
130          """  
131          constraints = settings.treeRules 
132          if not constraints[parent[2]][child_nb][0]: 
133              raise NoFunctionSet, "Empty function set! Root node has no function to choose from!" 
134              exit 
135          initial = constraints[parent[2]][child_nb][0] 
136          try: 
137              #filter functions (take aways those who don't have a function set) 
138              initial = [ x for x in initial if constraints[x[2]][child_nb][0] ] 
139              return random.choice(initial)  
140          except: 
141              # if there are no functions with function set, use the other ones 
142              return random.choice(settings.treeRules[parent[2]][child_nb][1]) 
143     
144   
145  # The FULL method (see KOZA GP Vol I and II) 
146 -    def AddFullNode(self,parent,depth,maxdepth): 
147          """ 
148          Function:  AddFullNode2 
149          ======================= 
150          Build a tree using Koza Full Algorithm 
151    
152          @param parent: the parent node (generally a root node) e.g. (0,2,'root') 
153          @param depth: starting depth (0 when building a tree from scratch) 
154          @param maxdepth: max tree depth (in principle unlimited - careful with memory limitation through :)) 
155          @return: returns a tree built using Koza Full 
156          """  
157          result = [parent] 
158          myDepth = depth 
159          # stopping condition - when maximum depth is reached 
160          if myDepth == maxdepth: 
161              return parent 
162          # add branch upon branch until before maximum depth, 
163          # then, build leafs 
164          else: 
165                  # if the parent node is a function,  
166               
167                  result = [parent] 
168                  # get the number of children of this function (arity) 
169                  nbChildren = parent[1] 
170                  listdepth =[] 
171                  # for every child 
172                  for i in xrange(nbChildren): 
173                      # add a new depth counter 
174                      listdepth.append(myDepth) 
175                      # if near max depth add a leaf 
176                      if maxdepth-listdepth[i]==1: 
177  #                        try: 
178                              result.append(self.setRandomLeafChild(parent,i)) 
179  #                        except: 
180  #                            try: 
181  #                                result.append(self.AddFullNode(self.setRandomBranchWithTerminalSet(parent,i),listdepth[i]+1,maxdepth)) 
182  #                                listdepth[i] = listdepth[i]+1 
183  #                            except: 
184  #                                result.append(self.AddFullNode(self.setRandomBranchChild(parent,i),listdepth[i]+1,maxdepth)) 
185  #                                listdepth[i] = listdepth[i]+1 
186                      # if 2 nodes from max depth, only use functions which have a terminal set 
187                      elif maxdepth-listdepth[i]==2: 
188                          try: 
189                              result.append(self.AddFullNode(self.setRandomBranchWithTerminalSet(parent,i),listdepth[i]+1,maxdepth)) 
190                              listdepth[i] = listdepth[i]+1 
191                          except: 
192                              try: 
193                                  result.append(self.AddFullNode(self.setRandomBranchChild(parent,i),listdepth[i]+1,maxdepth)) 
194                                  listdepth[i] = listdepth[i]+1 
195                              except: 
196                                  #print parent 
197                                  #print i 
198                                  result.append(self.setRandomLeafChild(parent,i)) 
199                      # else add a branch 
200                      else: 
201                          try: 
202                              result.append(self.AddFullNode(self.setRandomBranchWithFunctionSet(parent,i),listdepth[i]+1,maxdepth)) 
203                              listdepth[i] = listdepth[i]+1 
204                          except: 
205                              try: 
206                                  result.append(self.AddFullNode(self.setRandomBranchChild(parent,i),listdepth[i]+1,maxdepth)) 
207                                  listdepth[i] = listdepth[i]+1 
208                              except: 
209                                  result.append(self.setRandomLeafChild(parent,i)) 
210              
211          return result 
212   
213   
214  # The HALF method (see KOZA GP Vol I and II) 
215 -    def AddGrowNodeMin(self,parent,depth,mindepth,maxdepth): 
216          """ 
217          Function:  AddFullNode2 
218          ======================= 
219          Build a tree using Koza Half Algorithm 
220   
221          @param parent: the parent node (generally a root node) e.g. (0,2,'root') 
222          @param depth: starting depth (0 when building a tree from scratch) 
223          @param mindepth: min tree depth  
224          @param maxdepth: max tree depth (in principle unlimited - careful with memory limitation through :)) 
225          @return: returns a tree built using Koza Full 
226          """  
227          result = [parent] 
228          myDepth = depth 
229          # stopping condition - when maximum depth is reached 
230          if myDepth == maxdepth: 
231              return parent 
232          # add branch upon branch until before maximum depth, 
233          # then, build leafs 
234          else: 
235                  # if the parent node is a function,  
236               
237                  result = [parent] 
238                  # get the number of children of this function (arity) 
239                  nbChildren = parent[1] 
240                  listdepth =[] 
241                  # for every child 
242                  for i in xrange(nbChildren): 
243                      # add a new depth counter 
244                      listdepth.append(myDepth) 
245                      # if near max depth add a leaf 
246                      if maxdepth-listdepth[i]==1: 
247  #                        try: 
248                              result.append(self.setRandomLeafChild(parent,i)) 
249  #                        except: 
250  #                            try: 
251  #                                result.append(self.AddFullNode(self.setRandomBranchWithTerminalSet(parent,i),listdepth[i]+1,maxdepth)) 
252  #                                listdepth[i] = listdepth[i]+1 
253  #                            except: 
254  #                                result.append(self.AddFullNode(self.setRandomBranchChild(parent,i),listdepth[i]+1,maxdepth)) 
255  #                                listdepth[i] = listdepth[i]+1 
256                      # if 2 nodes from max depth, only use functions which have a terminal set 
257                      elif maxdepth-listdepth[i]==2 or depth-mindepth-1<=-1: 
258                          try: 
259                              result.append(self.AddGrowNodeMin(self.setRandomBranchWithTerminalSet(parent,i),listdepth[i]+1,mindepth,maxdepth)) 
260                              #listdepth[i] = listdepth[i]+1 
261                          except: 
262                              try: 
263                                  result.append(self.AddGrowNodeMin(self.setRandomBranchChild(parent,i),listdepth[i]+1,mindepth,maxdepth)) 
264                                  listdepth[i] = listdepth[i]+1 
265                              except: 
266                                  result.append(self.setRandomLeafChild(parent,i)) 
267                      # else in normal cases, add randomly a branch or a leave 
268                      else: 
269                          chosenType = random.randint(0, 1) 
270                          if chosenType: 
271                              result.append(self.AddGrowNodeMin(self.setRandomBranchChild(parent,i),listdepth[i]+1,mindepth,maxdepth)) 
272                              listdepth[i] = listdepth[i]+1 
273                          else: 
274                              result.append(self.setRandomLeafChild(parent,i)) 
275              
276          return result 
277       
278   
279   
280 -    def AddHalfNode(self,parent,depth,mindepth,maxdepth): 
281          """ 
282          Function:  AddHalfNode 
283          ====================== 
284           
285          Build a tree using Koza Ramped Half-n-Half 
286    
287          @param parent: the parent node (generally a root node) e.g. (0,2,'root') 
288          @param depth: starting depth (0 when building a tree from scratch) 
289          @param mindepth: min tree depth (only works with 2 in the present version) 
290          @param maxdepth: max tree depth (in principle unlimited - careful with memory limitation through :)) 
291          @return: returns a tree built using Koza Ramped Half-n-Half 
292          """  
293          #randomDepth = random.randint(mindepth+1, maxdepth) 
294          randomDepth = random.randint(mindepth, maxdepth) 
295          prob = random.random()< 0.5 
296          if prob: 
297              return self.AddFullNode(parent,depth,randomDepth) 
298          else: 
299              return self.AddGrowNodeMin(parent,depth,mindepth,randomDepth) 
300   
301  if __name__ == '__main__': 
302      #print buildTree().setRandomLeafChild((1,2,'*'),1) 
303      #print buildTree().setRandomBranchChild((0,2,'root'),0) 
304      #print buildTree().setRandomBranchWithTerminalSet((0,2,'root'),0) 
305      for i in xrange(10000): 
306          #a=buildTree().AddFullNode((0,3,'root'),0,8)   
307          #print a 
308           
309          #b=buildTree().AddGrowNodeMin((1, 2, 'or'),1,2,10)   
310          #print b 
311           
312          c=buildTree().AddHalfNode((0,2,'root'),0,2,10)   
313       
314          print c 
315   
316   
317      #t = timeit.Timer("buildtree.buildTree().AddFullNode((0,1,'root'),0,8)","import buildtree") 
318      #print t.repeat(1,10000) 
319