search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
39 stars 16 forks source link

Grammatical Evolution #2109

Closed HeuristicLab-Trac-Bot closed 10 years ago

HeuristicLab-Trac-Bot commented 11 years ago

Issue migrated from trac ticket # 2109

milestone: HeuristicLab 3.3.10 | component: Algorithms | priority: medium | resolution: done

2013-09-13 12:14:15: @gkronber created the issue

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

HeuristicLab-Trac-Bot commented 11 years ago

2013-09-13 12:57:49: sawinkle changed status from new to accepted

HeuristicLab-Trac-Bot commented 11 years ago

2013-09-13 12:57:49: sawinkle changed owner from @s-wagner to sawinkle

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-07 21:03:56: @gkronber commented

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

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-07 21:04:40: @gkronber commented

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

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-07 21:04:40: sawinkle

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-08 15:14:05: sawinkle commented

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

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-08 15:20:32: sawinkle edited the issue description

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-08 15:20:32: sawinkle commented

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-11 21:46:55: sawinkle commented

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.

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-11 21:46:55: sawinkle

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-20 18:47:07: sawinkle commented

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).

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-20 18:47:07: sawinkle

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-20 19:29:02: sawinkle commented

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

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-20 19:29:40: sawinkle commented

r10070: resolved switch error

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-20 19:32:37: sawinkle commented

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

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-20 19:53:04: sawinkle commented

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

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-20 19:53:04: sawinkle

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-20 20:21:11: sawinkle commented

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 to IGESymbolicDataAnalysisEvaluator; 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.

HeuristicLab-Trac-Bot commented 11 years ago

2013-10-21 11:32:07: sawinkle commented

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.
HeuristicLab-Trac-Bot commented 10 years ago

2013-12-14 11:03:21: sawinkle edited the issue description

HeuristicLab-Trac-Bot commented 10 years ago

2013-12-14 17:42:21: sawinkle commented

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
HeuristicLab-Trac-Bot commented 10 years ago

2013-12-14 17:47:23: sawinkle commented

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

  • ConstantOptimizationEvaluator
  • MaxAbsoluteErrorEvaluator
  • MeanAbsoluteErrorEvaluator
  • MeanSquaredErrorEvaluator
HeuristicLab-Trac-Bot commented 10 years ago

2013-12-15 12:38:40: sawinkle commented

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.
HeuristicLab-Trac-Bot commented 10 years ago

2013-12-15 15:57:22: sawinkle commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2013-12-15 15:57:22: sawinkle

HeuristicLab-Trac-Bot commented 10 years ago

2013-12-17 13:26:51: sawinkle commented

r10232: Updated csproj of Grammatical Evolution branch

HeuristicLab-Trac-Bot commented 10 years ago

2013-12-17 17:43:31: @mkommend commented

r10233: Added sample algorithm for grammatical evolution tests.

HeuristicLab-Trac-Bot commented 10 years ago

2013-12-20 16:18:07: @gkronber commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2013-12-20 16:18:07: @gkronber

HeuristicLab-Trac-Bot commented 10 years ago

2013-12-22 13:12:45: @gkronber commented

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.

HeuristicLab-Trac-Bot commented 10 years ago

2013-12-22 13:13:44: @gkronber commented

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.

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-04 12:26:02: sawinkle commented

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.
HeuristicLab-Trac-Bot commented 10 years ago

2014-01-04 13:20:01: sawinkle commented

Replying to [comment:23 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. [[BR]] The problem with the very "broad" trees should be fixed now.

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-04 13:21:45: sawinkle commented

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.

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-04 13:21:45: sawinkle

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-05 12:55:53: sawinkle commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-05 14:24:30: sawinkle commented

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.
HeuristicLab-Trac-Bot commented 10 years ago

2014-01-06 20:43:35: sawinkle commented

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
HeuristicLab-Trac-Bot commented 10 years ago

2014-01-07 14:49:54: sawinkle commented

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.
HeuristicLab-Trac-Bot commented 10 years ago

2014-01-07 14:52:19: sawinkle commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-12 20:01:46: sawinkle commented

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.
HeuristicLab-Trac-Bot commented 10 years ago

2014-01-12 20:11:04: sawinkle commented

r10329: Modified test configurations of problems:

  • Artificial Ant:
    • MaximumExpressionLength 50 -> 200
    • SelectedParents 200 -> 10
  • Symbolic Regression:
    • MaximumGenerations 50 -> 100
HeuristicLab-Trac-Bot commented 10 years ago

2014-01-12 21:05:59: sawinkle commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-14 19:28:17: sawinkle commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-14 20:29:31: sawinkle commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-15 19:23:52: sawinkle commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-16 17:45:26: @gkronber commented

r10349: removed unused references and fixed plugin dependencies

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-17 09:30:58: @gkronber commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2014-01-17 09:32:11: @gkronber commented

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

HeuristicLab-Trac-Bot commented 10 years ago

2014-06-01 14:44:03: sawinkle commented

r10923: Renamed plugin class from HeuristicLabProblemsGEArtificialAntPlugin to HeuristicLabProblemsGrammaticalEvolutionPlugin.