Changeset 7075

Timestamp:

11/25/11 11:41:48 (12 years ago)

Author:

bburlacu

Message:

#1682: Updated crossovers

Location:

branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4

Files:

• Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs (modified) (1 diff)
• Crossovers/SymbolicDataAnalysisExpressionCrossover.cs (modified) (5 diffs)
• Crossovers/SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover.cs (modified) (5 diffs)
• Crossovers/SymbolicDataAnalysisExpressionSemanticSimilarityCrossover.cs (modified) (5 diffs)
• Interfaces/ISymbolicDataAnalysisExpressionCrossover.cs (modified) (1 diff)

branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionContextAwareCrossover.cs

@@ -88 +88 @@
 
       // create symbols in order to improvize an ad-hoc tree so that the child can be evaluated
-      var rootSymbol = new ProgramRootSymbol();
-      var startSymbol = new StartSymbol();
-
       ISymbolicExpressionTreeNode selectedBranch = null;
 

branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionCrossover.cs

@@ -33 +33 @@
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  public abstract class SymbolicDataAnalysisExpressionCrossover<T> : SymbolicExpressionTreeCrossover where T : class, IDataAnalysisProblemData {
+  public abstract class SymbolicDataAnalysisExpressionCrossover<T> : SymbolicExpressionTreeCrossover, ISymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData {
     private const string RandomParameterName = "Random";
     private const string SymbolicDataAnalysisTreeInterpreterParameterName = "SymbolicExpressionTreeInterpreter";
     private const string ProblemDataParameterName = "ProblemData";
     private const string EstimationLimitsParameterName = "EstimationLimits";
-    private const string EvaluationPartitionParameterName = "EvaluationPartition";
+    private const string EvaluatorParameterName = "Evaluator";
+    private const string SymbolicDataAnalysisEvaluationPartitionParameterName = "EvaluationPartition";
     private const string RelativeNumberOfEvaluatedSamplesParameterName = "RelativeNumberOfEvaluatedSamples";
     private const string MaximumSymbolicExpressionTreeLengthParameterName = "MaximumSymbolicExpressionTreeLength";
@@ -52 +53 @@
       get { return (IValueLookupParameter<T>)Parameters[ProblemDataParameterName]; }
     }
-    public IValueLookupParameter<IntRange> EvaluationPartitionParameter {
-      get { return (IValueLookupParameter<IntRange>)Parameters[EvaluationPartitionParameterName]; }
+    public ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<T>> EvaluatorParameter {
+      get { return (ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<T>>) Parameters[EvaluatorParameterName]; }
+    }
+    public IValueLookupParameter<IntRange> SymbolicDataAnalysisEvaluationPartitionParameter {
+      get { return (IValueLookupParameter<IntRange>)Parameters[SymbolicDataAnalysisEvaluationPartitionParameterName]; }
     }
     public IValueLookupParameter<DoubleLimit> EstimationLimitsParameter {
@@ -86 +90 @@
       : base() {
       Parameters.Add(new LookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>(SymbolicDataAnalysisTreeInterpreterParameterName, "The interpreter that should be used to calculate the output values of the symbolic data analysis tree."));
+      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<T>>(EvaluatorParameterName, "The single objective solution evaluator"));
       Parameters.Add(new ValueLookupParameter<T>(ProblemDataParameterName, "The problem data on which the symbolic data analysis solution should be evaluated."));
-      Parameters.Add(new ValueLookupParameter<IntRange>(EvaluationPartitionParameterName, "The start index of the dataset partition on which the symbolic data analysis solution should be evaluated."));
+      Parameters.Add(new ValueLookupParameter<IntRange>(SymbolicDataAnalysisEvaluationPartitionParameterName, "The start index of the dataset partition on which the symbolic data analysis solution should be evaluated."));
       Parameters.Add(new ValueLookupParameter<DoubleLimit>(EstimationLimitsParameterName, "The upper and lower limit that should be used as cut off value for the output values of symbolic data analysis trees."));
       Parameters.Add(new ValueLookupParameter<PercentValue>(RelativeNumberOfEvaluatedSamplesParameterName, "The relative number of samples of the dataset partition, which should be randomly chosen for evaluation between the start and end index."));
+      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeDepthParameterName, "The maximum tree depth."));
+      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumSymbolicExpressionTreeLengthParameterName, "The maximum tree length."));
     }
 
@@ -100 +107 @@
     /// <param name="startSymbol"></param>
     /// <returns></returns>
-    protected static ISymbolicExpressionTree CreateTreeFromNode(IRandom random, ISymbolicExpressionTreeNode node, ProgramRootSymbol rootSymbol, StartSymbol startSymbol) {
-      ISymbolicExpressionTreeNode rootNode = rootSymbol.CreateTreeNode();
+    protected static ISymbolicExpressionTree CreateTreeFromNode(IRandom random, ISymbolicExpressionTreeNode node, ISymbolicExpressionGrammar grammar) {
+      SymbolicExpressionTree tree = new SymbolicExpressionTree();
+      var rootNode = (SymbolicExpressionTreeTopLevelNode)grammar.ProgramRootSymbol.CreateTreeNode();
       if (rootNode.HasLocalParameters)
         rootNode.ResetLocalParameters(random);
-      ISymbolicExpressionTreeNode startNode = startSymbol.CreateTreeNode();
+      rootNode.SetGrammar((ISymbolicExpressionTreeGrammar)grammar);
+      var startNode = (SymbolicExpressionTreeTopLevelNode)grammar.StartSymbol.CreateTreeNode();
+      startNode.SetGrammar((ISymbolicExpressionTreeGrammar)grammar);
       if (startNode.HasLocalParameters)
         startNode.ResetLocalParameters(random);
       rootNode.AddSubtree(startNode);
-      startNode.AddSubtree(node);
+
+      rootNode.AddSubtree(startNode); 
+      if (startNode.Grammar.IsAllowedChildSymbol(startNode.Symbol, node.Symbol))
+        startNode.AddSubtree(node);
+      else
+        throw new InvalidOperationException("The given node cannot be a child of the start symbol.");
       return new SymbolicExpressionTree(rootNode);
     }
@@ -118 +133 @@
     protected IEnumerable<int> GenerateRowsToEvaluate(double percentageOfRows) {
       IEnumerable<int> rows;
-      int samplesStart = EvaluationPartitionParameter.ActualValue.Start;
-      int samplesEnd = EvaluationPartitionParameter.ActualValue.End;
+      int samplesStart = SymbolicDataAnalysisEvaluationPartitionParameter.ActualValue.Start;
+      int samplesEnd = SymbolicDataAnalysisEvaluationPartitionParameter.ActualValue.End;
       int testPartitionStart = ProblemDataParameter.ActualValue.TestPartition.Start;
       int testPartitionEnd = ProblemDataParameter.ActualValue.TestPartition.End;

branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover.cs

@@ -37 +37 @@
     [StorableConstructor]
     private SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover(bool deserializing) : base(deserializing) { }
-    private SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover(SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T> original, Cloner cloner)
-      : base(original, cloner) {
-    }
-    public SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover()
-      : base() {
-    }
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T>(this, cloner);
-    } 
+    private SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover(SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T> original, Cloner cloner) 
+      : base(original, cloner) { }
+    public SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover() : base() { }
+    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicDataAnalysisExpressionProbabilisticFunctionalCrossover<T>(this, cloner); }
+ 
     protected override ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
       ISymbolicDataAnalysisExpressionTreeInterpreter interpreter = SymbolicDataAnalysisTreeInterpreterParameter.ActualValue;
       IEnumerable<int> rows = GenerateRowsToEvaluate();
       T problemData = ProblemDataParameter.ActualValue;
-      return Cross(random, parent0, parent1, interpreter, problemData, rows, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value);
+      var grammar = parent0.Root.Grammar;
+      return Cross(random, parent0, parent1, interpreter, problemData, 
+                   rows, MaximumSymbolicExpressionTreeDepth.Value, MaximumSymbolicExpressionTreeLength.Value);
     }
 
@@ -60 +58 @@
     /// choose the second crosspoint via a random weighted selection procedure.
     /// </summary>
-    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
+    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, 
                                                 ISymbolicDataAnalysisExpressionTreeInterpreter interpreter, T problemData, IEnumerable<int> rows, int maxDepth, int maxLength) {
       List<CutPoint> crossoverPoints0 = new List<CutPoint>();
@@ -89 +87 @@
 
       // create symbols in order to improvize an ad-hoc tree so that the child can be evaluated
-      var rootSymbol = new ProgramRootSymbol();
-      var startSymbol = new StartSymbol();
-      var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, rootSymbol, startSymbol);
+      var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, (ISymbolicExpressionGrammar)parent0.Root.Grammar);
       IEnumerable<double> estimatedValues0 = interpreter.GetSymbolicExpressionTreeValues(tree0, dataset, rows);
       double min0 = estimatedValues0.Min();
@@ -98 +94 @@
       List<double> weights = new List<double>();
       foreach (var node in allowedBranches) {
-        var tree1 = CreateTreeFromNode(random, node, rootSymbol, startSymbol);
+        var tree1 = CreateTreeFromNode(random, node, (ISymbolicExpressionGrammar)parent0.Root.Grammar);
         IEnumerable<double> estimatedValues1 = interpreter.GetSymbolicExpressionTreeValues(tree1, dataset, rows);
         double min1 = estimatedValues1.Min();
@@ -109 +105 @@
 
       ISymbolicExpressionTreeNode selectedBranch = SelectRandomBranch(random, allowedBranches, weights);
+      swap(crossoverPoint0, selectedBranch);
 
-      // perform the actual swap
-      if (crossoverPoint0.Child != null) {
+      return parent0;
+    }
+
+    private static void swap(CutPoint crossoverPoint, ISymbolicExpressionTreeNode selectedBranch) {
+      if (crossoverPoint.Child != null) {
         // manipulate the tree of parent0 in place
         // replace the branch in tree0 with the selected branch from tree1
-        crossoverPoint0.Parent.RemoveSubtree(crossoverPoint0.ChildIndex);
+        crossoverPoint.Parent.RemoveSubtree(crossoverPoint.ChildIndex);
         if (selectedBranch != null) {
-          crossoverPoint0.Parent.InsertSubtree(crossoverPoint0.ChildIndex, selectedBranch);
+          crossoverPoint.Parent.InsertSubtree(crossoverPoint.ChildIndex, selectedBranch);
         }
       } else {
         // child is null (additional child should be added under the parent)
         if (selectedBranch != null) {
-          crossoverPoint0.Parent.AddSubtree(selectedBranch);
+          crossoverPoint.Parent.AddSubtree(selectedBranch);
         }
       }
-
-      return parent0;
     }
 

branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Crossovers/SymbolicDataAnalysisExpressionSemanticSimilarityCrossover.cs

@@ -32 +32 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
 
-  [Item("ProbabilisticFunctionalCrossover", "An operator which performs subtree swapping based on behavioral similarity")]
+  [Item("SemanticSimilarityCrossover", "An operator which performs subtree swapping based on semantic similarity.")]
   public sealed class SymbolicDataAnalysisExpressionSemanticSimilarityCrossover<T> : SymbolicDataAnalysisExpressionCrossover<T> where T : class, IDataAnalysisProblemData 
   {
     [StorableConstructor]
     private SymbolicDataAnalysisExpressionSemanticSimilarityCrossover(bool deserializing) : base(deserializing) { }
-    private SymbolicDataAnalysisExpressionSemanticSimilarityCrossover(SymbolicDataAnalysisExpressionSemanticSimilarityCrossover<T> original, Cloner cloner)
-      : base(original, cloner) {
-    }
-    public SymbolicDataAnalysisExpressionSemanticSimilarityCrossover()
-      : base() {
-    }
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new SymbolicDataAnalysisExpressionSemanticSimilarityCrossover<T>(this, cloner);
-    } 
+    private SymbolicDataAnalysisExpressionSemanticSimilarityCrossover(SymbolicDataAnalysisExpressionSemanticSimilarityCrossover<T> original, Cloner cloner) : base(original, cloner) { }
+    public SymbolicDataAnalysisExpressionSemanticSimilarityCrossover() : base() { }
+    public override IDeepCloneable Clone(Cloner cloner) { return new SymbolicDataAnalysisExpressionSemanticSimilarityCrossover<T>(this, cloner); }
+ 
     protected override ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
       ISymbolicDataAnalysisExpressionTreeInterpreter interpreter = SymbolicDataAnalysisTreeInterpreterParameter.ActualValue;
@@ -56 +51 @@
     /// Randomly choose a node i from the first parent, then get a node j from the second parent that matches the semantic similarity criteria.
     /// </summary>
-    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
+    public static ISymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1, 
                                                 ISymbolicDataAnalysisExpressionTreeInterpreter interpreter, T problemData, IEnumerable<int> rows, int maxDepth, int maxLength) {
       List<CutPoint> crossoverPoints0 = new List<CutPoint>();
@@ -82 +77 @@
         return parent0;
 
-     var dataset = problemData.Dataset;
+      var dataset = problemData.Dataset;
 
       // create symbols in order to improvize an ad-hoc tree so that the child can be evaluated
-      var rootSymbol = new ProgramRootSymbol();
-      var startSymbol = new StartSymbol();
-      var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, rootSymbol, startSymbol);
+      //var rootSymbol = new ProgramRootSymbol();
+      //var startSymbol = new StartSymbol();
+      var tree0 = CreateTreeFromNode(random, crossoverPoint0.Child, (ISymbolicExpressionGrammar)parent0.Root.Grammar);
       IEnumerable<double> estimatedValues0 = interpreter.GetSymbolicExpressionTreeValues(tree0, dataset, rows);
 
@@ -94 +89 @@
       // pick the first node that fulfills the semantic similarity conditions
       foreach (var node in allowedBranches) {
-        var tree1 = CreateTreeFromNode(random, node, rootSymbol, startSymbol);
+        var tree1 = CreateTreeFromNode(random, node, (ISymbolicExpressionGrammar)parent0.Root.Grammar);
         IEnumerable<double> estimatedValues1 = interpreter.GetSymbolicExpressionTreeValues(tree1, dataset, rows);
 
@@ -109 +104 @@
 
       // perform the actual swap
-      if (crossoverPoint0.Child != null) {
+      swap(crossoverPoint0, selectedBranch);
+
+      return parent0;
+    }
+
+    private static void swap(CutPoint crossoverPoint, ISymbolicExpressionTreeNode selectedBranch) {
+      // perform the actual swap
+      if (crossoverPoint.Child != null) {
         // manipulate the tree of parent0 in place
         // replace the branch in tree0 with the selected branch from tree1
-        crossoverPoint0.Parent.RemoveSubtree(crossoverPoint0.ChildIndex);
+        crossoverPoint.Parent.RemoveSubtree(crossoverPoint.ChildIndex);
         if (selectedBranch != null) {
-          crossoverPoint0.Parent.InsertSubtree(crossoverPoint0.ChildIndex, selectedBranch);
+          crossoverPoint.Parent.InsertSubtree(crossoverPoint.ChildIndex, selectedBranch);
         }
       } else {
         // child is null (additional child should be added under the parent)
         if (selectedBranch != null) {
-          crossoverPoint0.Parent.AddSubtree(selectedBranch);
+          crossoverPoint.Parent.AddSubtree(selectedBranch);
         }
       }
-      return parent0;
     }
+
   }
 }

branches/gp-crossover/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interfaces/ISymbolicDataAnalysisExpressionCrossover.cs

@@ -27 +27 @@
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
-  public interface ISymbolicDataAnalysisExpressionCrossover : INamedItem {
+  public interface ISymbolicDataAnalysisExpressionCrossover<T> : IOperator {
     IValueLookupParameter<IntRange> SymbolicDataAnalysisEvaluationPartitionParameter { get; }
   }