Create HeuristicLab.Problems.GeneticProgramming

[gkronber]

This plugin should hold GP problems such as the aritificial ant or the lawn mower problem.

This ticket replaces individual tickets #2421, #2422, and #2469

For integration into stable merge the following changesets:

• ticket #2430 (in particular r12846) must be merged first
• r12895:12906 (Encoding, ArtificialAnt-3.5 (deleted), LawnMower-3.4 (deleted)
• r12911:12912, r12915:12918

[gkronber]

changesets originally commited to #2469: r12897: added SymbolicExpressionTreeProblem base class r12904: implemented override for Analyze(...) method in SymbolicExpressionTreeProblem

r12911: created project structure for HeuristicLab.Problems.GeneticProgramming and added implementations of ArtificialAnt and LawnMower

[gkronber]

r12912: svn:ignore

[gkronber]

r12915:

• include Problems.GeneticProgramming in solution
• use Problems.GeneticProgramming from Problems.GrammaticalEvolution (only ArtificialAnt part)
• simplified GEArtificialAntProblem by using BasicProblem<IntegerVectorEncoding>

[gkronber]

r12916:

• deleted unused files
• removed createable attribute from outdated implementation of GrammaticalEvolution problems

[gkronber]

r12917:12918: removed deleted projects from solution

[gkronber]

I left the SymbolicExpressionTreeProblem in the encoding plugin because I believe it fits better there (as a potential base class for all problems using the symbolic expression tree encoding). It is not strictly necessary to include a reference to Problems.GeneticProgramming.

[gkronber]

r12921: update best solution only if a solution with a better best quality is found

[gkronber]

r12936:12937 added an implementation of Koza-style symbolic regression as BasicProblem to Problems.GeneticProgramming

[gkronber]

r12938: added even parity and multiplexer problems (GP)

[gkronber]

r12940: minor fix in multiplexer problem

[gkronber]

r12947: removed unnecessary Filename property

[gkronber]

The samples (artificial ant, lawn mower, and multiplexer) should be updated. (Done)

[gkronber]

• r13055: changed ordering of symbols in the grammar for the artificial ant problem to make sure the new problem produces the same results as the old implementation
• r13056: changed GP artificial ant sample to use new implementation

[gkronber]

r13057: changed lawn mower sample to use the new implementation and added assertions for the results of the unit test (let's see if they work on the builder...)

[gkronber]

r13058: fixed lawn mower sample

[gkronber]

r13163 (sorry this commit messages incorrectly references #2069, but it was not possible to edit the svn log message afterwards)

• adapted the multiplexer sample to use the specific implementation of the multiplexer problem instead of symbolic regression.
• Added best known solutions for the Boolean benchmark problems

[gkronber]

all changesets mentioned in the comments are relevant but probably it is best to review the code in

• HeuristicLab.Problems.GeneticProgramming and
• HeuristicLab.Problems.GeneticProgramming.Views

[mkommend]

Reviewed the SymbolicExpressionTreeProblem and HL.Problems.GP and the according views and unit test for sample creation.

Comments:

• Odd source code organization (cloning and persistence in a region at the EOF)
• BasicSymbolicRegression
  • Recreates constants every time the problem is changed => not reproducible
  • Couldn't the solution be transformed to a standard data analysis tree (simplify, optimize?
• Why are the boolean problems restricted (number of bits) and why is this done in the evaluation function?

Overall pretty cool and easy to implement problems. I am especially impressed on how easy tree evaluation can be performed for the boolean and regression problems.

[mkommend]

r13267: Minor code improvements in HL.Problems.GP (typos, code organization, code unification).

[mkommend]

r13269: Moved cloning and persistence code near the default ctor for all new GP problems.

[gkronber]

Thanks for code reorganization. I'm going to create tickets for your remaining remarks from the review.

[gkronber]

Replying to mkommend:

Reviewed the SymbolicExpressionTreeProblem and HL.Problems.GP and the according views and unit test for sample creation.

Comments:

• Odd source code organization (cloning and persistence in a region at the EOF)

Fixed with r13269.

• BasicSymbolicRegression
  • Recreates constants every time the problem is changed => not reproducible
  • Couldn't the solution be transformed to a standard data analysis tree (simplify, optimize?

Might be fixed in the future (-> separate tickets #2515, #2517)

• Why are the boolean problems restricted (number of bits) and why is this done in the evaluation function?

In the case of the even-parity problem the restriction stems from the fact that only digits are used as terminal symbols and there are only 10 digits. Would be easy to extend this.

In the case of the mux-problem I don't remember the exact reason but I believe this is an artifact from an earlier implementation where only digits and characters were used as terminal symbols. In any case the limit of 37 bits input is rather large and would mean that a single evaluation would have to iterate over 2³⁷ different input cases... I'm going to create a ticket for this (#2516).

Overall pretty cool and easy to implement problems. I am especially impressed on how easy tree evaluation can be performed for the boolean and regression problems.

[gkronber]

r13278: merged r12895:12906 from trunk to stable

[gkronber]

r13279: merged r12911:12912, r12915:12918 from trunk to stable

[gkronber]

r13280: merged r12921,r12936:12938,r12940,r12947,r13055:13058,r13163,r13267,r13269 from trunk to stable