9686354911

Committed 26 Jun 2024 08:31PM UTC coverage: 93.22% (-1.4%) from 94.617%

Build # 9686354911

Build Type

Pull #326

github

Committed by

web-flow

Commit Message

Merge 6f8229c9f into ceddaa424

Pull Request Pull Request #326: BREAKING: Change expression types to `DynamicExpressions.Expression` (from `DynamicExpressions.Node`)

Run Details

275 of 296 new or added lines in 17 files covered. (92.91%)

34 existing lines in 5 files now uncovered.

2530 of 2714 relevant lines covered (93.22%)

32081968.55 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

81.22

/src/MutationFunctions.jl

module MutationFunctionsModule

using Random: default_rng, AbstractRNG
using DynamicExpressions:
    AbstractExpressionNode,
    AbstractExpression,
    AbstractNode,
    NodeSampler,
    get_contents,
    with_contents,
    constructorof,
    copy_node,
    set_node!,
    count_nodes,
    has_constants,
    has_operators
using Compat: Returns, @inline
using ..CoreModule: Options, DATA_TYPE

"""
    random_node(tree::AbstractNode; filter::F=Returns(true))

Return a random node from the tree. You may optionally
filter the nodes matching some condition before sampling.
"""
function random_node(
    tree::AbstractNode, rng::AbstractRNG=default_rng(); filter::F=Returns(true)
) where {F<:Function}
    Base.depwarn(
        "Instead of `random_node(tree, filter)`, use `rand(NodeSampler(; tree, filter))`",
        :random_node,
    )
    return rand(rng, NodeSampler(; tree, filter))
end

"""Swap operands in binary operator for ops like pow and divide"""
function swap_operands(ex::AbstractExpression, rng::AbstractRNG=default_rng())
    tree = get_contents(ex)
    ex = with_contents(ex, swap_operands(tree, rng))
    return ex
end
function swap_operands(tree::AbstractNode, rng::AbstractRNG=default_rng())
    if !any(node -> node.degree == 2, tree)
        return tree
    end
    node = rand(rng, NodeSampler(; tree, filter=t -> t.degree == 2))
    node.l, node.r = node.r, node.l
    return tree
end

"""Randomly convert an operator into another one (binary->binary; unary->unary)"""
function mutate_operator(
    ex::AbstractExpression{T}, options::Options, rng::AbstractRNG=default_rng()
) where {T<:DATA_TYPE}
    tree = get_contents(ex)
    ex = with_contents(ex, mutate_operator(tree, options, rng))
    return ex
end
function mutate_operator(
    tree::AbstractExpressionNode{T}, options::Options, rng::AbstractRNG=default_rng()
) where {T}
    if !(has_operators(tree))
        return tree
    end
    node = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))
    if node.degree == 1
        node.op = rand(rng, 1:(options.nuna))
    else
        node.op = rand(rng, 1:(options.nbin))
    end
    return tree
end

"""Randomly perturb a constant"""
function mutate_constant(
    ex::AbstractExpression{T}, temperature, options::Options, rng::AbstractRNG=default_rng()
) where {T<:DATA_TYPE}
    tree = get_contents(ex)
    ex = with_contents(ex, mutate_constant(tree, temperature, options, rng))
    return ex
end
function mutate_constant(
    tree::AbstractExpressionNode{T},
    temperature,
    options::Options,
    rng::AbstractRNG=default_rng(),
) where {T<:DATA_TYPE}
    # T is between 0 and 1.

    if !(has_constants(tree))
        return tree
    end
    node = rand(rng, NodeSampler(; tree, filter=t -> (t.degree == 0 && t.constant)))

    node.val *= mutate_factor(T, temperature, options, rng)

    return tree
end

function mutate_factor(::Type{T}, temperature, options, rng) where {T<:DATA_TYPE}
    bottom = 1//10
    maxChange = options.perturbation_factor * temperature + 1 + bottom
    factor = T(maxChange^rand(rng, T))
    makeConstBigger = rand(rng, Bool)

    factor = makeConstBigger ? factor : 1 / factor

    if rand(rng) > options.probability_negate_constant
        factor *= -1
    end
    return factor
end

# TODO: Shouldn't we add a mutate_feature here?

"""Add a random unary/binary operation to the end of a tree"""
function append_random_op(
    ex::AbstractExpression{T},
    options::Options,
    nfeatures::Int,
    rng::AbstractRNG=default_rng();
    makeNewBinOp::Union{Bool,Nothing}=nothing,
) where {T<:DATA_TYPE}
    tree = get_contents(ex)
    ex = with_contents(ex, append_random_op(tree, options, nfeatures, rng; makeNewBinOp))
    return ex
end
function append_random_op(
    tree::AbstractExpressionNode{T},
    options::Options,
    nfeatures::Int,
    rng::AbstractRNG=default_rng();
    makeNewBinOp::Union{Bool,Nothing}=nothing,
) where {T<:DATA_TYPE}
    node = rand(rng, NodeSampler(; tree, filter=t -> t.degree == 0))

    if makeNewBinOp === nothing
        choice = rand(rng)
        makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)
    end

    if makeNewBinOp
        newnode = constructorof(typeof(tree))(;
            op=rand(rng, 1:(options.nbin)),
            l=make_random_leaf(nfeatures, T, typeof(tree), rng, options),
            r=make_random_leaf(nfeatures, T, typeof(tree), rng, options),
        )
    else
        newnode = constructorof(typeof(tree))(;
            op=rand(rng, 1:(options.nuna)),
            l=make_random_leaf(nfeatures, T, typeof(tree), rng, options),
        )
    end

    set_node!(node, newnode)

    return tree
end

"""Insert random node"""
function insert_random_op(
    ex::AbstractExpression{T},
    options::Options,
    nfeatures::Int,
    rng::AbstractRNG=default_rng(),
) where {T<:DATA_TYPE}
    tree = get_contents(ex)
    ex = with_contents(ex, insert_random_op(tree, options, nfeatures, rng))
    return ex
end
function insert_random_op(
    tree::AbstractExpressionNode{T},
    options::Options,
    nfeatures::Int,
    rng::AbstractRNG=default_rng(),
) where {T<:DATA_TYPE}
    node = rand(rng, NodeSampler(; tree))
    choice = rand(rng)
    makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)
    left = copy_node(node)

    if makeNewBinOp
        right = make_random_leaf(nfeatures, T, typeof(tree), rng, options)
        newnode = constructorof(typeof(tree))(;
            op=rand(rng, 1:(options.nbin)), l=left, r=right
        )
    else
        newnode = constructorof(typeof(tree))(; op=rand(rng, 1:(options.nuna)), l=left)
    end
    set_node!(node, newnode)
    return tree
end

"""Add random node to the top of a tree"""
function prepend_random_op(
    ex::AbstractExpression{T},
    options::Options,
    nfeatures::Int,
    rng::AbstractRNG=default_rng(),
) where {T<:DATA_TYPE}
    tree = get_contents(ex)
    ex = with_contents(ex, prepend_random_op(tree, options, nfeatures, rng))
    return ex
end
function prepend_random_op(
    tree::AbstractExpressionNode{T},
    options::Options,
    nfeatures::Int,
    rng::AbstractRNG=default_rng(),
) where {T<:DATA_TYPE}
    node = tree
    choice = rand(rng)
    makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)
    left = copy_node(tree)

    if makeNewBinOp
        right = make_random_leaf(nfeatures, T, typeof(tree), rng, options)
        newnode = constructorof(typeof(tree))(;
            op=rand(rng, 1:(options.nbin)), l=left, r=right
        )
    else
        newnode = constructorof(typeof(tree))(; op=rand(rng, 1:(options.nuna)), l=left)
    end
    set_node!(node, newnode)
    return node
end

function make_random_leaf(
    nfeatures::Int,
    ::Type{T},
    ::Type{N},
    rng::AbstractRNG=default_rng(),
    ::Union{Options,Nothing}=nothing,
) where {T<:DATA_TYPE,N<:AbstractExpressionNode}
    if rand(rng, Bool)
        return constructorof(N)(; val=randn(rng, T))
    else
        return constructorof(N)(T; feature=rand(rng, 1:nfeatures))
    end
end

"""Return a random node from the tree with parent, and side ('n' for no parent)"""
function random_node_and_parent(tree::AbstractNode, rng::AbstractRNG=default_rng())
    if tree.degree == 0
        return tree, tree, 'n'
    end
    parent = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))
    if parent.degree == 1 || rand(rng, Bool)
        return (parent.l, parent, 'l')
    else
        return (parent.r, parent, 'r')
    end
end

"""Select a random node, and splice it out of the tree."""
function delete_random_op!(
    ex::AbstractExpression{T},
    options::Options,
    nfeatures::Int,
    rng::AbstractRNG=default_rng(),
) where {T<:DATA_TYPE}
    tree = get_contents(ex)
    ex = with_contents(ex, delete_random_op!(tree, options, nfeatures, rng))
    return ex
end
function delete_random_op!(
    tree::AbstractExpressionNode{T},
    options::Options,
    nfeatures::Int,
    rng::AbstractRNG=default_rng(),
) where {T<:DATA_TYPE}
    node, parent, side = random_node_and_parent(tree, rng)
    isroot = side == 'n'

    if node.degree == 0
        # Replace with new constant
        newnode = make_random_leaf(nfeatures, T, typeof(tree), rng, options)
        set_node!(node, newnode)
    elseif node.degree == 1
        # Join one of the children with the parent
        if isroot
            return node.l
        elseif parent.l == node
            parent.l = node.l
        else
            parent.r = node.l
        end
    else
        # Join one of the children with the parent
        if rand(rng, Bool)
            if isroot
                return node.l
            elseif parent.l == node
                parent.l = node.l
            else
                parent.r = node.l
            end
        else
            if isroot
                return node.r
            elseif parent.l == node
                parent.l = node.r
            else
                parent.r = node.r
            end
        end
    end
    return tree
end

"""Create a random equation by appending random operators"""
function gen_random_tree(
    length::Int, options::Options, nfeatures::Int, ::Type{T}, rng::AbstractRNG=default_rng()
) where {T<:DATA_TYPE}
    # Note that this base tree is just a placeholder; it will be replaced.
    tree = constructorof(options.node_type)(T; val=convert(T, 1))
    for i in 1:length
        # TODO: This can be larger number of nodes than length.
        tree = append_random_op(tree, options, nfeatures, rng)
    end
    return tree
end

function gen_random_tree_fixed_size(
    node_count::Int,
    options::Options,
    nfeatures::Int,
    ::Type{T},
    rng::AbstractRNG=default_rng(),
) where {T<:DATA_TYPE}
    tree = make_random_leaf(nfeatures, T, options.node_type, rng, options)
    cur_size = count_nodes(tree)
    while cur_size < node_count
        if cur_size == node_count - 1  # only unary operator allowed.
            options.nuna == 0 && break # We will go over the requested amount, so we must break.
            tree = append_random_op(tree, options, nfeatures, rng; makeNewBinOp=false)
        else
            tree = append_random_op(tree, options, nfeatures, rng)
        end
        cur_size = count_nodes(tree)
    end
    return tree
end

function crossover_trees(
    ex1::E, ex2::E, rng::AbstractRNG=default_rng()
) where {T,E<:AbstractExpression{T}}
    tree1 = get_contents(ex1)
    tree2 = get_contents(ex2)
    out1, out2 = crossover_trees(tree1, tree2, rng)
    ex1 = with_contents(ex1, out1)
    ex2 = with_contents(ex2, out2)
    return ex1, ex2
end

"""Crossover between two expressions"""
function crossover_trees(
    tree1::N, tree2::N, rng::AbstractRNG=default_rng()
) where {T,N<:AbstractExpressionNode{T}}
    tree1 = copy_node(tree1)
    tree2 = copy_node(tree2)

    node1, parent1, side1 = random_node_and_parent(tree1, rng)
    node2, parent2, side2 = random_node_and_parent(tree2, rng)

    node1 = copy_node(node1)

    if side1 == 'l'
        parent1.l = copy_node(node2)
        # tree1 now contains this.
    elseif side1 == 'r'
        parent1.r = copy_node(node2)
        # tree1 now contains this.
    else # 'n'
        # This means that there is no parent2.
        tree1 = copy_node(node2)
    end

    if side2 == 'l'
        parent2.l = node1
    elseif side2 == 'r'
        parent2.r = node1
    else # 'n'
        tree2 = node1
    end
    return tree1, tree2
end

function get_two_nodes_without_loop(tree::AbstractNode, rng::AbstractRNG; max_attempts=10)
    for _ in 1:max_attempts
        parent = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))
        new_child = rand(rng, NodeSampler(; tree, filter=t -> t !== tree))

        would_form_loop = any(t -> t === parent, new_child)
        if !would_form_loop
            return (parent, new_child, false)
        end
    end
    return (tree, tree, true)
end

function form_random_connection!(ex::AbstractExpression, rng::AbstractRNG=default_rng())
    tree = get_contents(ex)
    return with_contents(ex, form_random_connection!(tree, rng))
end
function form_random_connection!(tree::AbstractNode, rng::AbstractRNG=default_rng())
    if length(tree) < 5
        return tree
    end

    parent, new_child, would_form_loop = get_two_nodes_without_loop(tree, rng)

    if would_form_loop
        return tree
    end

    # Set one of the children to be this new child:
    if parent.degree == 1 || rand(rng, Bool)
        parent.l = new_child
    else
        parent.r = new_child
    end
    return tree
end

function break_random_connection!(ex::AbstractExpression, rng::AbstractRNG=default_rng())
    tree = get_contents(ex)
    return with_contents(ex, break_random_connection!(tree, rng))
end
function break_random_connection!(tree::AbstractNode, rng::AbstractRNG=default_rng())
    tree.degree == 0 && return tree
    parent = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))
    if parent.degree == 1 || rand(rng, Bool)
        parent.l = copy(parent.l)
    else
        parent.r = copy(parent.r)
    end
    return tree
end

end

1	module MutationFunctionsModule
2
3	using Random: default_rng, AbstractRNG
4	using DynamicExpressions:
5	AbstractExpressionNode,
6	AbstractExpression,
7	AbstractNode,
8	NodeSampler,
9	get_contents,
10	with_contents,
11	constructorof,
12	copy_node,
13	set_node!,
14	count_nodes,
15	has_constants,
16	has_operators
17	using Compat: Returns, @inline
18	using ..CoreModule: Options, DATA_TYPE
19
20	"""
21	random_node(tree::AbstractNode; filter::F=Returns(true))
22
23	Return a random node from the tree. You may optionally
24	filter the nodes matching some condition before sampling.
25	"""
26	function random_node(	×
27	tree::AbstractNode, rng::AbstractRNG=default_rng(); filter::F=Returns(true)
28	) where {F<:Function}
29	Base.depwarn(	×
30	"Instead of `random_node(tree, filter)`, use `rand(NodeSampler(; tree, filter))`",
31	:random_node,
32	)
33	return rand(rng, NodeSampler(; tree, filter))	×
34	end
35
36	"""Swap operands in binary operator for ops like pow and divide"""
37	function swap_operands(ex::AbstractExpression, rng::AbstractRNG=default_rng())	820,308✔
38	tree = get_contents(ex)	1,012,183✔
39	ex = with_contents(ex, swap_operands(tree, rng))	1,365,011✔
40	return ex	710,026✔
41	end
42	function swap_operands(tree::AbstractNode, rng::AbstractRNG=default_rng())	832,549✔
43	if !any(node -> node.degree == 2, tree)	1,996,203✔
44	return tree	×
45	end
46	node = rand(rng, NodeSampler(; tree, filter=t -> t.degree == 2))	19,138,224✔
47	node.l, node.r = node.r, node.l	832,546✔
48	return tree	832,543✔
49	end
50
51	"""Randomly convert an operator into another one (binary->binary; unary->unary)"""
52	function mutate_operator(	6,459,661✔
53	ex::AbstractExpression{T}, options::Options, rng::AbstractRNG=default_rng()
54	) where {T<:DATA_TYPE}
55	tree = get_contents(ex)	10,070,447✔
56	ex = with_contents(ex, mutate_operator(tree, options, rng))	10,718,149✔
57	return ex	6,521,900✔
58	end
59	function mutate_operator(	6,521,896✔
60	tree::AbstractExpressionNode{T}, options::Options, rng::AbstractRNG=default_rng()
61	) where {T}
62	if !(has_operators(tree))	6,523,262✔
63	return tree	×
64	end
65	node = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))	133,815,726✔
66	if node.degree == 1	6,523,225✔
67	node.op = rand(rng, 1:(options.nuna))	3,058,461✔
68	else
69	node.op = rand(rng, 1:(options.nbin))	3,464,825✔
70	end
71	return tree	6,523,247✔
72	end
73
74	"""Randomly perturb a constant"""
75	function mutate_constant(	8,163,727✔
76	ex::AbstractExpression{T}, temperature, options::Options, rng::AbstractRNG=default_rng()
77	) where {T<:DATA_TYPE}
78	tree = get_contents(ex)	10,349,707✔
79	ex = with_contents(ex, mutate_constant(tree, temperature, options, rng))	13,107,393✔
80	return ex	7,818,563✔
81	end
82	function mutate_constant(	7,823,208✔
83	tree::AbstractExpressionNode{T},
84	temperature,
85	options::Options,
86	rng::AbstractRNG=default_rng(),
87	) where {T<:DATA_TYPE}
88	# T is between 0 and 1.
89
90	if !(has_constants(tree))	7,823,166✔
91	return tree	698✔
92	end
93	node = rand(rng, NodeSampler(; tree, filter=t -> (t.degree == 0 && t.constant)))	245,913,337✔
94
95	node.val *= mutate_factor(T, temperature, options, rng)	7,822,586✔
96
97	return tree	7,822,315✔
98	end
99
100	function mutate_factor(::Type{T}, temperature, options, rng) where {T<:DATA_TYPE}	7,825,845✔
101	bottom = 1//10	7,825,168✔
102	maxChange = options.perturbation_factor * temperature + 1 + bottom	7,825,869✔
103	factor = T(maxChange^rand(rng, T))	7,825,876✔
104	makeConstBigger = rand(rng, Bool)	7,825,746✔
105
106	factor = makeConstBigger ? factor : 1 / factor	11,738,294✔
107
108	if rand(rng) > options.probability_negate_constant	7,825,741✔
109	factor *= -1	7,748,223✔
110	end
111	return factor	7,825,711✔
112	end
113
114	# TODO: Shouldn't we add a mutate_feature here?
115
116	"""Add a random unary/binary operation to the end of a tree"""
117	function append_random_op(	5,039,147✔
118	ex::AbstractExpression{T},
119	options::Options,
120	nfeatures::Int,
121	rng::AbstractRNG=default_rng();
122	makeNewBinOp::Union{Bool,Nothing}=nothing,
123	) where {T<:DATA_TYPE}
124	tree = get_contents(ex)	3,849,903✔
125	ex = with_contents(ex, append_random_op(tree, options, nfeatures, rng; makeNewBinOp))	4,098,782✔
126	return ex	2,795,817✔
127	end
128	function append_random_op(	49,509,800✔
129	tree::AbstractExpressionNode{T},
130	options::Options,
131	nfeatures::Int,
132	rng::AbstractRNG=default_rng();
133	makeNewBinOp::Union{Bool,Nothing}=nothing,
134	) where {T<:DATA_TYPE}
135	node = rand(rng, NodeSampler(; tree, filter=t -> t.degree == 0))	416,591,187✔
136
137	if makeNewBinOp === nothing	27,355,365✔
138	choice = rand(rng)	25,042,420✔
139	makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)	25,042,231✔
140	end
141
142	if makeNewBinOp	27,357,086✔
143	newnode = constructorof(typeof(tree))(;	16,454,735✔
144	op=rand(rng, 1:(options.nbin)),
145	l=make_random_leaf(nfeatures, T, typeof(tree), rng, options),
146	r=make_random_leaf(nfeatures, T, typeof(tree), rng, options),
147	)
148	else
149	newnode = constructorof(typeof(tree))(;	10,903,334✔
150	op=rand(rng, 1:(options.nuna)),
151	l=make_random_leaf(nfeatures, T, typeof(tree), rng, options),
152	)
153	end
154
155	set_node!(node, newnode)	27,355,907✔
156
157	return tree	27,356,411✔
158	end
159
160	"""Insert random node"""
161	function insert_random_op(	23,147,677✔
162	ex::AbstractExpression{T},
163	options::Options,
164	nfeatures::Int,
165	rng::AbstractRNG=default_rng(),
166	) where {T<:DATA_TYPE}
167	tree = get_contents(ex)	31,829,966✔
168	ex = with_contents(ex, insert_random_op(tree, options, nfeatures, rng))	34,602,480✔
169	return ex	23,425,756✔
170	end
171	function insert_random_op(	23,427,561✔
172	tree::AbstractExpressionNode{T},
173	options::Options,
174	nfeatures::Int,
175	rng::AbstractRNG=default_rng(),
176	) where {T<:DATA_TYPE}
177	node = rand(rng, NodeSampler(; tree))	34,601,182✔
178	choice = rand(rng)	23,429,283✔
179	makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)	23,428,887✔
180	left = copy_node(node)	34,602,195✔
181
182	if makeNewBinOp	23,428,667✔
183	right = make_random_leaf(nfeatures, T, typeof(tree), rng, options)	15,667,880✔
184	newnode = constructorof(typeof(tree))(;	15,667,853✔
185	op=rand(rng, 1:(options.nbin)), l=left, r=right
186	)
187	else
188	newnode = constructorof(typeof(tree))(; op=rand(rng, 1:(options.nuna)), l=left)	7,761,379✔
189	end
190	set_node!(node, newnode)	23,428,539✔
191	return tree	23,428,592✔
192	end
193
194	"""Add random node to the top of a tree"""
195	function prepend_random_op(	2,771,228✔
196	ex::AbstractExpression{T},
197	options::Options,
198	nfeatures::Int,
199	rng::AbstractRNG=default_rng(),
200	) where {T<:DATA_TYPE}
201	tree = get_contents(ex)	3,826,191✔
202	ex = with_contents(ex, prepend_random_op(tree, options, nfeatures, rng))	4,105,985✔
203	return ex	2,798,187✔
204	end
205	function prepend_random_op(	2,800,129✔
206	tree::AbstractExpressionNode{T},
207	options::Options,
208	nfeatures::Int,
209	rng::AbstractRNG=default_rng(),
210	) where {T<:DATA_TYPE}
211	node = tree	2,798,447✔
212	choice = rand(rng)	2,800,131✔
213	makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)	2,800,129✔
214	left = copy_node(tree)	4,105,982✔
215
216	if makeNewBinOp	2,800,136✔
217	right = make_random_leaf(nfeatures, T, typeof(tree), rng, options)	1,859,492✔
218	newnode = constructorof(typeof(tree))(;	1,859,495✔
219	op=rand(rng, 1:(options.nbin)), l=left, r=right
220	)
221	else
222	newnode = constructorof(typeof(tree))(; op=rand(rng, 1:(options.nuna)), l=left)	940,657✔
223	end
224	set_node!(node, newnode)	2,800,137✔
225	return node	2,800,125✔
226	end
227
228	function make_random_leaf(	76,605,788✔
229	nfeatures::Int,
230	::Type{T},
231	::Type{N},
232	rng::AbstractRNG=default_rng(),
233	::Union{Options,Nothing}=nothing,
234	) where {T<:DATA_TYPE,N<:AbstractExpressionNode}
235	if rand(rng, Bool)	76,603,901✔
236	return constructorof(N)(; val=randn(rng, T))	38,308,022✔
237	else
238	return constructorof(N)(T; feature=rand(rng, 1:nfeatures))	38,302,916✔
239	end
240	end
241
242	"""Return a random node from the tree with parent, and side ('n' for no parent)"""
243	function random_node_and_parent(tree::AbstractNode, rng::AbstractRNG=default_rng())	21,454,056✔
244	if tree.degree == 0	24,898,868✔
245	return tree, tree, 'n'	4,221✔
246	end
247	parent = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))	583,234,924✔
248	if parent.degree == 1 \|\| rand(rng, Bool)	38,951,568✔
249	return (parent.l, parent, 'l')	17,869,288✔
250	else
251	return (parent.r, parent, 'r')	7,026,006✔
252	end
253	end
254
255	"""Select a random node, and splice it out of the tree."""
256	function delete_random_op!(	19,781,437✔
257	ex::AbstractExpression{T},
258	options::Options,
259	nfeatures::Int,
260	rng::AbstractRNG=default_rng(),
261	) where {T<:DATA_TYPE}
262	tree = get_contents(ex)	27,278,071✔
263	ex = with_contents(ex, delete_random_op!(tree, options, nfeatures, rng))	29,282,267✔
264	return ex	19,976,359✔
265	end
266	function delete_random_op!(	19,979,225✔
267	tree::AbstractExpressionNode{T},
268	options::Options,
269	nfeatures::Int,
270	rng::AbstractRNG=default_rng(),
271	) where {T<:DATA_TYPE}
272	node, parent, side = random_node_and_parent(tree, rng)	40,901,218✔
273	isroot = side == 'n'	19,979,513✔
274
275	if node.degree == 0	19,979,509✔
276	# Replace with new constant
277	newnode = make_random_leaf(nfeatures, T, typeof(tree), rng, options)	11,964,083✔
278	set_node!(node, newnode)	17,964,446✔
279	elseif node.degree == 1	8,015,703✔
280	# Join one of the children with the parent
281	if isroot	4,784,940✔
282	return node.l	×
283	elseif parent.l == node	8,525,199✔
284	parent.l = node.l	3,563,518✔
285	else
286	parent.r = node.l	2,647,458✔
287	end
288	else
289	# Join one of the children with the parent
290	if rand(rng, Bool)	3,230,818✔
291	if isroot	1,614,095✔
292	return node.l	×
293	elseif parent.l == node	2,839,084✔
294	parent.l = node.l	1,152,579✔
295	else
296	parent.r = node.l	844,160✔
297	end
298	else
299	if isroot	1,616,728✔
300	return node.r	×
301	elseif parent.l == node	2,844,360✔
302	parent.l = node.r	1,153,857✔
303	else
304	parent.r = node.r	462,885✔
305	end
306	end
307	end
308	return tree	20,923,816✔
309	end
310
311	"""Create a random equation by appending random operators"""
312	function gen_random_tree(	593,804✔
313	length::Int, options::Options, nfeatures::Int, ::Type{T}, rng::AbstractRNG=default_rng()
314	) where {T<:DATA_TYPE}
315	# Note that this base tree is just a placeholder; it will be replaced.
316	tree = constructorof(options.node_type)(T; val=convert(T, 1))	1,106,629✔
317	for i in 1:length	681,129✔
318	# TODO: This can be larger number of nodes than length.
319	tree = append_random_op(tree, options, nfeatures, rng)	2,452,483✔
320	end	2,115,945✔
321	return tree	509,913✔
322	end
323
324	function gen_random_tree_fixed_size(	4,742,130✔
325	node_count::Int,
326	options::Options,
327	nfeatures::Int,
328	::Type{T},
329	rng::AbstractRNG=default_rng(),
330	) where {T<:DATA_TYPE}
331	tree = make_random_leaf(nfeatures, T, options.node_type, rng, options)	5,507,310✔
332	cur_size = count_nodes(tree)	5,770,014✔
333	while cur_size < node_count	27,021,447✔
334	if cur_size == node_count - 1 # only unary operator allowed.	23,031,694✔
335	options.nuna == 0 && break # We will go over the requested amount, so we must break.	2,315,163✔
336	tree = append_random_op(tree, options, nfeatures, rng; makeNewBinOp=false)	3,346,892✔
337	else
338	tree = append_random_op(tree, options, nfeatures, rng)	20,716,591✔
339	end
340	cur_size = count_nodes(tree)	37,632,939✔
341	end	18,617,057✔
342	return tree	3,989,865✔
343	end
344
345	function crossover_trees(	2,304,122✔
346	ex1::E, ex2::E, rng::AbstractRNG=default_rng()
347	) where {T,E<:AbstractExpression{T}}
348	tree1 = get_contents(ex1)	3,154,811✔
349	tree2 = get_contents(ex2)	2,350,391✔
350	out1, out2 = crossover_trees(tree1, tree2, rng)	3,520,434✔
351	ex1 = with_contents(ex1, out1)	3,521,348✔
352	ex2 = with_contents(ex2, out2)	3,521,339✔
353	return ex1, ex2	2,036,317✔
354	end
355
356	"""Crossover between two expressions"""
357	function crossover_trees(	2,461,999✔
358	tree1::N, tree2::N, rng::AbstractRNG=default_rng()
359	) where {T,N<:AbstractExpressionNode{T}}
360	tree1 = copy_node(tree1)	3,686,204✔
361	tree2 = copy_node(tree2)	3,838,083✔
362
363	node1, parent1, side1 = random_node_and_parent(tree1, rng)	5,223,298✔
364	node2, parent2, side2 = random_node_and_parent(tree2, rng)	5,071,211✔
365
366	node1 = copy_node(node1)	3,684,206✔
367
368	if side1 == 'l'	2,459,996✔
369	parent1.l = copy_node(node2)	2,461,884✔
370	# tree1 now contains this.
371	elseif side1 == 'r'	820,369✔
372	parent1.r = copy_node(node2)	818,250✔
373	# tree1 now contains this.
374	else # 'n'
375	# This means that there is no parent2.
376	tree1 = copy_node(node2)	2,119✔
377	end
378
379	if side2 == 'l'	2,459,995✔
380	parent2.l = node1	1,638,780✔
381	elseif side2 == 'r'	821,229✔
382	parent2.r = node1	819,126✔
383	else # 'n'
384	tree2 = node1	1,922✔
385	end
386	return tree1, tree2	2,460,002✔
387	end
388
389	function get_two_nodes_without_loop(tree::AbstractNode, rng::AbstractRNG; max_attempts=10)	×
390	for _ in 1:max_attempts	×
391	parent = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))	×
392	new_child = rand(rng, NodeSampler(; tree, filter=t -> t !== tree))	×
393
394	would_form_loop = any(t -> t === parent, new_child)	×
395	if !would_form_loop	×
396	return (parent, new_child, false)	×
397	end
398	end
399	return (tree, tree, true)	×
400	end
401
402	function form_random_connection!(ex::AbstractExpression, rng::AbstractRNG=default_rng())
NEW 403	tree = get_contents(ex)	×
NEW 404	return with_contents(ex, form_random_connection!(tree, rng))	×
405	end
406	function form_random_connection!(tree::AbstractNode, rng::AbstractRNG=default_rng())	×
407	if length(tree) < 5	×
408	return tree	×
409	end
410
411	parent, new_child, would_form_loop = get_two_nodes_without_loop(tree, rng)	×
412
413	if would_form_loop	×
414	return tree	×
415	end
416
417	# Set one of the children to be this new child:
418	if parent.degree == 1 \|\| rand(rng, Bool)	×
419	parent.l = new_child	×
420	else
421	parent.r = new_child	×
422	end
423	return tree	×
424	end
425
426	function break_random_connection!(ex::AbstractExpression, rng::AbstractRNG=default_rng())
NEW 427	tree = get_contents(ex)	×
NEW 428	return with_contents(ex, break_random_connection!(tree, rng))	×
429	end
430	function break_random_connection!(tree::AbstractNode, rng::AbstractRNG=default_rng())	×
431	tree.degree == 0 && return tree	×
432	parent = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))	×
433	if parent.degree == 1 \|\| rand(rng, Bool)	×
434	parent.l = copy(parent.l)	×
435	else
436	parent.r = copy(parent.r)	×
437	end
438	return tree	×
439	end
440
441	end

MilesCranmer / SymbolicRegression.jl / 9686354911

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous