Changeset 11972 for branches/HeuristicLab.Problems.GrammaticalOptimization

Timestamp:

02/09/15 09:48:30 (10 years ago)

Author:

gkronber

Message:

#2283 new experiments

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization

Files:

• HeuristicLab.Algorithms.GeneticProgramming/StandardGP.cs (modified) (2 diffs)
• HeuristicLab.Common/ExpressionExtender.cs (modified) (10 diffs)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs (modified) (2 diffs)
• HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs (modified) (6 diffs)
• HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj (modified) (1 diff)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/PermutationProblem.cs (added)
• HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs (modified) (2 diffs)
• Main/Program.cs (modified) (6 diffs)
• Test/TestCanonicalExpressions.cs (modified) (2 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/StandardGP.cs

@@ -29 +29 @@
       // default parameter values
       PopulationSize = 1000;
-      TournamentGroupSize = 7;
+      TournamentGroupSize = 4;
       MutationRate = 0.15;
       MaxSolutionSize = 100;
@@ -65 +65 @@
 
         ga.Problem = hlProblem;
+        //ga.Problem.SolutionCreatorParameter.ActualValue = new FullTreeCreator();
         var mutator = (MultiSymbolicExpressionTreeManipulator)ga.MutatorParameter.ValidValues.Single(op => op.Name == "MultiSymbolicExpressionTreeManipulator");
         foreach (var op in mutator.Operators) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

@@ -49 +49 @@
     }
 
-    // an expression is a list of terms 
+    // an expression is a sorted set of terms 
     // a term is an (ordered) list of factors
-    // a factor is a symbol or an inverted expression
+    // a factor is either a single symbol or an inverted expression
     // CanonicalExpression reads multiple terms (expressions) and must merge the terms in the expression (ordering and duplicates)
     // CanonicalTerm reads multiple factors and must expand factors whenever it reads a combined factor (expression) it produces an expression
@@ -83 +83 @@
     // canonical term returns either a single term (product of factors) or a set of terms 
     private Expr CanonicalTerm() {
-      var factors = new List<Expr>();
-      var invFactors = new List<Expr>();
+      var factors = new List<Factor>();
       var f = CanonicalFact();
       if (f != null) factors.Add(f);
@@ -97 +96 @@
           f = CanonicalFact();
           f.Invert();
-          if (f != null) invFactors.Add(f);
+          if (f != null) factors.Add(f);
         }
         curSy = CurSy();
       }
-
-      // cancellation
-      foreach (var invF in invFactors.ToArray()) {
-        invF.Invert();
-        if (factors.Contains(invF)) {
-          invFactors.Remove(invF);
-          factors.Remove(invF);
-          if (factors.Count == 0) factors.Add(new Expr(new Term('1')));
-        } else invF.Invert();
-      }
-
-      return ExpandFactors(factors, invFactors);
-    }
-
-    private Expr ExpandFactors(List<Expr> factors, List<Expr> invFactors) {
+      return ExpandFactors(factors);
+    }
+
+    /*
+    private List<Factor> CancelFactors(Term t) {
+      var nonInvF = t.Factors.Where(f => !f.IsInverse).ToArray();
+      var invF = t.Factors.Where(f => f.IsInverse).ToArray();
+
+      var result = new List<Factor>();
+      foreach (var f in nonInvF) {
+        if (!invF.Contains(f)) {
+          result.Add(f);
+        }
+      }
+      if (result.Count == 0) result.Add(new Factor('1'));
+      return result;
+    }
+    */
+    // canonical fact returns a factor (either a singe variable, or a set of terms)
+    private Factor CanonicalFact() {
+      var curSy = CurSy();
+      if (curSy == '!') {
+        throw new NotSupportedException();
+      } else if (curSy == '(') {
+        NewSy();
+        Expr r = CanonicalExpr(); // this is already simplified
+        if (CurSy() != ')') throw new ArgumentException();
+        NewSy();
+        return new Factor(r);
+      } else if (curSy >= 'a' && curSy <= 'z') {
+        NewSy();
+        return new Factor(curSy);
+        //       } else if (curSy >= '0' && curSy <= '9') {
+      } else if (curSy >= 'A' && curSy <= 'Z') {
+        // treat nonterminals in the same way as variables
+        NewSy();
+        return new Factor(curSy);
+
+      } else throw new ArgumentException("found symbol " + curSy);
+    }
+
+    // a list of factors (symbols, or expressions, and possibly inverses are read
+    // a lis to factors symbols or expressions and possibly inverses are produced
+    // all non-inverse expression factors are expanded
+    private Expr ExpandFactors(IEnumerable<Factor> factors) {
       // if (invFactors.Count > 0) throw new NotImplementedException();
-      Expr currentFact = factors.First(); // new Expr(simpleFactor));
-      Debug.Assert(!currentFact.Inverse); // the first factor is never an inverted factor
+      Debug.Assert(!factors.First().IsInverse); // the first factor is never an inverted factor
+
+      // each factor could be a list of terms (expression)
+
+      Expr currentFact = null;
+      var firstFactor = factors.First();
+      if (firstFactor.IsSimpleFactor) currentFact = new Expr(new Term(firstFactor));
+      else currentFact = firstFactor.Expr;
+
       foreach (var fact in factors.Skip(1)) {
-        currentFact = AllProducts(currentFact, fact);
-      }
-      foreach (var invF in invFactors) {
-        currentFact = AllInvProducts(currentFact, invF);
+        Expr curExpr = null;
+        if (fact.IsSimpleFactor || fact.IsInverse) curExpr = new Expr(new Term(fact));
+        else curExpr = fact.Expr;
+        currentFact = AllProducts(currentFact, curExpr);
       }
       return currentFact;
@@ -133 +169 @@
       var combs = from aT in aTerms
                   from bT in bTerms
-                  select new Term(aT.Symbols.Concat(bT.Symbols), aT.InvExpressions.Concat(bT.InvExpressions));
+                  let factors = CancelFactors(aT.Factors.Concat(bT.Factors))
+                  select new Term(factors);
       return new Expr(combs);
     }
 
-    private Expr AllInvProducts(Expr a, Expr b) {
-      var aTerms = a.Terms.ToArray();
-      var combs = from aT in aTerms
-                  select new Term(aT.Symbols, aT.InvExpressions.Concat(new Expr[] { b }));
-      return new Expr(combs);
-    }
-
-    // canonical fact returns a factor (either a singe variable, or a set of terms)
-    private Expr CanonicalFact() {
-      var curSy = CurSy();
-      if (curSy == '!') {
-        throw new NotSupportedException();
-      } else if (curSy == '(') {
-        NewSy();
-        Expr r = CanonicalExpr();
-        if (CurSy() != ')') throw new ArgumentException();
-        NewSy();
-        return r;
-      } else if (curSy >= 'a' && curSy <= 'z') {
-        NewSy();
-        return new Expr(new Term(curSy));
-        //       } else if (curSy >= '0' && curSy <= '9') {
-      } else if (curSy >= 'A' && curSy <= 'Z') {
-        // treat nonterminals in the same way as variables
-        NewSy();
-        return new Expr(new Term(curSy));
-
-      } else throw new ArgumentException("found symbol " + curSy);
+    private IEnumerable<Factor> CancelFactors(IEnumerable<Factor> factors) {
+      var factorsArr = factors.ToArray();
+      var results = new List<Factor>(factors);
+      foreach (var f in factorsArr) {
+        if (f.ToString() == "1") results.Remove(f);
+        if (f.IsInverse) {
+          // find matching
+          Factor match;
+          if (f.IsSimpleFactor) match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Symbol.Equals(other.Symbol));
+          else match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Expr.Equals(other.Expr));
+          if (match != null) {
+            results.Remove(match);
+            results.Remove(f);
+          }
+        }
+      }
+      if (results.Count == 0) results.Add(new Factor('1'));
+      return results;
     }
 
@@ -170 +197 @@
     // term can be merged (essentially an ordered list of factors)
     internal class Term : IComparable<Term> {
-      private readonly SortedList<char, int> factorSymbs; // factor symbol and the number of occurrences
-      private readonly SortedList<Expr, int> invExpressions;
-
-      public IEnumerable<char> Symbols {
+      private readonly SortedList<Factor, int> factors; // factor symbol and the number of occurrences
+
+      public IEnumerable<Factor> Factors {
         get {
-          return factorSymbs.SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
-        }
-      }
-
-      public IEnumerable<Expr> InvExpressions {
-        get {
-          if (invExpressions == null) return Enumerable.Empty<Expr>();
-          return invExpressions.Where(p => p.Value > 0).SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
-        }
-      }
-
-      public Term(char f) {
-        factorSymbs = new SortedList<char, int>(new FactorComparer());
-        factorSymbs.Add(f, 1);
-      }
-      public Term(IEnumerable<char> factors, IEnumerable<Expr> invFactors) {
-        factorSymbs = new SortedList<char, int>(new FactorComparer());
-        invExpressions = new SortedList<Expr, int>();
+          return factors.SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
+        }
+      }
+
+      public Term(Factor f) {
+        factors = new SortedList<Factor, int>();
+        factors.Add(f, 1);
+      }
+      public Term(IEnumerable<Factor> factors) {
+        this.factors = new SortedList<Factor, int>();
         foreach (var f in factors) {
-          if (factorSymbs.ContainsKey(f)) factorSymbs[f] += 1;
-          else factorSymbs.Add(f, 1);
-        }
-
-        foreach (var invF in invFactors) {
-          if (invF.Terms.Count == 1) {
-            var t = invF.Terms.First();
-            foreach (var f in factors.Concat(new char[] { '1' })) {
-              if (t.factorSymbs.ContainsKey(f)) {
-                t.factorSymbs[f] -= 1;
-                if (t.factorSymbs[f] == 0) t.factorSymbs.Remove(f);
-              }
-            }
-          }
-          if (invExpressions.ContainsKey(invF)) invExpressions[invF] += 1;
-          else invExpressions.Add(invF, 1);
+          if (this.factors.ContainsKey(f)) this.factors[f] += 1;
+          else this.factors.Add(f, 1);
         }
       }
 
       public int CompareTo(Term other) {
-        if (ContainsNonTerminal(Symbols) && !ContainsNonTerminal(other.Symbols)) {
+        if (ContainsNonTerminal(Factors) && !ContainsNonTerminal(other.Factors)) {
           return 1;
-        } else if (!ContainsNonTerminal(Symbols) && ContainsNonTerminal(other.Symbols)) {
+        } else if (!ContainsNonTerminal(Factors) && ContainsNonTerminal(other.Factors)) {
           return -1;
         } else {
-          var countComp = Symbols.Count().CompareTo(other.Symbols.Count());
+          var countComp = Factors.Count().CompareTo(other.Factors.Count());
           if (countComp != 0) return countComp;
-          return string.Join("", Symbols).CompareTo(string.Join("", other.Symbols));
+          return string.Join("", Factors).CompareTo(string.Join("", other.Factors));
         }
       }
 
       public override string ToString() {
-        if (InvExpressions.Any())
-          return string.Join("*", Symbols) + "%" + string.Join("%", InvExpressions);
-        else {
-          return string.Join("*", Symbols);
-        }
+
+        return string.Join("*", Factors);
       }
       public override bool Equals(object obj) {
         var other = obj as Term;
         if (other == null) return false;
-        if (this.Symbols.Count() != other.Symbols.Count()) return false;
-        if (this.InvExpressions.Count() != other.InvExpressions.Count()) return false;
-        if (this.Symbols.Zip(other.Symbols, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
-        if (this.InvExpressions.Zip(other.InvExpressions, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
+        if (this.Factors.Count() != other.Factors.Count()) return false;
+        if (this.Factors.Zip(other.Factors, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
         return true;
       }
       public override int GetHashCode() {
         var h = 31415;
-        foreach (var v in Symbols) {
+        foreach (var v in Factors) {
           h ^= v.GetHashCode();
         }
-        foreach (var v in InvExpressions) {
-          h ^= v.GetHashCode();
-        }
+        return h;
+      }
+    }
+    #endregion
+
+    #region factor
+    // factors is either a single symbol or an inverted expression
+    internal class Factor : IComparable<Factor> {
+      public bool IsSimpleFactor { get { return Expr == null; } }
+      public char Symbol { get { return symbol; } }
+      public Expr Expr { get { return expr; } }
+      public bool IsInverse { get { return inv; } }
+      private readonly char symbol = '\0';
+      private readonly Expr expr;
+      private bool inv;
+
+      public Factor(char f) {
+        this.symbol = f;
+      }
+      public Factor(Expr expr) {
+        this.expr = expr;
+      }
+
+      public void Invert() {
+        this.inv = !inv;
+      }
+
+      public int CompareTo(Factor other) {
+        // 1) single symbol factors first
+        // 2) expression factors by expression compare
+        var crit1 = ContainsNonTerminal(this).CompareTo(ContainsNonTerminal(other));
+        if (crit1 != 0) return crit1;
+
+        var crit2 = this.IsInverse.CompareTo(other.IsInverse);
+        if (crit2 != 0) return crit2;
+
+        var crit3 = this.IsSimpleFactor.CompareTo(other.IsSimpleFactor);
+        if (crit3 != 0) return crit3;
+
+        // both are simple or expressions
+        if (IsSimpleFactor) return this.symbol.CompareTo(other.symbol);
+        else return this.Expr.CompareTo(other.Expr);
+      }
+
+      public override string ToString() {
+        var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")";
+        if (IsInverse) {
+          return "1/" + s;
+        } else return s;
+      }
+      public override bool Equals(object obj) {
+        var other = obj as Factor;
+        if (other == null) return false;
+        if (IsInverse != other.IsInverse) return false;
+        if (this.symbol != other.symbol) return false;
+        if (this.Expr != other.Expr) return false;
+        return true;
+      }
+      public override int GetHashCode() {
+        var h = 31415;
+        h ^= symbol.GetHashCode();
+        if (Expr != null) h ^= Expr.GetHashCode();
         return h;
       }
@@ -258 +316 @@
     internal class Expr : IComparable<Expr> {
       public readonly SortedSet<Term> Terms; // only set for Kind == Expr 
-      public bool Inverse;
+      //public bool Inverse;
       public Expr(Term t) {
         Terms = new SortedSet<Term>();
@@ -286 +344 @@
 
       public override string ToString() {
-        if (Inverse && Terms.Count > 1)
-          return "(" + string.Join("+", Terms) + ")";
-        else if (Inverse && Terms.Count == 1) {
-          return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*");
-        } else
-          return string.Join("+", Terms);
+        // if (Inverse && Terms.Count > 1)
+        //   return "(" + string.Join("+", Terms) + ")";
+        // else if (Inverse && Terms.Count == 1) {
+        //   return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*");
+        // } else
+        return string.Join("+", Terms);
       }
       public override bool Equals(object obj) {
         var other = obj as Expr;
         if (other == null) return false;
-        if (this.Inverse != other.Inverse) return false;
+        //if (this.Inverse != other.Inverse) return false;
         if (this.Terms.Count() != other.Terms.Count()) return false;
         return this.Terms.Intersect(other.Terms).Count() == this.Terms.Count;
@@ -308 +366 @@
         return h;
       }
-
-      public void Invert() {
-        this.Inverse = !Inverse;
-      }
     }
     #endregion
@@ -317 +371 @@
       return symb >= 'A' && symb <= 'Z';
     }
-    internal static bool ContainsNonTerminal(IEnumerable<char> symbs) {
-      return symbs.Any(IsNonTerminal);
-    }
+    internal static bool ContainsNonTerminal(IEnumerable<Factor> factors) {
+      return factors.Any(ContainsNonTerminal);
+    }
+    internal static bool ContainsNonTerminal(Factor f) {
+      if (f.Expr == null) return IsNonTerminal(f.Symbol);
+      else return ContainsNonTerminal(f.Expr);
+    }
+
+    private static bool ContainsNonTerminal(Expr expr) {
+      return expr.Terms.Any(ContainsNonTerminal);
+    }
+
+    private static bool ContainsNonTerminal(Term term) {
+      return ContainsNonTerminal(term.Factors);
+    }
+
+
+    /*
 
     internal class FactorComparer : IComparer<char> {
@@ -333 +402 @@
         }
       }
-    }
+    }*/
   }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs

@@ -26 +26 @@
     // for boolean problems the symbol * representes the AND operator, the symbol + represents the OR operator, ! = NOT, ^ = XOR
 
-    public void Compile(string sentence, out Term f, out Variable[] variables, out Variable[] constants) {
+    public void Compile(string sentence, out Term f, Variable[] variables, out Variable[] constants) {
       InitLex(sentence);
-      var variablesList = new List<Variable>();
       var constantsList = new List<Variable>();
-      f = Expr(variablesList, constantsList);
-      variables = variablesList.ToArray();
+      f = Expr(variables, constantsList);
       constants = constantsList.ToArray();
     }
@@ -132 +130 @@
         NewSy();
       } else if (curSy >= 'a' && curSy <= 'z') {
-        var newVar = new Variable();
-        variables.Add(newVar);
-        r = newVar;
+        var varIdx = (byte)curSy - (byte)'a';
+        if (varIdx >= variables.Count) throw new ArgumentException();
+        r = variables[varIdx];
         NewSy();
       } else if (curSy >= '0' && curSy <= '9') {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

@@ -70 +70 @@
 
     public SymbolicRegressionProblem(Random random, string partOfName, bool useConstantOpt = true) {
-      var instanceProvider = new RegressionRealWorldInstanceProvider();
-      var dds = instanceProvider.GetDataDescriptors().OfType<RegressionDataDescriptor>();
+      var instanceProviders = new RegressionInstanceProvider[] 
+      {new RegressionRealWorldInstanceProvider(),
+        new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(),
+        new KeijzerInstanceProvider(), 
+        new VladislavlevaInstanceProvider(), 
+        new NguyenInstanceProvider(), 
+        new KornsInstanceProvider(), 
+    };
+      var instanceProvider = instanceProviders.FirstOrDefault(prov => prov.GetDataDescriptors().Any(dd => dd.Name.Contains(partOfName)));
+      if (instanceProvider == null) throw new ArgumentException("instance not found");
+
       this.useConstantOpt = useConstantOpt;
 
+      var dds = instanceProvider.GetDataDescriptors();
       var problemData = instanceProvider.LoadData(dds.Single(ds => ds.Name.Contains(partOfName)));
 
@@ -133 +143 @@
 
     public string CanonicalRepresentation(string phrase) {
-      throw new NotImplementedException();
+      return phrase;
     }
 
@@ -141 +151 @@
       // for each expression split into terms
       // for each term order factors to canonical // ../E = * 1/E
-      var canonical = CanonicalRepresentation(phrase);
-      throw new NotImplementedException();
+      return new Feature[] { new Feature(phrase, 1.0) };
     }
 
@@ -150 +159 @@
       AutoDiff.Term func;
       int pos = 0;
+      int n = x.GetLength(0);
+      int m = x.GetLength(1);
 
       var compiler = new ExpressionCompiler();
-      Variable[] variables;
+      Variable[] variables = Enumerable.Range(0, m).Select(_ => new Variable()).ToArray();
       Variable[] constants;
-      compiler.Compile(sentence, out func, out variables, out constants);
+      compiler.Compile(sentence, out func, variables, out constants);
 
       // constants are manipulated 
@@ -168 +179 @@
       int info;
 
-      int n = x.GetLength(0);
-      int m = x.GetLength(1);
+
       int k = c.Length;
 
@@ -222 +232 @@
       return sb.ToString();
     }
+
 
     private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj

@@ -79 +79 @@
     <Compile Include="Interfaces\IProblem.cs" />
     <Compile Include="Interfaces\ISymbolicExpressionTreeProblem.cs" />
+    <Compile Include="Problems\PermutationProblem.cs" />
     <Compile Include="Problems\EvenParityProblem.cs" />
     <Compile Include="Problems\FindPhrasesProblem.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs

@@ -87 +87 @@
       //optimalQualityForLevel[1] = 4;
 
-      for (int i = 1; i < maxSizeForLevel.Length; i++) {
+      for (int i = 1; i < levels; i++) {
         maxSizeForLevel[i] = i * maxSizeForLevel[i - 1] + 1; // e.g. lvl-2: baxax
 
@@ -110 +110 @@
       // search for corresponding level
       int level = 0;
-      while (maxSizeForLevel[level + 1] < maxLen) level++;
+      while (level+1 < maxSizeForLevel.Length && maxSizeForLevel[level + 1] < maxLen) level++;
       // ASSERT: maxSizeForLevel[level + 1] >= maxLen
       return optimalQualityForLevel[level];

branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

@@ -27 +27 @@
 
       //RunDemo();
-      // RunGpDemo();
-      RunGridTest();
-      //RunGpGridTest();
+      //RunGpDemo();
+      //RunGridTest();
+      RunGpGridTest();
     }
 
@@ -229 +229 @@
       // - ant: UCB1Tuned with canonical states also works very well for the artificial ant! constistent solutions in less than 10k iters      
 
-      var problem = new SymbolicRegressionPoly10Problem();
+      //var problem = new SymbolicRegressionPoly10Problem();
       //var problem = new SantaFeAntProblem();
-      //var problem = new SymbolicRegressionProblem(random, "Tower"); 
+      var problem = new SymbolicRegressionProblem(random, "Breiman");
       //var problem = new PalindromeProblem();
       //var problem = new HardPalindromeProblem();
@@ -244 +244 @@
       //var alg = new SequentialSearch(problem, 23, random, 0,
       //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericContextualGrammarPolicy(problem, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), true));
-      var alg = new SequentialSearch(problem, 23, random, 0,
+      var alg = new SequentialSearch(problem, 30, random, 0,
         new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericFunctionApproximationGrammarPolicy(problem, true));
       //var alg = new MctsQLearningSampler(problem, sentenceLen, random, 0, null);
@@ -265 +265 @@
         globalStatistics.AddSentence(sentence, quality);
 
-        if (iterations % 1000 == 0) {
-          if (iterations % 10000 == 0) Console.Clear();
-          Console.SetCursorPosition(0, 0);
-          alg.PrintStats();
+        //if (iterations % 100 == 0) {
+        //  if (iterations % 10000 == 0) Console.Clear();
+        //  Console.SetCursorPosition(0, 0);
+        //  alg.PrintStats();
+        //}
+
+        //Console.WriteLine(sentence);
+
+        if (iterations % 100 == 0) {
+          Console.WriteLine("{0}", globalStatistics);
         }
-
-        //Console.WriteLine(sentence);
-
-        //if (iterations % 10000 == 0) {
-        //  Console.WriteLine("{0}", globalStatistics);
-        //}
       };
 
@@ -309 +309 @@
       const int nReps = 20;
       const int seed = 31415;
-      const int maxIters = 200000;
+      //const int maxIters = 50000;
       var rand = new Random(seed);
-      var problemFactories = new Func<ISymbolicExpressionTreeProblem>[]
+      var problemFactories = new Func<Tuple<int, int, ISymbolicExpressionTreeProblem>>[]
       {
-        () => new SymbolicRegressionPoly10Problem(), 
-        () => new SantaFeAntProblem(), 
-      };
-      foreach (var popSize in new int[] { 50, 100, 250, 500, 1000, 2500, 5000, 10000 }) {
+        () => Tuple.Create(50000, 32, (ISymbolicExpressionTreeProblem)new PermutationProblem()), 
+        () => Tuple.Create(50000, 32, (ISymbolicExpressionTreeProblem)new RoyalPairProblem()), 
+        () => Tuple.Create(50000, 32,(ISymbolicExpressionTreeProblem)new RoyalSymbolProblem()), 
+        () => Tuple.Create(50000, 64, (ISymbolicExpressionTreeProblem)new RoyalPairProblem()), 
+        () => Tuple.Create(50000, 64,(ISymbolicExpressionTreeProblem)new RoyalSymbolProblem()), 
+        () => Tuple.Create(50000, 128, (ISymbolicExpressionTreeProblem)new RoyalPairProblem()), 
+        () => Tuple.Create(50000, 128,(ISymbolicExpressionTreeProblem)new RoyalSymbolProblem()), 
+        () => Tuple.Create(50000, 256, (ISymbolicExpressionTreeProblem)new RoyalPairProblem()), 
+        () => Tuple.Create(50000, 256,(ISymbolicExpressionTreeProblem)new RoyalSymbolProblem()), 
+        //() => new RoyalPairProblem(), 
+        //() => new FindPhrasesProblem(rand, 20, 5, 3, 5, 0, 1, 0, true), 
+        //() => new FindPhrasesProblem(rand, 20, 5, 3, 5, 0, 1, 0, false), 
+        //() => new FindPhrasesProblem(rand, 20, 5, 3, 5, 50, 1, 0.8, false), 
+      };
+
+      foreach (var popSize in new int[] { 100 /*, 250, 500, 1000, 2500, 5000, 10000 */ }) {
         foreach (var mutationRate in new double[] { /* 0.05, /* 0.10, */ 0.15, /* 0.25, 0.3 */}) {
-          foreach (var maxSize in new int[] { 30, 50, 100, 150, 250 }) {
-            // skip experiments that are already done
-            if (popSize == 10000 || maxSize == 150 || maxSize == 250) {
-              foreach (var problemFactory in problemFactories)
-                for (int i = 0; i < nReps; i++) {
-                  var solverSeed = rand.Next();
-                  {
-                    var prob = problemFactory();
-                    var sgp = new StandardGP(prob, new Random(solverSeed));
-                    RunGP(sgp, prob, maxIters, popSize, mutationRate, maxSize);
-                  }
-                  // {
-                  //   var prob = problemFactory();
-                  //   var osgp = new OffspringSelectionGP(prob, new Random(solverSeed));
-                  //   RunGP(osgp, prob, maxIters, popSize, mutationRate, maxSize);
-                  // }
-                }
+          // skip experiments that are already done
+          foreach (var problemFactory in problemFactories) {
+            for (int i = 0; i < nReps; i++) {
+              {
+                var solverSeed = rand.Next();
+                var tupel = problemFactory();
+                var maxIters = tupel.Item1;
+                var maxSize = tupel.Item2;
+                var prob = tupel.Item3;
+                var sgp = new StandardGP(prob, new Random(solverSeed));
+                RunGP(sgp, prob, maxIters, popSize, mutationRate, maxSize);
+              }
+              //{
+              //  var prob = problemFactory();
+              //  var osgp = new OffspringSelectionGP(prob, new Random(solverSeed));
+              //  RunGP(osgp, prob, maxIters, popSize, mutationRate, maxSize);
+              //}
             }
           }
         }
+
       }
     }
@@ -350 +363 @@
         globalStatistics.AddSentence(sentence, quality);
 
-        if (iterations % 1000 == 0) {
+        if (iterations % 100 == 0) {
           Console.WriteLine("\"{0,25}\" {1} {2:N2} {3} \"{4,25}\" {5}", gpName, popSize, mutationRate, maxSize, probName, globalStatistics);
         }

branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs

@@ -68 +68 @@
     public void TestDivisionExpansion() {
       var extender = new ExpressionExtender();
-      Assert.AreEqual("a%c+b%c", extender.CanonicalRepresentation("(b+a)%c"));
-      Assert.AreEqual("a%c%d+b%c%d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
-      Assert.AreEqual("a%(c+d)+b%(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
-      Assert.AreEqual("a*b%(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
+      Assert.AreEqual("a*1/c+b*1/c", extender.CanonicalRepresentation("(b+a)%c"));
+      Assert.AreEqual("a*1/c*1/d+b*1/c*1/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
+      Assert.AreEqual("a*1/(c+d)+b*1/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
+      Assert.AreEqual("a*b*1/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
 
-      Assert.AreEqual("a*b%(a+b)%(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
-      Assert.AreEqual("a*b%(a%e+b%e)%(c+d)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
+      Assert.AreEqual("a*b*1/(a+b)*1/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
+      Assert.AreEqual("a*b*1/(a*1/e+b*1/e)*1/(c+d)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
       // a*b*e%(c+d)%(a+b)
     }
@@ -82 +82 @@
       Assert.AreEqual("1", extender.CanonicalRepresentation("a%a"));
       Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a"));
-      Assert.AreEqual("1%a", extender.CanonicalRepresentation("(a%a)%a")); 
-      Assert.AreEqual("1%a", extender.CanonicalRepresentation("a%a%a"));
+      Assert.AreEqual("1/a", extender.CanonicalRepresentation("(a%a)%a"));
+      Assert.AreEqual("1/a", extender.CanonicalRepresentation("a%a%a"));
       Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
       Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)"));
-      Assert.AreEqual("1%a+1%b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
+      Assert.AreEqual("1/a+1/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
+      Assert.AreEqual("a*1/(a*c*1/b+e*1/d*1/f)+b*1/(a*c*1/b+e*1/d*1/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)"));
     }
   }