GitHub

Genetic Operators

SymbolicOptimization provides operators for generating, mutating, and recombining expression trees.

Tree Generation

tree = generate_tree(grammar; method=GrowMethod(), max_depth=4)
pop = generate_population(grammar, 100; method=HalfAndHalfMethod())

Generation methods:

Mutation

mutated = mutate(tree, grammar)               # Auto-select type
mutated = mutate_point(tree, grammar)         # Swap operator/variable
mutated = mutate_subtree(tree, grammar)       # Replace subtree
mutated = mutate_hoist(tree)                  # Promote subtree to root
mutated = mutate_constants(tree; std=0.5)     # Perturb constants
mutated = mutate_single_constant(tree)        # Perturb one constant
mutated = mutate_insert(tree, grammar)        # Add operator
mutated = mutate_delete(tree)                 # Remove operator

Crossover

child1, child2 = crossover(parent1, parent2)                # Subtree exchange
child1, child2 = crossover_subtree(parent1, parent2)        # Same as above
child1, child2 = crossover_one_point(parent1, parent2)      # One-point
child1, child2 = crossover_uniform(parent1, parent2)        # Uniform
child1, child2 = crossover_size_fair(parent1, parent2)      # Size-fair

Simplification

simplified = simplify(tree; grammar=grammar)   # Constant folding + algebra
simplified = simplify_algebra(tree)            # x + 0 -> x, x * 1 -> x, etc.
simplified = simplify_constants(tree)          # 1 + 2 -> 3
normalized = normalize_constants(tree)         # Round near-integer constants
clamped = clamp_constants(tree)                # Clamp extreme values

For deep algebraic simplification, see Advanced Topics.

Operators Reference

SymbolicOptimization.FullMethod — Type
FullMethod <: GenerationMethod

Generate trees where all branches have exactly the specified depth. All paths from root to leaves have the same length.

source
SymbolicOptimization.generate_tree — Function
generate_tree(grammar::Grammar; kwargs...) -> AbstractNode

Generate a random expression tree from the grammar.

Keyword Arguments

  • method::GenerationMethod = GrowMethod(): Generation strategy
  • min_depth::Int = 1: Minimum tree depth
  • max_depth::Int = 4: Maximum tree depth
  • target_type::Symbol = :Any: Target output type (for typed grammars)
  • rng::AbstractRNG = Random.GLOBAL_RNG: Random number generator

Examples

g = Grammar(binary_operators=[+, *], unary_operators=[sin], variables=[:x])

tree = generate_tree(g, max_depth=3)
tree = generate_tree(g, method=FullMethod(), max_depth=4)
tree = generate_tree(g, method=HalfAndHalfMethod(), min_depth=2, max_depth=5)
source
SymbolicOptimization.generate_population — Function
generate_population(grammar::Grammar, n::Int; kwargs...) -> Vector{AbstractNode}

Generate a population of random trees.

Arguments

  • grammar: The grammar to use
  • n: Number of trees to generate

Keyword Arguments

Same as generate_tree, plus:

  • unique::Bool = false: If true, ensure all trees are structurally unique
  • max_attempts::Int = n * 10: Maximum attempts when generating unique trees
source
SymbolicOptimization.generate_random_subtree — Function
generate_random_subtree(grammar::Grammar; max_depth=3, target_type=:Any, rng=Random.GLOBAL_RNG) -> AbstractNode

Generate a random subtree with the given maximum depth. Alias for generate_tree with GrowMethod.

source
SymbolicOptimization.mutate — Function
mutate(tree::AbstractNode, grammar::Grammar; kwargs...) -> AbstractNode

Apply mutation to an expression tree.

Keyword Arguments

  • rng::AbstractRNG = Random.GLOBAL_RNG: Random number generator
  • p_point::Float64 = 0.3: Probability of point mutation
  • p_subtree::Float64 = 0.3: Probability of subtree mutation
  • p_hoist::Float64 = 0.1: Probability of hoist mutation
  • p_constant::Float64 = 0.2: Probability of constant perturbation
  • p_insert::Float64 = 0.05: Probability of insert mutation
  • p_delete::Float64 = 0.05: Probability of delete mutation
  • max_depth::Int = 4: Maximum depth for new subtrees
  • constant_std::Float64 = 0.5: Standard deviation for constant perturbation

Returns a new mutated tree (original is not modified).

source
SymbolicOptimization.mutate_point — Function
mutate_point(tree::AbstractNode, grammar::Grammar; rng=Random.GLOBAL_RNG) -> AbstractNode

Replace a random node with another node of the same arity/type.

  • Function nodes: Replace with another function of same arity
  • Variables: Replace with another variable
  • Constants: Replace with a new random constant
source
SymbolicOptimization.mutate_subtree — Function
mutate_subtree(tree::AbstractNode, grammar::Grammar; rng=Random.GLOBAL_RNG, max_depth=4) -> AbstractNode

Replace a random subtree with a newly generated subtree.

source
SymbolicOptimization.mutate_hoist — Function
mutate_hoist(tree::AbstractNode; rng=Random.GLOBAL_RNG) -> AbstractNode

Replace the tree with one of its subtrees, effectively "hoisting" it up. Tends to simplify/shrink trees.

source
SymbolicOptimization.mutate_insert — Function
mutate_insert(tree::AbstractNode, grammar::Grammar; rng=Random.GLOBAL_RNG) -> AbstractNode

Insert a new operator above a random node, making the original node a child. Tends to grow trees.

source
SymbolicOptimization.mutate_delete — Function
mutate_delete(tree::AbstractNode; rng=Random.GLOBAL_RNG) -> AbstractNode

Delete a function node by replacing it with one of its children. Tends to shrink trees.

source
SymbolicOptimization.crossover — Function
crossover(parent1::AbstractNode, parent2::AbstractNode; kwargs...) -> Tuple{AbstractNode, AbstractNode}

Perform crossover between two parent trees, producing two offspring.

Keyword Arguments

  • rng::AbstractRNG = Random.GLOBAL_RNG: Random number generator
  • max_depth::Int = 10: Maximum depth of resulting trees
  • internal_prob::Float64 = 0.9: Probability of selecting internal (non-terminal) nodes

Returns a tuple of two new trees (originals are not modified).

source
SymbolicOptimization.crossover_subtree — Function
crossover_subtree(parent1::AbstractNode, parent2::AbstractNode; kwargs...) -> Tuple{AbstractNode, AbstractNode}

Standard subtree crossover (Koza-style).

Selects a random subtree from each parent and swaps them.

source
SymbolicOptimization.crossover_one_point — Function
crossover_one_point(parent1::AbstractNode, parent2::AbstractNode; kwargs...) -> Tuple{AbstractNode, AbstractNode}

One-point crossover: only the first child is produced by swapping subtrees. The second child is the other swap direction.

source
SymbolicOptimization.crossover_uniform — Function
crossover_uniform(parent1::AbstractNode, parent2::AbstractNode; kwargs...) -> Tuple{AbstractNode, AbstractNode}

Uniform crossover: at each node position, randomly choose from either parent.

Note: This only works well when parents have similar structure. Falls back to subtree crossover if structures are too different.

source
SymbolicOptimization.crossover_size_fair — Function
crossover_size_fair(parent1::AbstractNode, parent2::AbstractNode; kwargs...) -> Tuple{AbstractNode, AbstractNode}

Size-fair crossover: tries to select subtrees of similar size to avoid bloat.

source
SymbolicOptimization.simplify — Function
simplify(tree::AbstractNode; grammar::Union{Grammar,Nothing}=nothing, iterations::Int=3) -> AbstractNode

Apply all simplification passes repeatedly until the tree stabilizes.

Arguments

  • tree: The tree to simplify
  • grammar: Optional grammar for evaluation during constant folding. If provided with isempty(grammar.constants), no new constants will be created during simplification.
  • iterations: Maximum number of simplification passes
source
SymbolicOptimization.simplify_algebra — Function
simplify_algebra(tree::AbstractNode; grammar::Union{Grammar,Nothing}=nothing) -> AbstractNode

Apply basic algebraic simplification rules.

Rules include:

  • x + 0 → x, x - 0 → x, x * 1 → x, x / 1 → x
  • x * 0 → 0, 0 / x → 0 (only if constants allowed)
  • x - x → 0, x / x → 1 (only if constants allowed)
  • x ^ 0 → 1, x ^ 1 → x (constant creation only if allowed)
  • sin(0) → 0, cos(0) → 1, etc. (only if constants allowed)

When grammar is provided and has no constants (isempty(grammar.constants)), rules that would create new constant nodes are skipped. This ensures that constant_range = nothing is respected throughout the optimization process.

source
SymbolicOptimization.simplify_constants — Function
simplify_constants(tree::AbstractNode; grammar::Union{Grammar,Nothing}=nothing) -> AbstractNode

Evaluate and fold constant subexpressions.

Replaces subtrees that contain only constants with their evaluated result.

Note: This function only folds existing constants - it does not create new ones from variable expressions. Use simplify_algebra for algebraic simplifications.

source
SymbolicOptimization.normalize_constants — Function
normalize_constants(tree::AbstractNode; digits::Int=6) -> AbstractNode

Round all constants to a specified number of digits. Helps with numerical stability and canonical forms.

source