Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2457: added best-n scopes solution analyzer

File size: 8.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
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
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Operators;
26using HeuristicLab.Optimization;
27using HeuristicLab.Optimization.Operators;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using System;
31using System.Collections.Generic;
32using System.Linq;
33
34namespace HeuristicLab.Analysis {
35  /// <summary>
36  /// An operator that extracts (clones) the scope containing the best quality.
37  /// </summary>
38  [Item("BestNScopesSolutionAnalyzer", "An operator that maintains at most N scopes containing good quality solutions.")]
39  [StorableClass]
40  public class BestNScopesSolutionAnalyzer : SingleSuccessorOperator, IAnalyzer, ISingleObjectiveOperator {
41
42    public virtual bool EnabledByDefault {
43      get { return true; }
44    }
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    }
51    public IFixedValueParameter<StringValue> BestSolutionsResultNameParameter {
52      get { return (IFixedValueParameter<StringValue>)Parameters["BestSolutions ResultName"]; }
53    }
54    public IValueLookupParameter<ResultCollection> ResultsParameter {
55      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
56    }
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    }
66
67    public string BestSolutionsResultName {
68      get { return BestSolutionsResultNameParameter.Value.Value; }
69      set { BestSolutionsResultNameParameter.Value.Value = value; }
70    }
71
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
82    #region Storing & Cloning
83    [StorableConstructor]
84    protected BestNScopesSolutionAnalyzer(bool deserializing) : base(deserializing) { }
85    protected BestNScopesSolutionAnalyzer(BestNScopesSolutionAnalyzer original, Cloner cloner) : base(original, cloner) { }
86    public override IDeepCloneable Clone(Cloner cloner) {
87      return new BestNScopesSolutionAnalyzer(this, cloner);
88    }
89    #endregion
90    public BestNScopesSolutionAnalyzer()
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."));
94      Parameters.Add(new FixedValueParameter<StringValue>("BestSolutions ResultName", "The name of the result for storing the best solution.", new StringValue("Best Solutions")));
95      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the solution should be stored."));
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)));
99    }
100
101    public override IOperation Apply() {
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));
105      }
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      }
113
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;
119
120      IEnumerable<IScope> scopes = new [] { ExecutionContext.Scope };
121      for (var j = 0; j < depth; j++)
122        scopes = scopes.SelectMany(x => x.SubScopes);
123
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());
131
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++;
149
150          if (isIdentical || (newList.Count >= N && !isDiverse)) break;
151        }
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);
162      }
163
164      bestScopes.Replace(newList);
165
166      return base.Apply();
167    }
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    }
173  }
174}
Note: See TracBrowser for help on using the repository browser.