Changeset 5014 for trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3

Timestamp:

12/03/10 14:11:02 (13 years ago)

Author:

mkommend

Message:

Corrected SubTreeCrossover and ReplaceBranchManipulation to handle MaxExpressionDepth correctly. Additionally MaxExpressionDepth < 3 is not allowed.
(ticket #1315).

Location:

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3

Files:

• Crossovers/SubtreeCrossover.cs (modified) (1 diff)
• Manipulators/ReplaceBranchManipulation.cs (modified) (2 diffs)
• SymbolicExpressionTreeNode.cs (modified) (1 diff)

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/SubtreeCrossover.cs

@@ -66 +66 @@
       SymbolicExpressionTreeNode crossoverPoint0;
       int replacedSubtreeIndex;
-      SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, maxTreeSize - 1, maxTreeHeight - 1, out crossoverPoint0, out replacedSubtreeIndex);
+      SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, maxTreeSize, maxTreeHeight, out crossoverPoint0, out replacedSubtreeIndex);
 
       // calculate the max size and height that the inserted branch can have 

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Manipulators/ReplaceBranchManipulation.cs

@@ -53 +53 @@
                                from subtree in parent.SubTrees
                                select new { Parent = parent, Node = subtree, Index = parent.SubTrees.IndexOf(subtree) }).SelectRandom(random);
+
+      int maxSize = maxTreeSize - symbolicExpressionTree.Size + manipulationPoint.Node.GetSize();
+      int maxHeight = maxTreeHeight - symbolicExpressionTree.Height + manipulationPoint.Node.GetHeight();
       // find possible symbols for the node (also considering the existing branches below it)
-      var allowedSymbols = from symbol in manipulationPoint.Parent.GetAllowedSymbols(manipulationPoint.Index)
+      var allowedSymbols = from symbol in manipulationPoint.Parent.GetAllowedSymbols(manipulationPoint.Index, maxHeight)
                            select symbol;
+      if (allowedSymbols.Count() <= 1) return;
 
-      if (allowedSymbols.Count() <= 1) {
-        return;
-      }
-      var oldBranch = manipulationPoint.Node;
-      int oldBranchSize = manipulationPoint.Node.GetSize();
-
-      var seedSymbol = SelectRandomSymbol(random, allowedSymbols);
-
-      // replace the old node with the new node
+      var seedSymbol = SelectRandomSymbol(random, allowedSymbols);  // replace the old node with the new node
       var seedNode = seedSymbol.CreateTreeNode();
       if (seedNode.HasLocalParameters)
@@ -72 +68 @@
       manipulationPoint.Parent.RemoveSubTree(manipulationPoint.Index);
       manipulationPoint.Parent.InsertSubTree(manipulationPoint.Index, seedNode);
-      int maxSize = Math.Max(oldBranchSize, seedNode.Grammar.GetMinExpressionLength(seedNode.Symbol)) * 2;
-      var bla = ProbabilisticTreeCreator.PTC2(random, seedNode, maxSize, maxSize, 0, 0);
+      seedNode = ProbabilisticTreeCreator.PTC2(random, seedNode, maxSize, maxHeight, 0, 0);
       success = true;
     }

trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

@@ -178 +178 @@
       return Grammar.Symbols.Where(s => Grammar.IsAllowedChild(Symbol, s, argumentIndex));
     }
+    public IEnumerable<Symbol> GetAllowedSymbols(int argumentIndex, int maxExpressionDepth) {
+      return Grammar.Symbols.Where(s => Grammar.IsAllowedChild(Symbol, s, argumentIndex) && Grammar.GetMinExpressionDepth(s) <= maxExpressionDepth);
+    }
+
     public int GetMinSubtreeCount() {
       return Grammar.GetMinSubtreeCount(Symbol);