Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/Operators/DynOpEqComparator.cs @ 11986

Last change on this file since 11986 was 5275, checked in by gkronber, 14 years ago

Merged changes from trunk to data analysis exploration branch and added fractional distance metric evaluator. #1142

File size: 12.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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 System.Linq;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Operators;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
31using System.Collections.Generic;
32using HeuristicLab.Common;
33
34namespace HeuristicLab.Problems.DataAnalysis.Operators {
35  [Item("DynOpEqComparator", "Dynamic Operator Equalization.")]
36  [StorableClass]
37  public class DynOpEqComparator : SingleSuccessorOperator, ISubScopesQualityComparator {
38    public IValueLookupParameter<BoolValue> MaximizationParameter {
39      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
40    }
41    public ILookupParameter<BoolValue> ResultParameter {
42      get { return (ILookupParameter<BoolValue>)Parameters["Result"]; }
43    }
44    public ILookupParameter<DoubleValue> LeftSideParameter {
45      get { return (ILookupParameter<DoubleValue>)Parameters["LeftSide"]; }
46    }
47    public ILookupParameter<ItemArray<DoubleValue>> RightSideParameter {
48      get { return (ILookupParameter<ItemArray<DoubleValue>>)Parameters["RightSide"]; }
49    }
50    public ILookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
51      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
52    }
53    public ILookupParameter<DoubleValue> BestQualityParameter {
54      get { return (ILookupParameter<DoubleValue>)Parameters["BestQuality"]; }
55    }
56    public IValueLookupParameter<IntValue> BinSizeParameter {
57      get { return (IValueLookupParameter<IntValue>)Parameters["BinSize"]; }
58    }
59    public ILookupParameter<ItemList<IntValue>> BinCapacityParameter {
60      get { return (ILookupParameter<ItemList<IntValue>>)Parameters["BinCapacity"]; }
61    }
62    public ILookupParameter<ItemList<ItemList<DoubleValue>>> AcceptedBinQualitiesParameter {
63      get { return (ILookupParameter<ItemList<ItemList<DoubleValue>>>)Parameters["AcceptedBinQualities"]; }
64    }
65    public ILookupParameter<ItemList<IntValue>> AcceptedCountsParameter {
66      get { return (ILookupParameter<ItemList<IntValue>>)Parameters["AcceptedCounts"]; }
67    }
68    public ILookupParameter<ItemList<IntValue>> TotalCountsParameter {
69      get { return (ILookupParameter<ItemList<IntValue>>)Parameters["TotalCounts"]; }
70    }
71    public IValueLookupParameter<BoolValue> AntiOverfitParameter {
72      get { return (IValueLookupParameter<BoolValue>)Parameters["AntiOverfit"]; }
73    }
74    public ILookupParameter<DoubleValue> CurrentBestValidationQualityParameter {
75      get { return (ILookupParameter<DoubleValue>)Parameters["Current best validation quality"]; }
76    }
77    public ILookupParameter<DoubleValue> BestValidationQualityParameter {
78      get { return (ILookupParameter<DoubleValue>)Parameters["Best solution quality (validation)"]; }
79    }
80    public IValueLookupParameter<DoubleValue> CRaiseParameter {
81      get { return (IValueLookupParameter<DoubleValue>)Parameters["CRaise"]; }
82    }
83
84    [StorableConstructor]
85    protected DynOpEqComparator(bool deserializing) : base(deserializing) { }
86    protected DynOpEqComparator(DynOpEqComparator original, Cloner cloner)
87      : base(original, cloner) {
88    }
89    public DynOpEqComparator()
90      : base() {
91      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, false otherwise"));
92      Parameters.Add(new LookupParameter<BoolValue>("Result", "The result of the comparison: True means Quality is better, False means it is worse than parents."));
93      Parameters.Add(new LookupParameter<DoubleValue>("LeftSide", "The quality of the child."));
94      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("RightSide", "The qualities of the parents."));
95      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree", "The newly created child."));
96      Parameters.Add(new LookupParameter<DoubleValue>("BestQuality"));
97      Parameters.Add(new ValueLookupParameter<IntValue>("BinSize", new IntValue(5)));
98      Parameters.Add(new LookupParameter<ItemList<IntValue>>("BinCapacity"));
99      Parameters.Add(new LookupParameter<ItemList<ItemList<DoubleValue>>>("AcceptedBinQualities"));
100      Parameters.Add(new LookupParameter<ItemList<IntValue>>("AcceptedCounts"));
101      Parameters.Add(new LookupParameter<ItemList<IntValue>>("TotalCounts"));
102      Parameters.Add(new ValueLookupParameter<BoolValue>("AntiOverfit", new BoolValue(false)));
103      Parameters.Add(new LookupParameter<DoubleValue>("Current best validation quality"));
104      Parameters.Add(new LookupParameter<DoubleValue>("Best solution quality (validation)"));
105      Parameters.Add(new ValueLookupParameter<DoubleValue>("CRaise", "Necessary quality improvement per bin to allow extensions.", new DoubleValue(0.005)));
106    }
107
108    public override IDeepCloneable Clone(Cloner cloner) {
109      return new DynOpEqComparator(this, cloner);
110    }
111    public override IOperation Apply() {
112      if (ResultParameter.ActualValue == null || ResultParameter.ActualValue.Value == true) {
113        var tree = SymbolicExpressionTreeParameter.ActualValue;
114        int size = tree.Size;
115        int bin = GetBinIndexForSize(size);
116        if (LeftSideParameter.ActualValue == null) {
117          // not yet evaluated
118          #region debugging
119          ItemList<IntValue> totalCounts = TotalCountsParameter.ActualValue;
120          while (bin >= totalCounts.Count) totalCounts.Add(new IntValue(0));
121          totalCounts[bin].Value = totalCounts[bin].Value + 1;
122          #endregion
123          if (!Exists(bin)) {
124            if (AntiOverfitParameter.ActualValue.Value) {
125              // reject more complex solutions if the current validation quality is worse than the best so far
126              ResultParameter.ActualValue = new BoolValue(!IsOverfitting());
127            } else {
128              // new bin -> evaluate and check later
129              ResultParameter.ActualValue = new BoolValue(true);
130            }
131          } else {
132            // bin exists:
133            // if bin is full -> reject
134            // otherwise -> evaluate and check success criterion
135            ResultParameter.ActualValue = new BoolValue(IsNotFull(bin));
136          }
137        } else {
138          double leftQuality = LeftSideParameter.ActualValue.Value;
139          ResultParameter.ActualValue = new BoolValue(Accept(size, bin, leftQuality));
140        }
141      }
142      return base.Apply();
143    }
144
145    private bool IsOverfitting() {
146      bool maximization = MaximizationParameter.ActualValue.Value;
147      if (CurrentBestValidationQualityParameter.ActualValue != null && BestValidationQualityParameter.ActualValue != null) {
148        double currentValidationQuality = CurrentBestValidationQualityParameter.ActualValue.Value;
149        double bestValidationQuality = BestValidationQualityParameter.ActualValue.Value;
150        return maximization ? currentValidationQuality < bestValidationQuality : currentValidationQuality > bestValidationQuality;
151      } else
152        return false;
153    }
154
155    private int GetBinIndexForSize(int size) {
156      return (int)Math.Floor((size - 3.0) / BinSizeParameter.ActualValue.Value);
157    }
158
159    private bool Accept(int size, int binIndex, double solutionQuality) {
160      bool accept = false;
161      if (Exists(binIndex)) {
162        //if (IsNotFull(binIndex) /*||
163        //NewBestOfBin(solutionQuality, binIndex)*/) {       
164        AddToBin(solutionQuality, binIndex);
165        accept = true;
166        UpdateBestQuality(solutionQuality);
167        //}
168      } else if (NewBestOfRun(solutionQuality) && SignificantImprovement(solutionQuality, binIndex)) {
169        CreateNewBin(binIndex);
170        AddToBin(solutionQuality, binIndex);
171        accept = true;
172        UpdateBestQuality(solutionQuality);
173      }
174      return accept;
175    }
176
177    private void UpdateBestQuality(double solutionQuality) {
178      bool maximization = MaximizationParameter.ActualValue.Value;
179      double bestQuality = BestQualityParameter.ActualValue.Value;
180      if ((maximization && bestQuality < solutionQuality) ||
181         (!maximization && solutionQuality < bestQuality))
182        BestQualityParameter.ActualValue.Value = solutionQuality;
183    }
184
185    private bool SignificantImprovement(double solutionQuality, int newIndex) {
186      var binCapacities = BinCapacityParameter.ActualValue;
187      int binDiff = newIndex - binCapacities.Count + 1;
188      double bestQuality = BestQualityParameter.ActualValue.Value;
189      bool maximization = MaximizationParameter.ActualValue.Value;
190
191      double relativeQuality = maximization ? solutionQuality / bestQuality - 1 : bestQuality / solutionQuality - 1;
192      return relativeQuality >= binDiff * CRaiseParameter.ActualValue.Value;
193    }
194
195    private void AddToBin(double solutionQuality, int binIndex) {
196      ItemList<DoubleValue> acceptedBinQualities = AcceptedBinQualitiesParameter.ActualValue[binIndex];
197      ItemList<IntValue> acceptedCounts = AcceptedCountsParameter.ActualValue;
198      acceptedBinQualities.Add(new DoubleValue(solutionQuality));
199      acceptedCounts[binIndex].Value = acceptedCounts[binIndex].Value + 1;
200    }
201
202    private bool NewBestOfRun(double solutionQuality) {
203      bool maximization = MaximizationParameter.ActualValue.Value;
204      double bestQuality = BestQualityParameter.ActualValue.Value;
205      return maximization ? solutionQuality > bestQuality : solutionQuality < bestQuality;
206    }
207
208    private void CreateNewBin(int binIndex) {
209      ItemList<IntValue> binCapacities = BinCapacityParameter.ActualValue;
210      ItemList<ItemList<DoubleValue>> acceptedQualities = AcceptedBinQualitiesParameter.ActualValue;
211      ItemList<IntValue> acceptedCounts = AcceptedCountsParameter.ActualValue;
212
213      // create empty bins of capacity one up to the newly created bin
214      for (int i = binCapacities.Count; i <= binIndex; i++) {
215        binCapacities.Add(new IntValue(1));
216        acceptedQualities.Add(new ItemList<DoubleValue>(10));
217        acceptedCounts.Add(new IntValue(0));
218      }
219    }
220
221    //private bool NewBestOfBin(double solutionQuality, int binIndex) {
222    //  ItemList<ItemList<DoubleValue>> acceptedQualities = AcceptedBinQualitiesParameter.ActualValue;
223    //  if (acceptedQualities[binIndex].Count == 0) return true;
224    //  bool maximization = MaximizationParameter.ActualValue.Value;
225    //  IEnumerable<double> binQualities = acceptedQualities[binIndex].Select(x => x.Value);
226    //  // binQualities are always sorted so that the best is in bin 0
227    //  return maximization ? solutionQuality > binQualities.First() :
228    //    solutionQuality < binQualities.First();
229    //}
230
231    private bool IsNotFull(int binIndex) {
232      ItemList<IntValue> binCapacities = BinCapacityParameter.ActualValue;
233      ItemList<ItemList<DoubleValue>> acceptedQualities = AcceptedBinQualitiesParameter.ActualValue;
234      return acceptedQualities[binIndex].Count < binCapacities[binIndex].Value;
235    }
236
237    private bool Exists(int binIndex) {
238      // if the bin has a capacity set then it exists
239      ItemList<IntValue> binCapacities = BinCapacityParameter.ActualValue;
240      return binIndex < binCapacities.Count;
241    }
242  }
243}
Note: See TracBrowser for help on using the repository browser.