Free cookie consent management tool by TermsFeed Policy Generator

Changeset 10086


Ignore:
Timestamp:
10/27/13 20:17:17 (11 years ago)
Author:
gkronber
Message:

#2026 worked on random search solver (now all examples are working)

Location:
branches/HeuristicLab.Problems.GPDL
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

    r10080 r10086  
    8181            nextAlternative = (nextAlternative + 1) % subTrees.Length;
    8282          } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
    83 
    84           // from the nodes which are not done take the first with minimum count
    85           //nextAlternative = (from i in Enumerable.Range(0, subTrees.Length)
    86           //                   where subTrees[i] == null || !subTrees[i].Done
    87           //                   orderby subTrees[i]==null?0:subTrees[i].Count ascending
    88           //                   select i).FirstOrDefault(); // possibly there are no children left that can be tried
    8983        } else {
    9084          // for sequenceNodes update all sub-trees
    … …  
    177171
    178172    private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
     173
     174      var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
     175      var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
    179176      string startSymbolName = ast.Rules.First().NtSymbol;
    180       var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
     177
    181178      // create startSymbol
    182       var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
     179      var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
     180      var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
     181
     182      // add all production rules
    183183      foreach (var rule in ast.Rules) {
    184         // create nt-symbol
    185         var ntSymbolName = rule.NtSymbol;
    186         var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
    187         var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
    188         var ntSymbol = new Symbol(ntSymbolName, attributes);
    189         foreach (var alt in GetAlternatives(rule.Alternatives)) {
     184        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
     185        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
    190186          g.AddProductionRule(ntSymbol, alt);
    191187        }
    … …  
    196192    }
    197193
    198     private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
     194    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
    199195      return (from fieldDef in Util.ExtractParameters(formalParameters)
    200196              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
    … …  
    202198    }
    203199
    204     private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
     200    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
    205201      foreach (var alt in altNode.Alternatives) {
    206         yield return GetSequence(alt.Sequence);
    207       }
    208     }
    209 
    210     private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
     202        yield return GetSequence(alt.Sequence, allSymbols);
     203      }
     204    }
     205
     206    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
    211207      Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
    212208      var l = new List<ISymbol>();
    … …  
    215211        var actionNode = node as RuleActionNode;
    216212        if (callSymbolNode != null) {
    217           l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
     213          Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
     214          // create a new symbol with actual parameters
     215          l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
    218216        } else if (actionNode != null) {
    219217          l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
    … …  
    313311
    314312      // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
    315       var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
     313      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s)
     314        .OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
    316315
    317316      if (altsWithSemActions.Length > 1) {

  • branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

    r10080 r10086  
    2020namespace ?PROBLEMNAME? {
    2121  public sealed class ?IDENT?Solver {
     22    public sealed class SolverState {
     23      private int currentSeed;
     24      public Random random;
     25      public int depth;
     26      public int steps;
     27      public int maxDepth;
     28      public SolverState(int seed) {
     29        this.currentSeed = seed;
     30      }
     31
     32      public SolverState IncDepth() {
     33        depth++;
     34        if(depth>maxDepth) maxDepth = depth;
     35        return this;
     36      }
     37      public SolverState Prepare() {
     38        this.random = new Random(currentSeed);
     39        depth = 0;
     40        maxDepth = 0;
     41        steps = 0;
     42        return this;
     43      }
     44    }
    2245
    2346    public static void Main(string[] args) {
    … …  
    3861    }
    3962
    40 
    41     private Random seedRandom;
    42     private int currentSeed;
     63    private double TerminalProbForDepth(int depth) {
     64      const double baseProb = 0.05;  // 5% of all samples are only a terminal node
     65      const double probIncPerLevel = 0.05; // for each level the probability to sample a terminal grows by 5%
     66      return baseProb + depth * probIncPerLevel;
     67    }
     68
     69    private SolverState _state;
    4370    private void Start() {
    44       seedRandom = new Random();
     71      var seedRandom = new Random();
    4572      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
    4673      int n = 0;
    … …  
    5178        // must make sure that calling the start-symbol multiple times in the fitness function always leads to the same path through the grammar
    5279        // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called
    53         currentSeed = seedRandom.Next();
     80       
     81        _state = new SolverState(seedRandom.Next());
     82
    5483        var f = Calculate();
    5584
    5685        n++;
    57         if (IsBetter(f, bestF)) bestF = f;
    58         if (n % 100 == 0) {
     86        if (IsBetter(f, bestF)) {
     87          bestF = f;
     88          Console.WriteLine(""{0}\t{1}\t(depth={2})"", n, bestF, _state.maxDepth);
     89        }
     90        if (n % 1000 == 0) {
    5991          sw.Stop();
    60           Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
     92          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 1000.0 / sw.ElapsedMilliseconds);
    6193          sw.Reset();
    6294          sw.Start();
    … …  
    112144    }
    113145
     146    #region create grammar instance from AST
    114147    private AttributedGrammar CreateGrammarFromAst(GPDefNode ast) {
     148
     149      var nonTerminals = ast.NonTerminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
     150      var terminals = ast.Terminals.Select(t => new Symbol(t.Ident, GetSymbolAttributes(t.FormalParameters))).ToArray();
    115151      string startSymbolName = ast.Rules.First().NtSymbol;
    116       var startSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == startSymbolName);
     152
    117153      // create startSymbol
    118       var g = new AttributedGrammar(new Symbol(startSymbolName, ParseSymbolAttributes(startSymbolNode.FormalParameters)));
     154      var startSymbol = nonTerminals.Single(s => s.Name == startSymbolName);
     155      var g = new AttributedGrammar(startSymbol, nonTerminals, terminals);
     156
     157      // add all production rules
    119158      foreach (var rule in ast.Rules) {
    120         // create nt-symbol
    121         var ntSymbolName = rule.NtSymbol;
    122         var ntSymbolNode = ast.NonTerminals.Single(nt => nt.Ident == ntSymbolName);
    123         var attributes = ParseSymbolAttributes(ntSymbolNode.FormalParameters);
    124         var ntSymbol = new Symbol(ntSymbolName, attributes);
    125         foreach (var alt in GetAlternatives(rule.Alternatives)) {
     159        var ntSymbol = nonTerminals.Single(s => s.Name == rule.NtSymbol);
     160        foreach (var alt in GetAlternatives(rule.Alternatives, nonTerminals.Concat(terminals))) {
    126161          g.AddProductionRule(ntSymbol, alt);
    127162        }
    … …  
    132167    }
    133168
    134     private IEnumerable<IAttribute> ParseSymbolAttributes(string formalParameters) {
     169    private IEnumerable<IAttribute> GetSymbolAttributes(string formalParameters) {
    135170      return (from fieldDef in Util.ExtractParameters(formalParameters)
    136171              select new Attribute(fieldDef.Identifier, fieldDef.Type, AttributeType.Parse(fieldDef.RefOrOut))).
    … …  
    138173    }
    139174
    140     private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode) {
     175    private IEnumerable<Sequence> GetAlternatives(AlternativesNode altNode, IEnumerable<ISymbol> allSymbols) {
    141176      foreach (var alt in altNode.Alternatives) {
    142         yield return GetSequence(alt.Sequence);
    143       }
    144     }
    145 
    146     private Sequence GetSequence(IEnumerable<RuleExprNode> sequence) {
     177        yield return GetSequence(alt.Sequence, allSymbols);
     178      }
     179    }
     180
     181    private Sequence GetSequence(IEnumerable<RuleExprNode> sequence, IEnumerable<ISymbol> allSymbols) {
    147182      Debug.Assert(sequence.All(s => s is CallSymbolNode || s is RuleActionNode));
    148183      var l = new List<ISymbol>();
    … …  
    151186        var actionNode = node as RuleActionNode;
    152187        if (callSymbolNode != null) {
    153           l.Add(new Symbol(callSymbolNode.Ident, ParseSymbolAttributes(callSymbolNode.ActualParameter)));
     188          Debug.Assert(allSymbols.Any(s => s.Name == callSymbolNode.Ident));
     189          // create a new symbol with actual parameters
     190          l.Add(new Symbol(callSymbolNode.Ident, GetSymbolAttributes(callSymbolNode.ActualParameter)));
    154191        } else if (actionNode != null) {
    155192          l.Add(new SemanticSymbol("SEM", actionNode.SrcCode));
    … …  
    158195      return new Sequence(l);
    159196    }
    160 
     197    #endregion
     198
     199    #region helper methods for terminal symbols
    161200    // produces helper methods for the attributes of all terminal nodes
    162201    private string GenerateConstraintMethods(List<SymbolNode> symbols) {
    … …  
    177216          sb.AppendFormat("public {0} GetMax{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMaxExpression).AppendLine();
    178217          sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
     218          sb.AppendFormat("public {0} GetRandom{1}_{2}(SolverState _state) {{ return _state.random.NextDouble() * (GetMax{1}_{2}() - GetMin{1}_{2}()) + GetMin{1}_{2}(); }}", fieldType, t.Ident, c.Ident).AppendLine();
    179219        } else if (c.Type == ConstraintNodeType.Set) {
    180           sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3} }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
    181         }
    182       }
    183       return sb.ToString();
    184     }
     220          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
     221          sb.AppendFormat("public {0} GetRandom{1}_{2}(SolverState _state) {{ var tmp = GetAllowed{1}_{2}().ToArray(); return tmp[_state.random.Next(tmp.Length)]; }}", fieldType, t.Ident, c.Ident).AppendLine();
     222        }
     223      }
     224      return sb.ToString();
     225    }
     226    #endregion
    185227
    186228    private string GenerateInterpreterSource(AttributedGrammar grammar) {
    … …  
    197239    }
    198240
    199     private string GenerateTerminalInterpreterMethod(ISymbol s) {
    200       var sb = new StringBuilder();
    201       // if the terminal symbol has attributes then we must create values for these attributes
    202       if (!s.Attributes.Any())
    203         sb.AppendFormat("private void {0}(Random random) {{", s.Name);
    204       else
    205         sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
    206 
    207       // each field must match a formal parameter, assign a value for each parameter
    208       foreach (var element in s.Attributes) {
    209         // only works for "IN SET"-Constraints
    210         sb.AppendFormat("{{ var tmp = GetAllowed{1}_{0}().ToArray(); {0} = tmp[random.Next(tmp.Length)]; }} ", element.Name, s.Name);
    211       }
    212       sb.AppendLine("}");
    213       return sb.ToString();
    214     }
    215 
    216241    private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
    217242      var sb = new StringBuilder();
     243
    218244      // if this is the start symbol we additionally have to create the method which can be called from the fitness function
    219 
    220245      if (g.StartSymbol.Equals(s)) {
    221246        if (!s.Attributes.Any())
    … …  
    234259          actualParameter = string.Empty;
    235260
    236         sb.AppendFormat("{0}(new Random(currentSeed), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
     261        sb.AppendFormat("{0}(_state.Prepare(), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
    237262        sb.AppendLine("}");
    238263      }
    239264
    240265      if (!s.Attributes.Any())
    241         sb.AppendFormat("private void {0}(Random random) {{", s.Name);
     266        sb.AppendFormat("private void {0}(SolverState _state) {{", s.Name);
    242267      else
    243         sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
     268        sb.AppendFormat("private void {0}(SolverState _state, {1}) {{", s.Name, s.GetAttributeString());
    244269
    245270      // generate local definitions
    … …  
    250275      var terminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) == 0);
    251276      var nonTerminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) > 0);
    252       bool hasTerminalAlts = terminalAlts.Count() > 0;
    253       bool hasNonTerminalAlts = nonTerminalAlts.Count() > 0;
     277      bool hasTerminalAlts = terminalAlts.Any();
     278      bool hasNonTerminalAlts = nonTerminalAlts.Any();
    254279
    255280      if (altsWithSemActions.Length > 1) {
    … …  
    261286        // the probability of choosing terminals should depend on the depth of the tree (small likelihood to choose terminals for small depths, large likelihood for large depths)
    262287        if (hasTerminalAlts && hasNonTerminalAlts) {
    263           sb.AppendLine("if(random.NextDouble() < 0.5) {");
     288          sb.AppendLine("if(_state.random.NextDouble() < TerminalProbForDepth(_state.depth)) {");
    264289          // terminals
    265290          sb.AppendLine("// terminals ");
    … …  
    287312
    288313    private void GenerateSwitchStatement(StringBuilder sb, IEnumerable<Sequence> alts) {
    289       sb.AppendFormat("switch(random.Next({0})) {{", alts.Count());
     314      sb.AppendFormat("switch(_state.random.Next({0})) {{", alts.Count());
    290315      // generate a case for each alternative
    291316      int i = 0;
    … …  
    313338      } else {
    314339        if (!s.Attributes.Any())
    315           return string.Format("{0}(random);", s.Name);
     340          return string.Format("{0}(_state.IncDepth()); _state.depth--;", s.Name);
    316341        else
    317           return string.Format("{0}(random, {1});", s.Name, s.GetAttributeString());
    318       }
     342          return string.Format("{0}(_state.IncDepth(), {1}); _state.depth--;", s.Name, s.GetAttributeString());
     343      }
     344    }
     345
     346    private string GenerateTerminalInterpreterMethod(ISymbol s) {
     347      var sb = new StringBuilder();
     348      // if the terminal symbol has attributes then we must samples values for these attributes
     349      if (!s.Attributes.Any())
     350        sb.AppendFormat("private void {0}(SolverState _state) {{", s.Name);
     351      else
     352        sb.AppendFormat("private void {0}(SolverState _state, {1}) {{", s.Name, s.GetAttributeString());
     353
     354      // each field must match a formal parameter, assign a value for each parameter
     355      foreach (var element in s.Attributes) {
     356        sb.AppendFormat("{{ {0} = GetRandom{1}_{0}(_state); }} ", element.Name, s.Name);
     357      }
     358      sb.AppendLine("}");
     359      return sb.ToString();
    319360    }
    320361  }

  • branches/HeuristicLab.Problems.GPDL/Examples/symbreg HEAL.txt

    r10061 r10086  
    55  double[] y;
    66  string[] variableNames;
     7  int[] rows;
    78  Dictionary<string,int> nameToCol;
    89 
    … …  
    1920
    2021  double RSquared(IEnumerable<double> xs, IEnumerable<double> ys) {
    21      HeuristicLab.Problems.DataAnalysis.OnlineCalculatorError error;
    22      var r2 = HeuristicLab.Problems.DataAnalysis.OnlinePearsonsRSquaredCalculator.Calculate(xs, ys, out error);
    23      if(error == HeuristicLab.Problems.DataAnalysis.OnlineCalculatorError.None) return r2;
    24      else return 0.0;
    25   }
     22    // calculate Pearson's correlation in one pass over xs and ys
     23    double sumx = 0.0;
     24    double sumy = 0.0;
     25    double sumxSq = 0.0;
     26    double sumySq = 0.0;
     27    double sumxy = 0.0;
     28    int n = 0;
     29    var xEnum = xs.GetEnumerator();
     30    var yEnum = ys.GetEnumerator();
     31    while(xEnum.MoveNext() & yEnum.MoveNext()) {
     32      sumx += xEnum.Current;
     33      sumy += yEnum.Current;
     34      sumxSq += xEnum.Current * xEnum.Current;
     35      sumySq += yEnum.Current * yEnum.Current;
     36      sumxy += xEnum.Current * yEnum.Current;
     37      n++;
     38    }
     39    System.Diagnostics.Debug.Assert(!(xEnum.MoveNext() | yEnum.MoveNext()));
     40
     41    double num;
     42    double den;
     43    double r = 0.0;
     44    num = sumxy - ( ( sumx * sumy ) / n );
     45    den = Math.Sqrt( ( sumxSq - ( sumx*sumx ) / n ) *
     46                     ( sumySq - ( sumy*sumy ) / n ) );
     47    if(den > 0){
     48      r = num / den;
     49    }
     50    return r*r;
     51  }
    2652>>
    2753
    … …  
    3359  x = new double[n, 10];
    3460  y = new double[n];
    35   for(int row = 0; row < 500; row++) {
     61  for(int row = 0; row < n; row++) {
    3662    for(int col = 0; col < 10; col++) {
    3763      x[row, col] = rand.NextDouble() * 2.0 - 1.0;
    … …  
    4369             x[row, 2] * x[row, 5] + x[row, 9];
    4470  }
     71
     72  rows = System.Linq.Enumerable.Range(0, n).ToArray();
    4573>>
    4674
    … …  
    90118  .
    91119
    92 MAXIMIZE                                                   /* could also use the keyword MINIMIZE here */
     120MAXIMIZE
    93121  <<
    94     var rows = System.Linq.Enumerable.Range(0, x.GetLength(0));
    95122    var predicted = rows.Select(r => {
    96123      double result;

  • branches/HeuristicLab.Problems.GPDL/Examples/symbreg Koza.txt

    r10061 r10086  
    33  double[,] x;
    44  double[] y;
     5  int[] rows;
    56  string[] variableNames;
     7  double[] randomConsts;
     8 
    69  Dictionary<string,int> nameToCol;
    710 
    … …  
    1821
    1922  double RSquared(IEnumerable<double> xs, IEnumerable<double> ys) {
    20      HeuristicLab.Problems.DataAnalysis.OnlineCalculatorError error;
    21      var r2 = HeuristicLab.Problems.DataAnalysis.OnlinePearsonsRSquaredCalculator.Calculate(xs, ys, out error);
    22      if(error == HeuristicLab.Problems.DataAnalysis.OnlineCalculatorError.None) return r2;
    23      else return 0.0;
    24   }
     23    // calculate Pearson's correlation in one pass over xs and ys
     24    double sumx = 0.0;
     25    double sumy = 0.0;
     26    double sumxSq = 0.0;
     27    double sumySq = 0.0;
     28    double sumxy = 0.0;
     29    int n = 0;
     30    var xEnum = xs.GetEnumerator();
     31    var yEnum = ys.GetEnumerator();
     32    while(xEnum.MoveNext() & yEnum.MoveNext()) {
     33      sumx += xEnum.Current;
     34      sumy += yEnum.Current;
     35      sumxSq += xEnum.Current * xEnum.Current;
     36      sumySq += yEnum.Current * yEnum.Current;
     37      sumxy += xEnum.Current * yEnum.Current;
     38      n++;
     39    }
     40    System.Diagnostics.Debug.Assert(!(xEnum.MoveNext() | yEnum.MoveNext()));
     41
     42    double num;
     43    double den;
     44    double r = 0.0;
     45    num = sumxy - ( ( sumx * sumy ) / n );
     46    den = Math.Sqrt( ( sumxSq - ( sumx*sumx ) / n ) *
     47                     ( sumySq - ( sumy*sumy ) / n ) );
     48    if(den > 0){
     49      r = num / den;
     50    }
     51    return r*r;
     52  }
    2553>>
    2654
    … …  
    3260  x = new double[n, 10];
    3361  y = new double[n];
    34   for(int row = 0; row < 500; row++) {
     62  for(int row = 0; row < n; row++) {
    3563    for(int col = 0; col < 10; col++) {
    3664      x[row, col] = rand.NextDouble() * 2.0 - 1.0;
    … …  
    4270             x[row, 2] * x[row, 5] + x[row, 9];
    4371  }
     72 
     73  rows = System.Linq.Enumerable.Range(0, n).ToArray();
     74 
     75  // generate 100 random constants in [-100.0 .. 100.0[
     76  randomConsts = Enumerable.Range(0, 100).Select(i => rand.NextDouble()*200.0 - 100.0).ToArray();
    4477>>
    4578
    … …  
    5588  ERC<<out double val>>
    5689    CONSTRAINTS
    57     val IN RANGE <<-100>> .. <<100>>
     90      val IN SET << randomConsts >>
    5891  .
    5992
    6093  Var<<out string varName>>
    6194    CONSTRAINTS
    62     varName IN SET <<variableNames>>
     95      varName IN SET << variableNames >>
    6396  .
    6497
    … …  
    73106    | Multiplication<<row, out val>>
    74107    | Var<<out varName>>                                   SEM << val = GetValue(x, varName, row); >>
    75     | ERC<<out val>>
     108    /* | ERC<<out val>> */
    76109  .
    77110
    … …  
    89122  .
    90123
    91 MAXIMIZE                                                   /* could also use the keyword MINIMIZE here */
     124MAXIMIZE
    92125  <<
    93     var rows = System.Linq.Enumerable.Range(0, x.GetLength(0));
    94126    var predicted = rows.Select(r => {
    95127      double result;

  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/AttributedGrammar.cs

    r10067 r10086  
    2727namespace HeuristicLab.Grammars {
    2828  public class AttributedGrammar : Grammar {
    29     private Dictionary<ISymbol, string> localDefinitions = new Dictionary<ISymbol, string>();
    30     private Dictionary<ISymbol, IList<Sequence>> alternatives = new Dictionary<ISymbol, IList<Sequence>>();
     29    private readonly Dictionary<ISymbol, string> localDefinitions;
     30    private readonly Dictionary<ISymbol, List<Sequence>> alternatives;
    3131
    32     public AttributedGrammar(ISymbol startSymbol)
    33       : base(startSymbol) {
    34       Debug.Assert(!startSymbol.Equals(EmptySymbol));
     32    public AttributedGrammar(ISymbol startSymbol, IEnumerable<ISymbol> nonTerminals, IEnumerable<ISymbol> terminals)
     33      : base(startSymbol, nonTerminals, terminals) {
    3534      this.StartSymbol = startSymbol;
     35      localDefinitions = nonTerminals.ToDictionary(nt => nt, nt => string.Empty);
     36      alternatives = nonTerminals.ToDictionary(nt => nt, nt => new List<Sequence>());
    3637    }
    3738
    3839    public IEnumerable<Sequence> GetAlternativesWithSemanticActions(ISymbol ntSymbol) {
    39       Debug.Assert(!ntSymbol.Equals(EmptySymbol));
    4040      return alternatives[ntSymbol];
    4141    }
    4242    public Sequence GetAlternativeWithSemanticActions(ISymbol ntSymbol, int index) {
    43       Debug.Assert(!ntSymbol.Equals(EmptySymbol));
    4443      return alternatives[ntSymbol][index];
    4544    }
    … …  
    4847      base.AddProductionRule(ntSymbol, new Sequence(production.Where(symb => !(symb is SemanticSymbol)).ToList()));
    4948
    50       IList<Sequence> list;
    51       if (!alternatives.TryGetValue(ntSymbol, out list)) {
    52         list = new List<Sequence>();
    53         alternatives.Add(ntSymbol, list);
    54       }
     49      IList<Sequence> list = alternatives[ntSymbol];
     50
    5551      // make sure that there is not equivalent production registered already
    5652      Debug.Assert(!list.Any(s => s.SequenceEqual(production)));
    … …  
    6157    public void AddLocalDefinitions(ISymbol ntSymbol, string localDefCode) {
    6258      Debug.Assert(!ntSymbol.Equals(EmptySymbol));
    63       Debug.Assert(!localDefinitions.ContainsKey(ntSymbol));
    6459
    65       localDefinitions.Add(ntSymbol, localDefCode);
     60      localDefinitions[ntSymbol] = localDefCode;
    6661    }
    6762    public string GetLocalDefinitions(ISymbol ntSymbol) {
    68       string code;
    69       if (localDefinitions.TryGetValue(ntSymbol, out code)) return code;
    70       else return string.Empty;
     63      return localDefinitions[ntSymbol];
    7164    }
    72 
    73 
    74 
    75     //private static Regex ruleExpr = new Regex(@"\s*(?<ntSymbol>\w+)\s*(?<formPar>\<\w+\>)+\s*->\s*(?<alternative>\w+\s*(?<actPar>\<\w+\>)+(?:\s+\w+\s*(?<actPar>\<\w+\>)+)*)(?:\s*\|\s*(?<alternative>\w+\s*(?<formPar>\<\w+\>)+(?:\s+\w+\s*(?<formPar>\<\w+\>)+)*))*");
    76     //private static Regex empty = new Regex(@"^\s*$");
    77     //public static Grammar FromString(string gStr) {
    78     //  var lines = gStr.Split(new string[] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
    79     //  lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
    80 
    81     //  // first line is the rule for the start-symbol
    82     //  var m = ruleExpr.Match(lines.First());
    83     //  var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
    84 
    85     //  var g = new Grammar(startSymbol);
    86     //  foreach (var alt in m.Groups["alternative"].Captures) {
    87     //    g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
    88     //  }
    89     //  foreach (var line in lines.Skip(1)) {
    90     //    m = ruleExpr.Match(line);
    91     //    var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
    92     //    foreach (var alt in m.Groups["alternative"].Captures) {
    93     //      g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n))));
    94     //    }
    95     //  }
    96 
    97     //  return g;
    98     //}
    9965  }
    10066}

  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Grammars/3.3/Grammar.cs

    r10067 r10086  
    2929  public class Grammar : IGrammar {
    3030    public static readonly ISymbol EmptySymbol = new Symbol("EPS");
    31     private Dictionary<ISymbol, List<Sequence>> rules = new Dictionary<ISymbol, List<Sequence>>();
    32     private HashSet<ISymbol> allSymbols = new HashSet<ISymbol>();
     31    private readonly Dictionary<ISymbol, List<Sequence>> rules;
     32    private readonly HashSet<ISymbol> allSymbols;
    3333
    3434    public ISymbol StartSymbol { get; set; }
    … …  
    3737    public IEnumerable<ISymbol> Symbols { get { return allSymbols; } }
    3838
    39     public Grammar(ISymbol startSymbol) {
     39    public Grammar(ISymbol startSymbol, IEnumerable<ISymbol> nonTerminals, IEnumerable<ISymbol> terminals) {
    4040      Debug.Assert(startSymbol != EmptySymbol);
    4141      this.StartSymbol = startSymbol;
     42      this.allSymbols = new HashSet<ISymbol>(nonTerminals.Concat(terminals));
     43      this.rules = nonTerminals.ToDictionary(nt => nt, nt => new List<Sequence>());
    4244    }
    4345
    … …  
    5658    public virtual void AddProductionRule(ISymbol ntSymbol, Sequence production) {
    5759      Debug.Assert(ntSymbol != EmptySymbol);
     60      Debug.Assert(rules.ContainsKey(ntSymbol));
     61      Debug.Assert(production.All(s => allSymbols.Contains(s)));
    5862
    59       List<Sequence> l;
    60       if (!rules.TryGetValue(ntSymbol, out l)) {
    61         l = new List<Sequence>();
    62         rules.Add(ntSymbol, l);
    63 
    64         allSymbols.Add(ntSymbol); // register new nt-symbol
    65       }
    66       // check if the same production exists already
     63      var l = rules[ntSymbol];
    6764      Debug.Assert(!l.Any(s => s.SequenceEqual(production)));
    6865
    6966      l.Add(production);
    70 
    71       foreach (var s in production) allSymbols.Add(s); // register all symbols in the production
    7267    }
    7368
    7469    public bool IsTerminal(ISymbol symbol) {
     70      // terminals must not have rules but must occur in the set of all symbols
    7571      return !rules.ContainsKey(symbol) && allSymbols.Contains(symbol);
    7672    }
     73
    7774    public bool IsNonTerminal(ISymbol symbol) {
    7875      return rules.ContainsKey(symbol);
    79     }
    80 
    81     // checks if a rule exists for each NT symbol
    82     public bool IsComplete() {
    83       return rules.ContainsKey(StartSymbol) &&
    84              NonTerminalSymbols.All(nt => rules.ContainsKey(nt));
    8576    }
    8677
    … …  
    9182      lines = lines.Where(l => !empty.IsMatch(l)).ToArray(); // remove empty lines
    9283
     84      // make two passes: 1) find all symbols 2) add production rules
     85      var nonTerminals = new List<ISymbol>();
     86      var allSymbols = new List<ISymbol>();
     87
    9388      // first line is the rule for the start-symbol
    9489      var m = ruleExpr.Match(lines.First());
    9590      var startSymbol = new Symbol(m.Groups["ntSymbol"].Value);
    96       var g = new Grammar(startSymbol);
     91
     92      nonTerminals.Add(startSymbol);
     93      allSymbols.Add(startSymbol);
     94
     95      // parse first line
    9796      foreach (var alt in m.Groups["alternative"].Captures) {
    98         g.AddProductionRule(startSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n)).ToList<ISymbol>()));
     97        foreach (var s in alt.ToString()
     98          .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
     99          .Select(n => new Symbol(n))) allSymbols.Add(s);
    99100      }
     101      // parse all remaining lines
    100102      foreach (var line in lines.Skip(1)) {
    101103        m = ruleExpr.Match(line);
    102104        var ntSymbol = new Symbol(m.Groups["ntSymbol"].Value);
     105        nonTerminals.Add(ntSymbol);
     106        allSymbols.Add(ntSymbol);
     107
    103108        foreach (var alt in m.Groups["alternative"].Captures) {
    104           g.AddProductionRule(ntSymbol, new Sequence(alt.ToString().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(n => new Symbol(n)).ToList<ISymbol>()));
     109          foreach (var s in alt.ToString()
     110          .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
     111          .Select(n => new Symbol(n))) allSymbols.Add(s);
     112        }
     113      }
     114
     115      var g = new Grammar(startSymbol, nonTerminals, allSymbols.Except(nonTerminals));
     116
     117      m = ruleExpr.Match(lines.First());
     118      // add production rules
     119      foreach (var alt in m.Groups["alternative"].Captures) {
     120        g.AddProductionRule(startSymbol,
     121          new Sequence(alt.ToString()
     122            .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
     123            .Select(n => allSymbols.Single(s => s.Name == n)).ToList<ISymbol>()));
     124      }
     125      // parse all remaining lines
     126      foreach (var line in lines.Skip(1)) {
     127        m = ruleExpr.Match(line);
     128        var ntSymbol = nonTerminals.Single(s => s.Name == m.Groups["ntSymbol"].Value);
     129        foreach (var alt in m.Groups["alternative"].Captures) {
     130          g.AddProductionRule(ntSymbol,
     131            new Sequence(alt.ToString()
     132              .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
     133              .Select(n => allSymbols.Single(s => s.Name == n)).ToList<ISymbol>()));
    105134        }
    106135      }

  • branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL.sln

    r10079 r10086  
    55  ProjectSection(SolutionItems) = preProject
    66    GenerateFromAtg.cmd = GenerateFromAtg.cmd
     7    Performance1.psess = Performance1.psess
    78    PreBuildEvent.cmd = PreBuildEvent.cmd
    89  EndProjectSection
    … …  
    111112    {E2060931-6700-464B-9E82-50846D7AE4E9} = {3768D612-38EB-47D8-9E79-75D8E5AB00A8}
    112113  EndGlobalSection
     114  GlobalSection(Performance) = preSolution
     115    HasPerformanceSessions = true
     116  EndGlobalSection
    113117EndGlobal
Note: See TracChangeset for help on using the changeset viewer.