Changeset 4928 for branches/DataAnalysis.PopulationDiversityAnalysis

Timestamp:

11/25/10 00:22:15 (14 years ago)

Author:

swinkler

Message:

Worked on structural population diversity analysis (#1278):

• Improved definition of genetic items.
• Implemented recursive collection of all genetic items of symbolic expression trees.
• Added FineGrainedStructuralPopulationDiversityAnalyzer to SymbolicRegressionProblemBase.

Location:

branches/DataAnalysis.PopulationDiversityAnalysis/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Symbolic

Files:

• Analyzers/FineGrainedStructuralPopulationDiversityAnalyzer.cs (modified) (8 diffs)
• SymbolicRegressionProblemBase.cs (modified) (1 diff)

branches/DataAnalysis.PopulationDiversityAnalysis/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Symbolic/Analyzers/FineGrainedStructuralPopulationDiversityAnalyzer.cs

@@ -55 +55 @@
     protected override double[,] CalculateSimilarities(SymbolicExpressionTree[] solutions) {
       int n = solutions.Length;
+      List<string> variableNames = new List<string>();
+      foreach (StringValue variableName in ProblemData.InputVariables) {
+        variableNames.Add(variableName.Value);
+      }
+      variableNames.Add(ProblemData.TargetVariable.Value);
+      IList<GeneticInformationItem>[] geneticInformationItemsList = new List<GeneticInformationItem>[n];
+      for (int i = 0; i < n; i++) {
+        geneticInformationItemsList[i] = GeneticInformationItem.getGeneticInformationItems(solutions[i].Root, variableNames);
+      }
       double[,] result = new double[n, n];
       for (int i = 0; i < n; i++) {
@@ -66 +75 @@
       return result;
     }
-    /*
-    #region private class GeneticInformationItem, ported from HL 2
+
+
+    #region private class GeneticInformationItem
 
     private class GeneticInformationItem {
@@ -91 +101 @@
       }
 
-      private double myAncestorCoefficient;
-      public double AncestorCoefficient {
-        get { return myAncestorCoefficient; }
-      }
-
-      private double myAncestorVariableIndex;
-      public double AncestorVariableIndex {
-        get { return myAncestorVariableIndex; }
-      }
-
-      private int myAncestorTimeOffset;
-      public int AncestorTimeOffset {
-        get { return myAncestorTimeOffset; }
-      }
+      // not used in HL 3.3
+      // private double myAncestorCoefficient;
+      // public double AncestorCoefficient {
+      //   get { return myAncestorCoefficient; }
+      // }
+
+      // not used in HL 3.3
+      // private double myAncestorVariableIndex;
+      // public double AncestorVariableIndex {
+      //   get { return myAncestorVariableIndex; }
+      // }
+
+      // not used in HL 3.3
+      // private int myAncestorTimeOffset;
+      // public int AncestorTimeOffset {
+      //   get { return myAncestorTimeOffset; }
+      // }
 
       // not used in HL 3.3
@@ -127 +140 @@
       }
 
-      private int myDescendantVariant;
-      public int DescendantVariant {
-        get { return myDescendantVariant; }
-      }
-
-      public GeneticInformationItem(SymbolicExpressionTreeNode Ancestor, SymbolicExpressionTreeNode Descendant) {
-
-        myAncestorDefinition = Ancestor.Symbol.GetType();
-        myAncestorCoefficient = Ancestor.Coefficient;
-        myAncestorTimeOffset = Ancestor.TimeOffset;
-        myAncestorVariableIndex = Ancestor.VariableIndex;
-        //myAncestorVariant = Ancestor.Variant;
-
-        myDescendantDefinition = Descendant.Symbol.GetType();
-        myDescendantCoefficient = Descendant.Coefficient;
-        myDescendantTimeOffset = Descendant.TimeOffset;
-        myDescendantVariableIndex = Descendant.VariableIndex;
-        //myDescendantVariant = Descendant.Variant;
-
-        myLevelDelta = Descendant.Level - Ancestor.Level;
-        if (myLevelDelta < 0)
-          throw new InvalidOperationException("ERROR in GeneticInformationItem: The Given ancestor is not an ancestor of the given descendant node.");
-        myAncestorIndex = CalculateAncestorIndex(Ancestor, Descendant);
-
-      }
-
-      private GeneticInformationItem(GeneticInformationItem item) {
-        myAncestorDefinition = item.myAncestorDefinition;
-        myAncestorCoefficient = item.myAncestorCoefficient;
-        myAncestorTimeOffset = item.myAncestorTimeOffset;
-        myAncestorVariableIndex = item.myAncestorVariableIndex;
-        // myAncestorVariant = item.myAncestorVariant;
-        myDescendantDefinition = item.myDescendantDefinition;
-        myDescendantCoefficient = item.myDescendantCoefficient;
-        myDescendantTimeOffset = item.myDescendantTimeOffset;
-        myDescendantVariableIndex = item.myDescendantVariableIndex;
-        myDescendantVariant = item.myDescendantVariant;
-        myLevelDelta = item.myLevelDelta;
-        myAncestorIndex = item.myAncestorIndex;
-      }
-
-      public GeneticInformationItem Clone() {
-        return new GeneticInformationItem(this);
-      }
-
-      public static List<GeneticInformationItem> CopyList(List<GeneticInformationItem> list) {
-        List<GeneticInformationItem> result = new List<GeneticInformationItem>();
-        for (int i = 0; i < list.Count; i++)
-          result.Add(list[i]);
-        return result;
-      }
-
-      private static int CalculateAncestorIndex(SymbolicExpressionTreeNode Ancestor, SymbolicExpressionTreeNode Descendant) {
-        if (Ancestor == Descendant)
-          return 0;
-        // Node lastParent = Descendant, parent = Descendant.Parent;
-        // while (parent != Ancestor) {
-        //   lastParent = parent;
-        //   parent = parent.Parent;
-        //   if (parent == null)
-        //     throw new InvalidOperationException("Error in GeneticInformationItem: The given ancestor node does not seem to be an ancestor of the given descendant.");
-        // }
-        // // parent == Ancestor, lastParent is child of Ancestor
-        // int childIndex = 0;
-        // while (Ancestor.GetChild(childIndex) != lastParent)
-        //   childIndex++;
-        // return childIndex;
-        //
-        for (int i = 0; i < Ancestor.SubTrees.Count; i++)
-          if (treeContainsNode(Ancestor.SubTrees[i], Descendant))
-            return i;
-        return -1;
-      }
-
-      private static bool treeContainsNode(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode node) {
-        if (node == root)
-          return true;
-        foreach (SymbolicExpressionTreeNode subTree in root.SubTrees)
-          if(treeContainsNode(subTree, node))
-            return true;
-        return false;
-      }
-
+      // not used in HL 3.3
+      //private int myDescendantVariant;
+      //public int DescendantVariant {
+      //  get { return myDescendantVariant; }
+      //}
+
+      /*
       public static GeneticInformationItem FindBestPendant(GeneticInformationItem Item, List<GeneticInformationItem> ComparisonItems,
           StructuralSimilarityAnalysisParameters Parameters,
@@ -228 +165 @@
         else
           return null;
-      }
-
+      }*/
+
+      /*
       public static double Similarity(GeneticInformationItem Item1, GeneticInformationItem Item2,
           StructuralSimilarityAnalysisParameters Parameters,
@@ -395 +333 @@
         return result;
 
-      }
-
+      }*/
+
+      /*
       public static List<GeneticInformationItem> GetGeneticInformationItems(SymbolicExpressionTreeNode Formula, int MinLevelDifference, int MaxLevelDifference) {
         List<GeneticInformationItem> result = new List<GeneticInformationItem>();
@@ -413 +352 @@
         }
         return result;
-      }
-
-      public static List<SymbolicExpressionTreeNode> getDescendants(SymbolicExpressionTreeNode node) {
+      }*/
+
+      /*
+      public static List<SymbolicExpressionTreeNode> GetDescendants(SymbolicExpressionTreeNode node) {
         List<SymbolicExpressionTreeNode> descendants = new List<SymbolicExpressionTreeNode>();
         foreach (SymbolicExpressionTreeNode subTreeNode in node.SubTrees) {
-          addDescendants(descendants, subTreeNode);
+          AddDescendants(descendants, subTreeNode);
         }
         return descendants;
       }
-      private static void addDescendants(List<SymbolicExpressionTreeNode> list, SymbolicExpressionTreeNode node) {
+      private static void AddDescendants(List<SymbolicExpressionTreeNode> list, SymbolicExpressionTreeNode node) {
         list.Add(node);
         foreach (SymbolicExpressionTreeNode subTreeNode in node.SubTrees) {
-          addDescendants(list, subTreeNode);
-        }
-      }
-
-      private static IList<GeneticInformationItem> getGeneticInformationItems(SymbolicExpressionTreeNode node) {
+          AddDescendants(list, subTreeNode);
+        }
+      }*/
+
+      public static IList<GeneticInformationItem> getGeneticInformationItems(SymbolicExpressionTreeNode node, List<string> variableNames) {
         // Idea: collect all descendants' lists and then add new items using the retrieved ones.
         // This should save lots of time and reduce complexity of the items retrieval process.
+        if (node.Symbol is ProgramRootSymbol)
+          return getGeneticInformationItems(node.SubTrees[0], variableNames);
         List<GeneticInformationItem> list = new List<GeneticInformationItem>();
+        // add item for this node:
+        list.Add(new GeneticInformationItem(node, variableNames));
+        // add items for the descendants:
         for (int i = 0; i < node.SubTrees.Count; i++) {
-          IList<GeneticInformationItem> descendantItems = getGeneticInformationItems(node.SubTrees[i]);
+          IList<GeneticInformationItem> descendantItems = getGeneticInformationItems(node.SubTrees[i], variableNames);
           list.AddRange(descendantItems);
           foreach (GeneticInformationItem item in descendantItems) {
-            GeneticInformationItem newItem = new GeneticInformationItem();
-            newItem.AncestorIndex = i;
-            newItem.AncestorDefinition = node.Symbol.GetType();
-            // ... TODO!
+            list.Add(new GeneticInformationItem(node, item, i));
           }
         }
@@ -446 +388 @@
       }
 
+      private GeneticInformationItem (SymbolicExpressionTreeNode node, List<string> variableNames) {
+        myAncestorIndex = -1;
+        VariableTreeNode variableTreeNode = node as VariableTreeNode;
+        LaggedVariableTreeNode laggedVariableTreeNode = node as LaggedVariableTreeNode;
+        ConstantTreeNode constantTreeNode = node as ConstantTreeNode;
+        myAncestorDefinition = node.Symbol.GetType();
+        myDescendantDefinition = myAncestorDefinition;
+        if (variableTreeNode != null)
+          myDescendantCoefficient = variableTreeNode.Weight;
+        else if (constantTreeNode != null)
+          myDescendantCoefficient = constantTreeNode.Value;
+        else
+          myDescendantCoefficient = double.NaN;
+        if (laggedVariableTreeNode != null)
+          myDescendantTimeOffset = laggedVariableTreeNode.Lag;
+        else
+          myDescendantTimeOffset = 0;
+        if (variableTreeNode != null)
+          myDescendantVariableIndex = variableNames.IndexOf(variableTreeNode.VariableName);
+        else
+          myDescendantVariableIndex = -1;
+        myLevelDelta = 0;
+      }
+
+      private GeneticInformationItem(SymbolicExpressionTreeNode parentNode, GeneticInformationItem descendantGeneticInformationItem, int ancestorIndex) {
+        myAncestorIndex = ancestorIndex;
+        myLevelDelta = descendantGeneticInformationItem.LevelDelta + 1;
+        myAncestorDefinition = parentNode.Symbol.GetType();
+        myDescendantCoefficient = descendantGeneticInformationItem.DescendantCoefficient;
+        myDescendantDefinition = descendantGeneticInformationItem.DescendantDefinition;
+        myDescendantTimeOffset = descendantGeneticInformationItem.DescendantTimeOffset;
+        myDescendantVariableIndex = descendantGeneticInformationItem.DescendantVariableIndex;
+      }
+
+      public override string ToString() {
+        return "ancestor: " + AncestorDefinition.Name.ToString() + ", [" + AncestorIndex + "], delta " + LevelDelta
+          + "; descendant: " + DescendantDefinition.Name.ToString() + " (varIndex " + DescendantVariableIndex + ", "
+          + DescendantCoefficient + ", t-" + DescendantTimeOffset + ")";
+      }
+
     }
 
     #endregion
-    */
+
   }
 }

branches/DataAnalysis.PopulationDiversityAnalysis/HeuristicLab.Problems.DataAnalysis.Regression/3.3/Symbolic/SymbolicRegressionProblemBase.cs

@@ -299 +299 @@
       operators.Add(new SymbolicRegressionModelQualityAnalyzer());
       operators.Add(new VariablesUsagePopulationDiversityAnalyzer());
+      operators.Add(new FineGrainedStructuralPopulationDiversityAnalyzer());
       ParameterizeOperators();
       ParameterizeAnalyzers();