sisl / exproptimization.jl

Algorithms for optimization of Julia expressions

ExprOptimization.jl

Algorithms for the optimization of Julia expressions derived from a grammar. For an introduction to expression optimization, see chapter 20 of Algorithms for Optimization by Mykel J. Kochenderfer and Tim A. Wheeler (MIT Press, 2019).

The following algorithms are implemented:

• Monte Carlo
• Genetic Programming
• Grammatical Evolution
• Cross-Entropy Method
• Probabilistic Incremental Program Execution (PIPE)

Usage

Please see the example notebooks.

Maintainers:

• Ritchie Lee, [email protected]
• Mykel Kochenderfer, [email protected]

exproptimization.jl's Issues

A suggestion for performance improvement

Hi Ritchie,
The speed of GE may be significantly improved if the code only evaluates the modified individuals after reproducation, mutation and crossover operations.

Sheng

Error showing value of type TreeView.LabelledTree:

I was working in Atom, and when I tried to run display(results_gp.tree, grammar), I got the following error:
Error showing value of type TreeView.LabelledTree:
ERROR: IOError: could not spawn lualatex --enable-write18 --output-directory=./jl_2dHOU7 ./jl_2dHOU7/tikzpicture.tex: no such file or directory (ENOENT)
Stacktrace:
[1] _spawn_primitive(::String, ::Cmd, ::Array{Any,1}) at .\process.jl:99
[2] #550 at .\process.jl:112 [inlined]
[3] setup_stdios(::Base.var"#550#551"{Cmd}, ::Array{Any,1}) at .\process.jl:196
[4] _spawn at .\process.jl:111 [inlined]
[5] _spawn at .\process.jl:106 [inlined]
[6] success(::Cmd) at .\process.jl:496
[7] (::TikzPictures.var"#10#11"{TikzPictures.SVG,TikzPictures.TikzPicture,String})() at C:\Users\akahs.juliapro\JuliaPro_v1.4.0-1\packages\TikzPictures\QJ62d\src\TikzPictures.jl:338
[8] cd(::TikzPictures.var"#10#11"{TikzPictures.SVG,TikzPictures.TikzPicture,String}, ::String) at .\file.jl:93
[9] save(::TikzPictures.SVG, ::TikzPictures.TikzPicture) at C:\Users\akahs.juliapro\JuliaPro_v1.4.0-1\packages\TikzPictures\QJ62d\src\TikzPictures.jl:319
[10] show(::IOContext{Base.GenericIOBuffer{Array{UInt8,1}}}, ::MIME{Symbol("image/svg+xml")}, ::TikzPictures.TikzPicture) at C:\Users\akahs.juliapro\JuliaPro_v1.4.0-1\packages\TikzPictures\QJ62d\src\TikzPictures.jl:405
[11] show at C:\Users\akahs.juliapro\JuliaPro_v1.4.0-1\packages\TreeView\OEx44\src\display.jl:34 [inlined]
[12] show(::IOContext{Base.GenericIOBuffer{Array{UInt8,1}}}, ::String, ::TreeView.LabelledTree) at .\multimedia.jl:109
[13] displayinplotpane(::TreeView.LabelledTree) at C:\Users\akahs.juliapro\JuliaPro_v1.4.0-1\packages\Atom\wlPiw\src\display\showdisplay.jl:67
[14] display(::Atom.JunoDisplay, ::TreeView.LabelledTree) at C:\Users\akahs.juliapro\JuliaPro_v1.4.0-1\packages\Atom\wlPiw\src\display\showdisplay.jl:118
[15] display(::Any) at .\multimedia.jl:323
[16] #invokelatest#1 at .\essentials.jl:712 [inlined]
[17] invokelatest at .\essentials.jl:711 [inlined]
[18] print_response(::IO, ::Any, ::Bool, ::Bool, ::Any) at C:\Users\julia\AppData\Local\Julia-1.4.0\share\julia\stdlib\v1.4\REPL\src\REPL.jl:161
[19] print_response(::REPL.AbstractREPL, ::Any, ::Bool, ::Bool) at C:\Users\julia\AppData\Local\Julia-1.4.0\share\julia\stdlib\v1.4\REPL\src\REPL.jl:146
[20] (::REPL.var"#do_respond#38"{Bool,Atom.var"#232#233",REPL.LineEditREPL,REPL.LineEdit.Prompt})(::Any, ::Any, ::Any) at C:\Users\julia\AppData\Local\Julia-1.4.0\share\julia\stdlib\v1.4\REPL\src\REPL.jl:729
[21] #invokelatest#1 at .\essentials.jl:712 [inlined]
[22] invokelatest at .\essentials.jl:711 [inlined]
[23] run_interface(::REPL.Terminals.TextTerminal, ::REPL.LineEdit.ModalInterface, ::REPL.LineEdit.MIState) at C:\Users\julia\AppData\Local\Julia-1.4.0\share\julia\stdlib\v1.4\REPL\src\LineEdit.jl:2354
[24] run_frontend(::REPL.LineEditREPL, ::REPL.REPLBackendRef) at C:\Users\julia\AppData\Local\Julia-1.4.0\share\julia\stdlib\v1.4\REPL\src\REPL.jl:1055
[25] run_repl(::REPL.AbstractREPL, ::Any) at C:\Users\julia\AppData\Local\Julia-1.4.0\share\julia\stdlib\v1.4\REPL\src\REPL.jl:206
[26] (::Base.var"#764#766"{Bool,Bool,Bool,Bool})(::Module) at .\client.jl:383
[27] #invokelatest#1 at .\essentials.jl:712 [inlined]
[28] invokelatest at .\essentials.jl:711 [inlined]
[29] run_main_repl(::Bool, ::Bool, ::Bool, ::Bool, ::Bool) at .\client.jl:367
[30] exec_options(::Base.JLOptions) at .\client.jl:305
[31] _start() at .\client.jl:484

Feature: Return top expressions

Currently from my understanding optimize() of algorithms return only the best expression, right? It should be possible and useful to some to add a parameter to specify the number of top expressions to return.

Add parallel processing support

At the individual evaluation level.
I'm thinking Threads.@thread might be the easiest way to go.

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Time out when cloning from github

Hi

Experiencing a time out when cloning from github.

I checked to see if it was my connection by installing other packages which worked ok.

Here is my error:

| | || | | | (| | | Version 0.6.2 (2017-12-13 18:08 UTC)
/ |_'|||_'_| | Official http://julialang.org/ release
|__/ | x86_64-w64-mingw32

julia> Pkg.add("ExprOptimization")
INFO: Cloning cache of ExprOptimization from https://github.com/sisl/ExprOptimization.jl.git
ERROR: Cannot clone ExprOptimization from https://github.com/sisl/ExprOptimization.jl.git. failed to send request: The operation timed out

prefetch(::String, ::String, ::Array{String,1}) at .\pkg\cache.jl:56
resolve(::Dict{String,Base.Pkg.Types.VersionSet}, ::Dict{String,Dict{VersionNumber,Base.Pkg.Types.Available}}, ::Dict{String,Tuple{VersionNumber,Bool}}, ::Dict{String,Base.Pkg.Types.Fixed}, ::Dict{String,VersionNumber}, ::Set{String}) at .\pkg\entry.jl:516
resolve(::Dict{String,Base.Pkg.Types.VersionSet}, ::Dict{String,Dict{VersionNumber,Base.Pkg.Types.Available}}, ::Dict{String,Tuple{VersionNumber,Bool}}, ::Dict{String,Base.Pkg.Types.Fixed}) at .\pkg\entry.jl:479
edit(::Function, ::String, ::Base.Pkg.Types.VersionSet, ::Vararg{Base.Pkg.Types.VersionSet,N} where N) at .\pkg\entry.jl:30
(::Base.Pkg.Entry.##1#3{String,Base.Pkg.Types.VersionSet})() at .\task.jl:335
Stacktrace:
[1] sync_end() at .\task.jl:287
[2] macro expansion at .\task.jl:303 [inlined]
[3] add(::String, ::Base.Pkg.Types.VersionSet) at .\pkg\entry.jl:51
[4] (::Base.Pkg.Dir.##4#7{Array{Any,1},Base.Pkg.Entry.#add,Tuple{String}})() at .\pkg\dir.jl:36
[5] cd(::Base.Pkg.Dir.##4#7{Array{Any,1},Base.Pkg.Entry.#add,Tuple{String}}, ::String) at .\file.jl:59
[6] #cd#1(::Array{Any,1}, ::Function, ::Function, ::String, ::Vararg{String,N} where N) at .\pkg\dir.jl:36
[7] add(::String) at .\pkg\pkg.jl:117

Question: Optimal parameters for GE

Random.seed!(1)
p = GrammaticalEvolution(grammar,:Real,1000,20,10,10,6,0.2,0.4,0.4; select_method=GrammaticalEvolutions.TruncationSelection(300))
results_ge = optimize(p, grammar, :Real, loss)
(results_ge.expr, results_ge.loss)

grammar::Grammar: grammar
typ::Symbol: start symbol
pop_size::Int: population size
iterations::Int: number of iterations
init_gene_length::Int: initial length of genotype integer array
max_gene_length::Int: maximum length of genotype integer array
max_depth::Int: maximum depth of derivation tree
p_reproduction::Float64: probability of reproduction operator
p_crossover::Float64: probability of crossover operator
p_mutation::Float64: probability of mutation operator
select_method::SelectionMethod: selection method (default: tournament selection)
mutate_method::InitializationMethod: mutation method (default: multi-mutate)

Is there any formal process using the Grammatical Evolution example on how the parameters were chosen to suit the example problem?

What is maximum depth and how does that affect the GE process?
What are the implications of setting low / high probabilities of mutation / crossover / reproduction?
Also init_gene - how does that affect the GE process?

Be nice to have author response but happy to be sent to external source!

Thanks!
Andrew

Print expression used per iteration

Hi!

While the GE is running, is it possible to print out each expression being tested to the console?

If we take the symbolic regression example:

srand(0)
p = GrammaticalEvolution(grammar,:Real,1000,20,10,10,6,0.2,0.4,0.4; select_method=GrammaticalEvolutions.TruncationSelection(300))
results_ge = optimize(p, grammar, :Real, loss)
(results_ge.expr, results_ge.loss)

Can we add somewhere to print each expression per iteration? I just want to make sure its iterating through my grammar correctly.

Thanks!
Andrew

** Update:

By reading the faster symbolic regression example. I learned I can place this within the loss function.

print(get_executable(tree, grammar))

Closing.

Non-derivation-tree-based algorithms and _()

Similar issue to #4

Grammatical evolution also has a similar issue. The mapping from integer vector to derivation tree becomes non-deterministic in this case. The value doesn't get concretized until derivation tree is created.

TODO

• More examples
• Tests and activate Travis CI

Grammatical Evolution does not support _() functions in the grammar

I have a function Fun(sig,N, M) that needs input constrains like N > M, so I tried using grammer of

M=|(1:30)
Add=_(rand(1:50))
sig = Fun(sig, M+Add, M)

and it doesn' t support this kind. Using rand without _( would result in expressions that contains a rand(1:50) so I could not know what is the exact input. I also tried

M=|(1:30)
Add=|(1:30)
sig = Fun(sig, M+Add, M)

and the result is some different M in the expression, like (Fun(sig, 3+10, 5)) .

What is the recommended way of doing this for now if supporting _() is hard, with inputing integers with some constraints? Thanks.

Save tree to a .txt file?

Hi!

So the output:

display(results_ge.tree, grammar)

Can I save it as .txt file?

I use the Atom - juno IDE. It runs but not sure how I see the display?

Thanks
Andrew

PS loving this package

Enumerating algorithms and _()

Enumerating algorithms, such as Nested Monte Carlo, Iterated Depth-First Search, etc., will not be able to handle _() rules properly since they enumerate over production rules but there could be infinitely many possibilities hidden inside _().

Adding eval support for algorithms other than Genetic Programming

I noticed that Grammatical Evolution, Cross-Entropy, or PIPE don't currently support grammars that have eval statements "_()". Is this a fundamental limitation of those algorithms or just an implementation challenge?

I have a project where I would like to compare the performance of these different algorithms to Genetic Programming but I need the eval syntax to sample continuous values. I would be happy to look into implementing this feature if I can get a little direction.

Remove requirement for terminal for each type

There is currently a requirement for at least one terminal per type, which is restrictive.

plotting trees with symbols containing "_" results in error

When plotting trees that contains symbol including underscore ("_"), which can be common in programming, the plotting engine would result in errors like

! Missing $ inserted.
<inserted text> 
$
l.67 }
    ;

I don' t know if there can be workarounds in this package or we should report to TreeView.jl?

Genetic Programming Addition Vs Genetic Algorithm

Be interesting to see a genetic program which have variable length versus the algorithm which has a fixed length. During evolution, genetic programs can increase in complexity. However this would be very interesting and the SO post does a decent job of explaining the differences:

https://stackoverflow.com/questions/3819977/what-are-the-differences-between-genetic-algorithms-and-genetic-programming

https://stackoverflow.com/questions/5732917/code-generation-by-genetic-algorithms

and

Chapter 8
A Genetic Programming Tutorial
John R. Koza1
and Riccardo Poli2
1
Stanford University, Stanford, California

http://www.genetic-programming.com/jkpdf/burke2003tutorial.pdf

Would make an great addition!

The order of `evaluate!` and `fit_mle!` in CE

In the main loop of CE (below),

ExprOptimization.jl/src/CrossEntropy/CrossEntropys.jl

Lines 106 to 114 in 6d9a025

	best_tree, best_loss = evaluate!(p, loss, grammar, pop, losses, RuleNode(0), Inf)
	for iter = 1:p.iterations
	verbose && println("iterations: $iter of $(p.iterations)")
	for i in eachindex(pop)
	pop[i] = rand(RuleNode, pcfg, typ, dmap, p.max_depth)
	end
	fit_mle!(pcfg, pop[1:p.top_k], p.p_init)
	best_tree, best_loss = evaluate!(p, loss, grammar, pop, losses, best_tree, best_loss)
	end

it seems to me that fit_mle! should be called before the loop to resample population, i.e. L109 to L111.
Otherwise the PCFG is always fit using k samples that are not actually sorted or so.
Do I miss anything here?

0.7 precompile error

[ Info: Precompiling ExprOptimization [0d84ce59-e78b-5c9a-b954-3a5400d7f6ed]
┌ Warning: Package ExprOptimization does not have StatsBase in its dependencies:
│ - If you have ExprOptimization checked out for development and have
│ added StatsBase as a dependency but haven't updated your primary
│ environment's manifest file, try Pkg.resolve().
│ - Otherwise you may need to report an issue with ExprOptimization
└ Loading StatsBase into ExprOptimization from project dependency, future warnings for ExprOptimization are suppressed.
ERROR: LoadError: LoadError: ArgumentError: Package ExprOptimization does not have AbstractTrees in its dependencies:

• If you have ExprOptimization checked out for development and have
  added AbstractTrees as a dependency but haven't updated your primary
  environment's manifest file, try Pkg.resolve().
• Otherwise you may need to report an issue with ExprOptimization
  Stacktrace:
  [1] require(::Module, ::Symbol) at .\loading.jl:830
  [2] include at .\boot.jl:317 [inlined]
  [3] include_relative(::Module, ::String) at .\loading.jl:1038
  [4] include at .\sysimg.jl:29 [inlined]
  [5] include(::String) at C:\Users\Andrew.Bannerman.julia\packages\ExprOptimization\EBWRP\src\ExprOptimization.jl:3
  [6] top-level scope at none:0
  [7] include at .\boot.jl:317 [inlined]
  [8] include_relative(::Module, ::String) at .\loading.jl:1038
  [9] include(::Module, ::String) at .\sysimg.jl:29
  [10] top-level scope at none:2
  [11] eval at .\boot.jl:319 [inlined]
  [12] eval(::Expr) at .\client.jl:399
  [13] top-level scope at .\none:3
  in expression starting at C:\Users\Andrew.Bannerman.julia\packages\ExprOptimization\EBWRP\src\ProbabilisticExprRules\ProbabilisticExprRules.jl:5
  in expression starting at C:\Users\Andrew.Bannerman.julia\packages\ExprOptimization\EBWRP\src\ExprOptimization.jl:61

Max_depth is not globally enforced

When doing a crossover or mutation, you can end up with trees that are deeper than max_depth. The reason is that max_depth is not globally enforced at the moment. It is only enforced relative to the substitution point.

Also, there is currently a requirement for at least one terminal per type, which is restrictive.

Return of enqueue!() are always -1

There may be a little mistake in contrib/BoundedPriorityQueues.jl file when you define the function DataStructures.enqueue!, which results in return value of -1 all the time.

function DataStructures.enqueue!(q::BoundedPriorityQueue{K,V}, k::K, v::V;
    make_copy::Bool=false) where {K,V}
    haskey(q.pq, k) && return -1 #keys must be unique, return -1 if collision
    if make_copy
        k = deepcopy(k)
    end
    n = length(q.pq)
    enqueue!(q.pq, k, v)
    n_add = n - length(q.pq) #number of items added
    while length(q.pq) > q.N
        dequeue!(q.pq)
    end
    n_add
end

I guess the mistake is made in line 59:

n_add = n - length(q.pq) #number of items added

and it should be

n_add = length(q.pq) - n #number of items added