Opened 4 years ago

Closed 3 years ago

#2109 closed feature request (done)

Grammatical Evolution

Reported by: gkronber Owned by: gkronber
Priority: medium Milestone: HeuristicLab 3.3.10
Component: Algorithms Version:
Keywords: Cc:

Description (last modified by sawinkle)

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.

Change History (57)

comment:1 Changed 4 years ago by sawinkle

  • Owner changed from swagner to sawinkle
  • Status changed from new to accepted

comment:2 Changed 3 years ago by 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

comment:3 Changed 3 years ago by 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
Last edited 3 years ago by sawinkle (previous) (diff)

comment:4 Changed 3 years ago by sawinkle

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

comment:5 Changed 3 years ago by sawinkle

  • Description modified (diff)

comment:6 Changed 3 years ago by 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.
Last edited 3 years ago by sawinkle (previous) (diff)

comment:7 Changed 3 years ago by 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).
Last edited 3 years ago by sawinkle (previous) (diff)

comment:8 Changed 3 years ago by 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

comment:9 Changed 3 years ago by sawinkle

r10070: resolved switch error

comment:10 Changed 3 years ago by sawinkle

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

comment:11 Changed 3 years ago by sawinkle

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

Last edited 3 years ago by sawinkle (previous) (diff)

comment:12 Changed 3 years ago by 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.

comment:13 Changed 3 years ago by 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.

comment:14 Changed 3 years ago by sawinkle

  • Description modified (diff)

comment:15 Changed 3 years ago by 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

comment:16 Changed 3 years ago by sawinkle

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

  • ConstantOptimizationEvaluator
  • MaxAbsoluteErrorEvaluator
  • MeanAbsoluteErrorEvaluator
  • MeanSquaredErrorEvaluator

comment:17 Changed 3 years ago by 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.

comment:18 Changed 3 years ago by sawinkle

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

Last edited 3 years ago by sawinkle (previous) (diff)

comment:19 Changed 3 years ago by sawinkle

r10232: Updated csproj of Grammatical Evolution branch

comment:20 Changed 3 years ago by mkommend

r10233: Added sample algorithm for grammatical evolution tests.

comment:21 Changed 3 years ago by gkronber

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

Last edited 3 years ago by gkronber (previous) (diff)

comment:22 Changed 3 years ago by 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.

comment:23 follow-up: Changed 3 years ago by 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.

comment:24 Changed 3 years ago by 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.

comment:25 in reply to: ↑ 23 Changed 3 years ago by 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.

comment:26 Changed 3 years ago by 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.

Last edited 3 years ago by sawinkle (previous) (diff)

comment:27 Changed 3 years ago by sawinkle

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

comment:28 Changed 3 years ago by 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.

comment:29 Changed 3 years ago by 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

comment:30 Changed 3 years ago by 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.

comment:31 Changed 3 years ago by sawinkle

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

comment:32 Changed 3 years ago by 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.

comment:33 Changed 3 years ago by sawinkle

r10329: Modified test configurations of problems:

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

comment:34 Changed 3 years ago by sawinkle

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

comment:35 Changed 3 years ago by 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

comment:36 Changed 3 years ago by sawinkle

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

comment:37 Changed 3 years ago by sawinkle

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

comment:38 Changed 3 years ago by gkronber

r10349: removed unused references and fixed plugin dependencies

comment:39 Changed 3 years ago by gkronber

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

comment:40 Changed 3 years ago by gkronber

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

comment:41 Changed 3 years ago by sawinkle

r10923: Renamed plugin class from HeuristicLabProblemsGEArtificialAntPlugin to HeuristicLabProblemsGrammaticalEvolutionPlugin.

Last edited 3 years ago by sawinkle (previous) (diff)

comment:42 Changed 3 years ago by gkronber

  • Owner changed from sawinkle to gkronber
  • Status changed from accepted to assigned

comment:43 Changed 3 years ago by gkronber

  • Status changed from assigned to accepted

comment:44 Changed 3 years ago by gkronber

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

comment:45 Changed 3 years ago by gkronber

r10974: minor code cleanup

comment:46 Changed 3 years ago by gkronber

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

comment:47 Changed 3 years ago by gkronber

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.10
  • Version branch deleted

comment:48 Changed 3 years ago by gkronber

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

comment:49 Changed 3 years ago by gkronber

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

comment:50 Changed 3 years ago by gkronber

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

comment:51 Changed 3 years ago by gkronber

  • Status changed from accepted to reviewing

comment:52 Changed 3 years ago by gkronber

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

r10989: set svn:ignore properties

comment:53 Changed 3 years ago by gkronber

r10996: removed plugin dependency HeuristicLab.Analysis

comment:54 Changed 3 years ago by gkronber

r11008: removed incorrect unit test attributes from a helper method

comment:55 Changed 3 years ago by gkronber

  • Status changed from reviewing to readytorelease

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

comment:56 Changed 3 years ago by gkronber

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

comment:57 Changed 3 years ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
Note: See TracTickets for help on using tickets.