TreeGenome Reference

Tree-structured genome for genetic programming.

Module

use fugue_evo::genome::tree::{TreeGenome, TreeNode, ArithmeticTerminal, ArithmeticFunction};

Construction

// Generate full tree (all branches same depth)
let tree = TreeGenome::generate_full(&mut rng, min_depth, max_depth);

// Generate grow tree (variable depth)
let tree = TreeGenome::generate_grow(&mut rng, max_depth, terminal_prob);

// From root node
let root = TreeNode::function(Add, vec![
    TreeNode::terminal(X),
    TreeNode::terminal(Constant(1.0)),
]);
let tree = TreeGenome::new(root, 10);

TreeNode Types

pub enum TreeNode<T, F> {
    Terminal(T),           // Leaf node
    Function(F, Vec<Self>), // Internal node with children
}

Built-in Terminals

pub enum ArithmeticTerminal {
    X,              // Variable
    Constant(f64),  // Numeric constant
}

Built-in Functions

pub enum ArithmeticFunction {
    Add,  // Binary +
    Sub,  // Binary -
    Mul,  // Binary *
    Div,  // Protected division
}

Methods

Tree Properties

MethodReturnDescription
size()usizeTotal number of nodes
depth()usizeMaximum depth
height()usizeSame as depth

Evaluation

MethodDescription
evaluate(inputs)Evaluate tree with input values

Representation

MethodReturnDescription
to_sexpr()StringS-expression format
to_infix()StringInfix notation
MethodDescription
root.positions()Get all node positions
root.get_subtree(pos)Get subtree at position
root.replace_subtree(pos, new)Replace subtree

Operators

Crossover

fn subtree_crossover<T, F>(
    parent1: &TreeGenome<T, F>,
    parent2: &TreeGenome<T, F>,
    rng: &mut impl Rng,
) -> TreeGenome<T, F> {
    // Select random subtrees and exchange
}

Mutation

// Point mutation: change single node
fn point_mutate<T, F>(tree: &mut TreeGenome<T, F>, rng: &mut impl Rng);

// Subtree mutation: replace subtree with random
fn subtree_mutate<T, F>(tree: &mut TreeGenome<T, F>, rng: &mut impl Rng);

// Hoist mutation: replace tree with subtree
fn hoist_mutate<T, F>(tree: &mut TreeGenome<T, F>, rng: &mut impl Rng);

Custom Primitives

Define your own terminals and functions:

#[derive(Clone, Debug)]
pub enum MyTerminal {
    X, Y,  // Two variables
    Constant(f64),
}

#[derive(Clone, Debug)]
pub enum MyFunction {
    Add, Sub, Mul, Div,
    Sin, Cos, Exp, Log,
}

impl MyFunction {
    fn arity(&self) -> usize {
        match self {
            Add | Sub | Mul | Div => 2,
            Sin | Cos | Exp | Log => 1,
        }
    }

    fn apply(&self, args: &[f64]) -> f64 {
        match self {
            Add => args[0] + args[1],
            Sub => args[0] - args[1],
            Mul => args[0] * args[1],
            Div => if args[1].abs() < 1e-10 { 1.0 } else { args[0] / args[1] },
            Sin => args[0].sin(),
            Cos => args[0].cos(),
            Exp => args[0].exp().min(1e10),
            Log => if args[0] > 0.0 { args[0].ln() } else { 0.0 },
        }
    }
}

Bloat Control

Depth Limiting

if child.depth() > max_depth {
    child = parent.clone();  // Reject oversized trees
}

Parsimony Pressure

let fitness = raw_fitness - tree.size() as f64 * parsimony_coeff;

Example

See Genetic Programming Tutorial for a complete symbolic regression example.

See Also