Changeset 8333

Timestamp:

07/26/12 14:12:26 (12 years ago)

Author:

mkommend

Message:

#1070: Added RemoveBranchManipulation to HL.Encodings.SymbolicExpressionTree.

Location:

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4

Files:

• HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj (modified) (1 diff)
• Manipulators/RemoveBranchManipulation.cs (copied) (copied from trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ReplaceBranchManipulation.cs) (6 diffs)

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.csproj

@@ -152 +152 @@
     <Compile Include="Manipulators\ChangeNodeTypeManipulation.cs" />
     <Compile Include="Interfaces\Operators\ISymbolicExpressionTreeManipulator.cs" />
+    <Compile Include="Manipulators\RemoveBranchManipulation.cs" />
     <Compile Include="Manipulators\ReplaceBranchManipulation.cs" />
     <Compile Include="Manipulators\FullTreeShaker.cs" />

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/RemoveBranchManipulation.cs

@@ -20 +20 @@
 #endregion
 
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -26 +27 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System.Collections.Generic;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
   [StorableClass]
-  [Item("ReplaceBranchManipulation", "Selects a branch of the tree randomly and replaces it with a newly initialized branch (using PTC2).")]
-  public sealed class ReplaceBranchManipulation : SymbolicExpressionTreeManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
+  [Item("RemoveBranchManipulation", "Removes a random sub-tree of the input tree and fixes the tree by generating random subtrees if necessary..")]
+  public sealed class RemoveBranchManipulation : SymbolicExpressionTreeManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
     private const int MAX_TRIES = 100;
     private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
@@ -53 +53 @@
 
     [StorableConstructor]
-    private ReplaceBranchManipulation(bool deserializing) : base(deserializing) { }
-    private ReplaceBranchManipulation(ReplaceBranchManipulation original, Cloner cloner) : base(original, cloner) { }
-    public ReplaceBranchManipulation()
+    private RemoveBranchManipulation(bool deserializing) : base(deserializing) { }
+    private RemoveBranchManipulation(RemoveBranchManipulation original, Cloner cloner) : base(original, cloner) { }
+    public RemoveBranchManipulation()
       : base() {
       Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
@@ -62 +62 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new ReplaceBranchManipulation(this, cloner);
+      return new RemoveBranchManipulation(this, cloner);
     }
 
     protected override void Manipulate(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
-      ReplaceRandomBranch(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
+      RemoveRandomBranch(random, symbolicExpressionTree, MaximumSymbolicExpressionTreeLength.Value, MaximumSymbolicExpressionTreeDepth.Value);
     }
 
-    public static void ReplaceRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
+    public static void RemoveRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
       var allowedSymbols = new List<ISymbol>();
       ISymbolicExpressionTreeNode parent;
@@ -77 +77 @@
       // repeat until a fitting parent and child are found (MAX_TRIES times)
       int tries = 0;
+
+      var nodes = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).ToList();
       do {
-        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
+        parent = nodes.SelectRandom(random);
         childIndex = random.Next(parent.SubtreeCount);
         var child = parent.GetSubtree(childIndex);
@@ -97 +99 @@
       } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
 
-      if (tries < MAX_TRIES) {
-        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
-        var seedSymbol = allowedSymbols.SelectRandom(weights, random);
-        // replace the old node with the new node
-        var seedNode = seedSymbol.CreateTreeNode();
-        if (seedNode.HasLocalParameters)
-          seedNode.ResetLocalParameters(random);
+      if (tries >= MAX_TRIES) return;
+      ReplaceWithMinimalTree(random, symbolicExpressionTree.Root, parent, childIndex);
+    }
 
-        parent.RemoveSubtree(childIndex);
-        parent.InsertSubtree(childIndex, seedNode);
-        ProbabilisticTreeCreator.PTC2(random, seedNode, maxLength, maxDepth);
+    private static void ReplaceWithMinimalTree(IRandom random, ISymbolicExpressionTreeNode root, ISymbolicExpressionTreeNode parent, int childIndex) {
+      // determine possible symbols that will lead to the smallest possible tree
+      var possibleSymbols = (from s in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)
+                             where s.InitialFrequency > 0.0
+                             group s by parent.Grammar.GetMinimumExpressionLength(s) into g
+                             orderby g.Key
+                             select g).First().ToList();
+      var weights = possibleSymbols.Select(x => x.InitialFrequency).ToList();
+      var selectedSymbol = possibleSymbols.SelectRandom(weights, random);
+      var newTreeNode = selectedSymbol.CreateTreeNode();
+      if (newTreeNode.HasLocalParameters) newTreeNode.ResetLocalParameters(random);
+      parent.RemoveSubtree(childIndex);
+      parent.InsertSubtree(childIndex, newTreeNode);
+
+      var topLevelNode = newTreeNode as SymbolicExpressionTreeTopLevelNode;
+      if (topLevelNode != null)
+        topLevelNode.SetGrammar((ISymbolicExpressionTreeGrammar)root.Grammar.Clone());
+
+      for (int i = 0; i < newTreeNode.Grammar.GetMinimumSubtreeCount(newTreeNode.Symbol); i++) {
+        // insert a dummy sub-tree and add the pending extension to the list
+        var dummy = new SymbolicExpressionTreeNode();
+        newTreeNode.AddSubtree(dummy);
+        // replace the just inserted dummy by recursive application
+        ReplaceWithMinimalTree(random, root, newTreeNode, i);
       }
     }