eckity.genetic_operators.crossovers.subtree_crossover

  1from typing import Any, List, Tuple, Optional
  2
  3from overrides import override
  4
  5from eckity.genetic_encodings.gp import Tree, TreeNode
  6from eckity.genetic_operators.failable_operator import FailableOperator
  7
  8
  9class SubtreeCrossover(FailableOperator):
 10    def __init__(self, probability=1.0, arity=2, events=None, attempts=1):
 11        super().__init__(
 12            probability=probability,
 13            arity=arity,
 14            events=events,
 15            attempts=attempts,
 16        )
 17        self.individuals = None
 18        self.applied_individuals = None
 19
 20    @override
 21    def attempt_operator(
 22        self, payload: Any, attempt_num: int
 23    ) -> Tuple[bool, Any]:
 24        """
 25        Perform subtree crossover between a list of trees in a cyclic manner.
 26        Meaning, the second individual will have a subtree from the first,
 27        and the first individual will have a subtree from the last individual.
 28
 29        Parameters
 30        ----------
 31        payload: List[Individual]
 32            List of Trees to perform crossover on
 33
 34        individual: Tree
 35        tree individual to perform crossover on
 36
 37        Returns
 38        -------
 39        List
 40            List of individuals after crossover (modified in-place)
 41        """
 42        individuals = payload
 43
 44        if len(individuals) != self.arity:
 45            raise ValueError(
 46                f"Expected individuals of size {self.arity}, "
 47                f"got {len(individuals)}."
 48            )
 49
 50        self.individuals = individuals
 51
 52        subtrees: Optional[List[List[TreeNode]]] = self._pick_subtrees(
 53            individuals
 54        )
 55
 56        if subtrees is None:
 57            return False, individuals
 58
 59        self._swap_subtrees(individuals, subtrees)
 60        self.applied_individuals = individuals
 61
 62        return True, individuals
 63
 64    @staticmethod
 65    def _pick_subtrees(
 66        individuals: List[Tree],
 67    ) -> Optional[List[List[TreeNode]]]:
 68        # select a random subtree from first individual tree
 69        first_subtree: List[TreeNode] = individuals[0].random_subtree()
 70
 71        if first_subtree is None:
 72            # failed attempt
 73            return None
 74
 75        m_type: type = first_subtree[0].node_type
 76
 77        # now select a random subtree from the rest of the individuals
 78        # with regards to the type of the first subtree
 79        rest_subtrees = [ind.random_subtree(m_type) for ind in individuals[1:]]
 80
 81        # fails if any subtree doesn't contain a node with of type `m_type`
 82        if None in rest_subtrees:
 83            return None
 84
 85        subtrees = [first_subtree] + rest_subtrees
 86        return subtrees
 87
 88    @staticmethod
 89    def _swap_subtrees(
 90        individuals: List[TreeNode], subtrees: List[List[TreeNode]]
 91    ) -> None:
 92        """
 93        Replace subtrees for all individuals in a cyclic manner
 94        For n subtrees (st_1, st_2, ..., st_n):
 95        st_n receives the subtree of st_n-1
 96        st_n-1 receives the subtree of st_n-2
 97        ...
 98        st_2 receives the subtree of st_1
 99        st_1 receives the subtree of st_n
100        """
101        for i in range(len(individuals) - 1, -1, -1):
102            individuals[i].replace_subtree(
103                old_subtree=subtrees[i], new_subtree=subtrees[i - 1]
104            )
 11class SubtreeCrossover(FailableOperator):
 12    def __init__(self, probability=1.0, arity=2, events=None, attempts=1):
 13        super().__init__(
 14            probability=probability,
 15            arity=arity,
 16            events=events,
 17            attempts=attempts,
 18        )
 19        self.individuals = None
 20        self.applied_individuals = None
 21
 22    @override
 23    def attempt_operator(
 24        self, payload: Any, attempt_num: int
 25    ) -> Tuple[bool, Any]:
 26        """
 27        Perform subtree crossover between a list of trees in a cyclic manner.
 28        Meaning, the second individual will have a subtree from the first,
 29        and the first individual will have a subtree from the last individual.
 30
 31        Parameters
 32        ----------
 33        payload: List[Individual]
 34            List of Trees to perform crossover on
 35
 36        individual: Tree
 37        tree individual to perform crossover on
 38
 39        Returns
 40        -------
 41        List
 42            List of individuals after crossover (modified in-place)
 43        """
 44        individuals = payload
 45
 46        if len(individuals) != self.arity:
 47            raise ValueError(
 48                f"Expected individuals of size {self.arity}, "
 49                f"got {len(individuals)}."
 50            )
 51
 52        self.individuals = individuals
 53
 54        subtrees: Optional[List[List[TreeNode]]] = self._pick_subtrees(
 55            individuals
 56        )
 57
 58        if subtrees is None:
 59            return False, individuals
 60
 61        self._swap_subtrees(individuals, subtrees)
 62        self.applied_individuals = individuals
 63
 64        return True, individuals
 65
 66    @staticmethod
 67    def _pick_subtrees(
 68        individuals: List[Tree],
 69    ) -> Optional[List[List[TreeNode]]]:
 70        # select a random subtree from first individual tree
 71        first_subtree: List[TreeNode] = individuals[0].random_subtree()
 72
 73        if first_subtree is None:
 74            # failed attempt
 75            return None
 76
 77        m_type: type = first_subtree[0].node_type
 78
 79        # now select a random subtree from the rest of the individuals
 80        # with regards to the type of the first subtree
 81        rest_subtrees = [ind.random_subtree(m_type) for ind in individuals[1:]]
 82
 83        # fails if any subtree doesn't contain a node with of type `m_type`
 84        if None in rest_subtrees:
 85            return None
 86
 87        subtrees = [first_subtree] + rest_subtrees
 88        return subtrees
 89
 90    @staticmethod
 91    def _swap_subtrees(
 92        individuals: List[TreeNode], subtrees: List[List[TreeNode]]
 93    ) -> None:
 94        """
 95        Replace subtrees for all individuals in a cyclic manner
 96        For n subtrees (st_1, st_2, ..., st_n):
 97        st_n receives the subtree of st_n-1
 98        st_n-1 receives the subtree of st_n-2
 99        ...
100        st_2 receives the subtree of st_1
101        st_1 receives the subtree of st_n
102        """
103        for i in range(len(individuals) - 1, -1, -1):
104            individuals[i].replace_subtree(
105                old_subtree=subtrees[i], new_subtree=subtrees[i - 1]
106            )

Genetic operator that has a chance of failing.

For example, adding a gaussian noise to a FloatVector cell might exceed the legal bounds of the vector. In that case, the Gauss Mutation fails.

Parameters
  • probability (float): the probability of the operator to be applied
  • arity (int): number of individuals to be applied on
  • events (list of strings): events to be published before, after and during the operator
  • attempts (int): number of attempts to be made during the operator execution
SubtreeCrossover(probability=1.0, arity=2, events=None, attempts=1)
12    def __init__(self, probability=1.0, arity=2, events=None, attempts=1):
13        super().__init__(
14            probability=probability,
15            arity=arity,
16            events=events,
17            attempts=attempts,
18        )
19        self.individuals = None
20        self.applied_individuals = None
individuals
applied_individuals
@override
def attempt_operator(self, payload: Any, attempt_num: int) -> Tuple[bool, Any]:
22    @override
23    def attempt_operator(
24        self, payload: Any, attempt_num: int
25    ) -> Tuple[bool, Any]:
26        """
27        Perform subtree crossover between a list of trees in a cyclic manner.
28        Meaning, the second individual will have a subtree from the first,
29        and the first individual will have a subtree from the last individual.
30
31        Parameters
32        ----------
33        payload: List[Individual]
34            List of Trees to perform crossover on
35
36        individual: Tree
37        tree individual to perform crossover on
38
39        Returns
40        -------
41        List
42            List of individuals after crossover (modified in-place)
43        """
44        individuals = payload
45
46        if len(individuals) != self.arity:
47            raise ValueError(
48                f"Expected individuals of size {self.arity}, "
49                f"got {len(individuals)}."
50            )
51
52        self.individuals = individuals
53
54        subtrees: Optional[List[List[TreeNode]]] = self._pick_subtrees(
55            individuals
56        )
57
58        if subtrees is None:
59            return False, individuals
60
61        self._swap_subtrees(individuals, subtrees)
62        self.applied_individuals = individuals
63
64        return True, individuals

Perform subtree crossover between a list of trees in a cyclic manner. Meaning, the second individual will have a subtree from the first, and the first individual will have a subtree from the last individual.

Parameters
  • payload (List[Individual]): List of Trees to perform crossover on
  • individual (Tree):

  • tree individual to perform crossover on

Returns
  • List: List of individuals after crossover (modified in-place)