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.
Building a Tree
Trees in python aren't quite as expressive as in rust. A Tree is produced from a TreeCodec — encode a genotype, then decode it into a Tree you can evaluate.
import radiate as rd
codec = rd.TreeCodec(
shape=(2, 1), # 2 inputs, 1 output
min_depth=3, # starting depth of the tree (default 3)
max_size=30, # max number of nodes (default 30)
vertex=[rd.Op.add(), rd.Op.sub(), rd.Op.mul(), rd.Op.div()],
leaf=[rd.Op.var(0), rd.Op.var(1)],
)
# decode a (randomly initialized) genotype into a Tree
tree = codec.decode(codec.encode())
result = tree.eval([1.0, 2.0]) # list[float], one value per output
// 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("two", 2.0)))
.attach(TreeNode::new(Op::constant("three", 3.0))),
)
.attach(
TreeNode::new(Op::add())
.attach(TreeNode::new(Op::constant("two", 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(&[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 its value the allele.
Node Types:
- Root: Starting point of the tree (number of children is determined by its op's arity)
- Vertex: Internal computation nodes (number of children is determined by the op's arity)
- 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. Upon creation the codec will produce a 'perfect arity tree' of a specified min depth. This means that the initial tree will contain nodes each with children equal to their value's (op) arity. The max_size parameter can be used to limit the size of the tree, preventing it from growing too large (bloat) during evolution.
Radiate supports both single-rooted and multi-rooted tree structures to be evolved. The choice between these two structures essentially comes down to how many outputs you want to produce. For example, if you just want to evolve a single mathematical expression like such:
Then a single rooted tree would be sufficient. However, if you wanted to evolve a system of equations like such:
Then a multi-rooted tree would be necessary, with one root for f(x) and another for g(x).
Ops
The codec builds its trees from the ops you give it for each node role:
- Leaf: the terminals (inputs and constants).
- Vertex: the internal nodes. These must be provided, there are no default ops.
- Root: optional. When left unspecified, the root samples from the vertex options.
One Op.var(i) per input is always added to the leaves, so leaf= only needs extra terminals such as constants or Op.erc(). max_size defaults to 30.
The ops come from a NodeSet with Root, Vertex and Leaf entries. max_size defaults to 200.
import radiate as rd
# Create a tree codec with a starting (minimum) depth of 3
codec = rd.TreeCodec(
# Shape is (number of inputs, number of outputs). Each input becomes a
# `var` leaf, and each output is its own tree (a multi-rooted tree).
#
# Default: shape=(1, 1) - single rooted tree with 1 input variable
shape=(2, 1),
# The minimum depth of the tree. This is the depth
# of the initial tree that will be produced by
# the codec - evolution will be able
# to increase the total size of the tree (without regards to depth) up to max_size.
#
# Default: min_depth=3
min_depth=3,
# The maximum size of the tree. This is the maximum number of nodes that the tree can have.
#
# Default: max_size=30
max_size=30,
# The options for the root node of the tree. The root is the last node in the tree
# to be evaluated and is the node that produces the final output of the tree.
# This is optional; when left unspecified, the root samples from the vertex options.
root=rd.Op.add(),
# The options for the internal nodes. Required - there are no default ops.
vertex=[rd.Op.add(), rd.Op.sub(), rd.Op.mul()],
# Extra leaf options. One `var` per input is always included, so these are added
# on top of them - here an ephemeral random constant.
leaf=[rd.Op.erc()],
)
genotype = codec.encode()
tree = codec.decode(genotype)
let store = node_set![
Root => [Op::add(), Op::sub()],
Vertex => [Op::add(), Op::sub(), Op::mul()],
Leaf => [Op::constant("one", 1.0), Op::constant("two", 2.0)]
];
// Create a single rooted tree codec with a starting (minimum) depth of 3
// `max_size` caps the number of nodes per tree (default 200)
let codec = TreeCodec::single(3, store.clone()).max_size(50);
let genotype: Genotype<TreeChromosome<Op<f32>>> = 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.
SubtreeMutator
Inputs
rate: f32 - Mutation rate (0.0 to 1.0)max_depth: int - Maximum depth of the newly grown subtree (default 2)
- Purpose: Replaces a random subtree with a newly grown one.
The SubtreeMutator is the classic Koza-style subtree mutation. It picks a random non-root node, grows a fresh random subtree of up to max_depth levels from the tree's ops, and puts it in that node's place. If the result breaks the tree's max_size, the change is rolled back. It is often the most effective tree mutator for symbolic regression.
TreeCrossover
Inputs
rate: f32 - Crossover rate (0.0 to 1.0)max_size: int - Offspring with more nodes than this are rejected
- 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.