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)
class Tree(eckity.individual.Individual):
 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.
erc_range
function_set
terminal_set
tree
root_type
92    @property
93    def root(self) -> TreeNode:
94        return self.tree[0]
erc_type: Union[int, float, NoneType]
96    @property
97    def erc_type(self) -> Optional[Union[int, float]]:
98        return type(self.erc_range[0]) if self.erc_range else None
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).
def add_tree(self, node: eckity.genetic_encodings.gp.tree.tree_node.TreeNode) -> None:
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 empty_tree(self) -> None:
144    def empty_tree(self) -> None:
145        self.tree = []
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 call execute(x=..., y=..., z=...).
Returns
  • object: Result of tree execution.
def filter_tree(self, filter_func: Callable) -> None:
309    def filter_tree(self, filter_func: Callable) -> None:
310        return [node for node in self.tree if filter_func(node)]
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
def show(self):
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))

Print out a simple textual representation of the tree.

Returns
  • None.