Changeset 13624

Timestamp:

02/18/16 19:33:54 (9 years ago)

Author:

bburlacu

Message:

#1772: Improve the SchemaFrequencyAnalyzer and add calculation of schema genotype and phenotype diversities.

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/Analyzers/SymbolicDataAnalysisSchemaFrequencyAnalyzer.cs (modified) (6 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/Analyzers/SymbolicDataAnalysisSchemaFrequencyAnalyzer.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
 using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -35 +39 @@
   public class SymbolicDataAnalysisSchemaFrequencyAnalyzer : EvolutionTrackingAnalyzer<ISymbolicExpressionTree> {
     private const string MinimumSchemaLengthParameterName = "MinimumSchemaLength";
+    private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching";
+    private const string ProblemDataParameterName = "ProblemData";
+    private const string InterpreterParameterName = "SymbolicExpressionTreeInterpreter";
+    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
+    private const string MaximumDegreeOfParallelismParameterName = "MaximumDegreeOfParallelism";
+
+    private static readonly Dictionary<string, string> ShortNames = new Dictionary<string, string> {
+    { "Addition", "+" },
+    { "Subtraction", "-" },
+    { "Multiplication", "*" },
+    { "Division", "/" },
+    { "Exponential", "exp" },
+    { "Logarithm", "log" }
+  };
 
     [Storable]
@@ -46 +64 @@
     private QueryMatch qm;
 
+    public IFixedValueParameter<BoolValue> ExecuteInParallelParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
+    }
+
+    public IFixedValueParameter<IntValue> MaximumDegreeOfParallelismParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumDegreeOfParallelismParameterName]; }
+    }
+
     public IFixedValueParameter<IntValue> MinimumSchemaLengthParameter {
       get { return (IFixedValueParameter<IntValue>)Parameters[MinimumSchemaLengthParameterName]; }
+    }
+
+    public IFixedValueParameter<BoolValue> StrictSchemaMatchingParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[StrictSchemaMatchingParameterName]; }
+    }
+
+    public ILookupParameter<IRegressionProblemData> ProblemDataParameter {
+      get { return (ILookupParameter<IRegressionProblemData>)Parameters[ProblemDataParameterName]; }
+    }
+
+    public ILookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter> InterpreterParameter {
+      get { return (ILookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>)Parameters[InterpreterParameterName]; }
+    }
+
+    public bool ExecuteInParallel {
+      get { return ExecuteInParallelParameter.Value.Value; }
+      set { ExecuteInParallelParameter.Value.Value = value; }
+    }
+
+    public int MaximumDegreeOfParallelism {
+      get { return MaximumDegreeOfParallelismParameter.Value.Value; }
+      set { MaximumDegreeOfParallelismParameter.Value.Value = value; }
+    }
+
+    public int MinimumSchemaLength {
+      get { return MinimumSchemaLengthParameter.Value.Value; }
+      set { MinimumSchemaLengthParameter.Value.Value = value; }
+    }
+
+    public bool StrictSchemaMatching {
+      get { return StrictSchemaMatchingParameter.Value.Value; }
+      set { StrictSchemaMatchingParameter.Value.Value = value; }
     }
 
@@ -60 +118 @@
       genotypicSimilarityCalculator = new SymbolicExpressionTreeBottomUpSimilarityCalculator { SolutionVariableName = "SymbolicExpressionTree" };
       Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaximumDegreeOfParallelismParameterName, new IntValue(4)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(StrictSchemaMatchingParameterName, new BoolValue(true)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(ExecuteInParallelParameterName, new BoolValue(true)));
+      Parameters.Add(new LookupParameter<IRegressionProblemData>(ProblemDataParameterName));
+      Parameters.Add(new LookupParameter<ISymbolicDataAnalysisExpressionTreeInterpreter>(InterpreterParameterName));
     }
 
     protected SymbolicDataAnalysisSchemaFrequencyAnalyzer(SymbolicDataAnalysisSchemaFrequencyAnalyzer original,
       Cloner cloner) : base(original, cloner) {
-      comparer = original.comparer;
-      phenotypicSimilarityCalculator = original.phenotypicSimilarityCalculator;
-      genotypicSimilarityCalculator = original.genotypicSimilarityCalculator;
+      comparer = cloner.Clone(original.comparer);
+      phenotypicSimilarityCalculator = cloner.Clone(original.phenotypicSimilarityCalculator);
+      genotypicSimilarityCalculator = cloner.Clone(original.genotypicSimilarityCalculator);
+      MinimumSchemaLength = original.MinimumSchemaLength;
+      StrictSchemaMatching = original.StrictSchemaMatching;
       qm = new QueryMatch(comparer) { MatchParents = true };
     }
@@ -76 +141 @@
     [StorableConstructor]
     protected SymbolicDataAnalysisSchemaFrequencyAnalyzer(bool deserializing) : base(deserializing) { }
-
 
     [StorableHook(HookType.AfterDeserialization)]
@@ -84 +148 @@
 
     public override IOperation Apply() {
-      int updateInterval = UpdateIntervalParameter.Value.Value;
-      IntValue updateCounter = UpdateCounterParameter.ActualValue;
-      // if counter does not yet exist then initialize it with update interval
-      // to make sure the solutions are analyzed on the first application of this operator
-      if (updateCounter == null) {
-        updateCounter = new IntValue(updateInterval);
-        UpdateCounterParameter.ActualValue = updateCounter;
-      }
-      //analyze solutions only every 'updateInterval' times
-      if (updateCounter.Value != updateInterval) {
-        updateCounter.Value++;
+      if (PopulationGraph == null || Generation.Value == 0 ||
+          (Generation.Value > 1 && Generation.Value % UpdateInterval.Value != 0))
         return base.Apply();
-      }
-      updateCounter.Value = 1;
-
-      if (PopulationGraph == null || Generation.Value == 0)
-        return base.Apply();
-
-      var minimumSchemaLength = MinimumSchemaLengthParameter.Value.Value;
-      var vertices = PopulationGraph.GetByRank(Generation.Value).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>().ToList();
-      var formatter = new SymbolicExpressionTreeStringFormatter { Indent = false, AppendNewLines = false };
-
-      var schemas = SchemaCreator.GenerateSchemas(vertices, minimumSchemaLength).ToList();
-      var trees = vertices.Select(x => x.Data).ToList();
-      var qualities = vertices.Select(x => x.Quality).ToList();
-      var scopes = ExecutionContext.Scope.SubScopes; // the scopes of all the individuals, needed because the tree evaluated values are stored in the scope and we use them for the phenotypic similarity
-
-      var matrix = new DoubleMatrix(schemas.Count, 5) {
-        RowNames = schemas.Select(x => formatter.Format(x.Root.GetSubtree(0).GetSubtree(0))),
-        ColumnNames = new[] { "Avg. Length", "Avg. Quality", "Relative Frequency", "Avg. Phen. Sim.", "Avg. Gen. Sim" },
-        SortableView = true
-      };
-
-      for (int i = 0; i < schemas.Count; ++i) {
-        var schema = schemas[i];
-        int count = 0;
-        double avgLength = 0;
-        double avgQuality = 0;
-        var matchingScopes = new ScopeList();
-        for (int j = 0; j < trees.Count; ++j) {
-          var tree = trees[j];
-          if (qm.Match(tree, schema)) {
-            count++;
-            avgLength += tree.Length;
-            avgQuality += qualities[j];
-            matchingScopes.Add(scopes[j]);
+
+      comparer.MatchVariableWeights = comparer.MatchConstantValues = StrictSchemaMatching;
+      phenotypicSimilarityCalculator.Interpreter = InterpreterParameter.ActualValue;
+      phenotypicSimilarityCalculator.ProblemData = ProblemDataParameter.ActualValue;
+      var generation = Generation.Value;
+
+      var population = PopulationGraph.GetByRank(generation).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>().ToList();
+      var vertices = population.Where(x => x.InDegree == 2).OrderByDescending(x => x.Quality).ToList();
+      ResultCollection resultCollection;
+      if (Results.ContainsKey("Schema Frequencies")) {
+        resultCollection = (ResultCollection)Results["Schema Frequencies"].Value;
+      } else {
+        resultCollection = new ResultCollection();
+        var result = new Result("Schema Frequencies", resultCollection);
+        Results.Add(result);
+      }
+
+      var mostFrequentPerGeneration = new List<Tuple<string, double[]>>();
+
+      var trees = population.Select(x => x.Data).ToList();
+      var qualities = population.Select(x => x.Quality).ToList();
+      var genSimMatrix = new double[trees.Count, trees.Count];
+      var phenSimMatrix = new double[trees.Count, trees.Count];
+
+      for (int i = 0; i < trees.Count - 1; ++i) {
+        for (int j = i + 1; j < trees.Count; ++j) {
+          genSimMatrix[i, j] = double.NaN;
+          phenSimMatrix[i, j] = double.NaN;
+        }
+      }
+      var schemas = SchemaCreator.GenerateSchemas(vertices, MinimumSchemaLength, StrictSchemaMatching).ToList();
+      var schemaStrings = schemas.Select(x => SubtreeToString(x.Root.GetSubtree(0).GetSubtree(0), StrictSchemaMatching)).ToList();
+      int[][] matchingIndices;
+      if (ExecuteInParallel) {
+        matchingIndices = new int[schemas.Count][];
+        Parallel.For(0, schemas.Count, new ParallelOptions { MaxDegreeOfParallelism = MaximumDegreeOfParallelism }, i => {
+          var schema = schemas[i];
+          matchingIndices[i] = Enumerable.Range(0, trees.Count).Where(v => qm.Match(trees[v].Root, schema.Root)).ToArray();
+        });
+      } else {
+        matchingIndices = schemas.Select(x => Enumerable.Range(0, trees.Count).Where(v => qm.Match(trees[v].Root, x.Root)).ToArray()).ToArray();
+      }
+
+      var schemaStatistics = new List<Tuple<string, double[]>>();
+      var avgPopQuality = qualities.Average();
+
+      if (ExecuteInParallel) {
+        var locker = new object();
+        Parallel.For(0, schemas.Count, new ParallelOptions { MaxDegreeOfParallelism = MaximumDegreeOfParallelism }, i => {
+          var indices = matchingIndices[i];
+          if (indices.Length > 1) {
+            var avgSchemaQuality = indices.Average(x => qualities[x]);
+            var avgLength = indices.Average(x => trees[x].Length);
+            var avgGenSim = AverageSimilarity(indices, trees, genSimMatrix, genotypicSimilarityCalculator.CalculateSimilarity);
+            var avgPhenSim = AverageSimilarity(indices, trees, phenSimMatrix, phenotypicSimilarityCalculator.CalculateSimilarity);
+            var array = new[] { indices.Length, avgSchemaQuality, avgLength, avgGenSim, avgPhenSim, avgPopQuality };
+            var t = new Tuple<string, double[]>(schemaStrings[i], array);
+            lock (locker) {
+              schemaStatistics.Add(t);
+            }
           }
-        }
-        avgLength /= count;
-        avgQuality /= count;
-        double relativeFreq = (double)count / trees.Count;
-        double avgPhenotypicSimilarity = SchemaEvaluator.CalculateSimilarity(matchingScopes, phenotypicSimilarityCalculator, true, 4);
-        double avgGenotypicSimilarity = SchemaEvaluator.CalculateSimilarity(matchingScopes, genotypicSimilarityCalculator, true, 4);
-
-        matrix[i, 0] = avgLength;
-        matrix[i, 1] = avgQuality;
-        matrix[i, 2] = relativeFreq;
-        matrix[i, 3] = avgPhenotypicSimilarity;
-        matrix[i, 4] = avgGenotypicSimilarity;
-      }
-
-      if (Results.ContainsKey("Schema Frequencies")) {
-        var result = Results["Schema Frequencies"];
-        result.Value = matrix;
-      } else {
-        var result = new Result("Schema Frequencies", matrix);
-        Results.Add(result);
-      }
-
+        });
+      } else {
+        for (int i = 0; i < schemas.Count; ++i) {
+          var indices = matchingIndices[i];
+          if (indices.Length > 1) {
+            var avgSchemaQuality = indices.Average(x => qualities[x]);
+            var avgLength = indices.Average(x => trees[x].Length);
+            var avgGenSim = AverageSimilarity(indices, trees, genSimMatrix, genotypicSimilarityCalculator.CalculateSimilarity);
+            var avgPhenSim = AverageSimilarity(indices, trees, phenSimMatrix, phenotypicSimilarityCalculator.CalculateSimilarity);
+            var array = new[] { indices.Length, avgSchemaQuality, avgLength, avgGenSim, avgPhenSim, avgPopQuality };
+            var t = new Tuple<string, double[]>(schemaStrings[i], array);
+            schemaStatistics.Add(t);
+          }
+        }
+      }
+
+      if (!schemaStatistics.Any()) return base.Apply(); // shouldn't ever happen
+      var columnNames = new[] { "Count", "Avg Quality", "Avg Length", "Avg Genotype Similarity", "Avg Phenotype Similarity", "Avg Population Quality" };
+      var mostFrequent = new DoubleMatrix(schemaStatistics.Count, schemaStatistics[0].Item2.Length);
+      mostFrequent.SortableView = true;
+      schemaStatistics.Sort((a, b) => { if (a.Item2[0].Equals(b.Item2[0])) return b.Item2[1].CompareTo(a.Item2[1]); return b.Item2[0].CompareTo(a.Item2[0]); });
+      mostFrequentPerGeneration.Add(new Tuple<string, double[]>(schemaStatistics[0].Item1, new[] { (double)generation }.Concat(schemaStatistics[0].Item2).ToArray()));
+      mostFrequent.RowNames = schemaStatistics.Select(x => x.Item1);
+      mostFrequent.ColumnNames = columnNames;
+      for (int i = 0; i < schemaStatistics.Count; ++i) {
+        var values = schemaStatistics[i].Item2;
+        for (int j = 0; j < values.Length; ++j) {
+          mostFrequent[i, j] = values[j];
+        }
+      }
+      resultCollection.Add(new Result("Generation " + generation + " Most Frequent Schemas", mostFrequent));
+
+      columnNames = new[] { "Generation", "Count", "Avg Quality", "Avg Length", "Avg Genotype Similarity", "Avg Phenotype Similarity", "Avg Population Quality" };
+      // sort according to quality, then count
+      schemaStatistics.Sort((a, b) => { if (a.Item2[1].Equals(b.Item2[1])) return b.Item2[0].CompareTo(a.Item2[0]); return b.Item2[1].CompareTo(a.Item2[1]); });
+      DoubleMatrix bestSchemasMatrix;
+      if (!resultCollection.ContainsKey("Best Schemas")) {
+        bestSchemasMatrix = new DoubleMatrix(1, 7);
+        bestSchemasMatrix.RowNames = new[] { schemaStatistics[0].Item1 };
+        bestSchemasMatrix.ColumnNames = columnNames;
+        var values = new[] { (double)generation }.Concat(schemaStatistics[0].Item2).ToArray();
+        for (int i = 0; i < values.Length; ++i)
+          bestSchemasMatrix[0, i] = values[i];
+        resultCollection.Add(new Result("Best Schemas", bestSchemasMatrix));
+      } else {
+        bestSchemasMatrix = (DoubleMatrix)resultCollection["Best Schemas"].Value;
+        resultCollection["Best Schemas"].Value = AddRow(bestSchemasMatrix, new[] { (double)generation }.Concat(schemaStatistics[0].Item2).ToArray(), schemaStatistics[0].Item1);
+      }
+
+      // sort according to count, then quality
+      schemaStatistics.Sort((a, b) => { if (a.Item2[0].Equals(b.Item2[0])) return b.Item2[1].CompareTo(a.Item2[1]); return b.Item2[0].CompareTo(a.Item2[0]); });
+      DoubleMatrix frequentSchemasMatrix;
+      if (!resultCollection.ContainsKey("Most Frequent Schemas")) {
+        frequentSchemasMatrix = new DoubleMatrix(1, 7);
+        frequentSchemasMatrix.RowNames = new[] { schemaStatistics[0].Item1 };
+        frequentSchemasMatrix.ColumnNames = columnNames;
+        var values = new[] { (double)generation }.Concat(schemaStatistics[0].Item2).ToArray();
+        for (int i = 0; i < values.Length; ++i)
+          frequentSchemasMatrix[0, i] = values[i];
+        resultCollection.Add(new Result("Most Frequent Schemas", frequentSchemasMatrix));
+      } else {
+        frequentSchemasMatrix = (DoubleMatrix)resultCollection["Most Frequent Schemas"].Value;
+        resultCollection["Most Frequent Schemas"].Value = AddRow(frequentSchemasMatrix, new[] { (double)generation }.Concat(schemaStatistics[0].Item2).ToArray(), schemaStatistics[0].Item1);
+      }
       return base.Apply();
+    }
+
+    private static DoubleMatrix AddRow(DoubleMatrix m, double[] row, string rowName) {
+      if (row.Length != m.Columns)
+        throw new Exception("Row value count must match matrix column count.");
+      var x = new DoubleMatrix(m.Rows + 1, m.Columns);
+      x.RowNames = m.RowNames.Concat(new[] { rowName });
+      x.ColumnNames = m.ColumnNames;
+      for (int i = 0; i < m.Rows; ++i)
+        for (int j = 0; j < m.Columns; ++j)
+          x[i, j] = m[i, j];
+      for (int j = 0; j < m.Columns; ++j)
+        x[m.Rows, j] = row[j];
+      return x;
+    }
+
+    private static double AverageSimilarity(int[] indices, List<ISymbolicExpressionTree> trees, double[,] similarityMatrix, Func<ISymbolicExpressionTree, ISymbolicExpressionTree, double> similarityFunction) {
+      var agg = 0d;
+      int len = indices.Length;
+      var count = len * (len - 1) / 2d;
+      for (int i = 0; i < indices.Length - 1; ++i) {
+        var a = indices[i];
+        for (int j = i + 1; j < indices.Length; ++j) {
+          var b = indices[j];
+          if (double.IsNaN(similarityMatrix[a, b])) similarityMatrix[a, b] = similarityFunction(trees[a], trees[b]);
+          agg += similarityMatrix[a, b];
+        }
+      }
+      return agg / count;
+    }
+
+    private static string SubtreeToString(ISymbolicExpressionTreeNode node, bool strict = false) {
+      StringBuilder strBuilder = new StringBuilder();
+      // internal nodes or leaf nodes?
+      if (node is AnySubtree)
+        return "# ";
+
+      if (node.SubtreeCount > 0) {
+        strBuilder.Append("(");
+        // symbol on same line as '('
+        string label = string.Empty;
+        if (node is AnyNode)
+          label = "=";
+        else {
+          var name = node.Symbol.Name;
+          label = ShortNames.ContainsKey(name) ? ShortNames[name] : name;
+        }
+        strBuilder.Append(label + " ");
+        // each subtree expression on a new line
+        // and closing ')' also on new line
+        foreach (var subtree in node.Subtrees) {
+          strBuilder.Append(SubtreeToString(subtree, strict));
+        }
+        strBuilder.Append(") ");
+      } else {
+        // symbol in the same line with as '(' and ')'
+        var v = node as VariableTreeNode;
+        var c = node as ConstantTreeNode;
+        var w = node as AnyNode; // wildcard
+        string label = string.Empty;
+        if (w != null)
+          label = "=";
+        else if (v != null)
+          label = strict ? string.Format("{0:0.00}_{1}", v.Weight, v.VariableName) : string.Format("{0}", v.VariableName);
+        else if (c != null)
+          label = strict ? string.Format("{0:0.00}", c.Value) : "C";
+        strBuilder.Append(label);
+        if (node.Parent != null && node != node.Parent.Subtrees.Last())
+          strBuilder.Append(" ");
+      }
+      return strBuilder.ToString();
     }
   }