Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PerformanceComparison/HeuristicLab.Analysis/3.3/BestNScopesSolutionAnalyzer.cs @ 15529

Last change on this file since 15529 was 13744, checked in by abeham, 9 years ago

#2457: added best-n scopes solution analyzer

File size: 8.2 KB
RevLine 
[3872]1#region License Information
2/* HeuristicLab
[12012]3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[3872]4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
[4722]22using HeuristicLab.Common;
[3872]23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Operators;
26using HeuristicLab.Optimization;
[13744]27using HeuristicLab.Optimization.Operators;
[3872]28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
[13744]30using System;
31using System.Collections.Generic;
32using System.Linq;
[3872]33
34namespace HeuristicLab.Analysis {
35  /// <summary>
36  /// An operator that extracts (clones) the scope containing the best quality.
37  /// </summary>
[13744]38  [Item("BestNScopesSolutionAnalyzer", "An operator that maintains at most N scopes containing good quality solutions.")]
[3872]39  [StorableClass]
[13744]40  public class BestNScopesSolutionAnalyzer : SingleSuccessorOperator, IAnalyzer, ISingleObjectiveOperator {
[11615]41
[7172]42    public virtual bool EnabledByDefault {
43      get { return true; }
44    }
[3872]45    public LookupParameter<BoolValue> MaximizationParameter {
46      get { return (LookupParameter<BoolValue>)Parameters["Maximization"]; }
47    }
48    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
49      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
50    }
[13744]51    public IFixedValueParameter<StringValue> BestSolutionsResultNameParameter {
52      get { return (IFixedValueParameter<StringValue>)Parameters["BestSolutions ResultName"]; }
[11618]53    }
[3872]54    public IValueLookupParameter<ResultCollection> ResultsParameter {
55      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
56    }
[13744]57    public IValueParameter<ISolutionSimilarityCalculator> SimilarityCalculatorParameter {
58      get { return (IValueParameter<ISolutionSimilarityCalculator>)Parameters["SimilarityCalculator"]; }
59    }
60    private IFixedValueParameter<IntValue> NParameter {
61      get { return (IFixedValueParameter<IntValue>)Parameters["N"]; }
62    }
63    private IFixedValueParameter<DoubleValue> MaximumSimilarityParameter {
64      get { return (IFixedValueParameter<DoubleValue>)Parameters["MaximumSimilarity"]; }
65    }
[3872]66
[13744]67    public string BestSolutionsResultName {
68      get { return BestSolutionsResultNameParameter.Value.Value; }
69      set { BestSolutionsResultNameParameter.Value.Value = value; }
[11618]70    }
71
[13744]72    public int N {
73      get { return NParameter.Value.Value; }
74      set { NParameter.Value.Value = value; }
75    }
76
77    public double MaximumSimilarity {
78      get { return MaximumSimilarityParameter.Value.Value; }
79      set { MaximumSimilarityParameter.Value.Value = value; }
80    }
81
[4722]82    #region Storing & Cloning
83    [StorableConstructor]
[13744]84    protected BestNScopesSolutionAnalyzer(bool deserializing) : base(deserializing) { }
85    protected BestNScopesSolutionAnalyzer(BestNScopesSolutionAnalyzer original, Cloner cloner) : base(original, cloner) { }
[4722]86    public override IDeepCloneable Clone(Cloner cloner) {
[13744]87      return new BestNScopesSolutionAnalyzer(this, cloner);
[4722]88    }
89    #endregion
[13744]90    public BestNScopesSolutionAnalyzer()
[3872]91      : base() {
92      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem."));
93      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the solutions."));
[13744]94      Parameters.Add(new FixedValueParameter<StringValue>("BestSolutions ResultName", "The name of the result for storing the best solution.", new StringValue("Best Solutions")));
[3872]95      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the solution should be stored."));
[13744]96      Parameters.Add(new ValueParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The solution similarity calculator that is used to compare two solution scopes.", new QualitySimilarityCalculator()));
97      Parameters.Add(new FixedValueParameter<IntValue>("N", "The N best solutions that are kept.", new IntValue(10)));
98      Parameters.Add(new FixedValueParameter<DoubleValue>("MaximumSimilarity", "The maximum similarity between two solutions in order to be remembered in the list.", new DoubleValue(0.8)));
[3872]99    }
100
101    public override IOperation Apply() {
[13744]102      var results = ResultsParameter.ActualValue;
103      if (results.ContainsKey(BestSolutionsResultName) && !typeof(ScopeList).IsAssignableFrom(results[BestSolutionsResultName].DataType)) {
104        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));
[11615]105      }
[13744]106      ScopeList bestScopes = null;
107      if (results.ContainsKey(BestSolutionsResultName)) {
108        bestScopes = (ScopeList)results[BestSolutionsResultName].Value;
109      } else {
110        bestScopes = new ScopeList();
111        results.Add(new Result(BestSolutionsResultName, bestScopes));
112      }
[11615]113
[13744]114      var max = MaximizationParameter.ActualValue.Value;
115      var simCalc = SimilarityCalculatorParameter.Value;
116      var maxSim = MaximumSimilarity;
117      var qualityName = QualityParameter.TranslatedName;
118      var depth = QualityParameter.Depth;
[7172]119
[13744]120      IEnumerable<IScope> scopes = new [] { ExecutionContext.Scope };
121      for (var j = 0; j < depth; j++)
[11615]122        scopes = scopes.SelectMany(x => x.SubScopes);
[3872]123
[13744]124      scopes = max ? scopes.OrderByDescending(x => ((DoubleValue)x.Variables[qualityName].Value).Value)
125                   : scopes.OrderBy(x => ((DoubleValue)x.Variables[qualityName].Value).Value);
126     
127      var newList = new ScopeList(bestScopes.Take(N));
128      var cloner = new Cloner();
129      // avoid cloning the results collection that the solution is put in
130      cloner.RegisterClonedObject(results, new ResultCollection());
[3872]131
[13744]132      foreach (var s in scopes) {
133        bool isDiverse = true, isBetterThanWorst = false, isIdentical = false;
134        var worstIdx = -1;
135        IScope worst = null;
136        var idx = 0;
137        foreach (var a in newList) {
138          if (IsBetter(s, a, qualityName, max)) {
139            isBetterThanWorst = true;
140            if (worst == null || IsBetter(worst, a, qualityName, max)) {
141              worst = a;
142              worstIdx = idx;
143            }
144          }
145          var similarity = simCalc.CalculateSolutionSimilarity(s, a);
146          if (similarity.IsAlmost(1.0)) isIdentical = true;
147          if (similarity > maxSim) isDiverse = false;
148          idx++;
[11615]149
[13744]150          if (isIdentical || (newList.Count >= N && !isDiverse)) break;
[3872]151        }
[13744]152        // to accept a new solution it needs to be
153        // A) not identical
154        // B) must be less similar than a certain value
155        // C) must be better than at least one solution already accepted
156        // The exception to B) and C) is when the list is not full yet
157        if (isIdentical || (newList.Count >= N && !(isDiverse && isBetterThanWorst))) continue;
158        // avoid cloning subscopes of the solution
159        cloner.RegisterClonedObject(s.SubScopes, new ScopeList());
160        newList.Add(cloner.Clone(s));
161        if (newList.Count > N) newList.RemoveAt(worstIdx);
[3872]162      }
[13744]163
164      bestScopes.Replace(newList);
165
[3872]166      return base.Apply();
167    }
[13744]168
169    private static bool IsBetter(IScope a, IScope b, string qualityName, bool max) {
170      return max ? ((DoubleValue)a.Variables[qualityName].Value).Value > ((DoubleValue)b.Variables[qualityName].Value).Value
171                 : ((DoubleValue)a.Variables[qualityName].Value).Value < ((DoubleValue)b.Variables[qualityName].Value).Value;
172    }
[3872]173  }
174}
Note: See TracBrowser for help on using the repository browser.