Changeset 10080

Timestamp:

10/22/13 20:39:15 (10 years ago)

Author:

gkronber

Message:

#2026 implemented a code generator for random search solvers for GPDL problems

Location:

branches/HeuristicLab.Problems.GPDL

Files:

• CodeGenerator/BruteForceCodeGen.cs (modified) (2 diffs)
• CodeGenerator/CodeGenerator.csproj (modified) (1 diff)
• CodeGenerator/RandomSearchCodeGen.cs (copied) (copied from branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs) (9 diffs)
• Examples/Artificial Ant.txt (modified) (4 diffs)
• Examples/RoyalTree.txt (modified) (1 diff)
• GpdlCompiler/Program.cs (modified) (1 diff)
• HeuristicLab.Problems.GPDL/3.4/Util.cs (modified) (1 diff)

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

@@ -5 +5 @@
 using System.Linq;
 using System.Text;
-using System.Threading.Tasks;
 using HeuristicLab.Grammars;
 using Attribute = HeuristicLab.Grammars.Attribute;
@@ -254 +253 @@
 
 
-      // find formal parameters of root node
+      // get formal parameters of start symbol
       var attr = grammar.StartSymbol.Attributes;
 

branches/HeuristicLab.Problems.GPDL/CodeGenerator/CodeGenerator.csproj

@@ -38 +38 @@
     <Compile Include="BruteForceCodeGen.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="RandomSearchCodeGen.cs" />
   </ItemGroup>
   <ItemGroup>

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

@@ -5 +5 @@
 using System.Linq;
 using System.Text;
-using System.Threading.Tasks;
 using HeuristicLab.Grammars;
 using Attribute = HeuristicLab.Grammars.Attribute;
 
 namespace CodeGenerator {
-  public class BruteForceCodeGen {
+  public class RandomSearchCodeGen {
 
     private string usings = @"
@@ -39 +38 @@
     }
 
-    private class SearchTree {
-      private SearchTree[] subTrees;
-      public bool Done { get; private set; }
-      private int nextAlternative;
-
-      public SearchTree() {
-        Done = false;
-      }
-
-      public SearchTree GetSubtree(int i) {
-        // if (subTrees[i] == null) subTrees[i] = new SearchTree();
-        return subTrees[i];
-      }
-
-      public int GetNextAlternative() {
-        System.Diagnostics.Debug.Assert(IsAlternativeNode);
-        return nextAlternative;
-      }
-
-      public bool IsUninitialized {
-        get { return subTrees == null; }
-      }
-
-      public void SetNumberOfSubtrees(int n) {
-        this.subTrees = new SearchTree[n]; 
-        for(int i=0;i<n;i++) this.subTrees[i] = new SearchTree();
-        nextAlternative = 0;
-      }
-
-      public void UpdatePath() {
-        System.Diagnostics.Debug.Assert(!Done);
-        if (IsUninitialized) { return; }
-        Count++;
-        if (subTrees.Length == 0) {
-          Done = true;
-        }
-        if (IsAlternativeNode) {
-          // update only the active alternative and calculate a new alternative
-          subTrees[nextAlternative].UpdatePath();
-
-          do {
-            nextAlternative = (nextAlternative + 1) % subTrees.Length;
-          } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
-
-          // from the nodes which are not done take the first with minimum count
-          //nextAlternative = (from i in Enumerable.Range(0, subTrees.Length)
-          //                   where subTrees[i] == null || !subTrees[i].Done
-          //                   orderby subTrees[i]==null?0:subTrees[i].Count ascending
-          //                   select i).FirstOrDefault(); // possibly there are no children left that can be tried
-        } else {
-          // for sequenceNodes update all sub-trees
-          foreach (var t in subTrees) t.UpdatePath();
-        }
-        // set node to done if all nodes are non-null and done
-        this.Done = true;
-        foreach(var t in subTrees) {
-          if(t == null || !t.Done) 
-            { this.Done = false; break; }
-        }        
-      }
-
-      public bool IsAlternativeNode { get; set; }
-      public bool IsSequenceNode { get; set; }
-      public int Count { get; private set; }
-    }
-
-    private SearchTree tree;
+
+    private Random seedRandom;
+    private int currentSeed;
     private void Start() {
-      // start with empty tree
-      tree = new SearchTree();
+      seedRandom = new Random();
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
       int n = 0;
       var sw = new System.Diagnostics.Stopwatch();
       sw.Start();
-      while (!tree.Done) {
-
+      while (true) {
+
+        // must make sure that calling the start-symbol multiple times in the fitness function always leads to the same path through the grammar
+        // so we use a PRNG for generating seeds for a separate PRNG that is reset each time the start symbol is called
+        currentSeed = seedRandom.Next();
         var f = Calculate();
-        // do one more run through the tree to update the path
-        tree.UpdatePath();
 
         n++;
@@ -243 +178 @@
           sb.AppendFormat("public {0} GetMin{1}_{2}() {{ return {3}; }}", fieldType, t.Ident, c.Ident, c.RangeMinExpression).AppendLine();
         } else if (c.Type == ConstraintNodeType.Set) {
-          sb.AppendFormat("public {0}[] GetAllowed{1}_{2}() {{ return {3}.ToArray(); }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
-        }
-        sb.AppendFormat("public {0} Get{1}_{2}Element(int i) {{ return GetAllowed{1}_{2}()[i]; }}", fieldType, t.Ident, c.Ident);
+          sb.AppendFormat("public IEnumerable<{0}> GetAllowed{1}_{2}() {{ return {3} }}", fieldType, t.Ident, c.Ident, c.SetExpression).AppendLine();
+        }
       }
       return sb.ToString();
@@ -252 +186 @@
     private string GenerateInterpreterSource(AttributedGrammar grammar) {
       var sb = new StringBuilder();
-
-
-      // find formal parameters of root node
-      var attr = grammar.StartSymbol.Attributes;
-
-      var formalParameter = grammar.StartSymbol.GetAttributeString();
-      // actual parameter are the same as formalparameter only without type identifier
-      string actualParameter;
-      if (attr.Any())
-        actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
-      else
-        actualParameter = string.Empty;
-
-      // generate entry method for evaluation. This is called from the min/max function
-      // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
-      sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
-      sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
-      sb.AppendLine("}");
 
       // generate methods for all nonterminals and terminals using the grammar instance
@@ -285 +201 @@
       // if the terminal symbol has attributes then we must create values for these attributes
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
+        sb.AppendFormat("private void {0}(Random random) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
-
-      sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count());
+        sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
+
       // each field must match a formal parameter, assign a value for each parameter
-      int i = 0;
       foreach (var element in s.Attributes) {
-        // read next symbol
-        sb.AppendLine("throw new NotImplementedException(); // this is not yet supported ");
-        sb.AppendFormat("{0} = Get{1}_{0}Element(tree.GetSubTree({2}).GetAlternative())", element.Name, s.Name, i++).AppendLine(";");
+        // only works for "IN SET"-Constraints
+        sb.AppendFormat("{{ var tmp = GetAllowed{1}_{0}().ToArray(); {0} = tmp[random.Next(tmp.Length)]; }} ", element.Name, s.Name);
       }
       sb.AppendLine("}");
@@ -303 +216 @@
     private string GenerateInterpreterMethod(AttributedGrammar g, ISymbol s) {
       var sb = new StringBuilder();
+      // if this is the start symbol we additionally have to create the method which can be called from the fitness function
+
+      if (g.StartSymbol.Equals(s)) {
+        if (!s.Attributes.Any())
+          sb.AppendFormat("private void {0}() {{", s.Name);
+        else
+          sb.AppendFormat("private void {0}({1}) {{", s.Name, s.GetAttributeString());
+
+        // get formal parameters of start symbol
+        var attr = g.StartSymbol.Attributes;
+
+        // actual parameter are the same as formalparameter only without type identifier
+        string actualParameter;
+        if (attr.Any())
+          actualParameter = attr.Skip(1).Aggregate(attr.First().AttributeType + " " + attr.First().Name, (str, a) => str + ", " + a.AttributeType + " " + a.Name);
+        else
+          actualParameter = string.Empty;
+
+        sb.AppendFormat("{0}(new Random(currentSeed), {1});", g.StartSymbol.Name, actualParameter).AppendLine();
+        sb.AppendLine("}");
+      }
+
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
+        sb.AppendFormat("private void {0}(Random random) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
+        sb.AppendFormat("private void {0}(Random random, {1}) {{", s.Name, s.GetAttributeString());
 
       // generate local definitions
@@ -312 +247 @@
 
 
-
-      // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
-      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
+      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).ToArray();
+      var terminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) == 0);
+      var nonTerminalAlts = altsWithSemActions.Where(alt => alt.Count(g.IsNonTerminal) > 0);
+      bool hasTerminalAlts = terminalAlts.Count() > 0;
+      bool hasNonTerminalAlts = nonTerminalAlts.Count() > 0;
 
       if (altsWithSemActions.Length > 1) {
-        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length);
-
-        int i = 0;
-        sb.AppendLine("switch(tree.GetNextAlternative()) {");
-        // generate a case for each alternative
-        foreach (var alt in altsWithSemActions) {
-          sb.AppendFormat("case {0}: {{ ", i).AppendLine();
-          sb.AppendLine("SearchTree subtree = null; ");
-
-          // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
-          // handling multiple non-terminals here would require a change in the structure of the search tree
-          // another way to handle this is through grammar transformation (the examplary grammars all have the correct from)
-          Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
-          foreach (var altSymb in alt) {
-            if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", i);
-            sb.AppendLine(GenerateSourceForAction(altSymb));
-          }
-          i++;
-          sb.AppendLine("break;").AppendLine("}");
-        }
-        sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
+        // here we need to bias the selection of alternatives (non-terminal vs terminal alternatives) to make sure that
+        // terminals are selected with a certain probability to make sure that:
+        // 1) we don't create the same small trees all the time (terminals have high probability to be selected)
+        // 2) we don't create very big trees by recursing to deep (leads to stack-overflow) (terminals have a low probability to be selected)
+        // so we first decide if we want to generate a terminal or non-terminal (50%, 50%) and then choose a symbol in the class randomly
+        // 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)
+        if (hasTerminalAlts && hasNonTerminalAlts) {
+          sb.AppendLine("if(random.NextDouble() < 0.5) {");
+          // terminals
+          sb.AppendLine("// terminals ");
+          GenerateSwitchStatement(sb, terminalAlts);
+          sb.AppendLine("} else {");
+          // non-terminals
+          sb.AppendLine("// non-terminals ");
+          GenerateSwitchStatement(sb, nonTerminalAlts);
+          sb.AppendLine("}");
+        } else if (hasTerminalAlts) {
+          sb.AppendLine("// terminals ");
+          GenerateSwitchStatement(sb, terminalAlts);
+        } else if (hasNonTerminalAlts) {
+          sb.AppendLine("// non-terminals ");
+          GenerateSwitchStatement(sb, nonTerminalAlts);
+        }
       } else {
-        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", altsWithSemActions.Single().Count(symb => !(symb is SemanticSymbol)));
-        int j = 0;
-        sb.AppendLine("SearchTree subtree = null; ");
         foreach (var altSymb in altsWithSemActions.Single()) {
-          if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", j++);
           sb.AppendLine(GenerateSourceForAction(altSymb));
         }
@@ -349 +284 @@
       sb.AppendLine("}");
       return sb.ToString();
+    }
+
+    private void GenerateSwitchStatement(StringBuilder sb, IEnumerable<Sequence> alts) {
+      sb.AppendFormat("switch(random.Next({0})) {{", alts.Count());
+      // generate a case for each alternative
+      int i = 0;
+      foreach (var alt in alts) {
+        sb.AppendFormat("case {0}: {{ ", i).AppendLine();
+
+        // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
+        // a way to handle this is through grammar transformation (the examplary grammars all have the correct from)
+        Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
+        foreach (var altSymb in alt) {
+          sb.AppendLine(GenerateSourceForAction(altSymb));
+        }
+        i++;
+        sb.AppendLine("break;").AppendLine("}");
+      }
+      sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
+
     }
 
@@ -358 +313 @@
       } else {
         if (!s.Attributes.Any())
-          return string.Format("{0}(subtree);", s.Name);
+          return string.Format("{0}(random);", s.Name);
         else
-          return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
+          return string.Format("{0}(random, {1});", s.Name, s.GetAttributeString());
       }
     }

branches/HeuristicLab.Problems.GPDL/Examples/Artificial Ant.txt

@@ -6 +6 @@
   public Point(int x, int y) {
     this.x = x;
-  this.y = y;
+    this.y = y;
   }
 };
@@ -95 +95 @@
     if(p.x < 0 || p.y < 0) return false;
     if(world.Length <= p.y) return false;
-  if(world[p.y].Length <= p.x) return false;
+    if(world[p.y].Length <= p.x) return false;
     return world[p.y][p.x] == '#';
   }
   public void RemoveFoodAt(Point p) {
     if(world.Length < p.y) return;
-  if(world[p.y].Length < p.x) return;
+    if(world[p.y].Length < p.x) return;
     world[p.y][p.x] = ' ';
   }
@@ -116 +116 @@
  
   public AntState() {
-    Steps = 0;  
-  FoodEaten = 0;
+    Steps = 0;    
+    FoodEaten = 0;
   }
  
@@ -123 +123 @@
     Steps++;
     switch(Direction) {
-    case Direction.West: Direction = Direction.South; break;
-    case Direction.South: Direction = Direction.East; break;
-    case Direction.East: Direction = Direction.North; break;
-    case Direction.North: Direction = Direction.West; break;
-  }
+      case Direction.West: Direction = Direction.South; break;
+      case Direction.South: Direction = Direction.East; break;
+      case Direction.East: Direction = Direction.North; break;
+      case Direction.North: Direction = Direction.West; break;
+    }
   }
   public void TurnRight() {
     Steps++;
     switch(Direction) {
-    case Direction.West: Direction = Direction.North; break;
-    case Direction.South: Direction = Direction.West; break;
-    case Direction.East: Direction = Direction.South; break;
-    case Direction.North: Direction = Direction.East; break;
-  }
+      case Direction.West: Direction = Direction.North; break;
+      case Direction.South: Direction = Direction.West; break;
+      case Direction.East: Direction = Direction.South; break;
+      case Direction.North: Direction = Direction.East; break;
+    }
   }
   public void MoveForward() { 
     Position = NextPosition; 
-  Steps++; 
-  if(World.FoodAt(Position)) {
-      World.RemoveFoodAt(Position);
-    FoodEaten++;
+    Steps++; 
+    if(World.FoodAt(Position)) {
+        World.RemoveFoodAt(Position);
+        FoodEaten++;
     }
   }
   public Point NextPosition { 
     get { 
-      int x, y;
+        int x, y;
         switch(Direction) {
-        case Direction.West: 
-        x = (Position.x + World.Width - 1) % World.Width;
-      y = Position.y;
-      return new Point(x, y);
-        case Direction.South: 
-          x = Position.x;
-      y = (Position.y + World.Height + 1) % World.Height;
-      return new Point(x, y);
-        case Direction.East:
-          x = (Position.x + World.Width + 1) % World.Width;
-      y = Position.y;
-      return new Point(x, y);
-        case Direction.North:
-          x = Position.x;
-      y = (Position.y + World.Height - 1) % World.Height;
-      return new Point(x, y);
-      }
-    return new Point(-1,-1);
+          case Direction.West: 
+            x = (Position.x + World.Width - 1) % World.Width;
+            y = Position.y;
+            return new Point(x, y);
+          case Direction.South: 
+              x = Position.x;
+            y = (Position.y + World.Height + 1) % World.Height;
+            return new Point(x, y);
+          case Direction.East:
+              x = (Position.x + World.Width + 1) % World.Width;
+            y = Position.y;
+            return new Point(x, y);
+          case Direction.North:
+              x = Position.x;
+            y = (Position.y + World.Height - 1) % World.Height;
+            return new Point(x, y);
+        }
+         return new Point(-1,-1);
     } 
   }  

branches/HeuristicLab.Problems.GPDL/Examples/RoyalTree.txt

@@ -1 +1 @@
 /* The Royal Tree benchmark problem for GP */
 /* See paper: William F. Punch, How Effective are Multiple Populations in Genetic Programming */
-/* 
 /* for max. depth 7 (level: g) this is hard to solve. Full enumeration needs a lot of memory. */
+
 PROBLEM RoyalTree
 CODE <<

branches/HeuristicLab.Problems.GPDL/GpdlCompiler/Program.cs

@@ -32 +32 @@
       Parser parser = new Parser(scanner);
       parser.Parse();
-      var codeGen = new BruteForceCodeGen();
+      var codeGen = new RandomSearchCodeGen();
 
       codeGen.Generate(parser.AbstractSyntaxTree);

branches/HeuristicLab.Problems.GPDL/HeuristicLab.Problems.GPDL/3.4/Util.cs

@@ -29 +29 @@
   private static string refOrOutGroup = @"(?:(?<refOrOut>(out|ref))\s+)"; // "ref " | "out "
   private static string typeGroup = @"(?:(?<type>[^,]+)\s+)";
-  private static string identGroup = @"(?<id>[^,]+)\s*";
+  private static string identGroup = @"(?:(?<id>[^,]+)\s*)";
   private static Regex formalParameterExpr = new Regex(@"\s*,?\s*" + refOrOutGroup + "?" + typeGroup + "?" + identGroup, RegexOptions.ECMAScript);
   public static IEnumerable<TerminalNode.FieldDefinition> ExtractParameters(string formalParameterSrc) {