Mutation fixes: separate specific mutations from operator (aimclub#55)

* Add docs for generational scheme and regularization operator * Minor refactoring in EvoOptimizer: no while loops * Refactor mutation to be separate functions * Move MutationTypesEnum * Abstract Mutation for any set of mutations * Minor refactoring in Mutation * Add tree_growth mutation to set of available * Fix graph_growth * fixes: fix 'delete_node' to work with several roots * fixes: modify nodes_from_layer to work with multiple roots * fixes: fix verification rule for null graphs * fixes: single_drop mutation * fixes: Node.description in case of None name * fix review comments
SoloWayG · Mar 6, 2023 · 576f578 · 576f578
1 parent ad4eac4
commit 576f578
Show file tree

Hide file tree

Showing 14 changed files with 599 additions and 413 deletions.
diff --git a/examples/synthetic_graph_evolution/abstract_graph_search.py b/examples/synthetic_graph_evolution/abstract_graph_search.py
@@ -12,7 +12,7 @@
 from golem.core.optimisers.genetic.gp_optimizer import EvoGraphOptimizer
 from golem.core.optimisers.genetic.gp_params import GPAlgorithmParameters
 from golem.core.optimisers.genetic.operators.inheritance import GeneticSchemeTypesEnum
-from golem.core.optimisers.genetic.operators.mutation import MutationTypesEnum
+from golem.core.optimisers.genetic.operators.base_mutations import MutationTypesEnum
 from golem.core.optimisers.graph import OptGraph, OptNode
 from golem.core.optimisers.objective import Objective
 from golem.core.optimisers.optimizer import GraphGenerationParams, GraphOptimizer

diff --git a/golem/core/dag/graph_utils.py b/golem/core/dag/graph_utils.py
@@ -42,23 +42,23 @@ def nodes_from_layer(graph: 'Graph', layer_number: int) -> Sequence['GraphNode']
         all nodes from the surface to the ``layer_number`` layer
     """
 
-    def get_nodes(node: Union['GraphNode', List['GraphNode']], current_height: int):
-        """Gets all the parent nodes of ``node``
+    def get_nodes(roots: Sequence['GraphNode'], current_height: int) -> Sequence['GraphNode']:
+        """Gets all the parent nodes of ``roots``
 
-        :param node: node to get all subnodes from
+        :param roots: nodes to get all subnodes from
         :param current_height: current diving step depth
 
-        :return: all parent nodes of ``node``
+        :return: all parent nodes of ``roots`` in one sequence:69
         """
         nodes = []
         if current_height == layer_number:
-            nodes.append(node)
+            nodes.extend(roots)
         else:
-            for parent in node.nodes_from:
-                nodes.extend(get_nodes(parent, current_height + 1))
+            for root in roots:
+                nodes.extend(get_nodes(root.nodes_from, current_height + 1))
         return nodes
 
-    nodes = get_nodes(graph.root_node, current_height=0)
+    nodes = get_nodes(graph.root_nodes(), current_height=0)
     return nodes
 
 

diff --git a/golem/core/dag/linked_graph.py b/golem/core/dag/linked_graph.py
@@ -36,16 +36,18 @@ def _empty_postprocess(*args):
     @copy_doc(Graph.delete_node)
     def delete_node(self, node: GraphNode):
         node_children_cached = self.node_children(node)
-        self_root_node_cached = self.root_node
 
-        for node_child in self.node_children(node):
+        self._nodes.remove(node)
+        for node_child in node_children_cached:
             node_child.nodes_from.remove(node)
 
+        # if removed node had a single child
+        # then reconnect it to preceding parent nodes.
         if node.nodes_from and len(node_children_cached) == 1:
+            child = node_children_cached[0]
             for node_from in node.nodes_from:
-                node_children_cached[0].nodes_from.append(node_from)
-        self._nodes.clear()
-        self.add_node(self_root_node_cached)
+                child.nodes_from.append(node_from)
+
         self._postprocess_nodes(self, self._nodes)
 
     @copy_doc(Graph.delete_subtree)

diff --git a/golem/core/dag/linked_graph_node.py b/golem/core/dag/linked_graph_node.py
@@ -41,7 +41,8 @@ def nodes_from(self, nodes: Optional[Iterable['LinkedGraphNode']]):
 
     @property
     def name(self) -> str:
-        return str(self.content.get('name'))
+        name = self.content.get('name')
+        return str(name) if name is not None else ''
 
     @property
     def parameters(self) -> dict:
@@ -64,16 +65,14 @@ def __repr__(self) -> str:
         return self.__str__()
 
     def description(self) -> str:
-        node_operation = self.content.get('name')
-        if node_operation is None:
-            raise ValueError('Unknown content in the node: expected content[`name`], got None')
+        label = self.name or self.uid
         # TODO: possibly unify with __repr__ & don't duplicate Operation.description
         if not self.parameters:
-            node_label = f'n_{node_operation}'
-        elif isinstance(node_operation, str):
+            node_label = f'n_{label}'
+        elif isinstance(label, str):
             # If there is a string: name of operation (as in json repository)
-            node_label = f'n_{node_operation}_{self.parameters}'
+            node_label = f'n_{label}_{self.parameters}'
         else:
             # If instance of Operation is placed in 'name'
-            node_label = node_operation.description(self.parameters)
+            node_label = label.description(self.parameters)
         return node_label
diff --git a/golem/core/dag/verification_rules.py b/golem/core/dag/verification_rules.py
@@ -46,6 +46,8 @@ def has_no_isolated_components(graph: Graph):
     ud_nx_graph = nx.Graph()
     ud_nx_graph.add_nodes_from(nx_graph)
     ud_nx_graph.add_edges_from(nx_graph.edges)
+    if ud_nx_graph.number_of_nodes() == 0:
+        raise ValueError(f'{ERROR_PREFIX} Graph is null, connectivity not defined')
     if not nx.is_connected(ud_nx_graph):
         raise ValueError(f'{ERROR_PREFIX} Graph has isolated components')
     return True

diff --git a/golem/core/optimisers/genetic/gp_optimizer.py b/golem/core/optimisers/genetic/gp_optimizer.py
@@ -74,24 +74,25 @@ def _initial_population(self, evaluator: EvaluationOperator):
             self._update_population(evaluator(self.initial_individuals), 'extended_initial_assumptions')
 
     def _extend_population(self, initial_individuals: PopulationT) -> PopulationT:
-        iter_num = 0
         initial_individuals = list(initial_individuals)
         initial_graphs = [ind.graph for ind in initial_individuals]
         initial_req = deepcopy(self.requirements)
         initial_req.mutation_prob = 1
         self.mutation.update_requirements(requirements=initial_req)
-        while len(initial_individuals) < self.graph_optimizer_params.pop_size:
+
+        for iter_num in range(MAX_GRAPH_GEN_ATTEMPTS):
+            if len(initial_individuals) == self.graph_optimizer_params.pop_size:
+                break
             new_ind = self.mutation(choice(self.initial_individuals))
             new_graph = new_ind.graph
-            iter_num += 1
             if new_graph not in initial_graphs and self.graph_generation_params.verifier(new_graph):
                 initial_individuals.append(new_ind)
                 initial_graphs.append(new_graph)
-            if iter_num > MAX_GRAPH_GEN_ATTEMPTS:
-                self.log.warning(f'Exceeded max number of attempts for extending initial graphs, stopping.'
-                                 f'Current size {len(self.initial_individuals)} '
-                                 f'instead of {self.graph_optimizer_params.pop_size} graphs.')
-                break
+        else:
+            self.log.warning(f'Exceeded max number of attempts for extending initial graphs, stopping.'
+                             f'Current size {len(self.initial_individuals)} '
+                             f'instead of {self.graph_optimizer_params.pop_size} graphs.')
+
         self.mutation.update_requirements(requirements=self.requirements)
         return initial_individuals
 
@@ -101,8 +102,7 @@ def _evolve_population(self, evaluator: EvaluationOperator) -> PopulationT:
 
         individuals_to_select = self.regularization(self.population, evaluator)
         selected_individuals = self.selection(individuals_to_select)
-        new_population = self._spawn_evaluated_population(selected_individuals=selected_individuals,
-                                                          evaluator=evaluator)
+        new_population = self._spawn_evaluated_population(selected_individuals, evaluator)
         new_population = self.inheritance(self.population, new_population)
         new_population = self.elitism(self.generations.best_individuals, new_population)
 
@@ -126,19 +126,12 @@ def _spawn_evaluated_population(self, selected_individuals: PopulationT, evaluat
         """ Reproduce and evaluate new population. If at least one of received individuals can not be evaluated then
         mutate and evaluate selected individuals until a new population is obtained
         or the number of attempts is exceeded """
-
-        iter_num = 0
-        new_population = None
-        while not new_population:
+        for i in range(EVALUATION_ATTEMPTS_NUMBER):
             new_population = self.crossover(selected_individuals)
             new_population = self.mutation(new_population)
             new_population = evaluator(new_population)
-
-            if iter_num > EVALUATION_ATTEMPTS_NUMBER:
-                break
-            iter_num += 1
-
-        if not new_population:
+            if new_population:
+                return new_population
+        else:
+            # Could not generate valid population; raise an error
             raise EvaluationAttemptsError()
-
-        return new_population
diff --git a/golem/core/optimisers/genetic/gp_params.py b/golem/core/optimisers/genetic/gp_params.py
@@ -1,11 +1,12 @@
 from dataclasses import dataclass
 from typing import Sequence, Union, Any
 
+from golem.core.optimisers.genetic.operators.base_mutations import MutationStrengthEnum, MutationTypesEnum, \
+    rich_mutation_set
 from golem.core.optimisers.optimizer import AlgorithmParameters
 from golem.core.optimisers.genetic.operators.crossover import CrossoverTypesEnum
 from golem.core.optimisers.genetic.operators.elitism import ElitismTypesEnum
 from golem.core.optimisers.genetic.operators.inheritance import GeneticSchemeTypesEnum
-from golem.core.optimisers.genetic.operators.mutation import MutationTypesEnum, MutationStrengthEnum
 from golem.core.optimisers.genetic.operators.regularization import RegularizationTypesEnum
 from golem.core.optimisers.genetic.operators.selection import SelectionTypesEnum
 
@@ -27,8 +28,26 @@ class GPAlgorithmParameters(AlgorithmParameters):
     :param crossover_types: Sequence of crossover operators types
     :param mutation_types: Sequence of mutation operators types
     :param elitism_type: type of elitism operator evolution
+
     :param regularization_type: type of regularization operator
+
+    Regularization attempts to cut off the subtrees of the graph. If the truncated graph
+    is not worse than the original, then it enters the new generation as a simpler solution.
+    Regularization is not used by default, it must be explicitly enabled.
+
     :param genetic_scheme_type: type of genetic evolutionary scheme
+
+    The `generational` scheme is a standard scheme of the evolutionary algorithm.
+    It specifies that at each iteration the entire generation is updated.
+
+    In the `steady_state` scheme at each iteration only one individual is updated.
+
+    The `parameter_free` scheme is an adaptive variation of the `generational` scheme.
+    It specifies that the population size and the probability of mutation and crossover
+    change depending on the success of convergence. If there are no improvements in fitness,
+    then the size and the probabilities increase. When fitness improves, the size and the
+    probabilities decrease. That is, the algorithm choose a more stable and conservative
+    mode when optimization seems to converge.
     """
 
     crossover_prob: float = 0.8
@@ -43,11 +62,7 @@ class GPAlgorithmParameters(AlgorithmParameters):
     crossover_types: Sequence[Union[CrossoverTypesEnum, Any]] = \
         (CrossoverTypesEnum.subtree,
          CrossoverTypesEnum.one_point)
-    mutation_types: Sequence[Union[MutationTypesEnum, Any]] = \
-        (MutationTypesEnum.simple,
-         MutationTypesEnum.reduce,
-         MutationTypesEnum.growth,
-         MutationTypesEnum.local_growth)
+    mutation_types: Sequence[Union[MutationTypesEnum, Any]] = rich_mutation_set
     elitism_type: ElitismTypesEnum = ElitismTypesEnum.keep_n_best
     regularization_type: RegularizationTypesEnum = RegularizationTypesEnum.none
     genetic_scheme_type: GeneticSchemeTypesEnum = GeneticSchemeTypesEnum.generational