Grammatical Evolution

[gkronber]

Implementation of Grammatical Evolution (its genotype-to-phenotype mapping) in HL.
This includes the creation of a SymbolicExpressionTree (phenotype) out of an IntegerVector (genotype), using a SymbolicExpressionGrammar.
The implementation should be tested by adapting the Artificial Ant problem and the Symbolic Regression problem.

[gkronber]

r10012: added initial version of Problem class and Evaluator class; GEArtificialAntProblem randomly initializes an IntegerVector and prepares the GE run; GEEvaluator currently only creates a simple SymbolicExpressionTree, consisting of the RootSymbol, StartSymbol and the MoveSymbol

[gkronber]

r10022:

• simplified GEArtificialAntProblem and removed some unused code (e.g. parameter MaximumExpressionDepth is not necessary for an IntegerVector)

• extended GEEvaluator to perform a complete, recursive Genotype-To-Phenotype mapping (depth-first approach); currently no "wrapping" of the integer vector is possible; a full tree with the maximum possible nodes filled in is generated, dependent on the integer vector; the Interpreter, Analysers and other classes get reused

[sawinkle]

r10029: added additional documentation and refactored code of GEEvaluator.cs

[sawinkle]

r10039:

• Renamed GEEvaluator.cs to GEArtificialAntEvaluator.cs, because a further Evaluator for the Symbolic Regression problem (single objective) is planned to be implemented.

• Excluded the mapping process from GEArtificialAntEvaluator.cs and created several separated mapper classes. Created stubs for breath-first, depth-first, random and PIGE mappers. These mapper implementations should later be easily usable together with different problems. The mapper can be selected in the GUI, via a Problem parameter. The depth-first mapper is already usable, the others still cause exceptions.

[sawinkle]

r10068:

• Removed the parameters MaxFunctionDefinitions and MaxFunctionArguments from GEArtificialAntProblem.cs, because automatically defined functions (adf) won't be supported by the Grammatical Evolution implementation of the Artificial Ant problem.

• Switched from SharpDevelop to Visual Studio 2012 and installed 'Productivity Power Tools 2012'. This extension includes the options 'Format Document on save' and 'Remove and Sort Usings on save', so that some usings were deleted, sorted and the formating changed slightly. Furthermore 'Visual Studio 2010 text editor settings.vssettings' were included.

• Added new folders ArtificialAnt and Symbolic to separate the files for the ArtificialAnt problem and the Symbolic Regression problem (single objective).

[sawinkle]

r10069: an error occurred, when trying to switch GEArtificialAntEvaluator.cs to the sub folder ArtificialAnt; GEArtificialAntEvaluator.cs was switched as folder (!) to branches\GrammaticalEvolution\HeuristicLab.Problems.GrammaticalEvolution

[sawinkle]

r10070: resolved switch error

[sawinkle]

r10071: moved GEArtificialAntEvaluator.cs and GEArtificialAntProblem.cs to sub folder \ArtificialAnt

[sawinkle]

r10072: added copies of files of the DataAnalysis projects and the SymbolicRegression projects and renamed them to include 'GE'

[sawinkle]

r10073:

• Renamed all identifiers within the files to include 'GE', where necessary.

• Changed the namespaces of all files to 'HeuristicLab.Problems.GrammaticalEvolution'.

• Added the parameters IntegerVector, GenotypeToPhenotype and SymbolicExpressionTreeGrammar to the Evaluator classes, where necessary.

• Changed the SolutionCreator from ISymbolicDataAnalysisSolutionCreator to IIntegerVectorCreator; changed the Evaluator from ISymbolicDataAnalysisEvaluator<T> to IGESymbolicDataAnalysisEvaluator<T>; the problem data class/interface IDataAnalysisProblemData stays the same.

• The methods Evaluate() and Calculate() of the specific Evaluators won't change -> the genotype-to-phenotype mapping process is done within the Apply() method.

[sawinkle]

r10075:

• For each newly created node, ResetLocalParameters() has to be called, if possible. Otherwise 'Variable' symbols won't be initialized correctly. (E.g. internal ValueName is null and causes exceptions.)
• Method MapDepthFirstRecursively() of DepthFirstMapper.cs checks subtree boundaries by using the MinimumArity instead of the MaximumArity. Otherwise e.g. adding the 'Addition' symbol will cause very short trees, because this symbol has got a MaximumArity of 255! This would cause, that the tree is immediately full, after insertion of one 'Addition' symbol, if the genotype length is e.g. just 100.
• Several bug fixes.
• Unresolved issues:
  • Changes in the selected grammar are not taken into account during a run (e.g. 'Addition' symbols will be inserted into the tree, although its checkbox was unchecked previously).
  • Exception, if a division by zero is tried.
  • Wrapping mechanism.

[sawinkle]

r10226:

• Added file IGESymbolicDataAnalysisProblem.cs to determine, which parameters should be used. => Removed parameters MaximumSymbolicExpressionTreeDepthParameter, MaximumFunctionDefinitionsParameter and MaximumFunctionArgumentsParameter, which are unnecessary for Grammatical Evolution.
• Adapted the other files to use the interfaces of the new file IGESymbolicDataAnalysisProblem.cs

[sawinkle]

r10227: Added four additional evaluators for the Symbolic Regression problem, namely

• ConstantOptimizationEvaluator
• MaxAbsoluteErrorEvaluator
• MeanAbsoluteErrorEvaluator
• MeanSquaredErrorEvaluator

[sawinkle]

r10228: Updated DepthFirstMapper and abstract base class GenotypeToPhenotypeMapper:

• Added new method SampleArity() to GenotypeToPhenotypeMapper to determine a random arity for a given node, depending on a maximum allowed arity.
• Replaced the recursive depth-first mapping approach by an iterative one, which uses a stack of <node, arity> tuples. The recursive approach only generated trees with very small subtrees, depending on the minimumArity of each node. Now, the iterative one uses the SampleArity() method and pushes/pops the <node, arity> tuples from/to the used stack. Therefore, it is not necessary to only allow the minimumArity, but also to deal with arbitrarily sampled arities per node.

[sawinkle]

r10229: Implemented a BreathFirstMapper, which works similarly to the DepthFirstMapper, but uses a queue to enable a breath-first tree creation.

[sawinkle]

r10232: Updated csproj of Grammatical Evolution branch

[mkommend]

r10233: Added sample algorithm for grammatical evolution tests.

[gkronber]

r10263 implemented a wrapper for evaluators that transforms genotypes to phenotypes for symbolic regression (deleted obsolete evaluators.

[gkronber]

r10268: implemented a grammar especially for GE (the grammar is not configured correctly when used in a classic symbolic regression/classification problem).

To use this grammar in a classical symbolic expression problem, first set the grammar in a GEProblem and load the problem instance (this creates the necessary variable symbols). After this, the configured grammar can be dragged onto the grammar parameter of the classical problem.

[gkronber]

I tested the grammar with a symbolic regression problem. But I have not yet produced good solutions because the translator from genotype to phenotype still produces very "broad" trees.

[sawinkle]

r10276: Refactoring:

• Removed recursive version of mapping in /Mappers/DepthFirstMapper.cs, because only the iterative one is used.
• Removed unused using statements and unused commented code.

[sawinkle]

Replying to gkronber:

I tested the grammar with a symbolic regression problem. But I have not yet produced good solutions because the translator from genotype to phenotype still produces very "broad" trees.

The problem with the very "broad" trees should be fixed now.

[sawinkle]

r10277: Replaced MinimumArity/MaximumArity with method call GetMinimumSubtreeCount()/GetMaximumSubtreeCount() in /Mappers/GenotypeToPhenotypeMapper.cs. Now not the total arity (e.g. 1 to 255 for Addition) is taken, but the limited one (e.g. 2 to 2 for Addition). As a result, the problem with the "broad" trees is solved.

[sawinkle]

r10280: Fetched random number generator in Evaluator implementations from scope, so that the same results are produced using the same seed.

[sawinkle]

r10282: Added

• new Artificial Ant configuration (OSGA Artificial Ant 2.hl) including the previous bug fixes.
• Artificial Ant Experiment (OSGA Artificial Ant 2 Experiment.hl) including three experiments with genotype length 50, 30 and 100. Each experiment runs the Artificial Ant problem with a DepthFirstMapper and a BreathFirstMapper ten times each.

[sawinkle]

r10290:

• Implemented PIGEMapper. Due to that, it was necessary to modify the Map method interface to additionally take the bounds and length of the genotype.
• Corrected and simplified the different mappers. Simplified the SampleArity method of /Mappers/GenotypeToPhenotypeMapper.cs

[sawinkle]

r10296:

• Removed OSGA Artificial Ant 2 Experiment.hl, because it is not significant with only 5 generations for each run.
• Removed OSGA Artificial Ant 2.hl and instead updated OSGA Artificial Ant.hl
• Added OSGA Symbolic Regression Poly 10.hl with a correct configuration for the Symbolic Regression problem.

[sawinkle]

Note for experiments and batch runs:
To significantly test a problem, perform approximately 30 runs with at least 50 generations each.

[sawinkle]

r10328:

• Added method comments + refactoring.
• Implemented RandomMapper.
• Changed InitialTreeLength (genotype length) of Symbolic Regression problem from 25 to 30, equally to the Artificial Ant problem with also 30.

[sawinkle]

r10329: Modified test configurations of problems:

• Artificial Ant:
  • MaximumExpressionLength 50 -> 200
  • SelectedParents 200 -> 10
• Symbolic Regression:
  • MaximumGenerations 50 -> 100

[sawinkle]

r10330: Added an Artificial Ant experiment and a Symbolic Regression experiment.

[sawinkle]

r10334: added finished experiment for the artificial ant problem
r10336: added finished experiment for symbolic regression
r10337: added experiment for GE symb reg with a grammar without constants

[sawinkle]

r10339: Added Artificial Ant experiment (tree-based GP) with MaximumSymbolicExpressionTreeLength of 50, 100, 170 and 300.

[sawinkle]

r10340: added finished experiment (GE - Symbolic Regression) with a grammar without constants.

[gkronber]

r10349: removed unused references and fixed plugin dependencies

[gkronber]

r10350: added finished experiments for tree-based GP (artificial ant and symbolic regression without constants for the poly-10 problem)

[gkronber]

r10351: added finished experiment for tree-based GP with constants for the poly-10 problem.

[sawinkle]

r10923: Renamed plugin class from HeuristicLabProblemsGEArtificialAntPlugin to HeuristicLabProblemsGrammaticalEvolutionPlugin.

[gkronber]

r10968: updated license headers and the solution file (for VS2012)

[gkronber]

r10974: minor code cleanup

[gkronber]

r10975: copied grammatical evolution plugin from feature development branch into the trunk

[gkronber]

r10983: added unit test to create and run grammatical evolution samples

[gkronber]

r10984: retry until a unique constant is sampled when creating constants in the GE symbolic regression grammar

[gkronber]

r10986: added GE samples (symbreg and artificial ant) to the list of samples in the optimizer

[gkronber]

r10988: moved implementation of grammatical evolution problem into a version 3.3 folder and fixed build output paths

r10989: set svn:ignore properties

[gkronber]

r10996: removed plugin dependency HeuristicLab.Analysis

[gkronber]

r11008: removed incorrect unit test attributes from a helper method

[gkronber]

This ticket is ready to be released. A documentation page for grammatical evolution should be created.

[gkronber]

r11103: merged r10975,r10983,r10984,r10986,r10988,r10989,r10996,r11008 (grammatical evolution) from trunk to stable