9639805727

Committed 24 Jun 2024 05:00AM UTC coverage: 94.475% (-0.1%) from 94.617%

Build # 9639805727

Build Type

Pull #326

github

Committed by

web-flow

Commit Message

Merge 3ba1556f8 into ceddaa424

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

Run Details

239 of 250 new or added lines in 15 files covered. (95.6%)

4 existing lines in 3 files now uncovered.

2548 of 2697 relevant lines covered (94.48%)

46539295.05 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())	1,208,612✔
38	tree = get_contents(ex)	1,509,926✔
39	ex = with_contents(ex, swap_operands(tree, rng))	2,000,800✔
40	return ex	1,086,297✔
41	end
42	function swap_operands(tree::AbstractNode, rng::AbstractRNG=default_rng())	1,211,249✔
43	if !any(node -> node.degree == 2, tree)	2,879,861✔
44	return tree	×
45	end
46	node = rand(rng, NodeSampler(; tree, filter=t -> t.degree == 2))	27,859,720✔
47	node.l, node.r = node.r, node.l	1,211,240✔
48	return tree	1,211,239✔
49	end
50
51	"""Randomly convert an operator into another one (binary->binary; unary->unary)"""
52	function mutate_operator(	8,335,444✔
53	ex::AbstractExpression{T}, options::Options, rng::AbstractRNG=default_rng()
54	) where {T<:DATA_TYPE}
55	tree = get_contents(ex)	12,753,778✔
56	ex = with_contents(ex, mutate_operator(tree, options, rng))	13,969,402✔
57	return ex	8,332,914✔
58	end
59	function mutate_operator(	8,332,809✔
60	tree::AbstractExpressionNode{T}, options::Options, rng::AbstractRNG=default_rng()
61	) where {T}
62	if !(has_operators(tree))	8,334,193✔
63	return tree	×
64	end
65	node = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))	170,828,769✔
66	if node.degree == 1	8,334,203✔
67	node.op = rand(rng, 1:(options.nuna))	3,247,964✔
68	else
69	node.op = rand(rng, 1:(options.nbin))	5,086,257✔
70	end
71	return tree	8,334,202✔
72	end
73
74	"""Randomly perturb a constant"""
75	function mutate_constant(	7,158,979✔
76	ex::AbstractExpression{T}, temperature, options::Options, rng::AbstractRNG=default_rng()
77	) where {T<:DATA_TYPE}
78	tree = get_contents(ex)	9,942,058✔
79	ex = with_contents(ex, mutate_constant(tree, temperature, options, rng))	12,363,192✔
80	return ex	7,434,223✔
81	end
82	function mutate_constant(	7,448,261✔
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,448,206✔
91	return tree	1,922✔
92	end
93	node = rand(rng, NodeSampler(; tree, filter=t -> (t.degree == 0 && t.constant)))	207,886,247✔
94
95	node.val *= mutate_factor(T, temperature, options, rng)	7,446,501✔
96
97	return tree	7,446,147✔
98	end
99
100	function mutate_factor(::Type{T}, temperature, options, rng) where {T<:DATA_TYPE}	7,459,162✔
101	bottom = 1//10	7,458,369✔
102	maxChange = options.perturbation_factor * temperature + 1 + bottom	7,459,169✔
103	factor = T(maxChange^rand(rng, T))	7,459,184✔
104	makeConstBigger = rand(rng, Bool)	7,459,004✔
105
106	factor = makeConstBigger ? factor : 1 / factor	11,188,408✔
107
108	if rand(rng) > options.probability_negate_constant	7,459,006✔
109	factor *= -1	7,384,737✔
110	end
111	return factor	7,458,933✔
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(	11,123,494✔
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)	8,112,643✔
125	ex = with_contents(ex, append_random_op(tree, options, nfeatures, rng; makeNewBinOp))	9,091,462✔
126	return ex	6,059,936✔
127	end
128	function append_random_op(	56,912,008✔
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))	527,411,044✔
136
137	if makeNewBinOp === nothing	31,236,659✔
138	choice = rand(rng)	28,884,918✔
139	makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)	28,884,761✔
140	end
141
142	if makeNewBinOp	31,238,452✔
143	newnode = constructorof(typeof(tree))(;	20,093,551✔
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))(;	11,145,745✔
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)	31,237,687✔
156
157	return tree	31,237,775✔
158	end
159
160	"""Insert random node"""
161	function insert_random_op(	65,609,828✔
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)	87,397,467✔
168	ex = with_contents(ex, insert_random_op(tree, options, nfeatures, rng))	98,049,411✔
169	return ex	65,376,531✔
170	end
171	function insert_random_op(	65,373,243✔
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))	98,041,812✔
178	choice = rand(rng)	65,384,250✔
179	makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)	65,383,349✔
180	left = copy_node(node)	98,051,391✔
181
182	if makeNewBinOp	65,375,343✔
183	right = make_random_leaf(nfeatures, T, typeof(tree), rng, options)	56,558,488✔
184	newnode = constructorof(typeof(tree))(;	56,562,114✔
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)	8,817,991✔
189	end
190	set_node!(node, newnode)	65,375,890✔
191	return tree	65,375,533✔
192	end
193
194	"""Add random node to the top of a tree"""
195	function prepend_random_op(	6,086,838✔
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)	8,141,378✔
202	ex = with_contents(ex, prepend_random_op(tree, options, nfeatures, rng))	9,091,517✔
203	return ex	6,059,127✔
204	end
205	function prepend_random_op(	6,061,117✔
206	tree::AbstractExpressionNode{T},
207	options::Options,
208	nfeatures::Int,
209	rng::AbstractRNG=default_rng(),
210	) where {T<:DATA_TYPE}
211	node = tree	6,059,407✔
212	choice = rand(rng)	6,061,123✔
213	makeNewBinOp = choice < options.nbin / (options.nuna + options.nbin)	6,061,133✔
214	left = copy_node(tree)	9,091,502✔
215
216	if makeNewBinOp	6,061,079✔
217	right = make_random_leaf(nfeatures, T, typeof(tree), rng, options)	5,036,237✔
218	newnode = constructorof(typeof(tree))(;	5,036,250✔
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)	1,024,850✔
223	end
224	set_node!(node, newnode)	6,061,065✔
225	return node	6,061,063✔
226	end
227
228	function make_random_leaf(	130,789,796✔
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)	130,787,956✔
236	return constructorof(N)(; val=randn(rng, T))	65,398,522✔
237	else
238	return constructorof(N)(T; feature=rand(rng, 1:nfeatures))	65,412,338✔
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())	33,216,411✔
244	if tree.degree == 0	37,547,857✔
245	return tree, tree, 'n'	39,185✔
246	end
247	parent = rand(rng, NodeSampler(; tree, filter=t -> t.degree != 0))	894,537,063✔
248	if parent.degree == 1 \|\| rand(rng, Bool)	63,107,210✔
249	return (parent.l, parent, 'l')	24,711,432✔
250	else
251	return (parent.r, parent, 'r')	12,798,695✔
252	end
253	end
254
255	"""Select a random node, and splice it out of the tree."""
256	function delete_random_op!(	26,491,384✔
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)	35,742,999✔
263	ex = with_contents(ex, delete_random_op!(tree, options, nfeatures, rng))	39,676,759✔
264	return ex	26,446,505✔
265	end
266	function delete_random_op!(	26,449,160✔
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)	54,308,039✔
273	isroot = side == 'n'	26,449,648✔
274
275	if node.degree == 0	26,449,641✔
276	# Replace with new constant
277	newnode = make_random_leaf(nfeatures, T, typeof(tree), rng, options)	16,369,874✔
278	set_node!(node, newnode)	24,634,423✔
279	elseif node.degree == 1	10,080,086✔
280	# Join one of the children with the parent
281	if isroot	5,112,687✔
282	return node.l	×
283	elseif parent.l == node	9,150,945✔
284	parent.l = node.l	3,692,706✔
285	else
286	parent.r = node.l	2,763,479✔
287	end
288	else
289	# Join one of the children with the parent
290	if rand(rng, Bool)	4,967,434✔
291	if isroot	2,483,171✔
292	return node.l	×
293	elseif parent.l == node	4,351,678✔
294	parent.l = node.l	1,680,691✔
295	else
296	parent.r = node.l	1,358,095✔
297	end
298	else
299	if isroot	2,484,283✔
300	return node.r	×
301	elseif parent.l == node	4,353,046✔
302	parent.l = node.r	1,679,498✔
303	else
304	parent.r = node.r	804,793✔
305	end
306	end
307	end
308	return tree	27,861,613✔
309	end
310
311	"""Create a random equation by appending random operators"""
312	function gen_random_tree(	682,027✔
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,274,610✔
317	for i in 1:length	782,669✔
318	# TODO: This can be larger number of nodes than length.
319	tree = append_random_op(tree, options, nfeatures, rng)	2,824,435✔
320	end	2,425,108✔
321	return tree	584,929✔
322	end
323
324	function gen_random_tree_fixed_size(	4,817,972✔
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,553,376✔
332	cur_size = count_nodes(tree)	6,074,723✔
333	while cur_size < node_count	27,474,905✔
334	if cur_size == node_count - 1 # only unary operator allowed.	23,424,197✔
335	options.nuna == 0 && break # We will go over the requested amount, so we must break.	2,354,395✔
336	tree = append_random_op(tree, options, nfeatures, rng; makeNewBinOp=false)	3,528,238✔
337	else
338	tree = append_random_op(tree, options, nfeatures, rng)	21,069,872✔
339	end
340	cur_size = count_nodes(tree)	39,585,778✔
341	end	19,187,186✔
342	return tree	4,051,181✔
343	end
344
345	function crossover_trees(	5,114,743✔
346	ex1::E, ex2::E, rng::AbstractRNG=default_rng()
347	) where {T,E<:AbstractExpression{T}}
348	tree1 = get_contents(ex1)	6,893,435✔
349	tree2 = get_contents(ex2)	5,157,164✔
350	out1, out2 = crossover_trees(tree1, tree2, rng)	7,737,278✔
351	ex1 = with_contents(ex1, out1)	7,738,473✔
352	ex2 = with_contents(ex2, out2)	7,738,464✔
353	return ex1, ex2	4,749,107✔
354	end
355
356	"""Crossover between two expressions"""
357	function crossover_trees(	5,551,870✔
358	tree1::N, tree2::N, rng::AbstractRNG=default_rng()
359	) where {T,N<:AbstractExpressionNode{T}}
360	tree1 = copy_node(tree1)	8,333,774✔
361	tree2 = copy_node(tree2)	8,704,431✔
362
363	node1, parent1, side1 = random_node_and_parent(tree1, rng)	11,833,397✔
364	node2, parent2, side2 = random_node_and_parent(tree2, rng)	11,462,004✔
365
366	node1 = copy_node(node1)	8,331,817✔
367
368	if side1 == 'l'	5,549,894✔
369	parent1.l = copy_node(node2)	4,924,395✔
370	# tree1 now contains this.
371	elseif side1 == 'r'	2,268,639✔
372	parent1.r = copy_node(node2)	2,249,056✔
373	# tree1 now contains this.
374	else # 'n'
375	# This means that there is no parent2.
376	tree1 = copy_node(node2)	19,585✔
377	end
378
379	if side2 == 'l'	5,549,850✔
380	parent2.l = node1	3,283,316✔
381	elseif side2 == 'r'	2,266,590✔
382	parent2.r = node1	2,246,995✔
383	else # 'n'
384	tree2 = node1	19,409✔
385	end
386	return tree1, tree2	5,549,876✔
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 / 9639805727

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