Free cookie consent management tool by TermsFeed Policy Generator

source: branches/DataAnalysis/HeuristicLab.Problems.DataAnalysis/3.3/Operators/DynOpEqHistogramInitializer.cs @ 4222

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

Changed operator to adapt the target distribution for dynamic operator equalization to use scaled (0..1) qualities and treat minimization problem correctly. #1142

File size: 9.2 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 alglib;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
32using System.Collections.Generic;
33
34namespace HeuristicLab.Problems.DataAnalysis.Operators {
35  [Item("DynOpEqHistogramInitializer", "Dynamic Operator Equalization Histogram Initializer.")]
36  [StorableClass]
37  public class DynOpEqHistogramInitializer : SingleSuccessorOperator {
38    public ILookupParameter<ItemList<IntValue>> BinCapacityParameter {
39      get { return (ILookupParameter<ItemList<IntValue>>)Parameters["BinCapacity"]; }
40    }
41    public ILookupParameter<ItemList<ItemList<DoubleValue>>> AcceptedBinQualitiesParameter {
42      get { return (ILookupParameter<ItemList<ItemList<DoubleValue>>>)Parameters["AcceptedBinQualities"]; }
43    }
44    public ILookupParameter<IntValue> PopulationSizeParameter {
45      get { return (ILookupParameter<IntValue>)Parameters["PopulationSize"]; }
46    }
47    public IScopeTreeLookupParameter<SymbolicExpressionTree> SymbolicExpressionTreeParameter {
48      get { return (IScopeTreeLookupParameter<SymbolicExpressionTree>)Parameters["SymbolicExpressionTree"]; }
49    }
50    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
51      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
52    }
53    public ILookupParameter BinSizeParameter {
54      get { return (ILookupParameter<IntValue>)Parameters["BinSize"]; }
55    }
56    public ILookupParameter<ItemList<IntValue>> AcceptedCountsParameter {
57      get { return (ILookupParameter<ItemList<IntValue>>)Parameters["AcceptedCounts"]; }
58    }
59    public ILookupParameter<ItemList<IntValue>> TotalCountsParameter {
60      get { return (ILookupParameter<ItemList<IntValue>>)Parameters["TotalCounts"]; }
61    }
62    public ILookupParameter<BoolValue> MaximizationParameter {
63      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
64    }
65
66    public DynOpEqHistogramInitializer()
67      : base() {
68      Parameters.Add(new ScopeTreeLookupParameter<SymbolicExpressionTree>("SymbolicExpressionTree"));
69      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality"));
70      Parameters.Add(new LookupParameter<IntValue>("PopulationSize"));
71      Parameters.Add(new ValueLookupParameter<IntValue>("BinSize", new IntValue(5)));
72      Parameters.Add(new LookupParameter<ItemList<IntValue>>("BinCapacity"));
73      Parameters.Add(new LookupParameter<ItemList<ItemList<DoubleValue>>>("AcceptedBinQualities"));
74      Parameters.Add(new LookupParameter<ItemList<IntValue>>("AcceptedCounts"));
75      Parameters.Add(new LookupParameter<ItemList<IntValue>>("TotalCounts"));
76      Parameters.Add(new LookupParameter<BoolValue>("Maximization"));
77    }
78
79    public override IOperation Apply() {
80      if (BinCapacityParameter.ActualValue == null) {
81        InitDefaultCapacityHistogram();
82      } else {
83        ItemList<ItemList<DoubleValue>> acceptedBinQualities = AcceptedBinQualitiesParameter.ActualValue;
84        ItemList<IntValue> acceptedCounts = AcceptedCountsParameter.ActualValue;
85        ItemList<IntValue> totalCounts = TotalCountsParameter.ActualValue;
86
87        int popSize = PopulationSizeParameter.ActualValue.Value;
88
89        ScaleBinQualities(acceptedBinQualities, 0, 1, MaximizationParameter.ActualValue.Value);
90
91        double avgQualitySum = (from binAccepted in acceptedBinQualities
92                                where binAccepted.Count > 0
93                                select (from quality in binAccepted
94                                        select quality.Value).Average())
95                                      .Sum();
96        ItemList<IntValue> binCapacity = BinCapacityParameter.ActualValue;
97        int totalCapacity = 0;
98        for (int i = 0; i < binCapacity.Count; i++) {
99          double avgBinQuality = (from quality in acceptedBinQualities[i]
100                                  select quality.Value)
101                                 .DefaultIfEmpty(0.0)
102                                 .Average();
103
104          binCapacity[i].Value = Math.Max(1, (int)Math.Round(popSize * (avgBinQuality / avgQualitySum)));
105          // rounding can lead to loss of capacity
106          // this is problematic if the bin capacities are strict
107          totalCapacity += binCapacity[i].Value;
108          acceptedBinQualities[i].Clear();
109          acceptedCounts[i].Value = 0;
110        }
111        // distribute the remaining slots starting with the largest bins
112        IEnumerator<IntValue> orderedBinCapacities = binCapacity.OrderBy(x => -x.Value).GetEnumerator();
113
114        while (totalCapacity < popSize & orderedBinCapacities.MoveNext()) {
115          orderedBinCapacities.Current.Value = orderedBinCapacities.Current.Value + 1;
116          totalCapacity++;
117        }
118        if (totalCapacity < popSize) throw new InvalidProgramException("The sum of bin capacities doesn't match the population size");
119        for (int i = 0; i < totalCounts.Count; i++)
120          totalCounts[i].Value = 0;
121      }
122      return base.Apply();
123    }
124
125    public static void ScaleBinQualities(ItemList<ItemList<DoubleValue>> acceptedBinQualities, double min, double max, bool maximization) {
126      double minValue = (from bin in acceptedBinQualities
127                         from value in bin
128                         select value.Value).Min();
129      double maxValue = (from bin in acceptedBinQualities
130                         from value in bin
131                         select value.Value).Max();
132
133      if (!maximization) {
134        double tmp = minValue;
135        minValue = maxValue;
136        maxValue = tmp;
137      }
138
139      double valuesRange = maxValue - minValue;
140      double targetRange = max - min;
141
142      foreach (var bin in acceptedBinQualities) {
143        foreach (var value in bin) {
144          double unitScaledValue = (value.Value - minValue) / valuesRange;
145          double targetScaledValue = unitScaledValue * targetRange + min;
146          value.Value = targetScaledValue;
147        }
148      }
149    }
150
151    private void InitDefaultCapacityHistogram() {
152      ItemArray<SymbolicExpressionTree> trees = SymbolicExpressionTreeParameter.ActualValue;
153      ItemArray<DoubleValue> quality = QualityParameter.ActualValue;
154      var binCapacities = new ItemList<IntValue>();
155      var acceptedQuality = new ItemList<ItemList<DoubleValue>>(20);
156      var acceptedCounts = new ItemList<IntValue>();
157      var totalCounts = new ItemList<IntValue>();
158      BinCapacityParameter.ActualValue = binCapacities;
159      AcceptedBinQualitiesParameter.ActualValue = acceptedQuality;
160      TotalCountsParameter.ActualValue = totalCounts;
161      AcceptedCountsParameter.ActualValue = acceptedCounts;
162      for (int i = 0; i < trees.Length; i++) {
163        int binIndex = GetBinIndexForSize(trees[i].Size);
164        if (Exists(binIndex)) {
165          AddToBin(binIndex, quality[i].Value);
166        } else {
167          CreateNewBin(binIndex);
168        }
169      }
170    }
171
172    private void CreateNewBin(int binIndex) {
173      ItemList<IntValue> binCapacities = BinCapacityParameter.ActualValue;
174      ItemList<ItemList<DoubleValue>> acceptedQualities = AcceptedBinQualitiesParameter.ActualValue;
175      ItemList<IntValue> acceptedCounts = AcceptedCountsParameter.ActualValue;
176      ItemList<IntValue> totalCounts = TotalCountsParameter.ActualValue;
177      for (int i = binCapacities.Count; i <= binIndex; i++) {
178        binCapacities.Add(new IntValue(1));
179        acceptedQualities.Add(new ItemList<DoubleValue>(10));
180        acceptedCounts.Add(new IntValue(0));
181        totalCounts.Add(new IntValue(0));
182      }
183    }
184
185    private void AddToBin(int binIndex, double quality) {
186      ItemList<IntValue> binCapacity = BinCapacityParameter.ActualValue;
187      binCapacity[binIndex].Value = binCapacity[binIndex].Value + 1;
188    }
189
190    private bool Exists(int binIndex) {
191      // if the bin has a capacity set then it exists
192      ItemList<IntValue> binCapacities = BinCapacityParameter.ActualValue;
193      return binIndex < binCapacities.Count;
194    }
195
196    private int GetBinIndexForSize(int size) {
197      int binSize = ((IntValue)BinSizeParameter.ActualValue).Value;
198      return (int)Math.Floor((size - 3.0) / binSize);
199    }
200  }
201}
Note: See TracBrowser for help on using the repository browser.