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
@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)