Changeset 13744 for branches/PerformanceComparison/HeuristicLab.Analysis/3.3/BestNScopesSolutionAnalyzer.cs

Timestamp:

04/07/16 14:13:41 (9 years ago)

Author:

abeham

Message:

#2457: added best-n scopes solution analyzer

File:

• branches/PerformanceComparison/HeuristicLab.Analysis/3.3/BestNScopesSolutionAnalyzer.cs (copied) (copied from branches/PerformanceComparison/HeuristicLab.Analysis/3.3/BestScopeSolutionAnalyzer.cs) (4 diffs)

branches/PerformanceComparison/HeuristicLab.Analysis/3.3/BestNScopesSolutionAnalyzer.cs

@@ -20 +20 @@
 #endregion
 
-using System;
-using System.Collections.Generic;
-using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -28 +25 @@
 using HeuristicLab.Operators;
 using HeuristicLab.Optimization;
+using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using System;
+using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Analysis {
@@ -35 +36 @@
   /// An operator that extracts (clones) the scope containing the best quality.
   /// </summary>
-  [Item("BestScopeSolutionAnalyzer", "An operator that extracts the scope containing the best quality.")]
+  [Item("BestNScopesSolutionAnalyzer", "An operator that maintains at most N scopes containing good quality solutions.")]
   [StorableClass]
-  public class BestScopeSolutionAnalyzer : SingleSuccessorOperator, IAnalyzer, ISingleObjectiveOperator {
+  public class BestNScopesSolutionAnalyzer : SingleSuccessorOperator, IAnalyzer, ISingleObjectiveOperator {
 
     public virtual bool EnabledByDefault {
@@ -48 +49 @@
       get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
     }
-    public IFixedValueParameter<StringValue> BestSolutionResultNameParameter {
-      get { return (IFixedValueParameter<StringValue>)Parameters["BestSolution ResultName"]; }
-    }
-    public ILookupParameter<DoubleValue> BestKnownQualityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
+    public IFixedValueParameter<StringValue> BestSolutionsResultNameParameter {
+      get { return (IFixedValueParameter<StringValue>)Parameters["BestSolutions ResultName"]; }
     }
     public IValueLookupParameter<ResultCollection> ResultsParameter {
       get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
     }
+    public IValueParameter<ISolutionSimilarityCalculator> SimilarityCalculatorParameter {
+      get { return (IValueParameter<ISolutionSimilarityCalculator>)Parameters["SimilarityCalculator"]; }
+    }
+    private IFixedValueParameter<IntValue> NParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters["N"]; }
+    }
+    private IFixedValueParameter<DoubleValue> MaximumSimilarityParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters["MaximumSimilarity"]; }
+    }
 
-    public string BestSolutionResultName {
-      get { return BestSolutionResultNameParameter.Value.Value; }
-      set { BestSolutionResultNameParameter.Value.Value = value; }
+    public string BestSolutionsResultName {
+      get { return BestSolutionsResultNameParameter.Value.Value; }
+      set { BestSolutionsResultNameParameter.Value.Value = value; }
+    }
+
+    public int N {
+      get { return NParameter.Value.Value; }
+      set { NParameter.Value.Value = value; }
+    }
+
+    public double MaximumSimilarity {
+      get { return MaximumSimilarityParameter.Value.Value; }
+      set { MaximumSimilarityParameter.Value.Value = value; }
     }
 
     #region Storing & Cloning
     [StorableConstructor]
-    protected BestScopeSolutionAnalyzer(bool deserializing) : base(deserializing) { }
-    protected BestScopeSolutionAnalyzer(BestScopeSolutionAnalyzer original, Cloner cloner) : base(original, cloner) { }
+    protected BestNScopesSolutionAnalyzer(bool deserializing) : base(deserializing) { }
+    protected BestNScopesSolutionAnalyzer(BestNScopesSolutionAnalyzer original, Cloner cloner) : base(original, cloner) { }
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new BestScopeSolutionAnalyzer(this, cloner);
-    }
-
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      // BackwardsCompatibility3.3
-      #region Backwards compatible code, remove with 3.4
-      if (!Parameters.ContainsKey("BestSolution ResultName"))
-        Parameters.Add(new FixedValueParameter<StringValue>("BestSolution ResultName", "The name of the result for storing the best solution.", new StringValue("Best Solution")));
-      if (Parameters.ContainsKey("BestSolution")) Parameters.Remove("BestSolution");
-      if (Parameters.ContainsKey("BestKnownSolution")) Parameters.Remove("BestKnownSolution");
-      #endregion
+      return new BestNScopesSolutionAnalyzer(this, cloner);
     }
     #endregion
-    public BestScopeSolutionAnalyzer()
+    public BestNScopesSolutionAnalyzer()
       : base() {
       Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem."));
       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the solutions."));
-      Parameters.Add(new FixedValueParameter<StringValue>("BestSolution ResultName", "The name of the result for storing the best solution.", new StringValue("Best Solution")));
-      Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution."));
+      Parameters.Add(new FixedValueParameter<StringValue>("BestSolutions ResultName", "The name of the result for storing the best solution.", new StringValue("Best Solutions")));
       Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the solution should be stored."));
+      Parameters.Add(new ValueParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The solution similarity calculator that is used to compare two solution scopes.", new QualitySimilarityCalculator()));
+      Parameters.Add(new FixedValueParameter<IntValue>("N", "The N best solutions that are kept.", new IntValue(10)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>("MaximumSimilarity", "The maximum similarity between two solutions in order to be remembered in the list.", new DoubleValue(0.8)));
     }
 
     public override IOperation Apply() {
-      ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
-      ResultCollection results = ResultsParameter.ActualValue;
-      bool max = MaximizationParameter.ActualValue.Value;
-      DoubleValue bestKnownQuality = BestKnownQualityParameter.ActualValue;
-
-      if (results.ContainsKey(BestSolutionResultName) && !typeof(IScope).IsAssignableFrom(results[BestSolutionResultName].DataType)) {
-        throw new InvalidOperationException(string.Format("Could not add best solution result, because there is already a result with the name \"{0}\" present in the result collection.", BestSolutionResultName));
+      var results = ResultsParameter.ActualValue;
+      if (results.ContainsKey(BestSolutionsResultName) && !typeof(ScopeList).IsAssignableFrom(results[BestSolutionsResultName].DataType)) {
+        throw new InvalidOperationException(string.Format("Could not add best solutions result, because there is already a result with the name \"{0}\" present in the result collection.", BestSolutionsResultName));
+      }
+      ScopeList bestScopes = null;
+      if (results.ContainsKey(BestSolutionsResultName)) {
+        bestScopes = (ScopeList)results[BestSolutionsResultName].Value;
+      } else {
+        bestScopes = new ScopeList();
+        results.Add(new Result(BestSolutionsResultName, bestScopes));
       }
 
-      int i = -1;
-      if (!max)
-        i = qualities.Select((x, index) => new { index, x.Value }).OrderBy(x => x.Value).First().index;
-      else i = qualities.Select((x, index) => new { index, x.Value }).OrderByDescending(x => x.Value).First().index;
+      var max = MaximizationParameter.ActualValue.Value;
+      var simCalc = SimilarityCalculatorParameter.Value;
+      var maxSim = MaximumSimilarity;
+      var qualityName = QualityParameter.TranslatedName;
+      var depth = QualityParameter.Depth;
 
-      IEnumerable<IScope> scopes = new IScope[] { ExecutionContext.Scope };
-      for (int j = 0; j < QualityParameter.Depth; j++)
+      IEnumerable<IScope> scopes = new [] { ExecutionContext.Scope };
+      for (var j = 0; j < depth; j++)
         scopes = scopes.SelectMany(x => x.SubScopes);
-      IScope currentBestScope = scopes.ToList()[i];
 
-      if (bestKnownQuality == null ||
-          max && qualities[i].Value > bestKnownQuality.Value
-          || !max && qualities[i].Value < bestKnownQuality.Value) {
-        BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[i].Value);
+      scopes = max ? scopes.OrderByDescending(x => ((DoubleValue)x.Variables[qualityName].Value).Value)
+                   : scopes.OrderBy(x => ((DoubleValue)x.Variables[qualityName].Value).Value);
+      
+      var newList = new ScopeList(bestScopes.Take(N));
+      var cloner = new Cloner();
+      // avoid cloning the results collection that the solution is put in
+      cloner.RegisterClonedObject(results, new ResultCollection());
+
+      foreach (var s in scopes) {
+        bool isDiverse = true, isBetterThanWorst = false, isIdentical = false;
+        var worstIdx = -1;
+        IScope worst = null;
+        var idx = 0;
+        foreach (var a in newList) {
+          if (IsBetter(s, a, qualityName, max)) {
+            isBetterThanWorst = true;
+            if (worst == null || IsBetter(worst, a, qualityName, max)) {
+              worst = a;
+              worstIdx = idx;
+            }
+          }
+          var similarity = simCalc.CalculateSolutionSimilarity(s, a);
+          if (similarity.IsAlmost(1.0)) isIdentical = true;
+          if (similarity > maxSim) isDiverse = false;
+          idx++;
+
+          if (isIdentical || (newList.Count >= N && !isDiverse)) break;
+        }
+        // to accept a new solution it needs to be
+        // A) not identical
+        // B) must be less similar than a certain value
+        // C) must be better than at least one solution already accepted
+        // The exception to B) and C) is when the list is not full yet
+        if (isIdentical || (newList.Count >= N && !(isDiverse && isBetterThanWorst))) continue;
+        // avoid cloning subscopes of the solution
+        cloner.RegisterClonedObject(s.SubScopes, new ScopeList());
+        newList.Add(cloner.Clone(s));
+        if (newList.Count > N) newList.RemoveAt(worstIdx);
       }
 
-      if (!results.ContainsKey(BestSolutionResultName)) {
-        var cloner = new Cloner();
-        //avoid cloning of subscopes and the results collection that the solution is put in
-        cloner.RegisterClonedObject(results, new ResultCollection());
-        cloner.RegisterClonedObject(currentBestScope.SubScopes, new ScopeList());
-        var solution = cloner.Clone(currentBestScope);
+      bestScopes.Replace(newList);
 
-        results.Add(new Result(BestSolutionResultName, solution));
-      } else {
-        var bestSolution = (IScope)results[BestSolutionResultName].Value;
-        string qualityName = QualityParameter.TranslatedName;
-        if (bestSolution.Variables.ContainsKey(qualityName)) {
-          double bestQuality = ((DoubleValue)bestSolution.Variables[qualityName].Value).Value;
-          if (max && qualities[i].Value > bestQuality
-              || !max && qualities[i].Value < bestQuality) {
-            var cloner = new Cloner();
-            //avoid cloning of subscopes and the results collection that the solution is put in
-            cloner.RegisterClonedObject(results, new ResultCollection());
-            cloner.RegisterClonedObject(currentBestScope.SubScopes, new ScopeList());
-            var solution = cloner.Clone(currentBestScope);
+      return base.Apply();
+    }
 
-            results[BestSolutionResultName].Value = solution;
-          }
-        }
-      }
-      return base.Apply();
+    private static bool IsBetter(IScope a, IScope b, string qualityName, bool max) {
+      return max ? ((DoubleValue)a.Variables[qualityName].Value).Value > ((DoubleValue)b.Variables[qualityName].Value).Value
+                 : ((DoubleValue)a.Variables[qualityName].Value).Value < ((DoubleValue)b.Variables[qualityName].Value).Value;
     }
   }