Advanced Search Procedures in Herb.jl
A more verbose getting started with Herb.jl described the concept of a program space and showed how to search it with Herb.jl, using a simple breadth-first-search (BFS) iterator for the search. This tutorial takes a closer look at advanced search procedures hat can be employed to find a solution program to a program synthesis problem.
More specifically, you will learn about
Parameters that can be specified and their effect on the search procedure.
Deterministic search methods BFS and DFS.
Stochastic search methods, which introduce randomness to search the program space. We will look at Metropolis-Hastings, Very Large Scale Neighbourhood Search, Simulated Annealing and Genetic Search.
Let's import all the Herb modules that we will use throughout the tutorial.
begin
import Pkg
Pkg.activate(Base.current_project())
Pkg.instantiate()
endusing HerbWe start with a simple grammar:.
g_1 = @csgrammar begin
Number = |(1:2)
Number = x
Number = Number + Number
Number = Number * Number
end1: Number = 1 2: Number = 2 3: Number = x 4: Number = Number + Number 5: Number = Number * Number
Let's use the simple program 2x+1 as our problem and generate some input-output examples for the problem specification.
problem_1 = Problem([IOExample(Dict(:x => x), 2x+1) for x ∈ 1:5])Problem{Vector{IOExample{Int64, Int64}}}("", IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 3), IOExample{Int64, Int64}(Dict(:x => 2), 5), IOExample{Int64, Int64}(Dict(:x => 3), 7), IOExample{Int64, Int64}(Dict(:x => 4), 9), IOExample{Int64, Int64}(Dict(:x => 5), 11)])
Parameters
Search procedures typically have some hyperparameters that you can configure.
max_depth
max_depth controls the maximum depth of the program trees that are explored during the search, effectively limiting the size and complexity of the synthesized program. The parameter is configured as part of the iterator.
In the following example, we consider two different values for max_depth.
iterator_1 = BFSIterator(g_1, :Number, max_depth=3)BFSIterator(GenericSolver(1: Number = 1
2: Number = 2
3: Number = x
4: Number = Number + Number
5: Number = Number * Number
, SolverState(Hole[Bool[1, 1, 1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 3))
iterator_2 = BFSIterator(g_1, :Number, max_depth=6)BFSIterator(GenericSolver(1: Number = 1
2: Number = 2
3: Number = x
4: Number = Number + Number
5: Number = Number * Number
, SolverState(Hole[Bool[1, 1, 1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 6))
To see the effect max_depth has on the number of memory allocations made during the program synthesis process, we use the @time macro.
Solution for max_depth = 3:
solution_1 = @time synth(problem_1, iterator_1)(4{1,4{3,3}}, optimal_program)
rulenode2expr(solution_1[1], g_1):(1 + (x + x))
Solution for max_depth = 6:
begin
solution_2 = @time synth(problem_1, iterator_2)
rulenode2expr(solution_2[1], g_1)
end:((1 + x) + x)
While increasing max_depth allows us to explore more complex and deeper program trees, which may lead to a better solution, it also requires more memory allocation and can increase the execution time.
max_enumerations
max_enumerations defines the maximum number of candidate programs that can be evaluated before the search is terminated.
Let's explore how many enumerations are necessary to solve our simple problem.
begin
solutions = []
times = []
nodes = []
iterations = []
for i in range(1, 50)
iterator = BFSIterator(g_1, :Number, max_depth=i)
solution = @timed synth(problem_1, iterator)
push!(times, solution.time)
push!(nodes, solution[1][1])
push!(solutions, rulenode2expr(solution[1][1], g_1))
push!(iterations, i)
end
pretty_table(HTML, [iterations nodes solutions times], column_labels=[["Iteration", "RuleNode", "Program", "Duration"]])
end| Iteration | RuleNode | Program | Duration |
|---|---|---|---|
| 1 | 3 | x | 0.00296591 |
| 2 | 4{3,2} | x + 2 | 0.000165149 |
| 3 | 4{1,4{3,3}} | 1 + (x + x) | 0.000338472 |
| 4 | 4{1,4{3,3}} | 1 + (x + x) | 0.000476841 |
| 5 | 4{4{1,3},3} | (1 + x) + x | 0.000532515 |
| 6 | 4{4{1,3},3} | (1 + x) + x | 0.000597396 |
| 7 | 4{4{1,3},3} | (1 + x) + x | 0.000577388 |
| 8 | 4{4{1,3},3} | (1 + x) + x | 0.000618255 |
| 9 | 4{4{1,3},3} | (1 + x) + x | 0.000601614 |
| 10 | 4{4{1,3},3} | (1 + x) + x | 0.000581145 |
| 11 | 4{4{1,3},3} | (1 + x) + x | 0.000597367 |
| 12 | 4{4{1,3},3} | (1 + x) + x | 0.000578891 |
| 13 | 4{4{1,3},3} | (1 + x) + x | 0.00059923 |
| 14 | 4{4{1,3},3} | (1 + x) + x | 0.000591795 |
| 15 | 4{4{1,3},3} | (1 + x) + x | 0.000580134 |
| 16 | 4{4{1,3},3} | (1 + x) + x | 0.000599199 |
| 17 | 4{4{1,3},3} | (1 + x) + x | 0.000582879 |
| 18 | 4{4{1,3},3} | (1 + x) + x | 0.000610269 |
| 19 | 4{4{1,3},3} | (1 + x) + x | 0.00058857 |
| 20 | 4{4{1,3},3} | (1 + x) + x | 0.000580435 |
| 21 | 4{4{1,3},3} | (1 + x) + x | 0.000591976 |
| 22 | 4{4{1,3},3} | (1 + x) + x | 0.000599369 |
| 23 | 4{4{1,3},3} | (1 + x) + x | 0.00059394 |
| 24 | 4{4{1,3},3} | (1 + x) + x | 0.00060493 |
| 25 | 4{4{1,3},3} | (1 + x) + x | 0.000588529 |
| 26 | 4{4{1,3},3} | (1 + x) + x | 0.0187277 |
| 27 | 4{4{1,3},3} | (1 + x) + x | 0.000637671 |
| 28 | 4{4{1,3},3} | (1 + x) + x | 0.000603217 |
| 29 | 4{4{1,3},3} | (1 + x) + x | 0.000606834 |
| 30 | 4{4{1,3},3} | (1 + x) + x | 0.000588009 |
| 31 | 4{4{1,3},3} | (1 + x) + x | 0.000596414 |
| 32 | 4{4{1,3},3} | (1 + x) + x | 0.000592327 |
| 33 | 4{4{1,3},3} | (1 + x) + x | 0.000591696 |
| 34 | 4{4{1,3},3} | (1 + x) + x | 0.000598478 |
| 35 | 4{4{1,3},3} | (1 + x) + x | 0.000571998 |
| 36 | 4{4{1,3},3} | (1 + x) + x | 0.000601233 |
| 37 | 4{4{1,3},3} | (1 + x) + x | 0.000595112 |
| 38 | 4{4{1,3},3} | (1 + x) + x | 0.00058332 |
| 39 | 4{4{1,3},3} | (1 + x) + x | 0.000599911 |
| 40 | 4{4{1,3},3} | (1 + x) + x | 0.000578291 |
| 41 | 4{4{1,3},3} | (1 + x) + x | 0.000602796 |
| 42 | 4{4{1,3},3} | (1 + x) + x | 0.000592296 |
| 43 | 4{4{1,3},3} | (1 + x) + x | 0.000577459 |
| 44 | 4{4{1,3},3} | (1 + x) + x | 0.000594391 |
| 45 | 4{4{1,3},3} | (1 + x) + x | 0.0005837 |
| 46 | 4{4{1,3},3} | (1 + x) + x | 0.000597476 |
| 47 | 4{4{1,3},3} | (1 + x) + x | 0.000581346 |
| 48 | 4{4{1,3},3} | (1 + x) + x | 0.000594109 |
| 49 | 4{4{1,3},3} | (1 + x) + x | 0.000593198 |
| 50 | 4{4{1,3},3} | (1 + x) + x | 0.00058943 |
At i = 3, we observe that an optimal program is found. Increasing the number of enumerations beyond that does not affect the solution or the number of memory allocations.
allow_evaluation_errors
A final parameter we consider here is allow_evaluation_errors, which is false by default. When true, the search continues even if an exception occurs during the evaluation of a candidate program. This allows the search process to handle faulty candidate programs and explore other ones, instead of throwing an error and terminating prematurely.
We will use a new example to see the effect of allow_evaluation_errors. We begin defining a new simple grammar. We then create some input-output examples to specify the problem we want to solve. This time, we choose a problem that we cannot solve with the provided grammar.
g_2 = @csgrammar begin
Number = 1
List = []
Index = List[Number]
end1: Number = 1 2: List = [] 3: Index = List[Number]
problem_2 = Problem([IOExample(Dict{Symbol,Any}(), x) for x ∈ 1:5])Problem{Vector{IOExample{Any, Int64}}}("", IOExample{Any, Int64}[IOExample{Any, Int64}(Dict{Symbol, Any}(), 1), IOExample{Any, Int64}(Dict{Symbol, Any}(), 2), IOExample{Any, Int64}(Dict{Symbol, Any}(), 3), IOExample{Any, Int64}(Dict{Symbol, Any}(), 4), IOExample{Any, Int64}(Dict{Symbol, Any}(), 5)])
iterator_3 = BFSIterator(g_2, :Index, max_depth=2)BFSIterator(GenericSolver(1: Number = 1
2: List = []
3: Index = List[Number]
, SolverState(3{2,1}, Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 2))
Test.@test_throws HerbSearch.EvaluationError synth(problem_2, iterator_3)�[32m�[1mTest Passed�[22m�[39m
Thrown: EvaluationError
As expected, an exception occurs during the synthesis process. Now we try the same again, with allow_evaluation_errors=true.
solution_4 = synth(problem_2, iterator_3, allow_evaluation_errors=true)(3{2,1}, suboptimal_program)
"This time we find a solution, although a suboptimal one.
Top-down search
Herb.jl provides already implemented, ready-to-use search methods. The core building block of the search is the program iterator, which represents a walk through the program space. All program iterators share the top-level abstract type ProgramIterator. For more information on iterators and how to customize them, see this tutorial.
First, we explore two fundamental deterministic top-down search algorithms: breadth-first search (BFS) and depth-first search (DFS). Both algorithms are implemented using the abstract type TopDownIterator, which can be customized through the functions
priority_functionderivation_heuristichole_heuristic
First, we explore two fundamental deterministic top-down search algorithms: breadth-first search (BFS) and depth-first search (DFS). Both algorithms are implemented using the abstract type TopDownIterator, which can be customized through the functions priorityfunction, derivationheuristic, and hole_heuristic.
Breadth-First Search
The BFSIterator enumerates all possible programs at a given depth before progressing to the next level, ensuring that trees are explored in increasing order of size. This guarantees that smaller programs are evaluated first, and larger, more complex ones are considered only after all smaller ones have been processed.
To explore BFSIterator, we define another very simple grammar.
g_3 = @csgrammar begin
Real = 1 | 2
Real = Real * Real
end1: Real = 1 2: Real = 2 3: Real = Real * Real
Next, we define a BFSIterator with a max_depth of 2 and a max_size of infinite (which we approximate with the maximum value of Int), and a starting symbol of type Real. By default, BFSIterator uses the heuristic 'left-most first', i.e., the left-most child in the tree is always explored first.
iterator_bfs = BFSIterator(g_3, :Real, max_depth=2, max_size=typemax(Int))BFSIterator(GenericSolver(1: Real = 1
2: Real = 2
3: Real = Real * Real
, SolverState(Hole[Bool[1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 2))
To see all possible solution programs the iterator explores, we use collect. It returs a list of the programs, ordered by increasing size and depth.
programs_bfs = collect(iterator_bfs)6-element Vector{RuleNode}:
1
2
3{1,1}
3{1,2}
3{2,1}
3{2,2}
Let's verify that the iterator returns the programs we expect (keep in mind we use a leftmost-first heuristic).
answer_programs = [
RuleNode(1),
RuleNode(2),
RuleNode(3, [RuleNode(1), RuleNode(1)]),
RuleNode(3, [RuleNode(1), RuleNode(2)]),
RuleNode(3, [RuleNode(2), RuleNode(1)]),
RuleNode(3, [RuleNode(2), RuleNode(2)])
]6-element Vector{RuleNode}:
1
2
3{1,1}
3{1,2}
3{2,1}
3{2,2}
rulenode_programs = [rulenode2expr(r, g_3) for r in answer_programs]6-element Vector{Any}:
1
2
:(1 * 1)
:(1 * 2)
:(2 * 1)
:(2 * 2)
found_all_programs = all(p ∈ programs_bfs for p ∈ answer_programs)true
Depth-First Search
The DFSIterator explores one branch of the search tree at a time, fully traversing it unitl a correct program is found or the specified max_depth is reached. Only after completing the current branch, it proceeds to the next branch.
As before, we collect the candidate programs using the same grammar, but a DFSIterator.
iterator_dfs = DFSIterator(g_3, :Real, max_depth=2, max_size=typemax(Int))DFSIterator(GenericSolver(1: Real = 1
2: Real = 2
3: Real = Real * Real
, SolverState(Hole[Bool[1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 2))
programs_dfs = collect(iterator_dfs)6-element Vector{RuleNode}:
1
3{1,1}
3{1,2}
3{2,1}
3{2,2}
2
DFSIterator also uses by default a leftmost-first heuristic. If we want to use a rightmost-first heuristic instead, we can create our own iterator DFSIteratorRightmost as a sub-type of TopDownIterator, using the @programiterator macro. Then we implement the functions priority_function and hole_heuristic. Also see the tutorial Top Down Iterator for how to build iterators is Herb.jl.
@programiterator DFSIteratorRightmost() <: TopDownIteratorDFSIteratorRightmost
By default, priority_function for a TopDownIterator is that of a BFS iterator. Hence, we need to provide a new implementation.
function priority_function(
::DFSIteratorRightmost,
::AbstractGrammar,
::AbstractRuleNode,
parent_value::Union{Real, Tuple{Vararg{Real}}},
isrequeued::Bool
)
if isrequeued
return parent_value;
end
return parent_value - 1;
endpriority_function (generic function with 1 method)
Next, we need to implement the hole_heuristic to be rightmost-first.
function hole_heuristic(::DFSIteratorRightmost, node::AbstractRuleNode, max_depth::Int)::Union{ExpandFailureReason, HoleReference}
return heuristic_rightmost(node, max_depth);
endhole_heuristic (generic function with 1 method)
iteratordfs_rightmost = DFSIteratorRightmost(g_3, :Real, max_depth=2, max_size=typemax(Int))DFSIteratorRightmost(GenericSolver(1: Real = 1
2: Real = 2
3: Real = Real * Real
, SolverState(Hole[Bool[1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 2))
programs_dfs_rightmost = collect(iteratordfs_rightmost)6-element Vector{RuleNode}:
1
2
3{1,1}
3{1,2}
3{2,1}
3{2,2}
We observe that the order of programs has changed. We can also test if both DFS iterators return the same programs:
Set(programs_dfs)==Set(programs_dfs_rightmost)true
Stochastic search
While deterministic search methods explore the search space in a predictable way, stochastic ones introduce randomness to allow for more flexibility.
In this section, we will look at the stochastic search algorithms: Metropolis-Hastings (MH), Very Large Scale Neighbourhood Search (VLSNS), and Simulated Annealing (SA). In Herb.jl, all of these search methodsthe share a common supertype StochasticSearchIterator, which defines the following fields
examplescost_functioninitial_temperatureevaluation_function.
They are customized by overriding the functions neighbourhood, propose, accept and temperature as required.
We start with a simple grammar and a helper function to create the input-output examples for the problem we want to solve.
g_4 = @csgrammar begin
X = |(1:5)
X = X * X
X = X + X
X = X - X
X = x
end1: X = 1 2: X = 2 3: X = 3 4: X = 4 5: X = 5 6: X = X * X 7: X = X + X 8: X = X - X 9: X = x
function create_problem(f, range=20)
examples = [IOExample(Dict(:x => x), f(x)) for x ∈ 1:range]
return Problem(examples), examples
endcreate_problem (generic function with 2 methods)
Throughout the stochastic search examples, we will use mean-squared-error as cost function. The cost function helps to guide the search by evaluating how well a candidate program solves the given task. This is used to decide whether a proposed program should be accepted or rejected.
cost_function = mean_squared_errormean_squared_error (generic function with 1 method)
Metropolis-Hastings
Metropolis-Hastings (MH) is a method to produce samples from a distribution that may otherwise be difficult to sample. In the context of program synthesis, we sample from a distribution of programs defined by the grammar.
For more information on MH, see for example this webpage.
To illustrate MH, we use a simple arithmetic example.
e_mh = x -> x * x + 4#14 (generic function with 1 method)
problem_mh, examples_mh = create_problem(e_mh)(Problem{Vector{IOExample{Int64, Int64}}}("", IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 5), IOExample{Int64, Int64}(Dict(:x => 2), 8), IOExample{Int64, Int64}(Dict(:x => 3), 13), IOExample{Int64, Int64}(Dict(:x => 4), 20), IOExample{Int64, Int64}(Dict(:x => 5), 29), IOExample{Int64, Int64}(Dict(:x => 6), 40), IOExample{Int64, Int64}(Dict(:x => 7), 53), IOExample{Int64, Int64}(Dict(:x => 8), 68), IOExample{Int64, Int64}(Dict(:x => 9), 85), IOExample{Int64, Int64}(Dict(:x => 10), 104), IOExample{Int64, Int64}(Dict(:x => 11), 125), IOExample{Int64, Int64}(Dict(:x => 12), 148), IOExample{Int64, Int64}(Dict(:x => 13), 173), IOExample{Int64, Int64}(Dict(:x => 14), 200), IOExample{Int64, Int64}(Dict(:x => 15), 229), IOExample{Int64, Int64}(Dict(:x => 16), 260), IOExample{Int64, Int64}(Dict(:x => 17), 293), IOExample{Int64, Int64}(Dict(:x => 18), 328), IOExample{Int64, Int64}(Dict(:x => 19), 365), IOExample{Int64, Int64}(Dict(:x => 20), 404)]), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 5), IOExample{Int64, Int64}(Dict(:x => 2), 8), IOExample{Int64, Int64}(Dict(:x => 3), 13), IOExample{Int64, Int64}(Dict(:x => 4), 20), IOExample{Int64, Int64}(Dict(:x => 5), 29), IOExample{Int64, Int64}(Dict(:x => 6), 40), IOExample{Int64, Int64}(Dict(:x => 7), 53), IOExample{Int64, Int64}(Dict(:x => 8), 68), IOExample{Int64, Int64}(Dict(:x => 9), 85), IOExample{Int64, Int64}(Dict(:x => 10), 104), IOExample{Int64, Int64}(Dict(:x => 11), 125), IOExample{Int64, Int64}(Dict(:x => 12), 148), IOExample{Int64, Int64}(Dict(:x => 13), 173), IOExample{Int64, Int64}(Dict(:x => 14), 200), IOExample{Int64, Int64}(Dict(:x => 15), 229), IOExample{Int64, Int64}(Dict(:x => 16), 260), IOExample{Int64, Int64}(Dict(:x => 17), 293), IOExample{Int64, Int64}(Dict(:x => 18), 328), IOExample{Int64, Int64}(Dict(:x => 19), 365), IOExample{Int64, Int64}(Dict(:x => 20), 404)])
Run the following code block to define the iterator and perform the program synthesis multiple times. Since the search process is stochastic, you will likely see different solution programs with each run.
begin
rules = []
programs = []
iters = []
for i in range(1, 3)
iterator_mh = MHSearchIterator(g_4, :X, examples_mh, cost_function, max_depth=3)
program_mh = synth(problem_mh, iterator_mh)
push!(rules, program_mh[1])
push!(programs, rulenode2expr(program_mh[1], g_4))
push!(iters, i)
end
pretty_table(HTML, [iters rules programs], column_labels=[["Run", "RuleNode", "Program"]])
end| Run | RuleNode | Program |
|---|---|---|
| 1 | 7{4,6{9,9}} | 4 + x * x |
| 2 | 8{6{9,9},8{1,5}} | x * x - (1 - 5) |
| 3 | 8{6{9,9},8{1,5}} | x * x - (1 - 5) |
Very Large Scale Neighbourhood Search
The second stochastic search method we consider is Very Large Scale Neighbourhood Search (VLSN). In each iteration, the algorithm searches the neighbourhood of the current candidate program for a local optimum, aiming to find a better candidate solution.
For more information, see this article.
Given the same grammar as before, we can try it with some simple examples.
e_vlsn = x -> 10#17 (generic function with 1 method)
problem_vlsn1, examples_vlsn1 = create_problem(e_vlsn)(Problem{Vector{IOExample{Int64, Int64}}}("", IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 10), IOExample{Int64, Int64}(Dict(:x => 2), 10), IOExample{Int64, Int64}(Dict(:x => 3), 10), IOExample{Int64, Int64}(Dict(:x => 4), 10), IOExample{Int64, Int64}(Dict(:x => 5), 10), IOExample{Int64, Int64}(Dict(:x => 6), 10), IOExample{Int64, Int64}(Dict(:x => 7), 10), IOExample{Int64, Int64}(Dict(:x => 8), 10), IOExample{Int64, Int64}(Dict(:x => 9), 10), IOExample{Int64, Int64}(Dict(:x => 10), 10), IOExample{Int64, Int64}(Dict(:x => 11), 10), IOExample{Int64, Int64}(Dict(:x => 12), 10), IOExample{Int64, Int64}(Dict(:x => 13), 10), IOExample{Int64, Int64}(Dict(:x => 14), 10), IOExample{Int64, Int64}(Dict(:x => 15), 10), IOExample{Int64, Int64}(Dict(:x => 16), 10), IOExample{Int64, Int64}(Dict(:x => 17), 10), IOExample{Int64, Int64}(Dict(:x => 18), 10), IOExample{Int64, Int64}(Dict(:x => 19), 10), IOExample{Int64, Int64}(Dict(:x => 20), 10)]), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 10), IOExample{Int64, Int64}(Dict(:x => 2), 10), IOExample{Int64, Int64}(Dict(:x => 3), 10), IOExample{Int64, Int64}(Dict(:x => 4), 10), IOExample{Int64, Int64}(Dict(:x => 5), 10), IOExample{Int64, Int64}(Dict(:x => 6), 10), IOExample{Int64, Int64}(Dict(:x => 7), 10), IOExample{Int64, Int64}(Dict(:x => 8), 10), IOExample{Int64, Int64}(Dict(:x => 9), 10), IOExample{Int64, Int64}(Dict(:x => 10), 10), IOExample{Int64, Int64}(Dict(:x => 11), 10), IOExample{Int64, Int64}(Dict(:x => 12), 10), IOExample{Int64, Int64}(Dict(:x => 13), 10), IOExample{Int64, Int64}(Dict(:x => 14), 10), IOExample{Int64, Int64}(Dict(:x => 15), 10), IOExample{Int64, Int64}(Dict(:x => 16), 10), IOExample{Int64, Int64}(Dict(:x => 17), 10), IOExample{Int64, Int64}(Dict(:x => 18), 10), IOExample{Int64, Int64}(Dict(:x => 19), 10), IOExample{Int64, Int64}(Dict(:x => 20), 10)])
iterator_vlsn1 = VLSNSearchIterator(g_4, :X, examples_vlsn1, cost_function, max_depth=2) VLSNSearchIterator(GenericSolver(1: X = 1
2: X = 2
3: X = 3
4: X = 4
5: X = 5
6: X = X * X
7: X = X + X
8: X = X - X
9: X = x
, SolverState(Hole[Bool[1, 1, 1, 1, 1, 1, 1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 2), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 10), IOExample{Int64, Int64}(Dict(:x => 2), 10), IOExample{Int64, Int64}(Dict(:x => 3), 10), IOExample{Int64, Int64}(Dict(:x => 4), 10), IOExample{Int64, Int64}(Dict(:x => 5), 10), IOExample{Int64, Int64}(Dict(:x => 6), 10), IOExample{Int64, Int64}(Dict(:x => 7), 10), IOExample{Int64, Int64}(Dict(:x => 8), 10), IOExample{Int64, Int64}(Dict(:x => 9), 10), IOExample{Int64, Int64}(Dict(:x => 10), 10), IOExample{Int64, Int64}(Dict(:x => 11), 10), IOExample{Int64, Int64}(Dict(:x => 12), 10), IOExample{Int64, Int64}(Dict(:x => 13), 10), IOExample{Int64, Int64}(Dict(:x => 14), 10), IOExample{Int64, Int64}(Dict(:x => 15), 10), IOExample{Int64, Int64}(Dict(:x => 16), 10), IOExample{Int64, Int64}(Dict(:x => 17), 10), IOExample{Int64, Int64}(Dict(:x => 18), 10), IOExample{Int64, Int64}(Dict(:x => 19), 10), IOExample{Int64, Int64}(Dict(:x => 20), 10)], mean_squared_error, 2, 1, execute_on_input)
program_vlsn1 = synth(problem_vlsn1, iterator_vlsn1)(6{2,5}, optimal_program)
e_vlsn2 = x -> x#20 (generic function with 1 method)
problem_vlsn2, examples_vlsn2 = create_problem(e_vlsn2)(Problem{Vector{IOExample{Int64, Int64}}}("", IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 1), IOExample{Int64, Int64}(Dict(:x => 2), 2), IOExample{Int64, Int64}(Dict(:x => 3), 3), IOExample{Int64, Int64}(Dict(:x => 4), 4), IOExample{Int64, Int64}(Dict(:x => 5), 5), IOExample{Int64, Int64}(Dict(:x => 6), 6), IOExample{Int64, Int64}(Dict(:x => 7), 7), IOExample{Int64, Int64}(Dict(:x => 8), 8), IOExample{Int64, Int64}(Dict(:x => 9), 9), IOExample{Int64, Int64}(Dict(:x => 10), 10), IOExample{Int64, Int64}(Dict(:x => 11), 11), IOExample{Int64, Int64}(Dict(:x => 12), 12), IOExample{Int64, Int64}(Dict(:x => 13), 13), IOExample{Int64, Int64}(Dict(:x => 14), 14), IOExample{Int64, Int64}(Dict(:x => 15), 15), IOExample{Int64, Int64}(Dict(:x => 16), 16), IOExample{Int64, Int64}(Dict(:x => 17), 17), IOExample{Int64, Int64}(Dict(:x => 18), 18), IOExample{Int64, Int64}(Dict(:x => 19), 19), IOExample{Int64, Int64}(Dict(:x => 20), 20)]), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 1), IOExample{Int64, Int64}(Dict(:x => 2), 2), IOExample{Int64, Int64}(Dict(:x => 3), 3), IOExample{Int64, Int64}(Dict(:x => 4), 4), IOExample{Int64, Int64}(Dict(:x => 5), 5), IOExample{Int64, Int64}(Dict(:x => 6), 6), IOExample{Int64, Int64}(Dict(:x => 7), 7), IOExample{Int64, Int64}(Dict(:x => 8), 8), IOExample{Int64, Int64}(Dict(:x => 9), 9), IOExample{Int64, Int64}(Dict(:x => 10), 10), IOExample{Int64, Int64}(Dict(:x => 11), 11), IOExample{Int64, Int64}(Dict(:x => 12), 12), IOExample{Int64, Int64}(Dict(:x => 13), 13), IOExample{Int64, Int64}(Dict(:x => 14), 14), IOExample{Int64, Int64}(Dict(:x => 15), 15), IOExample{Int64, Int64}(Dict(:x => 16), 16), IOExample{Int64, Int64}(Dict(:x => 17), 17), IOExample{Int64, Int64}(Dict(:x => 18), 18), IOExample{Int64, Int64}(Dict(:x => 19), 19), IOExample{Int64, Int64}(Dict(:x => 20), 20)])
iterator_vlsn2 = VLSNSearchIterator(g_4, :X, examples_vlsn2, cost_function, max_depth=1) VLSNSearchIterator(GenericSolver(1: X = 1
2: X = 2
3: X = 3
4: X = 4
5: X = 5
6: X = X * X
7: X = X + X
8: X = X - X
9: X = x
, SolverState(Hole[Bool[1, 1, 1, 1, 1, 1, 1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 1), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 1), IOExample{Int64, Int64}(Dict(:x => 2), 2), IOExample{Int64, Int64}(Dict(:x => 3), 3), IOExample{Int64, Int64}(Dict(:x => 4), 4), IOExample{Int64, Int64}(Dict(:x => 5), 5), IOExample{Int64, Int64}(Dict(:x => 6), 6), IOExample{Int64, Int64}(Dict(:x => 7), 7), IOExample{Int64, Int64}(Dict(:x => 8), 8), IOExample{Int64, Int64}(Dict(:x => 9), 9), IOExample{Int64, Int64}(Dict(:x => 10), 10), IOExample{Int64, Int64}(Dict(:x => 11), 11), IOExample{Int64, Int64}(Dict(:x => 12), 12), IOExample{Int64, Int64}(Dict(:x => 13), 13), IOExample{Int64, Int64}(Dict(:x => 14), 14), IOExample{Int64, Int64}(Dict(:x => 15), 15), IOExample{Int64, Int64}(Dict(:x => 16), 16), IOExample{Int64, Int64}(Dict(:x => 17), 17), IOExample{Int64, Int64}(Dict(:x => 18), 18), IOExample{Int64, Int64}(Dict(:x => 19), 19), IOExample{Int64, Int64}(Dict(:x => 20), 20)], mean_squared_error, 2, 1, execute_on_input)
program_vlsn2 = synth(problem_vlsn2, iterator_vlsn2)(9, optimal_program)
Simulated Annealing
Simulated Annealing (SA) explores smaller, incremental changes to the candidate program in each iteration, gradually refining the solution. It is a variation of the hill-climbing algorithm: Instead of always selecting the best move, SA picks a random move. If the move improves the solution (i.e., the candidate program), it is accepted.
Occasionally, SA will accept a move that worsens the solution. This allows the algorithm to escape local optima and explore more of the solution space. However, this strategy follows a cooling (annealing) schedule: at the beginning (high temperature), the algorithm explores more broadly and is more likely to accept worse solutions. As the temperature decreases, it becomes more selective, accepting worse solutions less often.
For more information, see this page.
We use the same example as for MH. SA additionally has the option to specify the initial_temperature for the annealing (default initial_temperature=1). Let's see what effect changing the temperature from 1 to 2 has on the solution program.
problem_sa, examples_sa = create_problem(e_mh)(Problem{Vector{IOExample{Int64, Int64}}}("", IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 5), IOExample{Int64, Int64}(Dict(:x => 2), 8), IOExample{Int64, Int64}(Dict(:x => 3), 13), IOExample{Int64, Int64}(Dict(:x => 4), 20), IOExample{Int64, Int64}(Dict(:x => 5), 29), IOExample{Int64, Int64}(Dict(:x => 6), 40), IOExample{Int64, Int64}(Dict(:x => 7), 53), IOExample{Int64, Int64}(Dict(:x => 8), 68), IOExample{Int64, Int64}(Dict(:x => 9), 85), IOExample{Int64, Int64}(Dict(:x => 10), 104), IOExample{Int64, Int64}(Dict(:x => 11), 125), IOExample{Int64, Int64}(Dict(:x => 12), 148), IOExample{Int64, Int64}(Dict(:x => 13), 173), IOExample{Int64, Int64}(Dict(:x => 14), 200), IOExample{Int64, Int64}(Dict(:x => 15), 229), IOExample{Int64, Int64}(Dict(:x => 16), 260), IOExample{Int64, Int64}(Dict(:x => 17), 293), IOExample{Int64, Int64}(Dict(:x => 18), 328), IOExample{Int64, Int64}(Dict(:x => 19), 365), IOExample{Int64, Int64}(Dict(:x => 20), 404)]), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 5), IOExample{Int64, Int64}(Dict(:x => 2), 8), IOExample{Int64, Int64}(Dict(:x => 3), 13), IOExample{Int64, Int64}(Dict(:x => 4), 20), IOExample{Int64, Int64}(Dict(:x => 5), 29), IOExample{Int64, Int64}(Dict(:x => 6), 40), IOExample{Int64, Int64}(Dict(:x => 7), 53), IOExample{Int64, Int64}(Dict(:x => 8), 68), IOExample{Int64, Int64}(Dict(:x => 9), 85), IOExample{Int64, Int64}(Dict(:x => 10), 104), IOExample{Int64, Int64}(Dict(:x => 11), 125), IOExample{Int64, Int64}(Dict(:x => 12), 148), IOExample{Int64, Int64}(Dict(:x => 13), 173), IOExample{Int64, Int64}(Dict(:x => 14), 200), IOExample{Int64, Int64}(Dict(:x => 15), 229), IOExample{Int64, Int64}(Dict(:x => 16), 260), IOExample{Int64, Int64}(Dict(:x => 17), 293), IOExample{Int64, Int64}(Dict(:x => 18), 328), IOExample{Int64, Int64}(Dict(:x => 19), 365), IOExample{Int64, Int64}(Dict(:x => 20), 404)])
initial_temperature1 = 11
iterator_sa1 = SASearchIterator(g_4, :X, examples_sa, cost_function, max_depth=3, initial_temperature = initial_temperature1) SASearchIterator(GenericSolver(1: X = 1
2: X = 2
3: X = 3
4: X = 4
5: X = 5
6: X = X * X
7: X = X + X
8: X = X - X
9: X = x
, SolverState(Hole[Bool[1, 1, 1, 1, 1, 1, 1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 3), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 5), IOExample{Int64, Int64}(Dict(:x => 2), 8), IOExample{Int64, Int64}(Dict(:x => 3), 13), IOExample{Int64, Int64}(Dict(:x => 4), 20), IOExample{Int64, Int64}(Dict(:x => 5), 29), IOExample{Int64, Int64}(Dict(:x => 6), 40), IOExample{Int64, Int64}(Dict(:x => 7), 53), IOExample{Int64, Int64}(Dict(:x => 8), 68), IOExample{Int64, Int64}(Dict(:x => 9), 85), IOExample{Int64, Int64}(Dict(:x => 10), 104), IOExample{Int64, Int64}(Dict(:x => 11), 125), IOExample{Int64, Int64}(Dict(:x => 12), 148), IOExample{Int64, Int64}(Dict(:x => 13), 173), IOExample{Int64, Int64}(Dict(:x => 14), 200), IOExample{Int64, Int64}(Dict(:x => 15), 229), IOExample{Int64, Int64}(Dict(:x => 16), 260), IOExample{Int64, Int64}(Dict(:x => 17), 293), IOExample{Int64, Int64}(Dict(:x => 18), 328), IOExample{Int64, Int64}(Dict(:x => 19), 365), IOExample{Int64, Int64}(Dict(:x => 20), 404)], mean_squared_error, 1, 0.99, execute_on_input)
program_sa1 = synth(problem_sa, iterator_sa1)(7{4,6{9,9}}, optimal_program)
initial_temperature2 = 22
iterator_sa2 = SASearchIterator(g_4, :X, examples_sa, cost_function, max_depth=3, initial_temperature = initial_temperature2) SASearchIterator(GenericSolver(1: X = 1
2: X = 2
3: X = 3
4: X = 4
5: X = 5
6: X = X * X
7: X = X + X
8: X = X - X
9: X = x
, SolverState(Hole[Bool[1, 1, 1, 1, 1, 1, 1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 3), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 5), IOExample{Int64, Int64}(Dict(:x => 2), 8), IOExample{Int64, Int64}(Dict(:x => 3), 13), IOExample{Int64, Int64}(Dict(:x => 4), 20), IOExample{Int64, Int64}(Dict(:x => 5), 29), IOExample{Int64, Int64}(Dict(:x => 6), 40), IOExample{Int64, Int64}(Dict(:x => 7), 53), IOExample{Int64, Int64}(Dict(:x => 8), 68), IOExample{Int64, Int64}(Dict(:x => 9), 85), IOExample{Int64, Int64}(Dict(:x => 10), 104), IOExample{Int64, Int64}(Dict(:x => 11), 125), IOExample{Int64, Int64}(Dict(:x => 12), 148), IOExample{Int64, Int64}(Dict(:x => 13), 173), IOExample{Int64, Int64}(Dict(:x => 14), 200), IOExample{Int64, Int64}(Dict(:x => 15), 229), IOExample{Int64, Int64}(Dict(:x => 16), 260), IOExample{Int64, Int64}(Dict(:x => 17), 293), IOExample{Int64, Int64}(Dict(:x => 18), 328), IOExample{Int64, Int64}(Dict(:x => 19), 365), IOExample{Int64, Int64}(Dict(:x => 20), 404)], mean_squared_error, 2, 0.99, execute_on_input)
Genetic Search
Genetic search is a type of evolutionary algorithm, which simulates the process of natural selection. It evolves a population of candidate programs through operations like mutation, crossover (recombination), and selection. Then, the fitness of each program is assessed (i.e., how well it satisfies the given specifications). Only the 'fittest' programs are selected for the next generation, thus gradually refining the population of candidate programs.
For more information, see here.
We show the example of finding a lambda function. Try varying the parameters of the genetic search to see what happens.
e_gs = x -> 3 * x * x + (x + 2)#23 (generic function with 1 method)
problem_gs, examples_gs = create_problem(e_gs)(Problem{Vector{IOExample{Int64, Int64}}}("", IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 6), IOExample{Int64, Int64}(Dict(:x => 2), 16), IOExample{Int64, Int64}(Dict(:x => 3), 32), IOExample{Int64, Int64}(Dict(:x => 4), 54), IOExample{Int64, Int64}(Dict(:x => 5), 82), IOExample{Int64, Int64}(Dict(:x => 6), 116), IOExample{Int64, Int64}(Dict(:x => 7), 156), IOExample{Int64, Int64}(Dict(:x => 8), 202), IOExample{Int64, Int64}(Dict(:x => 9), 254), IOExample{Int64, Int64}(Dict(:x => 10), 312), IOExample{Int64, Int64}(Dict(:x => 11), 376), IOExample{Int64, Int64}(Dict(:x => 12), 446), IOExample{Int64, Int64}(Dict(:x => 13), 522), IOExample{Int64, Int64}(Dict(:x => 14), 604), IOExample{Int64, Int64}(Dict(:x => 15), 692), IOExample{Int64, Int64}(Dict(:x => 16), 786), IOExample{Int64, Int64}(Dict(:x => 17), 886), IOExample{Int64, Int64}(Dict(:x => 18), 992), IOExample{Int64, Int64}(Dict(:x => 19), 1104), IOExample{Int64, Int64}(Dict(:x => 20), 1222)]), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 6), IOExample{Int64, Int64}(Dict(:x => 2), 16), IOExample{Int64, Int64}(Dict(:x => 3), 32), IOExample{Int64, Int64}(Dict(:x => 4), 54), IOExample{Int64, Int64}(Dict(:x => 5), 82), IOExample{Int64, Int64}(Dict(:x => 6), 116), IOExample{Int64, Int64}(Dict(:x => 7), 156), IOExample{Int64, Int64}(Dict(:x => 8), 202), IOExample{Int64, Int64}(Dict(:x => 9), 254), IOExample{Int64, Int64}(Dict(:x => 10), 312), IOExample{Int64, Int64}(Dict(:x => 11), 376), IOExample{Int64, Int64}(Dict(:x => 12), 446), IOExample{Int64, Int64}(Dict(:x => 13), 522), IOExample{Int64, Int64}(Dict(:x => 14), 604), IOExample{Int64, Int64}(Dict(:x => 15), 692), IOExample{Int64, Int64}(Dict(:x => 16), 786), IOExample{Int64, Int64}(Dict(:x => 17), 886), IOExample{Int64, Int64}(Dict(:x => 18), 992), IOExample{Int64, Int64}(Dict(:x => 19), 1104), IOExample{Int64, Int64}(Dict(:x => 20), 1222)])
iterator_gs = GeneticSearchIterator(g_4, :X, examples_gs, population_size = 10, mutation_probability = 0.8, maximum_initial_population_depth = 3) GeneticSearchIterator(GenericSolver(1: X = 1
2: X = 2
3: X = 3
4: X = 4
5: X = 5
6: X = X * X
7: X = X + X
8: X = X - X
9: X = x
, SolverState(Hole[Bool[1, 1, 1, 1, 1, 1, 1, 1, 1]], Set{AbstractLocalConstraint}(), true), DataStructures.PriorityQueue{AbstractLocalConstraint, Int64, Base.Order.ForwardOrdering}(), nothing, false, 9223372036854775807, 9223372036854775807), IOExample{Int64, Int64}[IOExample{Int64, Int64}(Dict(:x => 1), 6), IOExample{Int64, Int64}(Dict(:x => 2), 16), IOExample{Int64, Int64}(Dict(:x => 3), 32), IOExample{Int64, Int64}(Dict(:x => 4), 54), IOExample{Int64, Int64}(Dict(:x => 5), 82), IOExample{Int64, Int64}(Dict(:x => 6), 116), IOExample{Int64, Int64}(Dict(:x => 7), 156), IOExample{Int64, Int64}(Dict(:x => 8), 202), IOExample{Int64, Int64}(Dict(:x => 9), 254), IOExample{Int64, Int64}(Dict(:x => 10), 312), IOExample{Int64, Int64}(Dict(:x => 11), 376), IOExample{Int64, Int64}(Dict(:x => 12), 446), IOExample{Int64, Int64}(Dict(:x => 13), 522), IOExample{Int64, Int64}(Dict(:x => 14), 604), IOExample{Int64, Int64}(Dict(:x => 15), 692), IOExample{Int64, Int64}(Dict(:x => 16), 786), IOExample{Int64, Int64}(Dict(:x => 17), 886), IOExample{Int64, Int64}(Dict(:x => 18), 992), IOExample{Int64, Int64}(Dict(:x => 19), 1104), IOExample{Int64, Int64}(Dict(:x => 20), 1222)], execute_on_input, 10, 0.8, 3)
begin
program_gs, error_gs = synth(problem_gs, iterator_gs)
rulenode2expr(program_gs, g_4)
end:(1 + ((((4 - 4) + (((4 + 2) - ((1 + ((4 * 4) * (1 - 1) + ((2 + ((3 - x) * 4 + ((4 + x) - 3 * 4) * 1)) + (x * x + 5)))) + 3 * 1)) * (1 - 1) + ((2 + ((3 - x) * 4 + ((4 + x) - 3 * 4) * 4)) + (x * x + 5)))) + 2 * 1) + ((x + 1) + (2 + (x * x + (4 + (x * x + 5)))))))