Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1871: Improved performance of ProportionalSelector.

File size: 4.8 KB
RevLine 
[2]1#region License Information
2/* HeuristicLab
[7259]3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[2]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
[2818]22using System;
23using System.Collections.Generic;
[2817]24using System.Linq;
[4722]25using HeuristicLab.Common;
[2]26using HeuristicLab.Core;
27using HeuristicLab.Data;
[3138]28using HeuristicLab.Optimization;
[2817]29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
[2]31
32namespace HeuristicLab.Selection {
[817]33  /// <summary>
[2817]34  /// A quality proportional selection operator which considers a single double quality value for selection.
[817]35  /// </summary>
[2817]36  [Item("ProportionalSelector", "A quality proportional selection operator which considers a single double quality value for selection.")]
[3017]37  [StorableClass]
[3138]38  public sealed class ProportionalSelector : StochasticSingleObjectiveSelector, ISingleObjectiveSelector {
[3048]39    private ValueParameter<BoolValue> WindowingParameter {
40      get { return (ValueParameter<BoolValue>)Parameters["Windowing"]; }
[2]41    }
42
[3048]43    public BoolValue Windowing {
[2817]44      get { return WindowingParameter.Value; }
45      set { WindowingParameter.Value = value; }
[2]46    }
47
[4722]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    }
[2817]56    public ProportionalSelector()
57      : base() {
[3048]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)));
[2817]59    }
[2]60
[2830]61    protected override IScope[] Select(List<IScope> scopes) {
[2817]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;
[2830]67      IScope[] selected = new IScope[count];
[2]68
[2817]69      // prepare qualities for proportional selection
[2818]70      var qualities = QualityParameter.ActualValue.Select(x => x.Value);
[7996]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;
[7995]77      }
78
[2817]79      if (minQuality == maxQuality) {  // all quality values are equal
[2818]80        qualities = qualities.Select(x => 1.0);
[2817]81      } else {
82        if (windowing) {
83          if (maximization)
[2818]84            qualities = qualities.Select(x => x - minQuality);
[2817]85          else
[2818]86            qualities = qualities.Select(x => maxQuality - x);
[2817]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);
[2818]91            qualities = qualities.Select(x => limit - x);
[2817]92          }
[2]93        }
94      }
95
[2818]96      List<double> list = qualities.ToList();
[7996]97      double qualitySum = list.Sum();
[2817]98      for (int i = 0; i < count; i++) {
99        double selectedQuality = random.NextDouble() * qualitySum;
100        int index = 0;
[2818]101        double currentQuality = list[index];
[2817]102        while (currentQuality < selectedQuality) {
103          index++;
[2818]104          currentQuality += list[index];
[2]105        }
[2817]106        if (copy)
[2830]107          selected[i] = (IScope)scopes[index].Clone();
[2817]108        else {
[2830]109          selected[i] = scopes[index];
[2817]110          scopes.RemoveAt(index);
[2818]111          qualitySum -= list[index];
112          list.RemoveAt(index);
[2]113        }
114      }
[2817]115      return selected;
[2]116    }
117  }
118}
Note: See TracBrowser for help on using the repository browser.