Free cookie consent management tool by TermsFeed Policy Generator

Changeset 10022


Ignore:
Timestamp:
10/03/13 22:47:11 (11 years ago)
Author:
sawinkle
Message:

#2109:

  • 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
Location:
branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/GEArtificialAntProblem.cs

    r10012 r10022  
    8686      get { return (IValueParameter<IntValue>)Parameters["MaximumExpressionLength"]; }
    8787    }
    88     public IValueParameter<IntValue> MaxExpressionDepthParameter {
    89       get { return (IValueParameter<IntValue>)Parameters["MaximumExpressionDepth"]; }
    90     }
    9188    public IValueParameter<IntValue> MaxFunctionDefinitionsParameter {
    9289      get { return (IValueParameter<IntValue>)Parameters["MaximumFunctionDefinitions"]; }
     
    104101      get { return (IValueParameter<IntMatrix>)Parameters["Bounds"]; }
    105102    }
    106    
    107103    #endregion
    108104
     
    119115      get { return MaxExpressionLengthParameter.Value; }
    120116      set { MaxExpressionLengthParameter.Value = value; }
    121     }
    122     public IntValue MaxExpressionDepth {
    123       get { return MaxExpressionDepthParameter.Value; }
    124       set { MaxExpressionDepthParameter.Value = value; }
    125117    }
    126118    public IntValue MaxFunctionDefinitions {
     
    174166      : base(new GEEvaluator(), new UniformRandomIntegerVectorCreator()) {
    175167      BoolMatrix world = new BoolMatrix(santaFeAntTrail);
    176       Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionLength", "Maximal length of the expression to control the artificial ant.", new IntValue(100)));
    177       Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionDepth", "Maximal depth of the expression to control the artificial ant.", new IntValue(10)));
     168      Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionLength", "Maximal length of the expression to control the artificial ant.", new IntValue(30)));
    178169      Parameters.Add(new ValueParameter<IntValue>("MaximumFunctionDefinitions", "Maximal number of automatically defined functions in the expression to control the artificial ant.", new IntValue(3)));
    179170      Parameters.Add(new ValueParameter<IntValue>("MaximumFunctionArguments", "Maximal number of arguments of automatically defined functions in the expression to control the artificial ant.", new IntValue(3)));
     
    181172      Parameters.Add(new ValueParameter<BoolMatrix>("World", "The world for the artificial ant with scattered food items.", world));
    182173      Parameters.Add(new ValueParameter<IntValue>("MaximumTimeSteps", "The number of time steps the artificial ant has available to collect all food items.", new IntValue(600)));
    183       IntMatrix m = new IntMatrix(1,2);
    184       m[0,0] = 1;
    185       m[0,1] = 10;
    186       Parameters.Add(new ValueParameter<IntMatrix>("Bounds", "", m));
     174      IntMatrix m = new IntMatrix(new int[,]{{0,100}});
     175      Parameters.Add(new ValueParameter<IntMatrix>("Bounds", "The integer number range in which the single genomes of a genotype are created.", m));
    187176     
    188177      Maximization.Value = true;
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/GEEvaluator.cs

    r10012 r10022  
    3030using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3131using HeuristicLab.Encodings.IntegerVectorEncoding;
     32using System.Collections.Generic;
     33using System.Linq;
     34using HeuristicLab.Random;
    3235
    3336namespace HeuristicLab.Problems.GrammaticalEvolution {
     
    3740    ISingleObjectiveEvaluator, ISymbolicExpressionTreeGrammarBasedOperator {
    3841
     42    // TODO: replace these horrible global variables ...
     43    private static int genotypeIndex    = 0;
     44    private static int currSubtreeCount = 1;
     45   
    3946    #region Parameter Properties
    4047    public ILookupParameter<DoubleValue> QualityParameter {
     
    5663      get { return (IValueLookupParameter<ISymbolicExpressionGrammar>)Parameters["SymbolicExpressionTreeGrammar"]; }
    5764    }
    58   #endregion
    59    
     65    #endregion
     66 
    6067    [StorableConstructor]
    6168    protected GEEvaluator(bool deserializing) : base(deserializing) { }
     
    7380
    7481    public sealed override IOperation Apply() {
    75       SymbolicExpressionTree expression = ConvertIntegerVectorToSymbolicExpressionTree(SymbolicExpressionTreeGrammarParameter.ActualValue);
     82      SymbolicExpressionTree expression = MapIntegerVectorToSymbolicExpressionTree();
    7683      BoolMatrix world = WorldParameter.ActualValue;
    7784      IntValue maxTimeSteps = MaxTimeStepsParameter.ActualValue;
     
    8996   
    9097    /// <summary>
    91     /// Genotype-to-Phenotype mapper.
    92     /// </summary>
    93     /// <param name="grammar">grammar definition used to guide the mapping process</param>
     98    /// Genotype-to-Phenotype mapper (depth-first approach).
     99    /// </summary>
    94100    /// <returns>solution tree</returns>
    95     public SymbolicExpressionTree ConvertIntegerVectorToSymbolicExpressionTree(ISymbolicExpressionGrammar grammar) {
    96       SymbolicExpressionTree tree = new SymbolicExpressionTree();
    97       var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
    98       // if (rootNode.HasLocalParameters) rootNode.ResetLocalParameters(random);
    99       rootNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
     101    private SymbolicExpressionTree MapIntegerVectorToSymbolicExpressionTree() {
     102     
     103      ISymbolicExpressionGrammar grammar = SymbolicExpressionTreeGrammarParameter.ActualValue;
     104      SymbolicExpressionTree     tree    = new SymbolicExpressionTree();
     105      IntegerVector integerVectorGenome  = IntegerVectorParameter.ActualValue;
     106      var rootNode  = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
    100107      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
    101       startNode.SetGrammar(new SymbolicExpressionTreeGrammar(grammar));
    102       // if (startNode.HasLocalParameters) startNode.ResetLocalParameters(random);
    103108      rootNode.AddSubtree(startNode);
    104       // PTC2(random, startNode, maxTreeLength, maxTreeDepth);
    105109      tree.Root = rootNode;
    106       var moveNode = grammar.GetSymbol("Move").CreateTreeNode();
    107       startNode.AddSubtree(moveNode);
     110     
     111      genotypeIndex    = 0;
     112      currSubtreeCount = 1;
     113     
     114      MapGenoToPhenoDepthFirstRec(startNode, integerVectorGenome,
     115                                  grammar, integerVectorGenome.Length);
     116     
    108117      SymbolicExpressionTreeParameter.ActualValue = tree;
    109118      return tree;
    110119    }
     120   
     121   
     122    private void MapGenoToPhenoDepthFirstRec(ISymbolicExpressionTreeNode currentNode,
     123                                             IntegerVector integerVectorGenome,
     124                                             ISymbolicExpressionGrammar grammar,
     125                                             int maxSubtreeCount) {
     126      if (currSubtreeCount < maxSubtreeCount) {
     127     
     128        var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);
     129       
     130        if ((currSubtreeCount + newNode.Symbol.MaximumArity) > maxSubtreeCount) {
     131          // TODO: maybe check, if there is any node, which fits in the tree yet
     132          currentNode.AddSubtree(GetRandomTerminalNode(currentNode, grammar));
     133        } else {
     134          currentNode.AddSubtree(newNode);
     135          genotypeIndex++;
     136          currSubtreeCount += newNode.Symbol.MaximumArity;
     137       
     138          while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {
     139            MapGenoToPhenoDepthFirstRec(newNode, integerVectorGenome,
     140                                        grammar, maxSubtreeCount);
     141          }
     142        }
     143       
     144      } else {
     145        while (currentNode.Symbol.MaximumArity > currentNode.SubtreeCount) {
     146          var newNode = GetNewChildNode(currentNode, integerVectorGenome, grammar, genotypeIndex);
     147          currentNode.AddSubtree(newNode);
     148          genotypeIndex++;
     149          while (newNode.Symbol.MaximumArity > newNode.SubtreeCount) {
     150            newNode.AddSubtree(GetRandomTerminalNode(newNode, grammar));
     151          }
     152        }
     153      }
     154    }
     155   
     156   
     157    /// <summary>
     158    /// Randomly returns a terminal node for the given parentNode.
     159    /// (A terminal has got a minimum and maximum arity of 0.)
     160    /// </summary>
     161    /// <param name="parentNode">parent node for which a child node is returned randomly</param>
     162    /// <param name="grammar">grammar definition to determine the allowed child symbols for parentNode</param>
     163    /// <returns>randomly chosen terminal node with arity 0</returns>
     164    private ISymbolicExpressionTreeNode GetRandomTerminalNode(ISymbolicExpressionTreeNode parentNode,
     165                                                              ISymbolicExpressionGrammar  grammar) {
     166      var possibleSymbolsList = from   s in grammar.GetAllowedChildSymbols(parentNode.Symbol)
     167                                where  s.MaximumArity == 0
     168                                where  s.MinimumArity == 0
     169                                select s;
     170      // TODO: Check, if symbol list is empty (no terminal nodes found) - what should happen?
     171      return possibleSymbolsList.SelectRandom(new MersenneTwister()).CreateTreeNode();
     172    }
     173   
     174   
     175    /// <summary>
     176    /// Utility method, which returns the number of elements of the parameter symbolList.
     177    /// </summary>
     178    /// <param name="symbolList">enumerable symbol list to count the elements for</param>
     179    /// <returns>number of elements in parameter symbolList</returns>
     180    private int GetNumberOfAllowedChildSymbols(IEnumerable<ISymbol> symbolList) {
     181      int count = 0;
     182      using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {
     183        while (enumerator.MoveNext()) {
     184          count++;
     185        }
     186      }
     187      return count;
     188    }
     189   
     190   
     191    /// <summary>
     192    /// Returns a randomly chosen child node for the given parentNode.
     193    /// </summary>
     194    /// <param name="parentNode">parent node to find a child node randomly for</param>
     195    /// <param name="integerVectorGenome">integer vector to map to production rules</param>
     196    /// <param name="grammar">grammar definition used to define the allowed child symbols</param>
     197    /// <param name="genotypeIndex">index in the integer vector; can be greater than vector length</param>
     198    /// <returns></returns>
     199    private ISymbolicExpressionTreeNode GetNewChildNode(ISymbolicExpressionTreeNode parentNode,
     200                                                        IntegerVector integerVectorGenome,
     201                                                        ISymbolicExpressionGrammar grammar,
     202                                                        int genotypeIndex) {
     203     
     204      var symbolList    = grammar.GetAllowedChildSymbols(parentNode.Symbol);
     205      int prodRuleCount = GetNumberOfAllowedChildSymbols(symbolList);
     206      int prodRuleIndex = integerVectorGenome[genotypeIndex] % prodRuleCount;
     207      int currentIndex  = 0;
     208     
     209      using (IEnumerator<ISymbol> enumerator = symbolList.GetEnumerator()) {
     210        while (enumerator.MoveNext() && (currentIndex != prodRuleIndex)) {
     211          currentIndex++;
     212        }
     213        return enumerator.Current.CreateTreeNode();
     214      }
     215    }
    111216  }
    112217}
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution-3.3.csproj

    r10012 r10022  
    151151      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.ArtificialAnt-3.4.dll</HintPath>
    152152    </Reference>
     153    <Reference Include="HeuristicLab.Random-3.3">
     154      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     155    </Reference>
    153156    <Reference Include="System" />
    154157    <Reference Include="System.Core">
Note: See TracChangeset for help on using the changeset viewer.