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

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

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs (modified) (14 diffs)

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 };