Genetic Algorithm

class gatree.ga.crossover.Crossover

Bases: object

Class implementing the crossover operator for the genetic algorithm.

crossover(tree2, random)

Crossover is a genetic operator used to combine the genetic information of two parent trees to generate new offspring. This enables exploration, which helps in creating diversity in the population and combining good traits from both parents.

Pseudocode of the implementation:

Copy the parent trees to avoid altering the originals.
Randomly select a crossover point in each tree.
Swap the subtrees at the selected points between the two trees.
Return the new tree created from the crossover.

Parameters:

tree1 (Node) – The first tree for crossover.
tree2 (Node) – The second tree for crossover.
random (Random) – Random number generator.

Returns:

The new tree resulting from crossover.

Return type:

Node

class gatree.ga.mutation.Mutation

Bases: object

Class implementing the mutation operator for the genetic algorithm.

static change_attribute(node, att_indexes, att_values, random)

Change attribute of a mid-tree node. The new attribute must be different from the old attribute.

Parameters:

node (Node) – The mid-tree node.
att_indexes (list) – List of attribute indexes.
att_values (list) – List of attribute values.
random (Random) – Random number generator.

static change_attribute_value(node, att_values, random)

Change attribute value of a mid-tree node. The new attribute value must be different from the old attribute value.

Parameters:

node (Node) – The mid-tree node.
att_values (list) – List of attribute values.
random (Random) – Random number generator.

static change_class(node, class_count, random)

Change class of a leaf node. The new class must be different from the old class.

Parameters:

node (Node) – The leaf node.
class_count (int) – Number of classes.
random (Random) – Random number generator.

static exchange_class_for_tree(node, att_indexes, att_values, class_count, random)

Exchange a leaf node for a new subtree. The new subtree is created with a random depth.

Parameters:

node (Node) – The leaf node.
att_indexes (list) – List of attribute indexes.
att_values (list) – List of attribute values.
class_count (int) – Number of classes.
random (Random) – Random number generator.

static exchange_tree_for_class(node, class_count, random)

Exchange a mid-tree node for a class. The new class is selected randomly.

Parameters:

node (Node) – The mid-tree node.
class_count (int) – Number of classes.
random (Random) – Random number generator.

static exchange_tree_for_tree(node, att_indexes, att_values, class_count, random)

Exchange a mid-tree node for a new subtree. The new subtree is created with a random depth.

Parameters:

node (Node) – The mid-tree node.
att_indexes (list) – List of attribute indexes.
att_values (list) – List of attribute values.
class_count (int) – Number of classes.
random (Random) – Random number generator.

static mutate_leaf(node, att_indexes, att_values, class_count, random)

Mutate a leaf node. The mutation operation can be one of the following:

Change the class of a leaf node.
Exchange a leaf node for a new subtree.

Parameters:

node (Node) – The leaf node.
att_indexes (list) – List of attribute indexes.
att_values (list) – List of attribute values.
class_count (int) – Number of classes.
random (Random) – Random number generator.

static mutate_operator(node, att_indexes, att_values, class_count, random)

Mutate a mid-tree node. The mutation operation can be one of the following:

Change the attribute of an operator node.
Change the attribute value of an operator node.
Exchange an operator node for a class.
Exchange an operator node for a new subtree.

Parameters:

node (Node) – The mid-tree node.
att_indexes (list) – List of attribute indexes.
att_values (list) – List of attribute values.
class_count (int) – Number of classes.
random (Random) – Random number generator.

static mutation(root, att_indexes, att_values, class_count, random)

Mutation introduces random changes to a tree to maintain genetic diversity and explore new solutions. This helps in avoiding local optima by introducing new genetic structures.

Pseudocode of the implementation:

Randomly select a node within the tree.
Depending on whether the selected node is a leaf or an internal node, apply different mutation strategies:
- Leaf Mutation: Change the class label or replace the leaf with a new subtree.
- Internal Node Mutation: Change the attribute, change the attribute value, replace the node with a class label, or replace the node with a new subtree.
Ensure the mutated node maintains the structural integrity of the tree.
Return the root of the mutated tree.

Parameters:

root (Node) – The root node of the tree.
att_indexes (list) – List of attribute indexes.
att_values (list) – List of attribute values.
class_count (int) – Number of classes.
random (Random) – Random number generator.

Returns:

The mutated node.

Return type:

Node

class gatree.ga.selection.Selection

Bases: object

Class implementing the selection operator for the genetic algorithm.

Parameters:

population (list) – List of trees.
selection_tournament_size (int) – Number of trees to select.
random (Random) – Random number generator.

selection(selection_tournament_size, random)

Selection is the process of choosing parent trees from the current population to produce offspring for the next generation. By default, GATree class uses tournament selection, a method where a subset of the population is randomly chosen, and the best individual from this subset is selected.

Pseudocode of the implementation:

Randomly select selection_tournament_size trees from the population.
Evaluate the fitness of the selected trees.
Choose the tree with the best fitness from the selected subset.
Repeat the process to select another parent.
Ensure the selected parents are different to maintain genetic diversity.

Parameters:

population (list) – List of trees.
selection_tournament_size (int) – Number of trees to select.
random (Random) – Random number generator.

Returns:

The two selected trees.

Return type:

tuple