Changeset 9083 for branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators

Timestamp:

12/20/12 16:24:54 (12 years ago)

Author:

bburlacu

Message:

#1772: Merged HeuristicLab.Encodings.SymbolicExpressionTreeEncoding from trunk. Added Fragment class implementing IFragment interface.

Location:

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding

Files:

• . (modified) (1 prop)
• 3.4/Manipulators/ChangeNodeTypeManipulation.cs (modified) (3 diffs)
• 3.4/Manipulators/MultiSymbolicExpressionTreeManipulator.cs (modified) (5 diffs)
• 3.4/Manipulators/OnePointShaker.cs (modified) (2 diffs)
• 3.4/Manipulators/RemoveBranchManipulation.cs (copied) (copied from trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/RemoveBranchManipulation.cs)
• 3.4/Manipulators/ReplaceBranchManipulation.cs (modified) (3 diffs)
• 3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs (modified) (4 diffs)

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ChangeNodeTypeManipulation.cs

@@ -24 +24 @@
 using HeuristicLab.Core;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
@@ -29 +30 @@
   [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol.")]
   public sealed class ChangeNodeTypeManipulation : TracingSymbolicExpressionTreeManipulator {
+    private const int MAX_TRIES = 100;
+
     [StorableConstructor]
     private ChangeNodeTypeManipulation(bool deserializing) : base(deserializing) { }
@@ -43 +46 @@
 
     public static void ChangeNodeType(IRandom random, ISymbolicExpressionTree symbolicExpressionTree) {
-      // select any node as parent (except the root node)
-      var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
-                                let subtreeCount = parent.Subtrees.Count()
-                                from subtreeIndex in Enumerable.Range(0, subtreeCount)
-                                let subtree = parent.GetSubtree(subtreeIndex)
-                                let existingSubtreeCount = subtree.Subtrees.Count()
-                                // find possible symbols for the node (also considering the existing branches below it)
-                                let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)
-                                                      // do not replace the existing symbol with itself
-                                                      where symbol.Name != subtree.Symbol.Name
-                                                      where symbol.InitialFrequency > 0
-                                                      where existingSubtreeCount <= parent.Grammar.GetMaximumSubtreeCount(symbol)
-                                                      where existingSubtreeCount >= parent.Grammar.GetMinimumSubtreeCount(symbol)
-                                                      // keep only symbols that are still possible considering the existing sub-trees
-                                                      where (from existingSubtreeIndex in Enumerable.Range(0, existingSubtreeCount)
-                                                             let existingSubtree = subtree.GetSubtree(existingSubtreeIndex)
-                                                             select parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex))
-                                                             .All(x => x == true)
-                                                      select symbol)
-                                                      .ToList()
-                                where allowedSymbols.Count() > 0
-                                select new { Parent = parent, Child = subtree, Index = subtreeIndex, AllowedSymbols = allowedSymbols })
-                               .ToList();
-      if (manipulationPoints.Count == 0) { return; }
-      var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
+      List<ISymbol> allowedSymbols = new List<ISymbol>();
+      ISymbolicExpressionTreeNode parent;
+      int childIndex;
+      ISymbolicExpressionTreeNode child;
+      // repeat until a fitting parent and child are found (MAX_TRIES times)
+      int tries = 0;
+      do {
+        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
+        childIndex = random.Next(parent.SubtreeCount);
 
-      var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
-      var newSymbol = selectedManipulationPoint.AllowedSymbols.SelectRandom(weights, random);
+        child = parent.GetSubtree(childIndex);
+        int existingSubtreeCount = child.SubtreeCount;
+        allowedSymbols.Clear();
+        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
+          // check basic properties that the new symbol must have
+          if (symbol.Name != child.Symbol.Name &&
+            symbol.InitialFrequency > 0 &&
+            existingSubtreeCount <= parent.Grammar.GetMinimumSubtreeCount(symbol) &&
+            existingSubtreeCount >= parent.Grammar.GetMaximumSubtreeCount(symbol)) {
+            // check that all existing subtrees are also allowed for the new symbol
+            bool allExistingSubtreesAllowed = true;
+            for (int existingSubtreeIndex = 0; existingSubtreeIndex < existingSubtreeCount && allExistingSubtreesAllowed; existingSubtreeIndex++) {
+              var existingSubtree = child.GetSubtree(existingSubtreeIndex);
+              allExistingSubtreesAllowed &= parent.Grammar.IsAllowedChildSymbol(symbol, existingSubtree.Symbol, existingSubtreeIndex);
+            }
+            if (allExistingSubtreesAllowed) {
+              allowedSymbols.Add(symbol);
+            }
+          }
+        }
+        tries++;
+      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
 
-      // replace the old node with the new node
-      var newNode = newSymbol.CreateTreeNode();
-      if (newNode.HasLocalParameters)
-        newNode.ResetLocalParameters(random);
-      foreach (var subtree in selectedManipulationPoint.Child.Subtrees)
-        newNode.AddSubtree(subtree);
-      selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);
-      selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, newNode);
+      if (tries < MAX_TRIES) {
+        var weights = allowedSymbols.Select(s => s.InitialFrequency).ToList();
+        var newSymbol = allowedSymbols.SelectRandom(weights, random);
+
+        // replace the old node with the new node
+        var newNode = newSymbol.CreateTreeNode();
+        if (newNode.HasLocalParameters)
+          newNode.ResetLocalParameters(random);
+        foreach (var subtree in child.Subtrees)
+          newNode.AddSubtree(subtree);
+        parent.RemoveSubtree(childIndex);
+        parent.InsertSubtree(childIndex, newNode);
+      }
     }
   }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/MultiSymbolicExpressionTreeManipulator.cs

@@ -37 +37 @@
   [StorableClass]
   public sealed class MultiSymbolicExpressionTreeManipulator : StochasticMultiBranch<ISymbolicExpressionTreeManipulator>,
+    ITracingSymbolicExpressionTreeOperator,
     ISymbolicExpressionTreeManipulator,
     IStochasticOperator,
@@ -43 +44 @@
     private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
     private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
+    private const string SymbolicExpressionTreeNodeComparerParameterName = "SymbolicExpressionTreeNodeComparer";
+    private const string SymbolicExpressionTreeNodeComparerParameterDescription = "The comparison operator used to check if two symbolic expression tree nodes are equal or similar.";
 
     public override bool CanChangeName {
@@ -49 +52 @@
     protected override bool CreateChildOperation {
       get { return true; }
+    }
+    public ValueParameter<ISymbolicExpressionTreeNodeComparer> SymbolicExpressionTreeNodeComparerParameter {
+      get { return (ValueParameter<ISymbolicExpressionTreeNodeComparer>)Parameters[SymbolicExpressionTreeNodeComparerParameterName]; }
+    }
+    public ISymbolicExpressionTreeNodeComparer SymbolicExpressionTreeNodeComparer {
+      get { return (ISymbolicExpressionTreeNodeComparer)SymbolicExpressionTreeNodeComparerParameter.ActualValue; }
     }
 
@@ -71 +80 @@
       Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximal length (number of nodes) of the symbolic expression tree."));
       Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximal depth of the symbolic expression tree (a tree with one node has depth = 0)."));
+      Parameters.Add(new ValueParameter<ISymbolicExpressionTreeNodeComparer>(SymbolicExpressionTreeNodeComparerParameterName, SymbolicExpressionTreeNodeComparerParameterDescription));
 
       List<ISymbolicExpressionTreeManipulator> list = new List<ISymbolicExpressionTreeManipulator>();
@@ -110 +120 @@
         manipulator.MaximumSymbolicExpressionTreeLengthParameter.ActualName = MaximumSymbolicExpressionTreeLengthParameter.Name;
       }
+      var comparers = ApplicationManager.Manager.GetInstances<ISymbolicExpressionTreeNodeComparer>().ToList();
+      if (comparers.Count > 0)
+        foreach (var manipulator in Operators.OfType<ITracingSymbolicExpressionTreeOperator>()) {
+          manipulator.SymbolicExpressionTreeNodeComparerParameter.ActualValue = comparers.First();
+        }
     }
   }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/OnePointShaker.cs

@@ -57 +57 @@
 
     protected override void Manipulate(IRandom random, ISymbolicExpressionTree tree) {
+      OnePointShaker.Shake(random, tree, ShakingFactor);
+    }
+
+    public static void Shake(IRandom random, ISymbolicExpressionTree tree, double shakingFactor) {
       List<ISymbolicExpressionTreeNode> parametricNodes = new List<ISymbolicExpressionTreeNode>();
       tree.Root.ForEachNodePostfix(n => {
@@ -63 +67 @@
       if (parametricNodes.Count > 0) {
         var selectedPoint = parametricNodes.SelectRandom(random);
-        selectedPoint.ShakeLocalParameters(random, ShakingFactor);
+        selectedPoint.ShakeLocalParameters(random, shakingFactor);
       }
     }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/ReplaceBranchManipulation.cs

@@ -26 +26 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System.Collections.Generic;
 
 namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
@@ -31 +32 @@
   [Item("ReplaceBranchManipulation", "Selects a branch of the tree randomly and replaces it with a newly initialized branch (using PTC2).")]
   public sealed class ReplaceBranchManipulation : TracingSymbolicExpressionTreeManipulator, ISymbolicExpressionTreeSizeConstraintOperator {
+    private const int MAX_TRIES = 100;
     private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
     private const string MaximumSymbolicExpressionTreeDepthParameterName = "MaximumSymbolicExpressionTreeDepth";
@@ -68 +70 @@
 
     public static void ReplaceRandomBranch(IRandom random, ISymbolicExpressionTree symbolicExpressionTree, int maxTreeLength, int maxTreeDepth) {
-      // select any node as parent (except the root node)
-      var manipulationPoints = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
-                                from subtree in parent.Subtrees
-                                let subtreeIndex = parent.IndexOfSubtree(subtree)
-                                let maxLength = maxTreeLength - symbolicExpressionTree.Length + subtree.GetLength()
-                                let maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + subtree.GetDepth()
-                                // find possible symbols for the node (also considering the existing branches below it)
-                                let allowedSymbols = (from symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, subtreeIndex)
-                                                      // do not replace symbol with the same symbol
-                                                      where symbol.Name != subtree.Symbol.Name
-                                                      where symbol.InitialFrequency > 0
-                                                      where parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth
-                                                      where parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength
-                                                      select symbol)
-                                                      .ToList()
-                                where allowedSymbols.Count > 0
-                                select new {
-                                  Parent = parent,
-                                  Child = subtree,
-                                  Index = subtreeIndex,
-                                  AllowedSymbols = allowedSymbols,
-                                  MaxLength = maxLength,
-                                  MaxDepth = maxDepth
-                                })
-                               .ToList();
+      var allowedSymbols = new List<ISymbol>();
+      ISymbolicExpressionTreeNode parent;
+      int childIndex;
+      int maxLength;
+      int maxDepth;
+      // repeat until a fitting parent and child are found (MAX_TRIES times)
+      int tries = 0;
+      do {
+        parent = symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1).Where(n => n.SubtreeCount > 0).SelectRandom(random);
+        childIndex = random.Next(parent.SubtreeCount);
+        var child = parent.GetSubtree(childIndex);
+        maxLength = maxTreeLength - symbolicExpressionTree.Length + child.GetLength();
+        maxDepth = maxTreeDepth - symbolicExpressionTree.Depth + child.GetDepth();
 
-      if (manipulationPoints.Count == 0) return;
-      var selectedManipulationPoint = manipulationPoints.SelectRandom(random);
+        allowedSymbols.Clear();
+        foreach (var symbol in parent.Grammar.GetAllowedChildSymbols(parent.Symbol, childIndex)) {
+          // check basic properties that the new symbol must have
+          if (symbol.Name != child.Symbol.Name &&
+            symbol.InitialFrequency > 0 &&
+            parent.Grammar.GetMinimumExpressionDepth(symbol) + 1 <= maxDepth &&
+            parent.Grammar.GetMinimumExpressionLength(symbol) <= maxLength) {
+            allowedSymbols.Add(symbol);
+          }
+        }
+        tries++;
+      } while (tries < MAX_TRIES && allowedSymbols.Count == 0);
 
-      var weights = selectedManipulationPoint.AllowedSymbols.Select(s => s.InitialFrequency).ToList();
-      var seedSymbol = selectedManipulationPoint.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) {
+        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);
 
-      selectedManipulationPoint.Parent.RemoveSubtree(selectedManipulationPoint.Index);
-      selectedManipulationPoint.Parent.InsertSubtree(selectedManipulationPoint.Index, seedNode);
-      ProbabilisticTreeCreator.PTC2(random, seedNode, selectedManipulationPoint.MaxLength, selectedManipulationPoint.MaxDepth);
+        parent.RemoveSubtree(childIndex);
+        parent.InsertSubtree(childIndex, seedNode);
+        ProbabilisticTreeCreator.PTC2(random, seedNode, maxLength, maxDepth);
+      }
     }
   }

branches/HeuristicLab.EvolutionaryTracking/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.4/Manipulators/TracingSymbolicExpressionTreeManipulator.cs

@@ -25 +25 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.EvolutionaryTracking;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -37 +36 @@
   public abstract class TracingSymbolicExpressionTreeManipulator : TracingSymbolicExpressionTreeOperator, ISymbolicExpressionTreeManipulator {
     private const string SymbolicExpressionTreeParameterName = "SymbolicExpressionTree";
+    [Storable]
+    private readonly Dictionary<Type, byte> manipulationTypes = new Dictionary<Type, byte>();
 
     #region Parameter Properties
@@ -52 +53 @@
     [StorableConstructor]
     protected TracingSymbolicExpressionTreeManipulator(bool deserializing) : base(deserializing) { }
-    protected TracingSymbolicExpressionTreeManipulator(TracingSymbolicExpressionTreeManipulator original, Cloner cloner) : base(original, cloner) { }
+    protected TracingSymbolicExpressionTreeManipulator(TracingSymbolicExpressionTreeManipulator original, Cloner cloner)
+      : base(original, cloner) {
+      this.manipulationTypes = new Dictionary<Type, byte>(original.manipulationTypes);
+    }
     public TracingSymbolicExpressionTreeManipulator()
       : base() {
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName, "The symbolic expression tree on which the operator should be applied."));
+
+      manipulationTypes.Add(typeof(FullTreeShaker), ManipulationType.FullTreeShaker);
+      manipulationTypes.Add(typeof(OnePointShaker), ManipulationType.OnePointShaker);
+      manipulationTypes.Add(typeof(ChangeNodeTypeManipulation), ManipulationType.ChangeNodeTypeManipulation);
+      manipulationTypes.Add(typeof(ReplaceBranchManipulation), ManipulationType.ReplaceBranchManipulation);
     }
 
@@ -72 +81 @@
        * - After tree is mutated, we set GlobalTraceMap[tree] = clone and GlobalFragmentMap[tree] = modified node from tree
        */
-      ISymbolicExpressionTreeNode fragment;
+      Fragment fragment = null;
       if (GlobalTraceMap.ContainsKey(tree)) {
-        var clone = (IItem)tree.Clone(); // create clone of tree
+        var clone = (IItem)tree.Clone();
+        GlobalCloneMap[clone] = GlobalCloneMap[tree];
+        GlobalCloneMap[tree] = clone;
         GlobalTraceMap[clone] = GlobalTraceMap[tree]; // clone gets parents of tree
         GlobalTraceMap[tree] = new ItemList<IItem> { clone }; // tree gets clone as parent
-        fragment = ((GenericWrapper<ISymbolicExpressionTreeNode>)GlobalFragmentMap[tree]).Content;
-        int index = tree.IterateNodesBreadth().ToList().IndexOf(fragment); // returns -1 if fragment is not present in tree
-        GlobalFragmentMap[clone] = new GenericWrapper<ISymbolicExpressionTreeNode>(index == -1 ? null : ((ISymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(index));
+        fragment = (Fragment)GlobalFragmentMap[tree];
+        int index = tree.IterateNodesBreadth().ToList().IndexOf(fragment.Root); // returns -1 if fragment is not present in tree (can happen if fragment is null)
+        GlobalFragmentMap[clone] = new Fragment(index == -1 ? null : ((ISymbolicExpressionTree)clone).IterateNodesBreadth().ElementAt(index));
       } else {
         GlobalTraceMap[tree] = new ItemList<IItem> { GlobalCloneMap[tree] };
       }
 
-      var original = GlobalCloneMap[tree];
-      var nodes0 = ((ISymbolicExpressionTree)original).IterateNodesBreadth().ToList();
+      var concreteType = this.GetType();
 
-      // perform mutation
+      if (!manipulationTypes.ContainsKey(concreteType))
+        throw new Exception(this.Name + ": Unknown manipulation type (key not found in the dictionary).");
+
+      var nodes0 = tree.IterateNodesBreadth().ToList(); // list of nodes before manipulation
       Manipulate(RandomParameter.ActualValue, tree);
+      var nodes1 = tree.IterateNodesBreadth().ToList(); // list of nodes after manipulation
+      int min = Math.Min(nodes0.Count, nodes1.Count);
 
-      var nodes1 = tree.IterateNodesBreadth().ToList();
+      switch (manipulationTypes[concreteType]) {
+        case ManipulationType.FullTreeShaker: {
+            // the FullTreeShaker changes the local parameters of all the nodes in the tree
+            // therefore, the whole tree is considered to be the fragment
+            fragment = new Fragment(tree.Root.GetSubtree(0).GetSubtree(0));
+            break;
+          }
+        case ManipulationType.OnePointShaker: {
+            var original = (ISymbolicExpressionTree)GlobalCloneMap[tree];
+            var nodesOriginal = original.IterateNodesBreadth().ToList();
+            int i = 0;
+            var comparer = SymbolicExpressionTreeNodeComparer;
+            while (i != min && comparer.Equals(nodesOriginal[i], nodes1[i])) ++i;
+            fragment = new Fragment(i == min ? null : nodes1[i], 1);
+            break;
+          }
+        case ManipulationType.ChangeNodeTypeManipulation: {
+            int i = 0;
+            while (i != min && ReferenceEquals(nodes0[i], nodes1[i])) ++i;
+            fragment = new Fragment(i == min ? null : nodes1[i], 1);
+            break;
+          }
+        case ManipulationType.ReplaceBranchManipulation: {
+            int i = 0;
+            while (i != min && ReferenceEquals(nodes0[i], nodes1[i])) ++i;
+            fragment = new Fragment(i == min ? null : nodes1[i]);
+            break;
+          }
+        default:
+          throw new Exception(Name + ": Unknown manipulaton type.");
+      }
 
-      int min = Math.Min(nodes0.Count, nodes1.Count);
-      // some tree manipulators only change local parameters while the actual node stays the same
-      // consequently, we need a stronger comparison than ReferenceEquals
-      var comp = SymbolicExpressionTreeNodeComparer;
-      if (comp == null)
-        throw new Exception(Name + ": Could not get SymbolicExpressionTreeNodeComparerParameter!");
-      var mismatches = new List<int>();
-      for (int i = 0; i != min; ++i) {
-        if (!comp.Equals(nodes0[i], nodes1[i])) {
-          mismatches.Add(i);
-        }
-      }
-      if (mismatches.Count == 0) // should never happen
-        fragment = null;
-      else
-        fragment = mismatches.Count > 1 ? nodes1[mismatches[0]].Parent : nodes1[mismatches[0]];
-      GlobalFragmentMap[tree] = new GenericWrapper<ISymbolicExpressionTreeNode>(fragment);
+      GlobalFragmentMap[tree] = fragment;
       return base.Apply();
     }
 
     protected abstract void Manipulate(IRandom random, ISymbolicExpressionTree symbolicExpressionTree);
+
+    private struct ManipulationType {
+      public const byte FullTreeShaker = 1;
+      public const byte OnePointShaker = 2;
+      public const byte ChangeNodeTypeManipulation = 3;
+      public const byte ReplaceBranchManipulation = 4;
+    }
   }
 }