source: trunk/sources/HeuristicLab.Selection/3.3/ProportionalSelector.cs @ 7996

Last change on this file since 7996 was 7996, checked in by mkommend, 9 years ago

#1871: Improved performance of ProportionalSelector.

File size: 4.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Selection {
33  /// <summary>
34  /// A quality proportional selection operator which considers a single double quality value for selection.
35  /// </summary>
36  [Item("ProportionalSelector", "A quality proportional selection operator which considers a single double quality value for selection.")]
37  [StorableClass]
38  public sealed class ProportionalSelector : StochasticSingleObjectiveSelector, ISingleObjectiveSelector {
39    private ValueParameter<BoolValue> WindowingParameter {
40      get { return (ValueParameter<BoolValue>)Parameters["Windowing"]; }
41    }
42
43    public BoolValue Windowing {
44      get { return WindowingParameter.Value; }
45      set { WindowingParameter.Value = value; }
46    }
47
48    [StorableConstructor]
49    private ProportionalSelector(bool deserializing) : base(deserializing) { }
50    private ProportionalSelector(ProportionalSelector original, Cloner cloner)
51      : base(original, cloner) {
52    }
53    public override IDeepCloneable Clone(Cloner cloner) {
54      return new ProportionalSelector(this, cloner);
55    }
56    public ProportionalSelector()
57      : base() {
58      Parameters.Add(new ValueParameter<BoolValue>("Windowing", "Apply windowing strategy (selection probability is proportional to the quality differences and not to the total quality).", new BoolValue(true)));
59    }
60
61    protected override IScope[] Select(List<IScope> scopes) {
62      int count = NumberOfSelectedSubScopesParameter.ActualValue.Value;
63      bool copy = CopySelectedParameter.Value.Value;
64      IRandom random = RandomParameter.ActualValue;
65      bool maximization = MaximizationParameter.ActualValue.Value;
66      bool windowing = WindowingParameter.Value.Value;
67      IScope[] selected = new IScope[count];
68
69      // prepare qualities for proportional selection
70      var qualities = QualityParameter.ActualValue.Select(x => x.Value);
71      double minQuality = double.MaxValue;
72      double maxQuality = double.MinValue;
73      foreach (var quality in qualities) {
74        if (!IsValidQuality(quality)) throw new ArgumentException("The scopes contain invalid quality values (either infinity or double.NaN) on which the selector cannot operate.");
75        if (quality < minQuality) minQuality = quality;
76        if (quality > maxQuality) maxQuality = quality;
77      }
78
79      if (minQuality == maxQuality) {  // all quality values are equal
80        qualities = qualities.Select(x => 1.0);
81      } else {
82        if (windowing) {
83          if (maximization)
84            qualities = qualities.Select(x => x - minQuality);
85          else
86            qualities = qualities.Select(x => maxQuality - x);
87        } else {
88          if (minQuality < 0.0) throw new InvalidOperationException("Proportional selection without windowing does not work with quality values < 0.");
89          if (!maximization) {
90            double limit = Math.Min(maxQuality * 2, double.MaxValue);
91            qualities = qualities.Select(x => limit - x);
92          }
93        }
94      }
95
96      List<double> list = qualities.ToList();
97      double qualitySum = list.Sum();
98      for (int i = 0; i < count; i++) {
99        double selectedQuality = random.NextDouble() * qualitySum;
100        int index = 0;
101        double currentQuality = list[index];
102        while (currentQuality < selectedQuality) {
103          index++;
104          currentQuality += list[index];
105        }
106        if (copy)
107          selected[i] = (IScope)scopes[index].Clone();
108        else {
109          selected[i] = scopes[index];
110          scopes.RemoveAt(index);
111          qualitySum -= list[index];
112          list.RemoveAt(index);
113        }
114      }
115      return selected;
116    }
117  }
118}
Note: See TracBrowser for help on using the repository browser.