Changeset 7832 for branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves

Timestamp:

05/15/12 19:09:09 (12 years ago)

Author:

gkronber

Message:

#1847 added operator for replacing branches with semantically similar branches

Location:

branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves

Files:

• ChangeNodeTypeMoveAbsoluteAttribute.cs (added)
• ChangeNodeTypeMoveGenerator.cs (modified) (5 diffs)
• ChangeNodeTypeMoveHardTabuCriterion.cs (added)
• ChangeNodeTypeMoveMaker.cs (modified) (3 diffs)
• ChangeNodeTypeMoveSoftTabuCriterion.cs (added)
• ChangeNodeTypeMoveTabuMaker.cs (added)
• ChangeNodeTypeMultiMoveGenerator.cs (modified) (6 diffs)
• ReplaceBranchMove.cs (added)
• ReplaceBranchMoveMaker.cs (added)
• ReplaceBranchMoveSoftTabuCriterion.cs (added)
• ReplaceBranchMoveTabuMaker.cs (added)
• ShakeMoveGenerator.cs (modified) (5 diffs)
• ShakeMultiMoveGenerator.cs (modified) (5 diffs)
• SymbolicExpressionTreeMoveAttribute.cs (added)

branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMoveGenerator.cs

@@ -30 +30 @@
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
-  [Item("ChangeNodeTypeMoveGenerator", "Operator that generates moves for changing the symbol of a single symbolic expression tree node.")]
+  [Item("ChangeNodeTypeExhaustiveMoveGenerator", "Operator that generates moves for changing the symbol of a single symbolic expression tree node.")]
   [StorableClass]
-  public class ChangeNodeTypeMoveGenerator : SingleSuccessorOperator, ISymbolicExpressionTreeMoveOperator, IMoveGenerator, IStochasticOperator {
+  public class ChangeNodeTypeMoveGenerator : SingleSuccessorOperator, ISymbolicExpressionTreeMoveOperator, IExhaustiveMoveGenerator, IStochasticOperator {
     public override bool CanChangeName {
       get { return false; }
@@ -39 +39 @@
       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     }
-    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
-      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
+    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
+      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
     }
     public ILookupParameter<ChangeNodeTypeMove> ChangeNodeTypeMoveParameter {
@@ -55 +55 @@
       : base() {
       Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
-      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
+      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
       Parameters.Add(new LookupParameter<ChangeNodeTypeMove>("ChangeNodeTypeMove", "The moves that should be generated in subscopes."));
       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope where the moves should be added as subscopes."));
@@ -66 +66 @@
 
     public override IOperation Apply() {
-      SymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
+      var tree = SymbolicExpressionTreeParameter.ActualValue;
       var moves = GenerateMoves(tree);
       string moveParameterName = ChangeNodeTypeMoveParameter.ActualName;
@@ -82 +82 @@
     }
 
-    public static IEnumerable<ChangeNodeTypeMove> GenerateMoves(SymbolicExpressionTree tree) {
+    public static IEnumerable<ChangeNodeTypeMove> GenerateMoves(ISymbolicExpressionTree tree) {
       var g = tree.Root.Grammar;
       return (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()

branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMoveMaker.cs

@@ -45 +45 @@
       get { return (ILookupParameter<ChangeNodeTypeMove>)Parameters["ChangeNodeTypeMove"]; }
     }
-    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
-      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
+    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
+      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
     }
 
@@ -57 +57 @@
       Parameters.Add(new LookupParameter<ChangeNodeTypeMove>("ChangeNodeTypeMove", "The move to evaluate."));
       Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The relative quality of the move."));
-      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree on which the move should be applied."));
+      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree on which the move should be applied."));
     }
 
@@ -66 +66 @@
     public override IOperation Apply() {
       ChangeNodeTypeMove move = ChangeNodeTypeMoveParameter.ActualValue;
-      SymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
+      var tree = SymbolicExpressionTreeParameter.ActualValue;
       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
       DoubleValue quality = QualityParameter.ActualValue;

branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ChangeNodeTypeMultiMoveGenerator.cs

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -46 +45 @@
       set { SampleSizeParameter.Value = value; }
     }
-    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
-      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
+    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
+      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
     }
     public ILookupParameter<ChangeNodeTypeMove> ChangeNodeTypeMoveParameter {
@@ -64 +63 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "The number of moves to generate."));
 
-      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
+      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
       Parameters.Add(new LookupParameter<ChangeNodeTypeMove>("ChangeNodeTypeMove", "The moves that should be generated in subscopes."));
       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope where the moves should be added as subscopes."));
@@ -75 +74 @@
 
     public override IOperation Apply() {
-      SymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
-      var moves = ChangeNodeTypeMoveGenerator.GenerateMoves(tree).ToArray();
+      var tree = SymbolicExpressionTreeParameter.ActualValue;
+
+
       string moveParameterName = ChangeNodeTypeMoveParameter.ActualName;
       var moveScopes = new List<Scope>();
@@ -82 +82 @@
       int n = SampleSizeParameter.ActualValue.Value;
 
-      var rand = Enumerable.Range(0, moves.Length).Select(i => random.NextDouble()).ToArray();
-      Array.Sort(rand, moves);
-      n = Math.Min(n, moves.Length);
+      var moves = GenerateMoves(tree, random, n);
 
-      foreach (var m in moves.Take(n)) {
+      foreach (var m in moves) {
         if (m.NewChild.HasLocalParameters)
           m.NewChild.ResetLocalParameters(random);
@@ -96 +94 @@
       return base.Apply();
     }
+
+    public static IEnumerable<ChangeNodeTypeMove> GenerateMoves(ISymbolicExpressionTree tree, IRandom random, int n) {
+      int count = 0;
+      var g = tree.Root.Grammar;
+      var possibleChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
+                              from i in Enumerable.Range(0, parent.SubtreeCount)
+                              from s in g.GetAllowedChildSymbols(parent.Symbol, i)
+                              where s.Enabled
+                              where s.InitialFrequency > 0.0
+                              let currentChild = parent.GetSubtree(i)
+                              where s.MinimumArity >= currentChild.SubtreeCount
+                              where s.MaximumArity <= currentChild.SubtreeCount
+                              where (from j in Enumerable.Range(0, currentChild.SubtreeCount)
+                                     let childOfChild = currentChild.GetSubtree(j)
+                                     select g.IsAllowedChildSymbol(s, childOfChild.Symbol, j)).All(p => p)
+                              select new { parent, i, s }).ToArray();
+      if (possibleChildren.Length < n) n = possibleChildren.Length;
+      while (count < n) {
+        var selected = possibleChildren[random.Next(possibleChildren.Length)];
+        yield return new ChangeNodeTypeMove(tree, selected.parent, selected.i, selected.s.CreateTreeNode());
+        count++;
+      }
+    }
   }
 }

branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ShakeMoveGenerator.cs

@@ -30 +30 @@
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
-  [Item("ShakeMoveGenerator", "Operator that generates moves for shaking a single symbolic expression tree node.")]
+  [Item("ShakeExhaustiveMoveGenerator", "Operator that generates moves for shaking a single symbolic expression tree node.")]
   [StorableClass]
-  public class ShakeMoveGenerator : SingleSuccessorOperator, ISymbolicExpressionTreeMoveOperator, IMoveGenerator, IStochasticOperator {
+  public class ShakeMoveGenerator : SingleSuccessorOperator, ISymbolicExpressionTreeMoveOperator, IExhaustiveMoveGenerator, IStochasticOperator {
     public override bool CanChangeName {
       get { return false; }
@@ -39 +39 @@
       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     }
-    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
-      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
+    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
+      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
     }
     public ILookupParameter<ChangeNodeTypeMove> ChangeNodeTypeMoveParameter {
@@ -55 +55 @@
       : base() {
       Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
-      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
+      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
       Parameters.Add(new LookupParameter<ChangeNodeTypeMove>("ChangeNodeTypeMove", "The moves that should be generated in subscopes."));
       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope where the moves should be added as subscopes."));
@@ -66 +66 @@
 
     public override IOperation Apply() {
-      SymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
+      var tree = SymbolicExpressionTreeParameter.ActualValue;
       var moves = GenerateMoves(tree);
       string moveParameterName = ChangeNodeTypeMoveParameter.ActualName;
@@ -81 +81 @@
     }
 
-    public static IEnumerable<ChangeNodeTypeMove> GenerateMoves(SymbolicExpressionTree tree) {
-      var g = tree.Root.Grammar;
+    public static IEnumerable<ChangeNodeTypeMove> GenerateMoves(ISymbolicExpressionTree tree) {
       return (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
               from i in Enumerable.Range(0, parent.SubtreeCount)

branches/GP-MoveOperators/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Moves/ShakeMultiMoveGenerator.cs

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -46 +45 @@
       set { SampleSizeParameter.Value = value; }
     }
-    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
-      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
+    public ILookupParameter<ISymbolicExpressionTree> SymbolicExpressionTreeParameter {
+      get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
     }
     public ILookupParameter<ChangeNodeTypeMove> ChangeNodeTypeMoveParameter {
@@ -64 +63 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "The number of moves to generate."));
 
-      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
+      Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree for which moves should be generated."));
       Parameters.Add(new LookupParameter<ChangeNodeTypeMove>("ChangeNodeTypeMove", "The moves that should be generated in subscopes."));
       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope where the moves should be added as subscopes."));
@@ -75 +74 @@
 
     public override IOperation Apply() {
-      SymbolicExpressionTree tree = SymbolicExpressionTreeParameter.ActualValue;
-      var moves = ChangeNodeTypeMoveGenerator.GenerateMoves(tree).ToArray();
+      var tree = SymbolicExpressionTreeParameter.ActualValue;
+      var random = RandomParameter.ActualValue;
+      int n = SampleSizeParameter.ActualValue.Value;
+      var moves = ChangeNodeTypeMultiMoveGenerator.GenerateMoves(tree, random, n);
       string moveParameterName = ChangeNodeTypeMoveParameter.ActualName;
       var moveScopes = new List<Scope>();
-      var random = RandomParameter.ActualValue;
-      int n = SampleSizeParameter.ActualValue.Value;
 
-      var rand = Enumerable.Range(0, moves.Length).Select(i => random.NextDouble()).ToArray();
-      Array.Sort(rand, moves);
-      n = Math.Min(n, moves.Length);
-
-      foreach (var m in moves.Take(n)) {
+      foreach (var m in moves) {
         m.NewChild.ShakeLocalParameters(random, 1);
         var moveScope = new Scope(moveScopes.Count.ToString());
@@ -95 +90 @@
       return base.Apply();
     }
+
+    public static IEnumerable<ChangeNodeTypeMove> GenerateMoves(ISymbolicExpressionTree tree, IRandom random, int n) {
+      int count = 0;
+      var g = tree.Root.Grammar;
+      var possibleChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
+                              from i in Enumerable.Range(0, parent.SubtreeCount)
+                              let currentChild = parent.GetSubtree(i)
+                              where currentChild.HasLocalParameters
+                              select new { parent, i, currentChild }).ToArray();
+      if (possibleChildren.Length < n) n = possibleChildren.Length;
+      while (count < n) {
+        var selected = possibleChildren[random.Next(possibleChildren.Length)];
+        yield return new ChangeNodeTypeMove(tree, selected.parent, selected.i, (ISymbolicExpressionTreeNode)selected.currentChild.Clone());
+        count++;
+      }
+    }
   }
 }