Changeset 10290


Ignore:
Timestamp:
01/06/14 20:41:57 (6 years ago)
Author:
sawinkle
Message:

#2109:

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

Legend:

Unmodified
Added
Removed
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/ArtificialAnt/GEArtificialAntEvaluator.cs

    r10280 r10290  
    6666      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    6767    }
     68    public ILookupParameter<IntMatrix> BoundsParameter {
     69      get { return (ILookupParameter<IntMatrix>)Parameters["Bounds"]; }
     70    }
     71    public ILookupParameter<IntValue> MaxExpressionLengthParameter {
     72      get { return (ILookupParameter<IntValue>)Parameters["MaximumExpressionLength"]; }
     73    }
    6874    #endregion
    6975
     
    8288      Parameters.Add(new LookupParameter<IGenotypeToPhenotypeMapper>("GenotypeToPhenotypeMapper", "Maps the genotype (an integer vector) to the phenotype (a symbolic expression tree)."));
    8389      Parameters.Add(new LookupParameter<IRandom>("Random", "Random number generator for the genotype creation and the genotype-to-phenotype mapping."));
     90
     91      Parameters.Add(new LookupParameter<IntMatrix>("Bounds", "The integer number range in which the single genomes of a genotype are created."));
     92      Parameters.Add(new LookupParameter<IntValue>("MaximumExpressionLength", "Maximal length of the expression to control the artificial ant."));
    8493    }
    8594
     
    8796      SymbolicExpressionTree tree = GenotypeToPhenotypeMapperParameter.ActualValue.Map(
    8897        RandomParameter.ActualValue,
     98        BoundsParameter.ActualValue,
     99        MaxExpressionLengthParameter.ActualValue.Value,
    89100        SymbolicExpressionTreeGrammarParameter.ActualValue,
    90101        IntegerVectorParameter.ActualValue
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/BreathFirstMapper.cs

    r10280 r10290  
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
     26using HeuristicLab.Data;
    2627using HeuristicLab.Encodings.IntegerVectorEncoding;
    2728using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    5455    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
    5556    /// <returns>phenotype (a symbolic expression tree)</returns>
    56     public override SymbolicExpressionTree Map(IRandom random,
     57    public override SymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,
    5758                                               ISymbolicExpressionGrammar grammar,
    5859                                               IntegerVector genotype) {
     
    8788
    8889      int genotypeIndex = 0;
    89       int currSubtreeCount = 1;
    90 
    9190      queue.Enqueue(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1));
    9291
    93       while ((currSubtreeCount < maxSubtreeCount) && (queue.Count > 0)) {
     92      while (queue.Count > 0) {
    9493
    9594        Tuple<ISymbolicExpressionTreeNode, int> current = queue.Dequeue();
     
    9897        for (int i = 0; i < current.Item2; ++i) {
    9998
    100           var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
    101           int arity = SampleArity(random, newNode, maxSubtreeCount - currSubtreeCount, grammar);
    102 
    103           if (arity < 0) {
     99          if (genotypeIndex >= maxSubtreeCount) {
     100            // if all genomes were used, only add terminal nodes to the remaining subtrees
    104101            current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
    105102          } else {
     103            var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
     104            int arity = SampleArity(random, newNode, grammar);
     105
    106106            current.Item1.AddSubtree(newNode);
    107107            genotypeIndex++;
    108             currSubtreeCount += arity;
    109108            if (arity > 0) {
    110109              // new node has subtrees so enqueue the node
     
    114113        }
    115114      }
    116 
    117       // maximum allowed subtree count was already reached, but there are still
    118       // incomplete subtrees (non-terminal symbols) in the tree
    119       // -> fill them with terminal symbols
    120       while (queue.Count > 0) {
    121         Tuple<ISymbolicExpressionTreeNode, int> current = queue.Dequeue();
    122         for (int i = 0; i < current.Item2; ++i) {
    123           current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
    124         }
    125       }
    126115    }
    127116  }
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/DepthFirstMapper.cs

    r10280 r10290  
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
     26using HeuristicLab.Data;
    2627using HeuristicLab.Encodings.IntegerVectorEncoding;
    2728using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    5455    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
    5556    /// <returns>phenotype (a symbolic expression tree)</returns>
    56     public override SymbolicExpressionTree Map(IRandom random,
     57    public override SymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,
    5758                                               ISymbolicExpressionGrammar grammar,
    5859                                               IntegerVector genotype) {
     
    8990
    9091      int genotypeIndex = 0;
    91       int currSubtreeCount = 1;
    92 
    9392      stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(startNode, 1));
    9493
    95       while ((currSubtreeCount < maxSubtreeCount) && (stack.Count > 0)) {
     94      while (stack.Count > 0) {
    9695
    9796        // get next node from stack and re-push it, if this node still has unhandled subtrees ...
     
    101100        }
    102101
    103         var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
    104         int arity = SampleArity(random, newNode, maxSubtreeCount - currSubtreeCount, grammar);
    105 
    106         if (arity < 0) {
     102        if (genotypeIndex >= maxSubtreeCount) {
     103          // if all genomes were used, only add terminal nodes to the remaining subtrees
    107104          current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
    108105        } else {
     106          var newNode = GetNewChildNode(current.Item1, genotype, grammar, genotypeIndex, random);
     107          int arity = SampleArity(random, newNode, grammar);
     108
    109109          current.Item1.AddSubtree(newNode);
    110110          genotypeIndex++;
    111           currSubtreeCount += arity;
    112111          if (arity > 0) {
    113112            // new node has subtrees so push it onto the stack
     
    116115        }
    117116      }
    118 
    119       // maximum allowed subtree count was already reached, but there are still
    120       // incomplete subtrees (non-terminal symbols) in the tree
    121       // -> fill them with terminal symbols
    122       while (stack.Count > 0) {
    123         Tuple<ISymbolicExpressionTreeNode, int> current = stack.Pop();
    124         if (current.Item2 > 1) {
    125           stack.Push(new Tuple<ISymbolicExpressionTreeNode, int>(current.Item1, current.Item2 - 1));
    126         }
    127         current.Item1.AddSubtree(GetRandomTerminalNode(current.Item1, grammar, random));
    128       }
    129117    }
    130118  }
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/GenotypeToPhenotypeMapper.cs

    r10280 r10290  
    2424using HeuristicLab.Common;
    2525using HeuristicLab.Core;
     26using HeuristicLab.Data;
    2627using HeuristicLab.Encodings.IntegerVectorEncoding;
    2728using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    4041    protected GenotypeToPhenotypeMapper() : base() { }
    4142
    42     public abstract SymbolicExpressionTree Map(IRandom random,
     43    public abstract SymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,
    4344                                               ISymbolicExpressionGrammar grammar,
    4445                                               IntegerVector genotype);
     
    9697      if (prodRuleCount < 1) return null;
    9798
    98       int prodRuleIndex = genotype[genotypeIndex % genotype.Length] % prodRuleCount;
     99      // genotypeIndex % genotype.Length
     100      int prodRuleIndex = genotype[genotypeIndex] % prodRuleCount;
    99101
    100102      var newNode = symbolList.ElementAt(prodRuleIndex).CreateTreeNode();
     
    109111    /// <param name="random">random number generator</param>
    110112    /// <param name="node">node, for which a random arity is determined</param>
    111     /// <param name="maxAllowedArity">the resulting arity must not exceed this maximum arity</param>
    112113    /// <param name="grammar">symbolic expression grammar to use</param>
    113     /// <returns>random arity in the interval [minArity, maxArity] of the node or
    114     ///          -1, if minArity exceeds maxAllowedArity</returns>
     114    /// <returns>random arity in the interval [minArity, maxArity]</returns>
    115115    protected int SampleArity(IRandom random,
    116116                              ISymbolicExpressionTreeNode node,
    117                               int maxAllowedArity,
    118117                              ISymbolicExpressionGrammar grammar) {
    119118
    120119      int minArity = grammar.GetMinimumSubtreeCount(node.Symbol);
    121120      int maxArity = grammar.GetMaximumSubtreeCount(node.Symbol);
    122 
    123       if (maxAllowedArity < maxArity) {
    124         maxArity = maxAllowedArity;
    125       }
    126 
    127       if (maxAllowedArity < minArity) {
    128         return -1;
    129       }
    130121
    131122      if (minArity == maxArity) {
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/IGenotypeToPhenotypeMapper.cs

    r10280 r10290  
    2121
    2222using HeuristicLab.Core;
     23using HeuristicLab.Data;
    2324using HeuristicLab.Encodings.IntegerVectorEncoding;
    2425using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    2930  /// </summary>
    3031  public interface IGenotypeToPhenotypeMapper : IIntegerVectorOperator {
    31     SymbolicExpressionTree Map(IRandom random,
     32    SymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,
    3233                               ISymbolicExpressionGrammar grammar,
    3334                               IntegerVector genotype);
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/PIGEMapper.cs

    r10280 r10290  
    2020#endregion
    2121
     22using System.Collections.Generic;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
     25using HeuristicLab.Data;
    2426using HeuristicLab.Encodings.IntegerVectorEncoding;
    2527using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    2729
    2830namespace HeuristicLab.Problems.GrammaticalEvolution {
     31
    2932  /// <summary>
    3033  /// Position Independent (PI) Grammatical Evolution Mapper
     34  /// -----------------------------------------------------------------------------------
     35  /// Standard GE mappers:
     36  ///   Rule = Codon Value % Number Of Rules
     37  ///   
     38  /// 𝜋GE:
     39  ///   𝜋GE codons consist of (nont, rule) tuples, where nont may be one value from an "order"
     40  ///   integer vector and rule may be one value from a "content" integer vector.
     41  ///   
     42  ///   Order:   NT   = nont % Num. NT      ... determines, which non-terminal to expand next
     43  ///   Content: Rule = rule % Num. Rules   ... rule determination as with standard GE mappers
     44  ///
     45  /// Four mutation and crossover strategies possible:
     46  ///  * Order-only:    only "order" vector is modified, "content" vector is fixed (1:0),
     47  ///                   worst result according to [2]
     48  ///  * Content-only:  only "content" vector is modified, "order" vector is fixed (0:1),
     49  ///                   best result according to [2]
     50  ///  * 𝜋GE:           genetic operators are applied equally (1:1),
     51  ///  * Content:Order: genetic operators are applied unequally (e.g. 2:1 or 1:2),
     52  ///
     53  /// Here, the "content-only" strategy is implemented, as it is the best solution according to [2]
     54  /// and it does not require much to change in the problem and evaluator classes.
     55  ///
    3156  /// </summary>
    32   [Item("PIGEMapper", "")]
     57  /// <remarks>
     58  /// Described in
     59  ///
     60  /// [1] Michael O’Neill et al. 𝜋Grammatical Evolution. In: GECCO 2004.
     61  /// Vol. 3103. LNCS. Heidelberg: Springer-Verlag Berlin, 2004, pp. 617–629.
     62  /// url: http://dynamics.org/Altenberg/UH_ICS/EC_REFS/GP_REFS/GECCO/2004/31030617.pdf.
     63  ///
     64  /// [2] David Fagan et al. Investigating Mapping Order in πGE. IEEE, 2010
     65  /// url: http://ncra.ucd.ie/papers/pigeWCCI2010.pdf
     66  /// </remarks>
     67  [Item("PIGEMapper", "Position Independent (PI) Grammatical Evolution Mapper")]
    3368  [StorableClass]
    3469  public class PIGEMapper : GenotypeToPhenotypeMapper {
     70
     71    private IntegerVector nontVector;
     72
     73    public IntegerVector NontVector {
     74      get { return nontVector; }
     75      set { nontVector = value; }
     76    }
     77
     78    private IntegerVector GetNontVector(IRandom random, IntMatrix bounds, int length) {
     79      IntegerVector v = new IntegerVector(length);
     80      v.Randomize(random, bounds);
     81      return v;
     82    }
    3583
    3684    [StorableConstructor]
     
    52100    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
    53101    /// <returns>phenotype (a symbolic expression tree)</returns>
    54     public override SymbolicExpressionTree Map(IRandom random,
     102    public override SymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,
    55103                                               ISymbolicExpressionGrammar grammar,
    56104                                               IntegerVector genotype) {
     
    62110      tree.Root = rootNode;
    63111
    64       // TODO
     112      if (NontVector == null) {
     113        NontVector = GetNontVector(random, bounds, length);
     114      }
     115
     116      MapPIGEIteratively(startNode, genotype, grammar,
     117                         genotype.Length, random);
    65118
    66119      return tree;
    67120    }
     121
     122
     123    private void MapPIGEIteratively(ISymbolicExpressionTreeNode startNode,
     124                                    IntegerVector genotype,
     125                                    ISymbolicExpressionGrammar grammar,
     126                                    int maxSubtreeCount, IRandom random) {
     127
     128      List<ISymbolicExpressionTreeNode> nonTerminals = new List<ISymbolicExpressionTreeNode>();
     129
     130      int genotypeIndex = 0;
     131      nonTerminals.Add(startNode);
     132
     133      while (nonTerminals.Count > 0) {
     134
     135        if (genotypeIndex >= maxSubtreeCount) {
     136          // if all genomes were used, only add terminal nodes to the remaining subtrees
     137          ISymbolicExpressionTreeNode current = nonTerminals[0];
     138          nonTerminals.RemoveAt(0);
     139          current.AddSubtree(GetRandomTerminalNode(current, grammar, random));
     140        } else {
     141          // Order:   NT   = nont % Num. NT
     142          int nt = NontVector[genotypeIndex] % nonTerminals.Count;
     143          ISymbolicExpressionTreeNode current = nonTerminals[nt];
     144          nonTerminals.RemoveAt(nt);
     145
     146          // Content: Rule = rule % Num. Rules
     147          ISymbolicExpressionTreeNode newNode = GetNewChildNode(current, genotype, grammar, genotypeIndex, random);
     148          int arity = SampleArity(random, newNode, grammar);
     149
     150          current.AddSubtree(newNode);
     151          genotypeIndex++;
     152          // new node has subtrees, so add "arity" number of copies of this node to the nonTerminals list
     153          for (int i = 0; i < arity; ++i) {
     154            nonTerminals.Add(newNode);
     155          }
     156        }
     157      }
     158    }
    68159  }
    69160}
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Mappers/RandomMapper.cs

    r10280 r10290  
    2222using HeuristicLab.Common;
    2323using HeuristicLab.Core;
     24using HeuristicLab.Data;
    2425using HeuristicLab.Encodings.IntegerVectorEncoding;
    2526using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    5253    /// <param name="genotype">integer vector, which should be mapped to a tree</param>
    5354    /// <returns>phenotype (a symbolic expression tree)</returns>
    54     public override SymbolicExpressionTree Map(IRandom random,
     55    public override SymbolicExpressionTree Map(IRandom random, IntMatrix bounds, int length,
    5556                                               ISymbolicExpressionGrammar grammar,
    5657                                               IntegerVector genotype) {
  • branches/GrammaticalEvolution/HeuristicLab.Problems.GrammaticalEvolution/Symbolic/GESymbolicRegressionSingleObjectiveEvaluator.cs

    r10280 r10290  
    2222using HeuristicLab.Common;
    2323using HeuristicLab.Core;
     24using HeuristicLab.Data;
    2425using HeuristicLab.Parameters;
    2526using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     
    3435    public const string EvaluatorParameterName = "Evaluator";
    3536    public const string RandomParameterName = "Random";
     37    public const string BoundsParameterName = "Bounds";
     38    public const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
    3639
    3740    public IValueParameter<ISymbolicRegressionSingleObjectiveEvaluator> EvaluatorParameter {
     
    4043    public ILookupParameter<IRandom> RandomParameter {
    4144      get { return (ILookupParameter<IRandom>)Parameters[RandomParameterName]; }
     45    }
     46    public ILookupParameter<IntMatrix> BoundsParameter {
     47      get { return (ILookupParameter<IntMatrix>)Parameters[BoundsParameterName]; }
     48    }
     49    public ILookupParameter<IntValue> MaximumSymbolicExpressionTreeLengthParameter {
     50      get { return (ILookupParameter<IntValue>)Parameters[MaximumSymbolicExpressionTreeLengthParameterName]; }
    4251    }
    4352
     
    5362      : base() {
    5463      Parameters.Add(new ValueParameter<ISymbolicRegressionSingleObjectiveEvaluator>(EvaluatorParameterName, "The symbolic regression evaluator that should be used to assess the quality of trees.", new SymbolicRegressionSingleObjectivePearsonRSquaredEvaluator()));
     64      Parameters.Add(new LookupParameter<IntMatrix>(BoundsParameterName, "The integer number range in which the single genomes of a genotype are created."));
     65      Parameters.Add(new LookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "Genotype length."));
    5566    }
    5667
     
    6980      var tree = GenotypeToPhenotypeMapperParameter.ActualValue.Map(
    7081        RandomParameter.ActualValue,
     82        BoundsParameter.ActualValue,
     83        MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value,
    7184        SymbolicExpressionTreeGrammarParameter.ActualValue,
    7285        genotype
Note: See TracChangeset for help on using the changeset viewer.