Changeset 3237 for trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers

Timestamp:

03/30/10 19:38:22 (15 years ago)

Author:

gkronber

Message:

Worked on symbolic expression tree encoding.
Added view for expression trees (simple textual view in s-exp format).
Implemented SubtreeCrossover.
Fixed bugs in ProbabilisticTreeCreator.
#937 (Data types and operators for symbolic expression tree encoding)

Location:

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

Files:

• GPCrossoverBase.cs (deleted)
• SubtreeCrossover.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/StandardCrossOver.cs) (2 diffs)

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

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -22 +22 @@
 using System.Collections.Generic;
 using HeuristicLab.Core;
-using HeuristicLab.GP.Interfaces;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Data;
+using System.Linq;
+using System;
+using HeuristicLab.Parameters;
+namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
 
-namespace HeuristicLab.Encodings.SymbolicExpressionTree {
-  public class StandardCrossOver : SizeConstrictedGPCrossoverBase {
-    private int MaxRecombinationTries { get { return 20; } }
 
-    public override string Description {
-      get {
-        return @"Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.
-And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
-When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1 
-until a valid configuration is found.";
+  /// <summary>
+  /// Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.
+  /// And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
+  /// When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1 
+  /// until a valid configuration is found.
+  /// </summary>  
+  [Item("SubtreeCrossover", "An operator which performs subtree swapping crossover.")]
+  [StorableClass]
+  public class SubtreeCrossover : SymbolicExpressionTreeCrossover {
+    private const int MAX_TRIES = 100;
+
+    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
+      get { return (IValueLookupParameter<PercentValue>)Parameters["InternalCrossoverPointProbability"]; }
+    }
+
+    public SubtreeCrossover()
+      : base() {
+      Parameters.Add(new ValueLookupParameter<PercentValue>("InternalCrossoverPointProbability", "The probability to select an internal crossover point (instead of a leaf node).", new PercentValue(0.9)));
+    }
+
+    protected override SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
+      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
+      IntValue maxTreeSize, IntValue maxTreeHeight) {
+      return Apply(random, grammar, parent0, parent1, InternalCrossoverPointProbabilityParameter.ActualValue.Value, maxTreeSize.Value, maxTreeHeight.Value);
+    }
+
+    public static SymbolicExpressionTree Apply(IRandom random, ISymbolicExpressionGrammar grammar,
+      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
+      double internalCrossoverPointProbability, int maxTreeSize, int maxTreeHeight) {
+      int tries = 0;
+      while (tries++ < MAX_TRIES) {
+        // select a random crossover point in the first parent 
+        SymbolicExpressionTreeNode crossoverPoint0;
+        int replacedSubtreeIndex;
+        SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, out crossoverPoint0, out replacedSubtreeIndex);
+
+        // calculate the max size and height that the inserted branch can have 
+        int maxInsertedBranchSize = maxTreeSize - (parent0.Size - crossoverPoint0.SubTrees[replacedSubtreeIndex].GetSize());
+        int maxInsertedBranchHeight = maxTreeHeight - GetBranchLevel(parent0.Root, crossoverPoint0);
+
+        var allowedBranches = from branch in IterateNodes(parent1.Root)
+                              where branch.GetSize() < maxInsertedBranchSize
+                              where branch.GetHeight() < maxInsertedBranchHeight
+                              where grammar.AllowedSymbols(crossoverPoint0.Symbol, replacedSubtreeIndex).Contains(branch.Symbol)
+                              select branch;
+
+        if (allowedBranches.Count() > 0) {
+          var selectedBranch = SelectRandomBranch(random, allowedBranches, internalCrossoverPointProbability);
+
+          // manipulate the tree of parent0 in place
+          // replace the branch in tree0 with the selected branch from tree1
+          crossoverPoint0.RemoveSubTree(replacedSubtreeIndex);
+          crossoverPoint0.InsertSubTree(replacedSubtreeIndex, selectedBranch);
+          return parent0;
+        }
+      }
+
+      // TODO: we should have a way to track the number of failed crossover attempts
+      // for now just return the first parent unchanged
+      return parent0;
+    }
+
+    private static void SelectCrossoverPoint(IRandom random, SymbolicExpressionTree parent0, double internalNodeProbability, out SymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) {
+      var crossoverPoints = from branch in IterateNodes(parent0.Root)
+                            where branch.SubTrees.Count > 0
+                            from index in Enumerable.Range(0, branch.SubTrees.Count)
+                            let p = new { CrossoverPoint = branch, SubtreeIndex = index, IsLeaf = branch.SubTrees[index].SubTrees.Count == 0 }
+                            select p;
+      var internalCrossoverPoints = (from p in crossoverPoints
+                                     where !p.IsLeaf
+                                     select p).ToList();
+      // select internal crossover point or leaf
+      if (random.NextDouble() < internalNodeProbability && internalCrossoverPoints.Count > 0) {
+        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
+        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
+        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
+      } else {
+        var leafCrossoverPoints = (from p in crossoverPoints
+                                   where p.IsLeaf
+                                   select p).ToList();
+        var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
+        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
+        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
       }
     }
 
-    internal override IFunctionTree Cross(TreeGardener gardener, IRandom random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
-      int tries = 0;
-      List<IFunctionTree> allowedCrossoverPoints = null;
-      IFunctionTree parent0;
-      int replacedChildIndex;
-      do {
-        // select a random crossover point in the first parent tree0
-        parent0 = null;
-        while (parent0 == null) parent0 = gardener.GetRandomParentNode(tree0);
-        // select a random branch to replace
-        replacedChildIndex = random.Next(parent0.SubTrees.Count);
-
-        // calculate the max size and height that the inserted branch can have 
-        int maxInsertedBranchSize = maxTreeSize - (tree0.GetSize() - parent0.SubTrees[replacedChildIndex].GetSize());
-        int maxInsertedBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, parent0); // branchlevel is 1 if tree0==parent0
-
-        IList<IFunction> allowedFunctions = new List<IFunction>(gardener.GetAllowedSubFunctions(parent0.Function, replacedChildIndex));
-        allowedCrossoverPoints = GetPossibleCrossoverPoints(tree1, maxInsertedBranchSize, maxInsertedBranchHeight, allowedFunctions);
-      } while (allowedCrossoverPoints.Count == 0 && tries++ < MaxRecombinationTries);
-
-      if (allowedCrossoverPoints.Count > 0) {
-        IFunctionTree branch1 = allowedCrossoverPoints[random.Next(allowedCrossoverPoints.Count)];
-
-        // replace the branch in tree0 with the selected branch from tree1
-        parent0.RemoveSubTree(replacedChildIndex);
-        parent0.InsertSubTree(replacedChildIndex, branch1);
+    private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<SymbolicExpressionTreeNode> branches, double internalNodeProbability) {
+      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
+      var groupedBranches = from branch in branches
+                            group branch by branch.SubTrees.Count into g
+                            select g;
+      var allowedInternalBranches = (from g in groupedBranches
+                                     where g.Key > 0
+                                     from branch in g
+                                     select branch).ToList();
+      if (random.NextDouble() < internalNodeProbability && allowedInternalBranches.Count > 0) {
+        return allowedInternalBranches[random.Next(allowedInternalBranches.Count)];
+      } else {
+        var allowedLeafBranches = (from g in groupedBranches
+                                   where g.Key == 0
+                                   from leaf in g
+                                   select leaf).ToList();
+        return allowedLeafBranches[random.Next(allowedLeafBranches.Count)];
       }
-      return tree0;
     }
 
-    private List<IFunctionTree> GetPossibleCrossoverPoints(IFunctionTree tree, int maxInsertedBranchSize, int maxInsertedBranchHeight, IList<IFunction> allowedFunctions) {
-      List<IFunctionTree> crossoverPoints = new List<IFunctionTree>();
-      foreach (IFunctionTree possiblePoint in TreeGardener.GetAllSubTrees(tree)) {
-        if (allowedFunctions.Contains(possiblePoint.Function) && possiblePoint.GetSize() <= maxInsertedBranchSize && possiblePoint.GetHeight() <= maxInsertedBranchHeight)
-          crossoverPoints.Add(possiblePoint);
+    private static IEnumerable<SymbolicExpressionTreeNode> IterateNodes(SymbolicExpressionTreeNode root) {
+      foreach (var subTree in root.SubTrees) {
+        foreach (var branch in IterateNodes(subTree)) {
+          yield return branch;
+        }
       }
-      return crossoverPoints;
+      yield return root;
+    }
+
+    private static int GetBranchLevel(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode point) {
+      if (root == point) return 0;
+      foreach (var subtree in root.SubTrees) {
+        int branchLevel = GetBranchLevel(subtree, point);
+        if (branchLevel < int.MaxValue) return 1 + branchLevel;
+      }
+      return int.MaxValue;
     }
   }