Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Analysis/3.3/QualityAnalysis/BestAverageWorstQualityAnalyzer.cs @ 6042

Last change on this file since 6042 was 6042, checked in by abeham, 12 years ago

#1425

  • Changed LocalImprovementOperators
    • Changed interface (made Problem a property, added a property that denotes the type of the problem that it can be applied on, added some general parameters)
    • Added some parameters and wiring
    • Changed move discovery and parameterization and added a helper class to ease finding compatible move operators
    • Discovering only IMultiMoveOperators and IExhaustiveMoveOperators and putting the multi move ones first
    • Fixed bug in Apply method that could create an endless string of nested execution contexts
    • Removed all problem specific analyzers in the two local improvement operators and only left the BestAverageWorstQualityAnalyzer since it doesn't make any sense to perform diversity or allele analysis during local improvement in the most common case and those analyzers take a lot of time (one can always add them manually should he/she be interested). The analyzers in the VNS's Analyzer parameter are left untouched.
  • Removed shaking operator and interface from VNS plugin and added that to Optimization and Optimization.Operators
  • Changed some ValueParameters to ConstrainedValueParameters and added type discovery to fill them (using the ProblemType property to get compatible local improvement operators)
  • Added missing GPL license headers
  • Changed some ValueParameters to the new FixedValueParameters
  • Added an additional encoding specific ShakingOperator to each encoding and added that to each problem
    • reason is that only the problem/encoding can really decide if a shaking operator is meaningful or not
  • Fixed an unrelated bug in the BestAverageWorstQualityAnalyzer that I encountered (and made the fix backwards compatible)
    • Also added a snippet for creating the backwards compatible comment marker and region
  • Fixed the operator graph of the VNS main loop
    • The condition to continue only when the local search was not successful is not necessary and is not part of the VNS definition as far as I know it (only condition to break the inner loop is when k reaches k_max)
  • Changed the ShakingOperator to input current index and output the maximum number of neighborhoods instead of a boolean that indicates that the last index has been reached since the maximum number is a little more generally useful and equally powerful in modeling
    • Remodeled the VNS main loop to check for k < k_max in order to continue the inner loop
  • other changes that I forgot...

Still necessary

  • test, test, test
  • check for backwards compatible breakers
  • add a maximum evaluated solutions stop criterion
  • optionally: implement fast problem specific local search improvement operators that do not build on the whole generic overhead (e.g. a 2-opt TSP specific local search operator). The idea of VNS is really to converge to a local optimum which is difficult to achieve using the current rather limited termination options
File size: 11.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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 System;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Operators;
27using HeuristicLab.Optimization;
28using HeuristicLab.Optimization.Operators;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Analysis {
33  /// <summary>
34  /// An operator which analyzes the best, average and worst quality of solutions in the scope tree.
35  /// </summary>
36  [Item("BestAverageWorstQualityAnalyzer", "An operator which analyzes the best, average and worst quality of solutions in the scope tree.")]
37  [StorableClass]
38  public sealed class BestAverageWorstQualityAnalyzer : AlgorithmOperator, IAnalyzer {
39    #region Parameter properties
40    public ValueLookupParameter<BoolValue> MaximizationParameter {
41      get { return (ValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
42    }
43    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
44      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
45    }
46    public ValueLookupParameter<DoubleValue> BestKnownQualityParameter {
47      get { return (ValueLookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
48    }
49    public ValueLookupParameter<DoubleValue> BestQualityParameter {
50      get { return (ValueLookupParameter<DoubleValue>)Parameters["BestQuality"]; }
51    }
52    public ValueLookupParameter<DoubleValue> CurrentBestQualityParameter {
53      get { return (ValueLookupParameter<DoubleValue>)Parameters["CurrentBestQuality"]; }
54    }
55    public ValueLookupParameter<DoubleValue> CurrentAverageQualityParameter {
56      get { return (ValueLookupParameter<DoubleValue>)Parameters["CurrentAverageQuality"]; }
57    }
58    public ValueLookupParameter<DoubleValue> CurrentWorstQualityParameter {
59      get { return (ValueLookupParameter<DoubleValue>)Parameters["CurrentWorstQuality"]; }
60    }
61    public ValueLookupParameter<DataTable> QualitiesParameter {
62      get { return (ValueLookupParameter<DataTable>)Parameters["Qualities"]; }
63    }
64    public ValueLookupParameter<DoubleValue> AbsoluteDifferenceBestKnownToBestParameter {
65      get { return (ValueLookupParameter<DoubleValue>)Parameters["AbsoluteDifferenceBestKnownToBest"]; }
66    }
67    public ValueLookupParameter<PercentValue> RelativeDifferenceBestKnownToBestParameter {
68      get { return (ValueLookupParameter<PercentValue>)Parameters["RelativeDifferenceBestKnownToBest"]; }
69    }
70    public ValueLookupParameter<ResultCollection> ResultsParameter {
71      get { return (ValueLookupParameter<ResultCollection>)Parameters["Results"]; }
72    }
73    #endregion
74
75    #region Properties
76    private BestQualityMemorizer BestQualityMemorizer {
77      get { return (BestQualityMemorizer)OperatorGraph.InitialOperator; }
78    }
79    private BestAverageWorstQualityCalculator BestAverageWorstQualityCalculator {
80      get { return (BestAverageWorstQualityCalculator)BestQualityMemorizer.Successor; }
81    }
82    #endregion
83
84    #region Storing & Cloning
85    [StorableConstructor]
86    private BestAverageWorstQualityAnalyzer(bool deserializing) : base(deserializing) { }
87    private BestAverageWorstQualityAnalyzer(BestAverageWorstQualityAnalyzer original, Cloner cloner)
88      : base(original, cloner) {
89      Initialize();
90    }
91    public override IDeepCloneable Clone(Cloner cloner) {
92      return new BestAverageWorstQualityAnalyzer(this, cloner);
93    }
94    #endregion
95    public BestAverageWorstQualityAnalyzer()
96      : base() {
97      #region Create parameters
98      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, otherwise false."));
99      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The value which represents the quality of a solution."));
100      Parameters.Add(new ValueLookupParameter<DoubleValue>("BestKnownQuality", "The best known quality value found so far."));
101      Parameters.Add(new ValueLookupParameter<DoubleValue>("BestQuality", "The best quality value found in the current run."));
102      Parameters.Add(new ValueLookupParameter<DoubleValue>("CurrentBestQuality", "The best quality value found in the current population."));
103      Parameters.Add(new ValueLookupParameter<DoubleValue>("CurrentAverageQuality", "The average quality value of all solutions in the current population."));
104      Parameters.Add(new ValueLookupParameter<DoubleValue>("CurrentWorstQuality", "The worst quality value found in the current population."));
105      Parameters.Add(new ValueLookupParameter<DataTable>("Qualities", "The data table to store the current best, current average, current worst, best and best known quality value."));
106      Parameters.Add(new ValueLookupParameter<DoubleValue>("AbsoluteDifferenceBestKnownToBest", "The absolute difference of the best known quality value to the best quality value."));
107      Parameters.Add(new ValueLookupParameter<PercentValue>("RelativeDifferenceBestKnownToBest", "The relative difference of the best known quality value to the best quality value."));
108      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The results collection where the analysis values should be stored."));
109      #endregion
110
111      #region Create operators
112      BestQualityMemorizer bestQualityMemorizer = new BestQualityMemorizer();
113      BestAverageWorstQualityCalculator bestAverageWorstQualityCalculator = new BestAverageWorstQualityCalculator();
114      DataTableValuesCollector dataTableValuesCollector = new DataTableValuesCollector();
115      QualityDifferenceCalculator qualityDifferenceCalculator = new QualityDifferenceCalculator();
116      ResultsCollector resultsCollector = new ResultsCollector();
117
118      bestQualityMemorizer.BestQualityParameter.ActualName = BestQualityParameter.Name;
119      bestQualityMemorizer.MaximizationParameter.ActualName = MaximizationParameter.Name;
120      bestQualityMemorizer.QualityParameter.ActualName = QualityParameter.Name;
121      bestQualityMemorizer.QualityParameter.Depth = QualityParameter.Depth;
122
123      bestAverageWorstQualityCalculator.AverageQualityParameter.ActualName = CurrentAverageQualityParameter.Name;
124      bestAverageWorstQualityCalculator.BestQualityParameter.ActualName = CurrentBestQualityParameter.Name;
125      bestAverageWorstQualityCalculator.MaximizationParameter.ActualName = MaximizationParameter.Name;
126      bestAverageWorstQualityCalculator.QualityParameter.ActualName = QualityParameter.Name;
127      bestAverageWorstQualityCalculator.QualityParameter.Depth = QualityParameter.Depth;
128      bestAverageWorstQualityCalculator.WorstQualityParameter.ActualName = CurrentWorstQualityParameter.Name;
129
130      dataTableValuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("CurrentBestQuality", null, CurrentBestQualityParameter.Name));
131      dataTableValuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("CurrentAverageQuality", null, CurrentAverageQualityParameter.Name));
132      dataTableValuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("CurrentWorstQuality", null, CurrentWorstQualityParameter.Name));
133      dataTableValuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("BestQuality", null, BestQualityParameter.Name));
134      dataTableValuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("BestKnownQuality", null, BestKnownQualityParameter.Name));
135      dataTableValuesCollector.DataTableParameter.ActualName = QualitiesParameter.Name;
136
137      qualityDifferenceCalculator.AbsoluteDifferenceParameter.ActualName = AbsoluteDifferenceBestKnownToBestParameter.Name;
138      qualityDifferenceCalculator.FirstQualityParameter.ActualName = BestKnownQualityParameter.Name;
139      qualityDifferenceCalculator.RelativeDifferenceParameter.ActualName = RelativeDifferenceBestKnownToBestParameter.Name;
140      qualityDifferenceCalculator.SecondQualityParameter.ActualName = BestQualityParameter.Name;
141
142      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("CurrentBestQuality", null, CurrentBestQualityParameter.Name));
143      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("CurrentAverageQuality", null, CurrentAverageQualityParameter.Name));
144      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("CurrentWorstQuality", null, CurrentWorstQualityParameter.Name));
145      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("BestQuality", null, BestQualityParameter.Name));
146      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("BestKnownQuality", null, BestKnownQualityParameter.Name));
147      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("AbsoluteDifferenceBestKnownToBest", null, AbsoluteDifferenceBestKnownToBestParameter.Name));
148      resultsCollector.CollectedValues.Add(new LookupParameter<PercentValue>("RelativeDifferenceBestKnownToBest", null, RelativeDifferenceBestKnownToBestParameter.Name));
149      resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>(QualitiesParameter.Name));
150      resultsCollector.ResultsParameter.ActualName = ResultsParameter.Name;
151      #endregion
152
153      #region Create operator graph
154      OperatorGraph.InitialOperator = bestQualityMemorizer;
155      bestQualityMemorizer.Successor = bestAverageWorstQualityCalculator;
156      bestAverageWorstQualityCalculator.Successor = dataTableValuesCollector;
157      dataTableValuesCollector.Successor = qualityDifferenceCalculator;
158      qualityDifferenceCalculator.Successor = resultsCollector;
159      resultsCollector.Successor = null;
160      #endregion
161
162      Initialize();
163    }
164
165    [StorableHook(HookType.AfterDeserialization)]
166    private void AfterDeserialization() {
167      Initialize();
168      // BackwardsCompatibility3.3
169      #region Backwards compatible code, remove with 3.4
170      if (Parameters["Results"] is ValueLookupParameter<VariableCollection>) {
171        Parameters.Remove("Results");
172        Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The results collection where the analysis values should be stored."));
173      }
174      #endregion
175    }
176
177    private void Initialize() {
178      QualityParameter.DepthChanged += new EventHandler(QualityParameter_DepthChanged);
179    }
180
181    private void QualityParameter_DepthChanged(object sender, System.EventArgs e) {
182      BestQualityMemorizer.QualityParameter.Depth = QualityParameter.Depth;
183      BestAverageWorstQualityCalculator.QualityParameter.Depth = QualityParameter.Depth;
184    }
185  }
186}
Note: See TracBrowser for help on using the repository browser.