Changeset 13480

Timestamp:

12/17/15 20:13:57 (9 years ago)

Author:

bburlacu

Message:

#1772: Schema diversification strategy: implement adaptive replacement ratio and added number of evaluated solutions per generation to the diversification statistics operator

Location:

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification

Files:

• DiversificationStatisticsOperator.cs (modified) (5 diffs)
• SchemaCreator.cs (modified) (7 diffs)
• SchemaEvaluator.cs (modified) (14 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/DiversificationStatisticsOperator.cs

@@ -37 +37 @@
     private const string AverageSchemaLengthParameterName = "AverageSchemaLength";
     private const string ResultCollectionParameterName = "Results";
+    private const string EvaluatedSolutionsParameterName = "EvaluatedSolutions";
 
     public ILookupParameter<IntValue> NumberOfChangedTreesParameter {
@@ -50 +51 @@
       get { return (ILookupParameter<ResultCollection>)Parameters[ResultCollectionParameterName]; }
     }
+    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters[EvaluatedSolutionsParameterName]; }
+    }
+
+    private int evaluatedSolutionsTracker;
 
     public DiversificationStatisticsOperator() {
@@ -56 +62 @@
       Parameters.Add(new LookupParameter<DoubleValue>(AverageSchemaLengthParameterName));
       Parameters.Add(new LookupParameter<ResultCollection>(ResultCollectionParameterName));
+      Parameters.Add(new LookupParameter<IntValue>(EvaluatedSolutionsParameterName));
+    }
+
+    public override void ClearState() {
+      evaluatedSolutionsTracker = 0;
+      base.ClearState();
     }
 
@@ -66 +78 @@
 
     public override IOperation Apply() {
-
       var results = ResultCollectionParameter.ActualValue;
       DataTable table;
@@ -87 +98 @@
         table.Rows.Add(row);
       }
+      if (!results.ContainsKey("EvaluatedSolutionsPerGeneration")) {
+        table = new DataTable();
+        results.Add(new Result("EvaluatedSolutionsPerGeneration", table));
+        var row = new DataRow("Evaluated solutions");
+        table.Rows.Add(row);
+        row.Values.Add(0);
+      }
+
+      var evaluatedSolutions = EvaluatedSolutionsParameter.ActualValue.Value - evaluatedSolutionsTracker;
       ((DataTable)results["NumberOfChangedTrees"].Value).Rows["Changed trees"].Values.Add(NumberOfChangedTreesParameter.ActualValue.Value);
       ((DataTable)results["AverageSchemaLength"].Value).Rows["Average schema length"].Values.Add(AverageSchemaLengthParameter.ActualValue.Value);
       ((DataTable)results["NumberOfSchemas"].Value).Rows["Number of schemas"].Values.Add(NumberOfSchemasParameter.ActualValue.Value);
+      ((DataTable)results["EvaluatedSolutionsPerGeneration"].Value).Rows["Evaluated solutions"].Values.Add(evaluatedSolutions);
+      evaluatedSolutionsTracker += evaluatedSolutions;
 
       return base.Apply();

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs

@@ -35 +35 @@
   [StorableClass]
   public class SchemaCreator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
+    #region parameter names
     private const string MinimumSchemaLengthParameterName = "MinimumSchemaLength";
     private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
@@ -48 +49 @@
     private const string NumberOfSchemasParameterName = "NumberOfSchemas";
     private const string AverageSchemaLengthParameterName = "AverageSchemaLength";
+    private const string UseAdaptiveReplacementRatioParameterName = "UseAdaptiveReplacementRatio";
+    private const string ReplacementRatioUpdateRuleParameterName = "ReplacementRatioUpdateRule";
+    #endregion
 
     #region parameters
+
+    public IConstrainedValueParameter<StringValue> ReplacementRatioUpdateRuleParameter {
+      get { return (IConstrainedValueParameter<StringValue>)Parameters[ReplacementRatioUpdateRuleParameterName]; }
+    }
+    public IFixedValueParameter<BoolValue> UseAdaptiveReplacementRatioParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[UseAdaptiveReplacementRatioParameterName]; }
+    }
     public IFixedValueParameter<BoolValue> ExclusiveMatchingParameter {
       get { return (IFixedValueParameter<BoolValue>)Parameters[ExclusiveMatchingParameterName]; }
@@ -99 +110 @@
 
     public SchemaCreator() {
+      #region add parameters
       Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
       Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.01)));
@@ -112 +124 @@
       Parameters.Add(new ValueParameter<IntValue>(NumberOfSchemasParameterName, new IntValue(0)));
       Parameters.Add(new ValueParameter<DoubleValue>(AverageSchemaLengthParameterName, new DoubleValue(0)));
-
+      Parameters.Add(new FixedValueParameter<BoolValue>(UseAdaptiveReplacementRatioParameterName, new BoolValue(true)));
+
+      var replacementRatioUpdateRules = new ItemSet<StringValue>(new[] { new StringValue("f(x) = x"), new StringValue("f(x) = tanh(x)"), new StringValue("f(x) = tanh(2x)"), new StringValue("f(x) = tanh(3x)") });
+      Parameters.Add(new ConstrainedValueParameter<StringValue>(ReplacementRatioUpdateRuleParameterName, replacementRatioUpdateRules));
+      #endregion
       NumberOfChangedTreesParameter.Hidden = true;
       NumberOfSchemasParameter.Hidden = true;
@@ -138 +154 @@
       var n = (int)Math.Round(ExecutionContext.Scope.SubScopes.Count * PercentageOfPopulation);
       var scopes = new ScopeList(ExecutionContext.Scope.SubScopes.Take(n));
+
+      var updateEstimatedValues = new OperationCollection { Parallel = true };
+      if (updateEstimatedValuesOperator == null)
+        updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
+
+      foreach (var s in scopes) {
+        if (!s.Variables.ContainsKey("EstimatedValues"))
+          s.Variables.Add(new Core.Variable("EstimatedValues"));
+        updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, s));
+      }
+
+      Func<double, double> rule;
+      var replacementRule = ReplacementRatioUpdateRuleParameter.Value.Value;
+
+      switch (replacementRule) {
+        case "f(x) = x": {
+            rule = x => x;
+            break;
+          }
+        case "f(x) = tanh(x)": {
+            rule = x => Math.Tanh(x);
+            break;
+          }
+        case "f(x) = tanh(2x)": {
+            rule = x => Math.Tanh(2 * x);
+            break;
+          }
+        case "f(x) = tanh(3x)": {
+            rule = x => Math.Tanh(3 * x);
+            break;
+          }
+        default:
+          throw new ArgumentException("Unknown replacement rule");
+      }
+
+      var evaluateSchemas = new OperationCollection();
 
       // for now, only consider crossover offspring
@@ -146 +198 @@
                      select v;
 
+      var schemas = new List<ISymbolicExpressionTree>(GenerateSchemas(vertices, MinimumSchemaLength));
+
+      #region create schemas and add subscopes representing the individuals
+      foreach (var schema in schemas) {
+        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = rule }, ExecutionContext.Scope));
+      }
+      #endregion
+
+      if (diversificationStatisticsOperator == null)
+        diversificationStatisticsOperator = new DiversificationStatisticsOperator();
+
+      var calculateStatistics = ExecutionContext.CreateChildOperation(diversificationStatisticsOperator);
+
+      // set parameters for statistics
+      AverageSchemaLengthParameter.Value = new DoubleValue(schemas.Average(x => x.Length));
+      NumberOfSchemasParameter.Value = new IntValue(schemas.Count);
+      NumberOfChangedTreesParameter.Value = new IntValue(0);
+
+      // return an operation collection containing all the scope operations + base.Apply()
+      return new OperationCollection { updateEstimatedValues, evaluateSchemas, calculateStatistics, base.Apply() };
+    }
+
+    public static IEnumerable<ISymbolicExpressionTree> GenerateSchemas(IEnumerable<IGenealogyGraphNode<ISymbolicExpressionTree>> vertices, int minimumSchemaLength) {
+      var anySubtreeSymbol = new AnySubtreeSymbol();
+      //      var anyNodeSymbol = new AnyNodeSymbol();
       var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
-      var anySubtreeSymbol = new AnySubtreeSymbol();
-
-      var updateEstimatedValues = new OperationCollection { Parallel = true };
-      if (updateEstimatedValuesOperator == null)
-        updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
-
-      foreach (var s in scopes) {
-        if (!s.Variables.ContainsKey("EstimatedValues"))
-          s.Variables.Add(new Core.Variable("EstimatedValues"));
-        updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, s));
-      }
-
-      var evaluateSchemas = new OperationCollection();
-      var schemas = new List<ISymbolicExpressionTree>();
-      var wildCardCounts = new List<double>();
-      #region create schemas and add subscopes representing the individuals
+      var hash = new HashSet<string>();
+      var formatter = new SymbolicExpressionTreeStringFormatter { Indent = false, AppendNewLines = false };
       foreach (var g in groups) {
         var parent = g.Key;
-        if (parent.Data.Length < MinimumSchemaLength)
+        if (parent.Data.Length < minimumSchemaLength)
           continue;
         bool replaced = false;
@@ -171 +234 @@
         var nodes = schema.IterateNodesPrefix().ToList();
         var arcs = g.Select(x => x.InArcs.Last()).Where(x => x.Data != null);
-        var indices = arcs.Select(x => ((IFragment<ISymbolicExpressionTreeNode>)x.Data).Index1).Distinct().ToArray();
+        var indices = (from arc in arcs
+                       let fragment = (IFragment<ISymbolicExpressionTreeNode>)arc.Data
+                       select fragment.Index1).Distinct().ToArray();
         Array.Sort(indices);
         var nodesToReplace = indices.Select(x => nodes[x]).ToList();
-        int w = 0;
         for (int i = nodesToReplace.Count - 1; i >= 0; --i) {
           var node = nodesToReplace[i];
 
           // do not replace the node with a wildcard if it would result in a length < MinimumSchemaLength
-          if ((schema.Length - node.GetLength() + 1) < MinimumSchemaLength)
+          if (schema.Length - node.GetLength() + 1 < minimumSchemaLength)
             continue;
 
-          var replacement = anySubtreeSymbol.CreateTreeNode();
-          ReplaceSubtree(node, replacement, false);
+          //          var replacement = anySubtreeSymbol.CreateTreeNode();
+          //          ReplaceSubtree(node, replacement, false);
+          var replacement = new AnyNodeSymbol(node.Symbol.MinimumArity, node.Symbol.MinimumArity).CreateTreeNode();
+          ReplaceSubtree(node, replacement, true);
           replaced = true;
-          ++w;
         }
         if (replaced) {
-          // store the schemas and the number of wildcards they contain in two lists
-          schemas.Add(schema);
-          wildCardCounts.Add(w);
+          var str = formatter.Format(schema.Root.GetSubtree(0).GetSubtree(0));
+          if (hash.Contains(str)) continue;
+          yield return schema;
+          hash.Add(str);
         }
       }
-
-      for (int i = 0; i < schemas.Count; ++i) {
-        var schema = schemas[i];
-        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema }, ExecutionContext.Scope));
-      }
-      #endregion
-
-      if (diversificationStatisticsOperator == null)
-        diversificationStatisticsOperator = new DiversificationStatisticsOperator();
-
-      var calculateStatistics = ExecutionContext.CreateChildOperation(diversificationStatisticsOperator);
-
-      // set parameters for statistics
-      AverageSchemaLengthParameter.Value = new DoubleValue(schemas.Average(x => x.Length));
-      NumberOfSchemasParameter.Value = new IntValue(schemas.Count);
-      NumberOfChangedTreesParameter.Value = new IntValue(0);
-
-      // return an operation collection containing all the scope operations + base.Apply()
-      return new OperationCollection { updateEstimatedValues, evaluateSchemas, calculateStatistics, base.Apply() };
-    }
-
-    private static void ReplaceSubtree(ISymbolicExpressionTreeNode original, ISymbolicExpressionTreeNode replacement,
-      bool preserveChildren = true) {
+    }
+
+    private static void ReplaceSubtree(ISymbolicExpressionTreeNode original, ISymbolicExpressionTreeNode replacement, bool preserveChildren = true) {
       var parent = original.Parent;
       if (parent == null)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using System.Threading.Tasks;
@@ -28 +29 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.EvolutionTracking;
+using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -49 +51 @@
     private const string ApplyLinearScalingParameterName = "ApplyLinearScaling";
     private const string MutatorParameterName = "Mutator";
+    private const string CrossoverParameterName = "Crossover";
     private const string RandomReplacementParameterName = "RandomReplacement";
     private const string NumberOfChangedTreesParameterName = "NumberOfChangedTrees";
@@ -54 +57 @@
     private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
     private const string ExclusiveMatchingParameterName = "ExclusiveMatching";
+    private const string UseAdaptiveReplacementRatioParameterName = "UseAdaptiveReplacementRatio";
     #endregion
 
     #region parameters
+    public ILookupParameter<BoolValue> UseAdaptiveReplacementRatioParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters[UseAdaptiveReplacementRatioParameterName]; }
+    }
     public ILookupParameter<BoolValue> ExclusiveMatchingParameter {
       get { return (ILookupParameter<BoolValue>)Parameters[ExclusiveMatchingParameterName]; }
@@ -86 +93 @@
     public ILookupParameter<ISymbolicExpressionTreeManipulator> MutatorParameter {
       get { return (ILookupParameter<ISymbolicExpressionTreeManipulator>)Parameters[MutatorParameterName]; }
+    }
+    public ILookupParameter<ISymbolicExpressionTreeCrossover> CrossoverParameter {
+      get { return (ILookupParameter<ISymbolicExpressionTreeCrossover>)Parameters[CrossoverParameterName]; }
     }
     public ILookupParameter<IRandom> RandomParameter {
@@ -120 +130 @@
     private readonly SymbolicExpressionTreePhenotypicSimilarityCalculator calculator = new SymbolicExpressionTreePhenotypicSimilarityCalculator();
     private readonly QueryMatch qm;
+
+    public Func<double, double> ReplacementRule { get; set; }
 
     private readonly ISymbolicExpressionTreeNodeEqualityComparer comp = new SymbolicExpressionTreeNodeEqualityComparer {
@@ -148 +160 @@
       Parameters.Add(new LookupParameter<BoolValue>(ApplyLinearScalingParameterName));
       Parameters.Add(new LookupParameter<ISymbolicExpressionTreeManipulator>(MutatorParameterName));
+      Parameters.Add(new LookupParameter<ISymbolicExpressionTreeCrossover>(CrossoverParameterName));
       Parameters.Add(new LookupParameter<BoolValue>(RandomReplacementParameterName));
       Parameters.Add(new LookupParameter<IntValue>(NumberOfChangedTreesParameterName));
@@ -153 +166 @@
       Parameters.Add(new LookupParameter<IntValue>(MaxDegreeOfParalellismParameterName));
       Parameters.Add(new LookupParameter<BoolValue>(ExclusiveMatchingParameterName));
+      Parameters.Add(new LookupParameter<BoolValue>(UseAdaptiveReplacementRatioParameterName));
       #endregion
     }
@@ -175 +189 @@
     public override IOperation Apply() {
       var individuals = ExecutionContext.Scope.SubScopes; // the scopes represent the individuals
+      var trees = individuals.Select(x => (ISymbolicExpressionTree)x.Variables["SymbolicExpressionTree"].Value).ToList();
+      var qualities = individuals.Select(x => (DoubleValue)x.Variables["Quality"].Value).ToList();
 
       var random = RandomParameter.ActualValue;
@@ -185 +201 @@
       // first apply the length and root equality checks in order to filter the individuals
       var exclusiveMatching = ExclusiveMatchingParameter.ActualValue.Value;
-      var filtered = exclusiveMatching ? (from ind in individuals
-                                          where !ind.Variables.ContainsKey("AlreadyMatched")
-                                          let t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value
-                                          where t.Length >= s.Length && qm.Comparer.Equals(t.Root.GetSubtree(0).GetSubtree(0), sRoot)
-                                          select ind).ToList()
-                                       : (from ind in individuals
-                                          let t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value
-                                          where t.Length >= s.Length && qm.Comparer.Equals(t.Root.GetSubtree(0).GetSubtree(0), sRoot)
-                                          select ind).ToList();
+      var filtered = new List<int>();
+      for (int i = 0; i < individuals.Count; ++i) {
+        if (exclusiveMatching && individuals[i].Variables.ContainsKey("AlreadyMatched")) continue;
+        var t = trees[i];
+        var tRoot = t.Root.GetSubtree(0).GetSubtree(0);
+        if (t.Length < s.Length || !qm.Comparer.Equals(tRoot, sRoot)) continue;
+        filtered.Add(i);
+      }
 
       // if we don't have enough filtered individuals, then we are done
+      // if the schema exceeds the minimum frequency, it gets processed further
       if (filtered.Count < countThreshold) {
         return base.Apply();
@@ -211 +227 @@
         Parallel.For(0, filtered.Count, new ParallelOptions { MaxDegreeOfParallelism = maxDegreeOfParallelism },
           i => {
-            var t = (ISymbolicExpressionTree)filtered[i].Variables["SymbolicExpressionTree"].Value;
+            var index = filtered[i];
+            var t = trees[index];
             var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
             if (qm.Match(tNodes, sNodes)) {
@@ -218 +235 @@
           });
 
-        for (int i = 0; i < matching.Length; ++i) {
-          if (matching[i])
-            matchingIndividuals.Add(filtered[i]);
-        }
+        matchingIndividuals.AddRange(filtered.Where((x, i) => matching[i]).Select(x => individuals[x]));
       } else {
         for (int i = 0; i < filtered.Count; ++i) {
@@ -228 +242 @@
             break;
 
-          var ind = filtered[i];
-          var t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
-          var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
+          var index = filtered[i];
+          var tRoot = trees[index].Root.GetSubtree(0).GetSubtree(0);
+          var tNodes = QueryMatch.InitializePostOrder(tRoot);
           if (qm.Match(tNodes, sNodes))
-            matchingIndividuals.Add(ind);
+            matchingIndividuals.Add(individuals[index]);
         }
       }
 
-      // additional condition: the average schema quality should be equal or greater than the population average quality
       if (matchingIndividuals.Count < countThreshold) {
         return base.Apply();
       }
 
-      var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator, executeInParallel, maxDegreeOfParallelism);
+      var similarity = CalculateSimilarity(matchingIndividuals, calculator, executeInParallel, maxDegreeOfParallelism);
       if (similarity < MinimumPhenotypicSimilarity.Value) {
         return base.Apply();
       }
 
-      int n = (int)Math.Floor(matchingIndividuals.Count * ReplacementRatio.Value);
+      double replacementRatio;
+      var adaptiveReplacementRatio = UseAdaptiveReplacementRatioParameter.ActualValue.Value;
+
+      if (adaptiveReplacementRatio) {
+        var r = (double)matchingIndividuals.Count / individuals.Count;
+        replacementRatio = ReplacementRule(r);
+      } else {
+        replacementRatio = ReplacementRatio.Value;
+      }
+
+      int n = (int)Math.Floor(matchingIndividuals.Count * replacementRatio);
       var individualsToReplace = RandomReplacement.Value ? matchingIndividuals.SampleRandomWithoutRepetition(random, n).ToList()
                                                          : matchingIndividuals.OrderBy(x => (DoubleValue)x.Variables["Quality"].Value).Take(n).ToList();
@@ -265 +288 @@
     }
 
-    private static double CalculatePhenotypicSimilarity(ScopeList individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator, bool parallel = false, int nThreads = -1) {
+    public static double CalculateSimilarity(ScopeList individuals, ISolutionSimilarityCalculator calculator, bool parallel = false, int nThreads = -1) {
       double similarity = 0;
       int count = individuals.Count;
+      if (count < 2) return double.NaN;
       if (parallel) {
         var parallelOptions = new ParallelOptions { MaxDegreeOfParallelism = nThreads };