eckity.genetic_encodings.gp.tree.tree_individual

  1"""
  2This module implements the tree class.
  3"""
  4
  5import numpy as np
  6from numbers import Number
  7from random import randint, uniform, random
  8
  9from eckity.base.utils import arity
 10from eckity.genetic_encodings.gp.tree.utils import _generate_args
 11
 12from eckity.individual import Individual
 13from eckity.genetic_encodings.gp.tree.functions import f_add, f_sub, f_mul, f_div
 14
 15
 16class Tree(Individual):
 17    """
 18    A tree optimized for genetic programming operations.
 19    It is represented by a list of nodes in depth-first order.
 20    There are two types of nodes: functions and terminals.
 21
 22    (tree is not meant as a stand-alone -- parameters are supplied through the call from the Tree Creators)
 23
 24    Parameters
 25    ----------
 26    init_depth : (int, int)
 27        Min and max depths of initial random trees. The default is None.
 28        
 29    function_set : list
 30        List of functions used as internal nodes in the GP tree. The default is None.
 31        
 32    terminal_set : list
 33        List of terminals used in the GP-tree leaves. The default is None.
 34        
 35    erc_range : (float, float)
 36        Range of values for ephemeral random constant (ERC). The default is None.
 37    """
 38    def __init__(self,
 39                 fitness,
 40                 function_set=None,
 41                 terminal_set=None,
 42                 erc_range=None,
 43                 init_depth=(1, 2)):
 44        super().__init__(fitness)
 45        if function_set is None:
 46            function_set = [f_add, f_sub, f_mul, f_div]
 47
 48        if terminal_set is None:
 49            terminal_set = ['x', 'y', 'z', 0, 1, -1]
 50
 51        self.function_set = function_set
 52        self.terminal_set = terminal_set
 53        self.n_terminals = len(terminal_set)
 54        self.arity = dict([(func, arity(func)) for func in self.function_set])
 55        self.vars = [t for t in terminal_set if not isinstance(t, Number)]
 56        self.erc_range = erc_range
 57        self.n_functions = len(self.function_set)
 58        self.init_depth = init_depth
 59        self.tree = []
 60
 61    def size(self):
 62        """
 63        Compute size of tree.
 64
 65        Returns
 66        -------
 67        int
 68            tree size (= number of nodes).
 69        """
 70        return len(self.tree)
 71
 72    def add_tree(self, node):
 73        self.tree.append(node)
 74
 75    def empty_tree(self):
 76        self.tree = []
 77
 78    def _depth(self, pos, depth):
 79        """Recursively compute depth 
 80           (pos is a size-1 list so as to pass "by reference" on successive recursive calls)."""
 81
 82        node = self.tree[pos[0]]
 83
 84        depths = []
 85        if node in self.function_set:
 86            for i in range(self.arity[node]):
 87                pos[0] += 1
 88                depths.append(1 + self._depth(pos, depth + 1))
 89            return max(depths)
 90        else:
 91            return 0
 92
 93    def depth(self):
 94        """
 95        Compute depth of tree (maximal path length to a leaf).
 96
 97        Returns
 98        -------
 99        int
100            tree depth.
101        """
102
103        return self._depth([0], 0)
104
105    def random_function(self):
106        """select a random function"""
107        return self.function_set[randint(0, self.n_functions - 1)]
108
109    def random_terminal(self):
110        """Select a random terminal or create an ERC terminal"""
111        if self.erc_range is None:
112            node = self.terminal_set[randint(0, self.n_terminals - 1)]
113        else:
114            if random() > 0.5:
115                node = self.terminal_set[randint(0, self.n_terminals - 1)]
116            else:
117                node = round(uniform(*self.erc_range), 4)
118        return node
119
120    def _execute(self, pos, **kwargs):
121        """Recursively execute the tree by traversing it in a depth-first order 
122           (pos is a size-1 list so as to pass "by reference" on successive recursive calls)."""
123
124        node = self.tree[pos[0]]
125
126        if node in self.function_set:
127            arglist = []
128            for i in range(self.arity[node]):
129                pos[0] += 1
130                res = self._execute(pos, **kwargs)
131                arglist.append(res)
132            return node(*arglist)
133        else:  # terminal
134            if isinstance(node, Number):  # terminal is a constant
135                return node
136            else:  # terminal is a variable, return its value
137                return kwargs[node]
138
139    def execute(self, *args, **kwargs):
140        """
141        Execute the program (tree). 
142        Input is a numpy array or keyword arguments (but not both).
143
144        Parameters
145        ----------
146        args : arguments
147            A numpy array.
148        
149        kwargs : keyword arguments
150            Input to program, including every variable in the terminal set as a keyword argument.
151            For example, if `terminal_set=['x', 'y', 'z', 0, 1, -1]` 
152            then call `execute(x=..., y=..., z=...)`.
153
154        Returns
155        -------
156        object
157            Result of tree execution.
158        """
159
160        reshape = False
161        if args != ():  # numpy array -- convert to kwargs
162            try:
163                X = args[0]
164                kwargs = _generate_args(X)
165                reshape = True
166            except Exception:
167                raise ValueError(f'Bad argument to tree.execute, must be numpy array or kwargs: {args}')
168
169        kw = list(kwargs.keys())
170
171        bad_vars = [item for item in kw if item not in self.vars]
172        if len(bad_vars) > 0:
173            raise ValueError(f'tree.execute received variable arguments not in terminal set: {bad_vars}')
174
175        missing_vars = [item for item in self.vars if item not in kw]
176        if len(missing_vars) > 0:
177            raise ValueError(
178                f'Some variable terminals were not passed to tree.execute as keyword arguments: {missing_vars}')
179
180        res = self._execute([0], **kwargs)
181        if reshape and (isinstance(res, Number) or res.shape == np.shape(0)):
182            # sometimes a tree degenrates to a scalar value
183            res = np.full_like(X[:, 0], res)
184        return res
185
186    def random_subtree(self):
187        # select a random node index from this individual's tree
188        rnd_i = randint(0, self.size() - 1)
189        # find the subtree's end
190        end_i = self._find_subtree_end([rnd_i])
191        # now we have a random subtree from this individual
192        return self.tree[rnd_i:end_i + 1]
193
194    def _find_subtree_end(self, pos):
195        """find index of final node of subtree that starts at `pos` 
196          (pos is a size-1 list so as to pass "by reference" on successive recursive calls)."""
197
198        node = self.tree[pos[0]]
199
200        if node in self.function_set:
201            for i in range(self.arity[node]):
202                pos[0] += 1
203                self._find_subtree_end(pos)
204
205        return pos[0]
206
207    def replace_subtree(self, subtree):
208        """
209        Replace the subtree starting at `index` with `subtree`
210
211        Parameters
212        ----------
213        subtree - new subtree to replace the some existing subtree in this individual's tree
214
215        Returns
216        -------
217        None
218        """
219
220        index = randint(0, self.size() - 1)  # select a random node (index)
221        end_i = self._find_subtree_end([index])
222        if isinstance(self.tree[end_i], list):
223            print(self.tree[end_i], list)
224        left_part = self.tree[:index]
225        right_part = self.tree[(end_i + 1):]
226        self.tree = left_part + subtree + right_part
227
228    def _node_label(self, node):
229        """
230        return a string label for the node
231
232        Parameters
233        ----------
234        node - some node in the tree's function/terminal set
235
236        Returns
237        -------
238        node name - either a terminal (x0, x1,...) or a function (f_add, f_or, ...)
239        """
240        return node.__name__ if node in self.function_set else str(node)
241
242    def _show(self, prefix, pos):
243        """Recursively produce a simple textual printout of the tree 
244        (pos is a size-1 list so as to pass "by reference" on successive recursive calls)."""
245
246        node = self.tree[pos[0]]
247        if node in self.function_set:
248            print(f'{prefix}{self._node_label(node)}')
249            for i in range(self.arity[node]):
250                pos[0] += 1
251                self._show(prefix + "   ", pos)
252        else:  # terminal
253            print(f'{prefix}{self._node_label(node)}')
254
255    def show(self):
256        """
257        Print out a simple textual representation of the tree.
258
259        Returns
260        -------
261        None.
262        """
263        self._show("", [0])
264
265# end class tree