eckity.genetic_encodings.gp.tree.tree_individual
This module implements the tree class.
1""" 2This module implements the tree class. 3""" 4 5import logging 6import random 7from numbers import Number 8from typing import Any, Callable, Dict, List, Optional, Tuple, Union 9 10import numpy as np 11 12from eckity.fitness import Fitness, GPFitness 13from eckity.genetic_encodings.gp.tree.tree_node import ( 14 FunctionNode, 15 TerminalNode, 16 TreeNode, 17) 18from eckity.individual import Individual 19 20from .utils import generate_args, get_func_types, get_return_type 21 22logger = logging.getLogger(__name__) 23 24 25class Tree(Individual): 26 """ 27 A tree optimized for genetic programming operations. 28 It is represented by a list of nodes in depth-first order. 29 There are two types of nodes: functions and terminals. 30 31 (tree is not meant as a stand-alone, 32 parameters are supplied through the call from the Tree Creators) 33 """ 34 35 def __init__( 36 self, 37 fitness: Fitness = GPFitness(), 38 function_set: List[Callable] = None, 39 terminal_set: Union[Dict[Any, type], List[Any]] = None, 40 tree: List[TreeNode] = None, 41 erc_range: Optional[ 42 Union[Tuple[float, float], Tuple[int, int]] 43 ] = None, 44 root_type: Optional[type] = None, 45 update_parents: bool = False 46 ): 47 """ 48 GP Tree Individual. 49 50 Parameters 51 ---------- 52 fitness : Fitness 53 Manages fitness state, by default GPFitness 54 function_set: List[Callable], default=None 55 List of functions used as internal nodes in the GP tree. 56 terminal_set : Union[Dict[Any, type], List[Any]], optional 57 Mapping of terminal nodes and their types. 58 In the untyped case, all types are None. 59 Lists are treated as untyped, and will be assigned None. 60 tree : List[TreeNode], optional 61 Actual tree representation, by default None 62 erc_range : tuple of float or int, optional 63 Range of Ephemeral random constant values, by default None 64 root_type: type, optional 65 Root node type, by default None 66 67 Raises 68 ------ 69 ValueError 70 If typed function is used with untyped terminals. 71 """ 72 super().__init__(fitness, update_parents=update_parents) 73 74 self.erc_range = erc_range 75 76 function_set, terminal_set = self._handle_input_types( 77 function_set, terminal_set, root_type 78 ) 79 80 self.function_set = function_set 81 self.terminal_set = terminal_set 82 83 # actual tree representation 84 if tree is None: 85 tree = [] 86 self.tree = tree 87 88 # this is the type of the execution result of the program (tree) 89 self.root_type = root_type 90 91 @property 92 def root(self) -> TreeNode: 93 return self.tree[0] 94 95 @property 96 def erc_type(self) -> Optional[Union[int, float]]: 97 return type(self.erc_range[0]) if self.erc_range else None 98 99 def size(self) -> int: 100 """ 101 Compute size of tree. 102 103 Returns 104 ------- 105 int 106 tree size (= number of nodes). 107 """ 108 return len(self.tree) 109 110 def add_tree(self, node: TreeNode) -> None: 111 """Add a node to the tree following the defined type constrains""" 112 if ( 113 self.size() == 0 and node.node_type == self.root_type 114 ) or self._should_add([0], node): 115 self.tree.append(node) 116 else: 117 raise ValueError(f"Could not add node {node} to tree {self.tree}") 118 119 def _should_add(self, pos: int, new_node: TreeNode) -> bool: 120 """ 121 Recursively find the parent function of the new node and check it 122 matches by type to the expected parameter. (pos is a size-1 list 123 so as to pass "by reference" on successive recursive calls). 124 """ 125 if ( 126 pos[0] == self.size() 127 ): # reached the place the new node should be placed 128 return True 129 130 node = self.tree[pos[0]] 131 res = None 132 if isinstance(node, FunctionNode): 133 func_types = get_func_types(node.function) 134 for i in range(node.n_args): 135 pos[0] += 1 136 res = self._should_add(pos, node) 137 if res: 138 return func_types[i] == new_node.node_type 139 elif res is not None: 140 return res 141 return res 142 143 def empty_tree(self) -> None: 144 self.tree = [] 145 146 def depth(self) -> int: 147 """ 148 Compute depth of tree (maximal path length to a leaf). 149 150 Returns 151 ------- 152 int 153 tree depth. 154 """ 155 return self._depth([0], d=0) 156 157 def _depth(self, pos, d) -> int: 158 """Recursively compute depth 159 (pos is a size-1 list so as to pass "by reference" 160 on successive recursive calls). 161 """ 162 163 node = self.tree[pos[0]] 164 165 depths = [] 166 if isinstance(node, FunctionNode): 167 for _ in range(node.n_args): 168 pos[0] += 1 169 depths.append(1 + self._depth(pos, d + 1)) 170 return max(depths) 171 else: 172 return 0 173 174 def random_function( 175 self, 176 node_type: Optional[type] = None 177 ) -> Optional[FunctionNode]: 178 functions_types = { 179 func: get_return_type(func) for func in self.function_set 180 } 181 relevant_functions = [ 182 func 183 for func in self.function_set 184 if functions_types[func] == node_type 185 ] 186 187 # Return None in case there are no functions of the given type 188 if not relevant_functions: 189 return None 190 191 func = random.choice(relevant_functions) 192 return FunctionNode(func) 193 194 def random_terminal( 195 self, 196 node_type: Optional[type] = None 197 ) -> Optional[TerminalNode]: 198 """Select a random terminal, including constants from ERC range""" 199 relevant_terminals = [ 200 term 201 for term, term_type in self.terminal_set.items() 202 if term_type == node_type 203 ] 204 205 if self.erc_range is not None and ( 206 node_type is None or issubclass(node_type, Number) 207 ): 208 relevant_terminals.append( 209 random.uniform(*self.erc_range) 210 if type(self.erc_range[0]) is float 211 else random.randint(*self.erc_range) 212 ) 213 214 # Return None in case there are no terminals of the given type 215 if not relevant_terminals: 216 return None 217 218 terminal = random.choice(relevant_terminals) 219 220 # erc terminal will be typeless in untyped case, 221 # and int/float in typed case 222 default_type = None if node_type is None else type(terminal) 223 node_type = self.terminal_set.get(terminal, default_type) 224 225 return TerminalNode(terminal, node_type=node_type) 226 227 def execute(self, *args, **kwargs) -> object: 228 """ 229 Execute the program (tree). 230 Input is a numpy array or keyword arguments (but not both). 231 232 Parameters 233 ---------- 234 args : arguments 235 A numpy array. 236 237 kwargs : keyword arguments 238 Input to program, including every variable 239 in the terminal set as a keyword argument. 240 For example, if `terminal_set=['x', 'y', 'z']` 241 then call `execute(x=..., y=..., z=...)`. 242 243 Returns 244 ------- 245 object 246 Result of tree execution. 247 """ 248 249 if not self.tree: 250 raise ValueError("Tree is empty, cannot execute.") 251 252 reshape = False 253 if args: # numpy array -- convert to kwargs 254 try: 255 X = args[0] 256 kwargs = generate_args(X) 257 reshape = True 258 except Exception: 259 raise ValueError( 260 f"Bad argument to tree.execute, " 261 f"must be np array or kwargs: {args}" 262 ) 263 264 kw = list(kwargs.keys()) 265 266 bad_vars = [item for item in kw if item not in self.terminal_set] 267 if len(bad_vars) > 0: 268 raise ValueError( 269 f"received variable arguments not in terminal set: {bad_vars}" 270 ) 271 272 missing_vars = [item for item in self.terminal_set if item not in kw] 273 if len(missing_vars) > 0: 274 raise ValueError( 275 f"Missing variable terminals as execute kwargs: {missing_vars}" 276 ) 277 278 res = self._execute([0], **kwargs) 279 280 if reshape and (isinstance(res, Number) or res.shape == np.shape(0)): 281 # sometimes a tree degenrates to a scalar value 282 res = np.full_like(X[:, 0], res) 283 return res 284 285 def _execute(self, pos, **kwargs): 286 """ 287 Recursively execute the tree by traversing it in a depth-first order 288 (pos is a size-1 list so as to pass "by reference" 289 on successive recursive calls). 290 """ 291 292 node = self.tree[pos[0]] 293 294 if isinstance(node, FunctionNode): 295 arglist = [] 296 for _ in range(node.n_args): 297 pos[0] += 1 298 res = self._execute(pos, **kwargs) 299 arglist.append(res) 300 return node.function(*arglist) 301 else: # terminal 302 if node.value in kwargs: 303 # terminal is a variable, return its value 304 return kwargs[node.value] 305 else: # terminal is a constant 306 return node.value 307 308 def filter_tree(self, filter_func: Callable) -> None: 309 return [node for node in self.tree if filter_func(node)] 310 311 def get_random_numeric_node(self) -> Optional[TerminalNode]: 312 """ 313 Get a random leaf node of the tree. 314 315 Parameters 316 ---------- 317 node_type : type, default=None 318 Type of node to return. 319 320 Returns 321 ------- 322 TreeNode 323 Random leaf node. 324 """ 325 erc_nodes = self.filter_tree( 326 lambda node: isinstance(node, TerminalNode) 327 and isinstance(node.value, Number) 328 ) 329 return random.choice(erc_nodes) if erc_nodes else None 330 331 def random_subtree( 332 self, 333 node_type: Optional[type] = None 334 ) -> Optional[List[TreeNode]]: 335 relevant_nodes = self.filter_tree( 336 lambda node: node.node_type is None # untyped case 337 or ( 338 node_type is None and node != self.root 339 ) # typed case with first invocation 340 or ( 341 node.node_type == node_type and node != self.root 342 ) # typed case with subsequent invocations 343 ) 344 if not relevant_nodes: 345 return None 346 subtree_root = random.choice(relevant_nodes) 347 348 return self._get_subtree_by_root(subtree_root) 349 350 def _get_subtree_by_root(self, subtree_root: TreeNode) -> List[TreeNode]: 351 start_i = self.tree.index(subtree_root) 352 353 if start_i == 0: 354 return self.tree 355 356 end_i = self._find_subtree_end([start_i]) 357 return self.tree[start_i: end_i + 1] 358 359 def replace_subtree( 360 self, old_subtree: List[TreeNode], new_subtree: List[TreeNode] 361 ) -> None: 362 """ 363 Replace the subtree starting at `index` with `subtree` 364 365 Parameters 366 ---------- 367 subtree - new subtree to replace the existing subtree in the tree 368 369 Returns 370 ------- 371 None 372 """ 373 start_i = self.tree.index(old_subtree[0]) 374 end_i = start_i + len(old_subtree) 375 left_part = self.tree[:start_i] 376 right_part = self.tree[end_i:] 377 self.tree = left_part + new_subtree + right_part 378 379 def _find_subtree_end(self, pos): 380 """find index of final node of subtree that starts at `pos` 381 (pos is a size-1 list so as to pass "by reference" on successive recursive calls). 382 """ 383 384 node = self.tree[pos[0]] 385 386 if ( 387 isinstance(node, FunctionNode) 388 and node.function in self.function_set 389 ): 390 for _ in range(node.n_args): 391 pos[0] += 1 392 self._find_subtree_end(pos) 393 394 return pos[0] 395 396 def _handle_input_types( 397 self, 398 function_set: List[Callable], 399 terminal_set: Union[Dict[Any, type], List[str]], 400 root_type: type 401 ): 402 if function_set is None: 403 raise ValueError("Function set must be provided.") 404 405 if terminal_set is None: 406 raise ValueError("Terminal set must be provided.") 407 408 for t in function_set: 409 if not isinstance(t, Callable): 410 raise ValueError( 411 f"Functions must be Callble, but {t} is of type {type(t)}" 412 ) 413 414 if not isinstance(terminal_set, (list, dict)): 415 raise ValueError( 416 "Terminal set must be a list or a dictionary, " 417 f"got {type(terminal_set)}." 418 ) 419 420 # untyped case - convert to dictionary of Nones. 421 if isinstance(terminal_set, list): 422 # check if any function has type hints 423 if any(f.__annotations__ for f in function_set): 424 raise ValueError( 425 "Detected typed function with untyped terminal set. \ 426 Please provide a dictionary with types for terminals." 427 ) 428 429 terminal_set = {t: None for t in terminal_set} 430 return function_set, terminal_set 431 432 # typed case - check every value is a type 433 for v in terminal_set.values(): 434 if not isinstance(v, type): 435 raise ValueError( 436 "Values in terminal set dictionary must be types, " 437 f"but {v} is of type {type(v)}." 438 ) 439 440 function_return_types = { 441 get_return_type(f) for f in function_set 442 } 443 if root_type not in function_return_types: 444 raise ValueError( 445 f"Detected a mismatch between root_type ({root_type}) " 446 f"and function set ({function_set}).\n" 447 f"Root type must be the return type of at least one function." 448 ) 449 if self.erc_type is not None and self.erc_type not in function_return_types: 450 raise ValueError( 451 f"Detected a mismatch between ERC type ({self.erc_type}) " 452 f"and function set ({function_set}).\n" 453 f"ERC range should not be defined if there are no numeric functions." 454 ) 455 456 # check terminals and functions type intersection 457 function_arg_types = { 458 t for func in function_set for t in get_func_types(func)[:-1] 459 } 460 terminal_types = set(terminal_set.values()) 461 462 if self.erc_type: 463 terminal_types.add(self.erc_type) 464 465 if function_arg_types != terminal_types: 466 raise ValueError( 467 f"Function args type hints ({function_arg_types}) " 468 f"must match terminal types ({terminal_types})." 469 ) 470 471 return function_set, terminal_set 472 473 def __str__(self) -> str: 474 """ 475 Return a simple textual representation of the tree. 476 477 Returns 478 ------- 479 str 480 String representation of the tree. 481 482 Examples 483 -------- 484 untyped case: 485 >>> ut = Tree(terminal_set=[x, y, z], function_set=[f_add]) 486 >>> ut.tree = [FunctionNode(f_add), TerminalNode(1), TerminalNode(2)] 487 >>> tree.show() 488 def func_0(x, y, z): 489 return f_add(x, y) 490 491 typed case: 492 >>> tt = Tree(terminal_set={x: float, y: float}, 493 ... function_set=[typed_add]) 494 >>> tt.tree = [FunctionNode(typed_add), 495 ... TerminalNode(1.0, float), 496 ... TerminalNode(2.0, float)] 497 >>> str(tree) 498 def func_0(x: float, y: float) -> float: 499 return typed_add(1.0, 2.0) 500 """ 501 args = ( 502 list(self.terminal_set.keys()) 503 if None in self.terminal_set.values() 504 else [f"{k}: {v.__name__}" for k, v in self.terminal_set.items()] 505 ) 506 ret_type_str = ( 507 "" 508 if None in self.terminal_set.values() 509 else f" -> {self.root.node_type.__name__}" 510 ) 511 512 result = [ 513 f"def func_{str(self.id)}({', '.join(args)}){ret_type_str}:\n return " 514 ] 515 self._str_rec("", [0], result) 516 return "".join(result) 517 518 def _str_rec(self, prefix: str, pos: List[int], result: str) -> str: 519 """Recursively produce a simple textual printout of the tree 520 (pos is a size-1 list so as to pass "by reference" on successive 521 recursive calls). 522 """ 523 524 node = self.tree[pos[0]] 525 if isinstance(node, FunctionNode): 526 result.append(f"{prefix}{str(node)}(\n") 527 prefix = prefix + " " if pos[0] == 0 else prefix 528 for i in range(node.n_args): 529 pos[0] += 1 530 self._str_rec(prefix + " ", pos, result) 531 if i < node.n_args - 1: 532 result.append(",\n") 533 elif 0 < i < node.n_args: 534 result.append("\n") 535 result.append(prefix + ")") 536 else: # terminal 537 result.append(f"{prefix}{str(node)}") 538 539 def show(self): 540 """ 541 Print out a simple textual representation of the tree. 542 543 Returns 544 ------- 545 None. 546 """ 547 logger.info("\n" + str(self)) 548 549 def __repr__(self): 550 return str(self)
logger =
<Logger eckity.genetic_encodings.gp.tree.tree_individual (INFO)>
26class Tree(Individual): 27 """ 28 A tree optimized for genetic programming operations. 29 It is represented by a list of nodes in depth-first order. 30 There are two types of nodes: functions and terminals. 31 32 (tree is not meant as a stand-alone, 33 parameters are supplied through the call from the Tree Creators) 34 """ 35 36 def __init__( 37 self, 38 fitness: Fitness = GPFitness(), 39 function_set: List[Callable] = None, 40 terminal_set: Union[Dict[Any, type], List[Any]] = None, 41 tree: List[TreeNode] = None, 42 erc_range: Optional[ 43 Union[Tuple[float, float], Tuple[int, int]] 44 ] = None, 45 root_type: Optional[type] = None, 46 update_parents: bool = False 47 ): 48 """ 49 GP Tree Individual. 50 51 Parameters 52 ---------- 53 fitness : Fitness 54 Manages fitness state, by default GPFitness 55 function_set: List[Callable], default=None 56 List of functions used as internal nodes in the GP tree. 57 terminal_set : Union[Dict[Any, type], List[Any]], optional 58 Mapping of terminal nodes and their types. 59 In the untyped case, all types are None. 60 Lists are treated as untyped, and will be assigned None. 61 tree : List[TreeNode], optional 62 Actual tree representation, by default None 63 erc_range : tuple of float or int, optional 64 Range of Ephemeral random constant values, by default None 65 root_type: type, optional 66 Root node type, by default None 67 68 Raises 69 ------ 70 ValueError 71 If typed function is used with untyped terminals. 72 """ 73 super().__init__(fitness, update_parents=update_parents) 74 75 self.erc_range = erc_range 76 77 function_set, terminal_set = self._handle_input_types( 78 function_set, terminal_set, root_type 79 ) 80 81 self.function_set = function_set 82 self.terminal_set = terminal_set 83 84 # actual tree representation 85 if tree is None: 86 tree = [] 87 self.tree = tree 88 89 # this is the type of the execution result of the program (tree) 90 self.root_type = root_type 91 92 @property 93 def root(self) -> TreeNode: 94 return self.tree[0] 95 96 @property 97 def erc_type(self) -> Optional[Union[int, float]]: 98 return type(self.erc_range[0]) if self.erc_range else None 99 100 def size(self) -> int: 101 """ 102 Compute size of tree. 103 104 Returns 105 ------- 106 int 107 tree size (= number of nodes). 108 """ 109 return len(self.tree) 110 111 def add_tree(self, node: TreeNode) -> None: 112 """Add a node to the tree following the defined type constrains""" 113 if ( 114 self.size() == 0 and node.node_type == self.root_type 115 ) or self._should_add([0], node): 116 self.tree.append(node) 117 else: 118 raise ValueError(f"Could not add node {node} to tree {self.tree}") 119 120 def _should_add(self, pos: int, new_node: TreeNode) -> bool: 121 """ 122 Recursively find the parent function of the new node and check it 123 matches by type to the expected parameter. (pos is a size-1 list 124 so as to pass "by reference" on successive recursive calls). 125 """ 126 if ( 127 pos[0] == self.size() 128 ): # reached the place the new node should be placed 129 return True 130 131 node = self.tree[pos[0]] 132 res = None 133 if isinstance(node, FunctionNode): 134 func_types = get_func_types(node.function) 135 for i in range(node.n_args): 136 pos[0] += 1 137 res = self._should_add(pos, node) 138 if res: 139 return func_types[i] == new_node.node_type 140 elif res is not None: 141 return res 142 return res 143 144 def empty_tree(self) -> None: 145 self.tree = [] 146 147 def depth(self) -> int: 148 """ 149 Compute depth of tree (maximal path length to a leaf). 150 151 Returns 152 ------- 153 int 154 tree depth. 155 """ 156 return self._depth([0], d=0) 157 158 def _depth(self, pos, d) -> int: 159 """Recursively compute depth 160 (pos is a size-1 list so as to pass "by reference" 161 on successive recursive calls). 162 """ 163 164 node = self.tree[pos[0]] 165 166 depths = [] 167 if isinstance(node, FunctionNode): 168 for _ in range(node.n_args): 169 pos[0] += 1 170 depths.append(1 + self._depth(pos, d + 1)) 171 return max(depths) 172 else: 173 return 0 174 175 def random_function( 176 self, 177 node_type: Optional[type] = None 178 ) -> Optional[FunctionNode]: 179 functions_types = { 180 func: get_return_type(func) for func in self.function_set 181 } 182 relevant_functions = [ 183 func 184 for func in self.function_set 185 if functions_types[func] == node_type 186 ] 187 188 # Return None in case there are no functions of the given type 189 if not relevant_functions: 190 return None 191 192 func = random.choice(relevant_functions) 193 return FunctionNode(func) 194 195 def random_terminal( 196 self, 197 node_type: Optional[type] = None 198 ) -> Optional[TerminalNode]: 199 """Select a random terminal, including constants from ERC range""" 200 relevant_terminals = [ 201 term 202 for term, term_type in self.terminal_set.items() 203 if term_type == node_type 204 ] 205 206 if self.erc_range is not None and ( 207 node_type is None or issubclass(node_type, Number) 208 ): 209 relevant_terminals.append( 210 random.uniform(*self.erc_range) 211 if type(self.erc_range[0]) is float 212 else random.randint(*self.erc_range) 213 ) 214 215 # Return None in case there are no terminals of the given type 216 if not relevant_terminals: 217 return None 218 219 terminal = random.choice(relevant_terminals) 220 221 # erc terminal will be typeless in untyped case, 222 # and int/float in typed case 223 default_type = None if node_type is None else type(terminal) 224 node_type = self.terminal_set.get(terminal, default_type) 225 226 return TerminalNode(terminal, node_type=node_type) 227 228 def execute(self, *args, **kwargs) -> object: 229 """ 230 Execute the program (tree). 231 Input is a numpy array or keyword arguments (but not both). 232 233 Parameters 234 ---------- 235 args : arguments 236 A numpy array. 237 238 kwargs : keyword arguments 239 Input to program, including every variable 240 in the terminal set as a keyword argument. 241 For example, if `terminal_set=['x', 'y', 'z']` 242 then call `execute(x=..., y=..., z=...)`. 243 244 Returns 245 ------- 246 object 247 Result of tree execution. 248 """ 249 250 if not self.tree: 251 raise ValueError("Tree is empty, cannot execute.") 252 253 reshape = False 254 if args: # numpy array -- convert to kwargs 255 try: 256 X = args[0] 257 kwargs = generate_args(X) 258 reshape = True 259 except Exception: 260 raise ValueError( 261 f"Bad argument to tree.execute, " 262 f"must be np array or kwargs: {args}" 263 ) 264 265 kw = list(kwargs.keys()) 266 267 bad_vars = [item for item in kw if item not in self.terminal_set] 268 if len(bad_vars) > 0: 269 raise ValueError( 270 f"received variable arguments not in terminal set: {bad_vars}" 271 ) 272 273 missing_vars = [item for item in self.terminal_set if item not in kw] 274 if len(missing_vars) > 0: 275 raise ValueError( 276 f"Missing variable terminals as execute kwargs: {missing_vars}" 277 ) 278 279 res = self._execute([0], **kwargs) 280 281 if reshape and (isinstance(res, Number) or res.shape == np.shape(0)): 282 # sometimes a tree degenrates to a scalar value 283 res = np.full_like(X[:, 0], res) 284 return res 285 286 def _execute(self, pos, **kwargs): 287 """ 288 Recursively execute the tree by traversing it in a depth-first order 289 (pos is a size-1 list so as to pass "by reference" 290 on successive recursive calls). 291 """ 292 293 node = self.tree[pos[0]] 294 295 if isinstance(node, FunctionNode): 296 arglist = [] 297 for _ in range(node.n_args): 298 pos[0] += 1 299 res = self._execute(pos, **kwargs) 300 arglist.append(res) 301 return node.function(*arglist) 302 else: # terminal 303 if node.value in kwargs: 304 # terminal is a variable, return its value 305 return kwargs[node.value] 306 else: # terminal is a constant 307 return node.value 308 309 def filter_tree(self, filter_func: Callable) -> None: 310 return [node for node in self.tree if filter_func(node)] 311 312 def get_random_numeric_node(self) -> Optional[TerminalNode]: 313 """ 314 Get a random leaf node of the tree. 315 316 Parameters 317 ---------- 318 node_type : type, default=None 319 Type of node to return. 320 321 Returns 322 ------- 323 TreeNode 324 Random leaf node. 325 """ 326 erc_nodes = self.filter_tree( 327 lambda node: isinstance(node, TerminalNode) 328 and isinstance(node.value, Number) 329 ) 330 return random.choice(erc_nodes) if erc_nodes else None 331 332 def random_subtree( 333 self, 334 node_type: Optional[type] = None 335 ) -> Optional[List[TreeNode]]: 336 relevant_nodes = self.filter_tree( 337 lambda node: node.node_type is None # untyped case 338 or ( 339 node_type is None and node != self.root 340 ) # typed case with first invocation 341 or ( 342 node.node_type == node_type and node != self.root 343 ) # typed case with subsequent invocations 344 ) 345 if not relevant_nodes: 346 return None 347 subtree_root = random.choice(relevant_nodes) 348 349 return self._get_subtree_by_root(subtree_root) 350 351 def _get_subtree_by_root(self, subtree_root: TreeNode) -> List[TreeNode]: 352 start_i = self.tree.index(subtree_root) 353 354 if start_i == 0: 355 return self.tree 356 357 end_i = self._find_subtree_end([start_i]) 358 return self.tree[start_i: end_i + 1] 359 360 def replace_subtree( 361 self, old_subtree: List[TreeNode], new_subtree: List[TreeNode] 362 ) -> None: 363 """ 364 Replace the subtree starting at `index` with `subtree` 365 366 Parameters 367 ---------- 368 subtree - new subtree to replace the existing subtree in the tree 369 370 Returns 371 ------- 372 None 373 """ 374 start_i = self.tree.index(old_subtree[0]) 375 end_i = start_i + len(old_subtree) 376 left_part = self.tree[:start_i] 377 right_part = self.tree[end_i:] 378 self.tree = left_part + new_subtree + right_part 379 380 def _find_subtree_end(self, pos): 381 """find index of final node of subtree that starts at `pos` 382 (pos is a size-1 list so as to pass "by reference" on successive recursive calls). 383 """ 384 385 node = self.tree[pos[0]] 386 387 if ( 388 isinstance(node, FunctionNode) 389 and node.function in self.function_set 390 ): 391 for _ in range(node.n_args): 392 pos[0] += 1 393 self._find_subtree_end(pos) 394 395 return pos[0] 396 397 def _handle_input_types( 398 self, 399 function_set: List[Callable], 400 terminal_set: Union[Dict[Any, type], List[str]], 401 root_type: type 402 ): 403 if function_set is None: 404 raise ValueError("Function set must be provided.") 405 406 if terminal_set is None: 407 raise ValueError("Terminal set must be provided.") 408 409 for t in function_set: 410 if not isinstance(t, Callable): 411 raise ValueError( 412 f"Functions must be Callble, but {t} is of type {type(t)}" 413 ) 414 415 if not isinstance(terminal_set, (list, dict)): 416 raise ValueError( 417 "Terminal set must be a list or a dictionary, " 418 f"got {type(terminal_set)}." 419 ) 420 421 # untyped case - convert to dictionary of Nones. 422 if isinstance(terminal_set, list): 423 # check if any function has type hints 424 if any(f.__annotations__ for f in function_set): 425 raise ValueError( 426 "Detected typed function with untyped terminal set. \ 427 Please provide a dictionary with types for terminals." 428 ) 429 430 terminal_set = {t: None for t in terminal_set} 431 return function_set, terminal_set 432 433 # typed case - check every value is a type 434 for v in terminal_set.values(): 435 if not isinstance(v, type): 436 raise ValueError( 437 "Values in terminal set dictionary must be types, " 438 f"but {v} is of type {type(v)}." 439 ) 440 441 function_return_types = { 442 get_return_type(f) for f in function_set 443 } 444 if root_type not in function_return_types: 445 raise ValueError( 446 f"Detected a mismatch between root_type ({root_type}) " 447 f"and function set ({function_set}).\n" 448 f"Root type must be the return type of at least one function." 449 ) 450 if self.erc_type is not None and self.erc_type not in function_return_types: 451 raise ValueError( 452 f"Detected a mismatch between ERC type ({self.erc_type}) " 453 f"and function set ({function_set}).\n" 454 f"ERC range should not be defined if there are no numeric functions." 455 ) 456 457 # check terminals and functions type intersection 458 function_arg_types = { 459 t for func in function_set for t in get_func_types(func)[:-1] 460 } 461 terminal_types = set(terminal_set.values()) 462 463 if self.erc_type: 464 terminal_types.add(self.erc_type) 465 466 if function_arg_types != terminal_types: 467 raise ValueError( 468 f"Function args type hints ({function_arg_types}) " 469 f"must match terminal types ({terminal_types})." 470 ) 471 472 return function_set, terminal_set 473 474 def __str__(self) -> str: 475 """ 476 Return a simple textual representation of the tree. 477 478 Returns 479 ------- 480 str 481 String representation of the tree. 482 483 Examples 484 -------- 485 untyped case: 486 >>> ut = Tree(terminal_set=[x, y, z], function_set=[f_add]) 487 >>> ut.tree = [FunctionNode(f_add), TerminalNode(1), TerminalNode(2)] 488 >>> tree.show() 489 def func_0(x, y, z): 490 return f_add(x, y) 491 492 typed case: 493 >>> tt = Tree(terminal_set={x: float, y: float}, 494 ... function_set=[typed_add]) 495 >>> tt.tree = [FunctionNode(typed_add), 496 ... TerminalNode(1.0, float), 497 ... TerminalNode(2.0, float)] 498 >>> str(tree) 499 def func_0(x: float, y: float) -> float: 500 return typed_add(1.0, 2.0) 501 """ 502 args = ( 503 list(self.terminal_set.keys()) 504 if None in self.terminal_set.values() 505 else [f"{k}: {v.__name__}" for k, v in self.terminal_set.items()] 506 ) 507 ret_type_str = ( 508 "" 509 if None in self.terminal_set.values() 510 else f" -> {self.root.node_type.__name__}" 511 ) 512 513 result = [ 514 f"def func_{str(self.id)}({', '.join(args)}){ret_type_str}:\n return " 515 ] 516 self._str_rec("", [0], result) 517 return "".join(result) 518 519 def _str_rec(self, prefix: str, pos: List[int], result: str) -> str: 520 """Recursively produce a simple textual printout of the tree 521 (pos is a size-1 list so as to pass "by reference" on successive 522 recursive calls). 523 """ 524 525 node = self.tree[pos[0]] 526 if isinstance(node, FunctionNode): 527 result.append(f"{prefix}{str(node)}(\n") 528 prefix = prefix + " " if pos[0] == 0 else prefix 529 for i in range(node.n_args): 530 pos[0] += 1 531 self._str_rec(prefix + " ", pos, result) 532 if i < node.n_args - 1: 533 result.append(",\n") 534 elif 0 < i < node.n_args: 535 result.append("\n") 536 result.append(prefix + ")") 537 else: # terminal 538 result.append(f"{prefix}{str(node)}") 539 540 def show(self): 541 """ 542 Print out a simple textual representation of the tree. 543 544 Returns 545 ------- 546 None. 547 """ 548 logger.info("\n" + str(self)) 549 550 def __repr__(self): 551 return str(self)
A tree optimized for genetic programming operations. It is represented by a list of nodes in depth-first order. There are two types of nodes: functions and terminals.
(tree is not meant as a stand-alone, parameters are supplied through the call from the Tree Creators)
Tree( fitness: eckity.fitness.fitness.Fitness = <eckity.fitness.gp_fitness.GPFitness object>, function_set: List[Callable] = None, terminal_set: Union[Dict[Any, type], List[Any]] = None, tree: List[eckity.genetic_encodings.gp.tree.tree_node.TreeNode] = None, erc_range: Union[Tuple[float, float], Tuple[int, int], NoneType] = None, root_type: Optional[type] = None, update_parents: bool = False)
36 def __init__( 37 self, 38 fitness: Fitness = GPFitness(), 39 function_set: List[Callable] = None, 40 terminal_set: Union[Dict[Any, type], List[Any]] = None, 41 tree: List[TreeNode] = None, 42 erc_range: Optional[ 43 Union[Tuple[float, float], Tuple[int, int]] 44 ] = None, 45 root_type: Optional[type] = None, 46 update_parents: bool = False 47 ): 48 """ 49 GP Tree Individual. 50 51 Parameters 52 ---------- 53 fitness : Fitness 54 Manages fitness state, by default GPFitness 55 function_set: List[Callable], default=None 56 List of functions used as internal nodes in the GP tree. 57 terminal_set : Union[Dict[Any, type], List[Any]], optional 58 Mapping of terminal nodes and their types. 59 In the untyped case, all types are None. 60 Lists are treated as untyped, and will be assigned None. 61 tree : List[TreeNode], optional 62 Actual tree representation, by default None 63 erc_range : tuple of float or int, optional 64 Range of Ephemeral random constant values, by default None 65 root_type: type, optional 66 Root node type, by default None 67 68 Raises 69 ------ 70 ValueError 71 If typed function is used with untyped terminals. 72 """ 73 super().__init__(fitness, update_parents=update_parents) 74 75 self.erc_range = erc_range 76 77 function_set, terminal_set = self._handle_input_types( 78 function_set, terminal_set, root_type 79 ) 80 81 self.function_set = function_set 82 self.terminal_set = terminal_set 83 84 # actual tree representation 85 if tree is None: 86 tree = [] 87 self.tree = tree 88 89 # this is the type of the execution result of the program (tree) 90 self.root_type = root_type
GP Tree Individual.
Parameters
- fitness (Fitness): Manages fitness state, by default GPFitness
- function_set (List[Callable], default=None): List of functions used as internal nodes in the GP tree.
- terminal_set (Union[Dict[Any, type], List[Any]], optional): Mapping of terminal nodes and their types. In the untyped case, all types are None. Lists are treated as untyped, and will be assigned None.
- tree (List[TreeNode], optional): Actual tree representation, by default None
- erc_range (tuple of float or int, optional): Range of Ephemeral random constant values, by default None
- root_type (type, optional): Root node type, by default None
Raises
- ValueError: If typed function is used with untyped terminals.
def
size(self) -> int:
100 def size(self) -> int: 101 """ 102 Compute size of tree. 103 104 Returns 105 ------- 106 int 107 tree size (= number of nodes). 108 """ 109 return len(self.tree)
Compute size of tree.
Returns
- int: tree size (= number of nodes).
111 def add_tree(self, node: TreeNode) -> None: 112 """Add a node to the tree following the defined type constrains""" 113 if ( 114 self.size() == 0 and node.node_type == self.root_type 115 ) or self._should_add([0], node): 116 self.tree.append(node) 117 else: 118 raise ValueError(f"Could not add node {node} to tree {self.tree}")
Add a node to the tree following the defined type constrains
def
depth(self) -> int:
147 def depth(self) -> int: 148 """ 149 Compute depth of tree (maximal path length to a leaf). 150 151 Returns 152 ------- 153 int 154 tree depth. 155 """ 156 return self._depth([0], d=0)
Compute depth of tree (maximal path length to a leaf).
Returns
- int: tree depth.
def
random_function( self, node_type: Optional[type] = None) -> Optional[eckity.genetic_encodings.gp.tree.tree_node.FunctionNode]:
175 def random_function( 176 self, 177 node_type: Optional[type] = None 178 ) -> Optional[FunctionNode]: 179 functions_types = { 180 func: get_return_type(func) for func in self.function_set 181 } 182 relevant_functions = [ 183 func 184 for func in self.function_set 185 if functions_types[func] == node_type 186 ] 187 188 # Return None in case there are no functions of the given type 189 if not relevant_functions: 190 return None 191 192 func = random.choice(relevant_functions) 193 return FunctionNode(func)
def
random_terminal( self, node_type: Optional[type] = None) -> Optional[eckity.genetic_encodings.gp.tree.tree_node.TerminalNode]:
195 def random_terminal( 196 self, 197 node_type: Optional[type] = None 198 ) -> Optional[TerminalNode]: 199 """Select a random terminal, including constants from ERC range""" 200 relevant_terminals = [ 201 term 202 for term, term_type in self.terminal_set.items() 203 if term_type == node_type 204 ] 205 206 if self.erc_range is not None and ( 207 node_type is None or issubclass(node_type, Number) 208 ): 209 relevant_terminals.append( 210 random.uniform(*self.erc_range) 211 if type(self.erc_range[0]) is float 212 else random.randint(*self.erc_range) 213 ) 214 215 # Return None in case there are no terminals of the given type 216 if not relevant_terminals: 217 return None 218 219 terminal = random.choice(relevant_terminals) 220 221 # erc terminal will be typeless in untyped case, 222 # and int/float in typed case 223 default_type = None if node_type is None else type(terminal) 224 node_type = self.terminal_set.get(terminal, default_type) 225 226 return TerminalNode(terminal, node_type=node_type)
Select a random terminal, including constants from ERC range
def
execute(self, *args, **kwargs) -> object:
228 def execute(self, *args, **kwargs) -> object: 229 """ 230 Execute the program (tree). 231 Input is a numpy array or keyword arguments (but not both). 232 233 Parameters 234 ---------- 235 args : arguments 236 A numpy array. 237 238 kwargs : keyword arguments 239 Input to program, including every variable 240 in the terminal set as a keyword argument. 241 For example, if `terminal_set=['x', 'y', 'z']` 242 then call `execute(x=..., y=..., z=...)`. 243 244 Returns 245 ------- 246 object 247 Result of tree execution. 248 """ 249 250 if not self.tree: 251 raise ValueError("Tree is empty, cannot execute.") 252 253 reshape = False 254 if args: # numpy array -- convert to kwargs 255 try: 256 X = args[0] 257 kwargs = generate_args(X) 258 reshape = True 259 except Exception: 260 raise ValueError( 261 f"Bad argument to tree.execute, " 262 f"must be np array or kwargs: {args}" 263 ) 264 265 kw = list(kwargs.keys()) 266 267 bad_vars = [item for item in kw if item not in self.terminal_set] 268 if len(bad_vars) > 0: 269 raise ValueError( 270 f"received variable arguments not in terminal set: {bad_vars}" 271 ) 272 273 missing_vars = [item for item in self.terminal_set if item not in kw] 274 if len(missing_vars) > 0: 275 raise ValueError( 276 f"Missing variable terminals as execute kwargs: {missing_vars}" 277 ) 278 279 res = self._execute([0], **kwargs) 280 281 if reshape and (isinstance(res, Number) or res.shape == np.shape(0)): 282 # sometimes a tree degenrates to a scalar value 283 res = np.full_like(X[:, 0], res) 284 return res
Execute the program (tree). Input is a numpy array or keyword arguments (but not both).
Parameters
- args (arguments): A numpy array.
- kwargs (keyword arguments):
Input to program, including every variable
in the terminal set as a keyword argument.
For example, if
terminal_set=['x', 'y', 'z']then callexecute(x=..., y=..., z=...).
Returns
- object: Result of tree execution.
def
get_random_numeric_node( self) -> Optional[eckity.genetic_encodings.gp.tree.tree_node.TerminalNode]:
312 def get_random_numeric_node(self) -> Optional[TerminalNode]: 313 """ 314 Get a random leaf node of the tree. 315 316 Parameters 317 ---------- 318 node_type : type, default=None 319 Type of node to return. 320 321 Returns 322 ------- 323 TreeNode 324 Random leaf node. 325 """ 326 erc_nodes = self.filter_tree( 327 lambda node: isinstance(node, TerminalNode) 328 and isinstance(node.value, Number) 329 ) 330 return random.choice(erc_nodes) if erc_nodes else None
Get a random leaf node of the tree.
Parameters
- node_type (type, default=None): Type of node to return.
Returns
- TreeNode: Random leaf node.
def
random_subtree( self, node_type: Optional[type] = None) -> Optional[List[eckity.genetic_encodings.gp.tree.tree_node.TreeNode]]:
332 def random_subtree( 333 self, 334 node_type: Optional[type] = None 335 ) -> Optional[List[TreeNode]]: 336 relevant_nodes = self.filter_tree( 337 lambda node: node.node_type is None # untyped case 338 or ( 339 node_type is None and node != self.root 340 ) # typed case with first invocation 341 or ( 342 node.node_type == node_type and node != self.root 343 ) # typed case with subsequent invocations 344 ) 345 if not relevant_nodes: 346 return None 347 subtree_root = random.choice(relevant_nodes) 348 349 return self._get_subtree_by_root(subtree_root)
def
replace_subtree( self, old_subtree: List[eckity.genetic_encodings.gp.tree.tree_node.TreeNode], new_subtree: List[eckity.genetic_encodings.gp.tree.tree_node.TreeNode]) -> None:
360 def replace_subtree( 361 self, old_subtree: List[TreeNode], new_subtree: List[TreeNode] 362 ) -> None: 363 """ 364 Replace the subtree starting at `index` with `subtree` 365 366 Parameters 367 ---------- 368 subtree - new subtree to replace the existing subtree in the tree 369 370 Returns 371 ------- 372 None 373 """ 374 start_i = self.tree.index(old_subtree[0]) 375 end_i = start_i + len(old_subtree) 376 left_part = self.tree[:start_i] 377 right_part = self.tree[end_i:] 378 self.tree = left_part + new_subtree + right_part
Replace the subtree starting at index with subtree
Parameters
- subtree - new subtree to replace the existing subtree in the tree
Returns
- None