Changeset 8292

Timestamp:

07/16/12 09:06:27 (12 years ago)

Author:

gkronber

Message:

#1847: worked on move operators. version of the final EMSS submission

Location:

branches/GP-MoveOperators

Files:

• HeuristicLab.Algorithms.TabuSearch/3.3/TabuSelector.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMove.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveMaker.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs (modified) (11 diffs)

branches/GP-MoveOperators/HeuristicLab.Algorithms.TabuSearch/3.3/TabuSelector.cs

@@ -75 +75 @@
       get { return (ILookupParameter<BoolValue>)Parameters["EmptyNeighborhood"]; }
     }
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
+    }
 
     public BoolValue CopySelected {
@@ -103 +106 @@
       Parameters.Add(new ValueLookupParameter<BoolValue>("CopySelected", "True if the selected move should be copied.", new BoolValue(false)));
       Parameters.Add(new LookupParameter<BoolValue>("EmptyNeighborhood", "Will be set to true if the neighborhood didn't contain any non-tabu moves, otherwise it is set to false."));
+      Parameters.Add(new LookupParameter<IRandom>("Random"));
       CopySelectedParameter.Hidden = true;
+    }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      if (!Parameters.ContainsKey("Random"))
+        Parameters.Add(new LookupParameter<IRandom>("Random"));
     }
 
@@ -134 +144 @@
       }
 
-      if (selected[0] == null) {
-        EmptyNeighborhoodParameter.ActualValue = new BoolValue(true);
-        selected[0] = new Scope("All moves are tabu.");
-      } else EmptyNeighborhoodParameter.ActualValue = new BoolValue(false);
-
       // remove from last to first so that the stored indices remain the same
       if (!copy) {
@@ -146 +151 @@
         }
       }
+      if (selected[0] == null) {
+        //EmptyNeighborhoodParameter.ActualValue = new BoolValue(true);
+        //selected[0] = new Scope("All moves are tabu.");
+        // select a random move
+        selected[0] = scopes[RandomParameter.ActualValue.Next(scopes.Count)];
+      } else EmptyNeighborhoodParameter.ActualValue = new BoolValue(false);
+
 
       return selected;

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMove.cs

@@ -29 +29 @@
   [StorableClass]
   public class ReplaceBranchMove : Item {
-
+    [Storable]
+    public int FragmentIndex { get; set; }
     [Storable]
     public ISymbolicExpressionTree Tree { get; set; }
@@ -59 +60 @@
     protected ReplaceBranchMove(ReplaceBranchMove original, Cloner cloner)
       : base(original, cloner) {
+      this.FragmentIndex = original.FragmentIndex;
       this.Tree = cloner.Clone(original.Tree);
       this.SubtreeIndex = original.SubtreeIndex;
@@ -68 +70 @@
       this.Beta = original.Beta;
     }
-    public ReplaceBranchMove(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode parent, int subtreeIndex, ISymbolicExpressionTreeNode newChild, double[] originalOutput, double[] newOutput)
+    public ReplaceBranchMove(ISymbolicExpressionTree tree, ISymbolicExpressionTreeNode parent, int subtreeIndex, ISymbolicExpressionTreeNode newChild, double[] originalOutput, double[] newOutput, int fragmentIndex)
       : base() {
       this.Tree = tree;
@@ -76 +78 @@
       this.OriginalOutput = originalOutput;
       this.NewOutput = newOutput;
+      this.FragmentIndex = fragmentIndex;
     }
 

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveEvaluator.cs

@@ -87 +87 @@
 
       // prevent scaling to a constant value
-      if (beta.IsAlmost(0.0)) beta = 10E-5;
+      if (beta.IsAlmost(0.0)) beta = 1.0;
 
       move.Alpha = alpha;

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveMaker.cs

@@ -48 +48 @@
       get { return (ILookupParameter<ISymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
     }
+    public ILookupParameter<ItemList<ISymbolicExpressionTree>> FragmentsParameter {
+      get { return (ILookupParameter<ItemList<ISymbolicExpressionTree>>)Parameters["Fragments"]; }
+    }
+    public ILookupParameter<ItemList<DoubleArray>> FragmentOutputsParameter {
+      get { return (ILookupParameter<ItemList<DoubleArray>>)Parameters["FragmentOutputs"]; }
+    }
 
     [StorableConstructor]
@@ -58 +64 @@
       Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The relative quality of the move."));
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>("SymbolicExpressionTree", "The symbolic expression tree on which the move should be applied."));
+      Parameters.Add(new LookupParameter<ItemList<ISymbolicExpressionTree>>("Fragments"));
+      Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("FragmentOutputs"));
     }
 
@@ -65 +73 @@
 
     public override IOperation Apply() {
+      var fragments = FragmentsParameter.ActualValue;
+      var fragmentOutputs = FragmentOutputsParameter.ActualValue;
+
       var move = ReplaceBranchMoveParameter.ActualValue;
       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
@@ -70 +81 @@
 
       var newNode = (ISymbolicExpressionTreeNode)move.NewBranch.Clone();
+      var oldBranch = move.Parent.GetSubtree(move.SubtreeIndex);
+
       move.Parent.RemoveSubtree(move.SubtreeIndex);
       move.Parent.InsertSubtree(move.SubtreeIndex, Scale(newNode, move.Alpha, move.Beta));
 
+      // move oldBranch into pool
+      var fragmentStart = fragments[move.FragmentIndex].Root.GetSubtree(0);
+      fragmentStart.RemoveSubtree(0);
+      fragmentStart.AddSubtree(oldBranch);
+      fragmentOutputs[move.FragmentIndex] = new DoubleArray(move.NewOutput);
       quality.Value = moveQuality.Value;
       // update solution

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMoveSoftTabuCriterion.cs

@@ -101 +101 @@
       ItemList<IItem> tabuList = TabuListParameter.ActualValue;
       var move = ReplaceBranchMoveParameter.ActualValue;
-      var tree = SymbolicExpressionTreeParameter.ActualValue;
       bool isTabu = true;
       bool useQualityAspiration = UseQualityAspirationCriterion.Value;

branches/GP-MoveOperators/HeuristicLab.Problems.DataAnalysis.Symbolic.Regression/3.4/ReplaceBranchMultiMoveGenerator.cs

@@ -94 +94 @@
       get { return (IValueLookupParameter<BoolValue>)Parameters["Semantic"]; }
     }
-
-    private IList<ISymbolicExpressionTree> fragments;
-    private IList<double[]> fragmentOutput;
+    public ILookupParameter<ItemList<ISymbolicExpressionTree>> FragmentsParameter {
+      get { return (ILookupParameter<ItemList<ISymbolicExpressionTree>>)Parameters["Fragments"]; }
+    }
+    public ILookupParameter<ItemList<DoubleArray>> FragmentOutputsParameter {
+      get { return (ILookupParameter<ItemList<DoubleArray>>)Parameters["FragmentOutputs"]; }
+    }
 
     [StorableConstructor]
@@ -119 +122 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("NeighbourhoodSize", new IntValue(5)));
       Parameters.Add(new ValueLookupParameter<BoolValue>("Semantic", new BoolValue()));
+      Parameters.Add(new LookupParameter<ItemList<ISymbolicExpressionTree>>("Fragments"));
+      Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("FragmentOutputs"));
     }
 
@@ -139 +144 @@
     }
 
-    public override void ClearState() {
-      fragments = null;
-      fragmentOutput = null;
-      base.ClearState();
-    }
-    public override void InitializeState() {
-      fragments = null;
-      fragmentOutput = null;
-      base.InitializeState();
-    }
-
     public override IOperation Apply() {
       var random = RandomParameter.ActualValue;
-      if (fragments == null || fragmentOutput == null) {
+      if (FragmentsParameter.ActualValue == null || FragmentOutputsParameter.ActualValue == null) {
         InitializeOperator();
       }
@@ -176 +170 @@
       int maxDepth = MaximumSymbolicExpressionTreeDepthParameter.ActualValue.Value;
       int maxLength = MaximumSymbolicExpressionTreeLengthParameter.ActualValue.Value;
-      var possibleInternalChildren = (from parent in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()
+      var possibleInternalChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
                                       from i in Enumerable.Range(0, parent.SubtreeCount)
                                       let currentChild = parent.GetSubtree(i)
                                       where currentChild.SubtreeCount > 0
-                                      where tree.Root.GetBranchLevel(currentChild) <= maxDepth + 2
+                                      where tree.Root.GetBranchLevel(currentChild) < maxDepth + 2
                                       where tree.Length - currentChild.GetLength() < maxLength
                                       select new CutPoint(parent, i)).ToArray();
 
-      var possibleLeaveChildren = (from parent in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()
+      var possibleLeaveChildren = (from parent in tree.Root.GetSubtree(0).IterateNodesPrefix()
                                    from i in Enumerable.Range(0, parent.SubtreeCount)
                                    let currentChild = parent.GetSubtree(i)
                                    where currentChild.SubtreeCount == 0
-                                   where tree.Root.GetBranchLevel(currentChild) <= maxDepth + 2
+                                   where tree.Root.GetBranchLevel(currentChild) < maxDepth + 2
                                    where tree.Length - 1 < maxLength
                                    select new CutPoint(parent, i)).ToArray();
-
+      if (possibleInternalChildren.Length == 0) possibleInternalChildren = possibleLeaveChildren;
+      if (possibleLeaveChildren.Length == 0) possibleLeaveChildren = possibleInternalChildren;
 
       var root = (new ProgramRootSymbol()).CreateTreeNode();
@@ -202 +197 @@
 
       bool semantic = SemanticParameter.ActualValue.Value;
-
-      // select a random replacement point
-      CutPoint[] possibleChildren;
-      if (random.NextDouble() < 0.9)
-        possibleChildren = possibleInternalChildren;
-      else possibleChildren = possibleLeaveChildren;
-      var selected = possibleChildren[random.Next(possibleChildren.Length)];
-      // evaluate 
-      start.AddSubtree(selected.Parent.GetSubtree(selected.ChildIndex));
-      var output = interpreter.GetSymbolicExpressionTreeValues(t, ds, rows).ToArray();
-      start.RemoveSubtree(0);
-
-      if (semantic) {
-        return FindMostSimilarFragments(tree, maxLength, maxDepth, selected, random, n, output);
-      } else {
-        return FindRandomFragments(tree, maxLength, maxDepth, selected, random, n, output);
+      int maxNeighbours = NeighbourhoodSizeParameter.ActualValue.Value;
+      var count = 0;
+      while (count < n) {
+        // select a random replacement point
+        CutPoint[] possibleChildren;
+        if (random.NextDouble() < 0.9)
+          possibleChildren = possibleInternalChildren;
+        else possibleChildren = possibleLeaveChildren;
+        var selected = possibleChildren[random.Next(possibleChildren.Length)];
+        // evaluate 
+        start.AddSubtree(selected.Parent.GetSubtree(selected.ChildIndex));
+        var output = interpreter.GetSymbolicExpressionTreeValues(t, ds, rows).ToArray();
+        start.RemoveSubtree(0);
+
+        if (semantic) {
+          foreach (var m in FindMostSimilarFragments(tree, maxLength, maxDepth, selected, random, maxNeighbours, output)) {
+            yield return m;
+            count++;
+          }
+        } else {
+          foreach (var m in FindRandomFragments(tree, maxLength, maxDepth, selected, random, maxNeighbours, output)) {
+            yield return m;
+            count++;
+          }
+        }
       }
     }
@@ -223 +227 @@
     private IEnumerable<ReplaceBranchMove> FindRandomFragments(ISymbolicExpressionTree tree, int maxLength, int maxDepth, CutPoint selected,
   IRandom random, int maxNeighbours, double[] output) {
-      var selectedFragments = new List<Tuple<ISymbolicExpressionTree, double[]>>(maxNeighbours);
+      var selectedFragments = new List<int>(maxNeighbours);
       int treeLength = tree.Length;
       int removedFragementLength = selected.Parent.GetSubtree(selected.ChildIndex).GetLength();
@@ -229 +233 @@
       int iterations = 0;
       int maxIterations = maxNeighbours + 100;
+      var fragments = FragmentsParameter.ActualValue;
+      var fragmentOutput = FragmentOutputsParameter.ActualValue;
       // select random fragments
       while (selectedFragments.Count < maxNeighbours && iterations++ < maxIterations) {
@@ -238 +244 @@
           parentBranchLevel + selectedFragment.Depth - 2 <= maxDepth + 2 &&
           tree.Root.Grammar.IsAllowedChildSymbol(selected.Parent.Symbol, selectedFragment.Root.GetSubtree(0).GetSubtree(0).Symbol, selected.ChildIndex)) {
-          selectedFragments.Add(Tuple.Create(selectedFragment, selectedFragmentOutput));
+          selectedFragments.Add(r);
         }
       }
       // yield moves (we need to add linear scaling parameters for the inserted tree)
       return selectedFragments
-        .Select(pair => new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, pair.Item1.Root.GetSubtree(0).GetSubtree(0), output, pair.Item2));
+        .Select(i => new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, fragments[i].Root.GetSubtree(0).GetSubtree(0), output, fragmentOutput[i].ToArray(), i));
     }
 
     private IEnumerable<ReplaceBranchMove> FindMostSimilarFragments(ISymbolicExpressionTree tree, int maxLength, int maxDepth, CutPoint selected,
       IRandom random, int maxNeighbours, double[] output) {
-      var bestTrees = new SortedList<double, List<Tuple<ISymbolicExpressionTree, double[]>>>(fragments.Count);
+      var fragments = FragmentsParameter.ActualValue;
+      var fragmentOutput = FragmentOutputsParameter.ActualValue;
+      var bestTrees = new SortedList<double, List<int>>(fragments.Count);
       int treeLength = tree.Length;
       int removedFragementLength = selected.Parent.GetSubtree(selected.ChildIndex).GetLength();
@@ -266 +274 @@
           if (similarity < 1 && ((bestTrees.Count < maxNeighbours) || similarity > bestTrees.ElementAt(0).Key)) {
             if (!bestTrees.ContainsKey(similarity)) {
-              var l = new List<Tuple<ISymbolicExpressionTree, double[]>>();
+              var l = new List<int>();
               bestTrees.Add(similarity, l);
             }
-            bestTrees[similarity].Add(Tuple.Create(fragments[i], fragmentOutput[i]));
+            bestTrees[similarity].Add(i);
             if (bestTrees.Count > maxNeighbours) bestTrees.RemoveAt(0);
           }
@@ -278 +286 @@
       while (c < maxNeighbours) {
         var l = bestTrees.ElementAt(c % bestTrees.Count).Value;
-        var pair = l[random.Next(l.Count)];
+        var index = l[random.Next(l.Count)];
         yield return
-          new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, pair.Item1.Root.GetSubtree(0).GetSubtree(0),
-                                output, pair.Item2);
+          new ReplaceBranchMove(tree, selected.Parent, selected.ChildIndex, fragments[index].Root.GetSubtree(0).GetSubtree(0),
+                                output, fragmentOutput[index].ToArray(), index);
         c++;
       }
@@ -313 +321 @@
       // enable constants again
       constSym.InitialFrequency = oldConstFreq;
-      this.fragments = trees;
-      this.fragmentOutput = treeOutput;
+      // set parameters
+      FragmentsParameter.ActualValue = new ItemList<ISymbolicExpressionTree>(trees);
+      FragmentOutputsParameter.ActualValue = new ItemList<DoubleArray>(treeOutput.Select(a => new DoubleArray(a)));
     }
   }