Skip to content

Trees

A tree represents a hierarchical structure where each node has exactly one parent (except the root) and zero or more children. When combined with the ops, it allows for the evolution of mathematical expressions, decision trees, and symbolic regression.

op-tree

Building a Tree

Trees in python aren't quite as expressive as in rust, but they can still be constructed and used in a similar way.

import radiate as rd

tree = rd.Tree(
    min_height=3,       # Default
    max_size=30,        # Default
    root=rd.Op.add(),   # The root operation - isn't necessary to specify
    vertex=[rd.Op.add(), rd.Op.sub(), rd.Op.mul(), rd.Op.div()],
    leaf=[rd.Op.var(0), rd.Op.var(1)],
)

result = tree.eval([1, 2]) 

use radiate::*;

// create a simple tree:
//              42
//           /  |   \
//          1   2    3
//             / \    
//            3   4    
let tree: Tree<i32> = Tree::new(TreeNode::new(42)
    .attach(TreeNode::new(1))
    .attach(TreeNode::new(2)
        .attach(TreeNode::new(3))
        .attach(TreeNode::new(4))
    .attach(TreeNode::new(3))));

// The tree can be evaluated with a function that takes a vector of inputs
// This creates a `Tree` that looks like:
//      +
//    /   \
//   *     +
//  / \   / \
// 2  3  2   x
//
// Where `x` is the first variable in the input.
// This can also be thought of (and is functionally equivalent) as:
//
// f(x) = (2 * 3) + (2 + x)
//
let root = TreeNode::new(Op::add())
    .attach(
        TreeNode::new(Op::mul())
            .attach(TreeNode::new(Op::constant(2.0)))
            .attach(TreeNode::new(Op::constant(3.0))),
    )
    .attach(
        TreeNode::new(Op::add())
            .attach(TreeNode::new(Op::constant(2.0)))
            .attach(TreeNode::new(Op::var(0))),
    );

// And the result of evaluating this tree with an input of `1` would be:
let result = root.eval(&vec![1_f32]);
assert_eq!(result, 9.0);

Key Properties:

  • Rooted: Always has a single root node
  • Acyclic: No node is its own ancestor
  • Hierarchical: Parent-child relationships

Node

Each node in a tree contains a value and optional children & arity. The TreeNode also implements the gene trait, making the node itself a gene and it's value the allele.

Node Types:

  • Root: Starting point of the tree (can have any number of children)
  • Vertex: Internal computation nodes (can have any number of children)
  • Leaf: Terminal nodes with no children (arity is Arity::Zero)

Codec

The TreeCodec is simply a codec that encodes a TreeChromosome and decodes it back into a Tree. The TreeCodec can be configured to create a single tree or a multi-root tree structure.

Codec Types:

  • Single Root: Creates one tree per genotype
  • Multi-Root: Creates multiple trees per genotype
import radiate as rd

# Create a tree codec with a starting (minimum) depth of 3
codec = rd.TreeCodec(
    shape=(2, 1),
    min_depth=3,
    max_size=30,
    root=rd.Op.add(),
    vertex=[rd.Op.add(), rd.Op.sub(), rd.Op.mul()],
    leaf=[rd.Op.var(0), rd.Op.var(1)],
)

genotype = codec.encode()  
tree = codec.decode(genotype)

use radiate::*;

let store = vec![
    (NodeType::Root, vec![Op::add(), Op::sub()]),
    (NodeType::Vertex, vec![Op::add(), Op::sub(), Op::mul()]),
    (NodeType::Leaf, vec![Op::constant(1.0), Op::constant(2.0)]),
];

// Create a single rooted tree codec with a starting (minimum) depth of 3
let codec = TreeCodec::single(3, store);
let genotype: Genotype<TreeChromosome<Op<f32>>> = single_root_codec.encode();
let tree: Tree<Op<f32>> = codec.decode(&genotype);

// Create a multi-rooted tree codec with a starting (minimum) depth of 3 and 2 trees
let codec = TreeCodec::multi_root(3, 2, store);
let genotype: Genotype<TreeChromosome<Op<f32>>> = codec.encode();
// multi-rooted codec decodes to a Vec of Trees
// one for each root in the genotype
let trees: Vec<Tree<Op<f32>>> = codec.decode(&genotype);

Alters

HoistMutator

Inputs

  • rate: f32 - Mutation rate (0.0 to 1.0)
  • Purpose: Randomly hoists subtrees from one part of the tree to another.

The HoistMutator is a mutation operator that randomly selects a subtree from the tree and moves it to a different location in the tree. This can create new structures and relationships between nodes, allowing for more complex solutions to emerge.

import radiate as rd

mutator = rd.HoistMutator(rate=0.1)

use radiate::*;

let mutator = HoistMutator::new(0.1);

TreeCrossover

Inputs

  • rate: f32 - Mutation rate (0.0 to 1.0)
  • Purpose: Swaps two subtrees between two trees.

The TreeCrossover is a crossover operator that randomly selects a subtree from one parent tree and swaps it with a subtree from another parent tree.

import radiate as rd

mutator = rd.TreeCrossover(rate=0.1)

use radiate::*;

let mutator = TreeCrossover::new(0.1);