Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Selection/3.3/NoSameMatesSelector.cs @ 5957

Last change on this file since 5957 was 5957, checked in by cfischer, 13 years ago

#1364 revised NSM based on review feedback from mkommend:

  • use linq to select min/max quality for use range option
  • use range option is now enabled by default
  • added event handler to throw exception in case CopySelected is set to false (NSM itself ignores this flag and works like this flag is true)
  • changed behavior of max attempts: execute the inner selector up to max attempts times to find different parents and fill the remaining positions only afterwards
  • some variable name refactoring
  • changed type of inner selector to ISingleObjectiveSelector
  • changed parameter types for the three NSM parameters to FixedValueParameter
  • added AfterDeserializationHook to enable opening and executing of optimizers with old NSM implementations
File size: 12.7 KB
Line 
1using System;
2using System.Linq;
3using System.Collections.Generic;
4using System.Threading;
5using HeuristicLab.Common;
6using HeuristicLab.Core;
7using HeuristicLab.Data;
8using HeuristicLab.Optimization;
9using HeuristicLab.Parameters;
10using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
11
12namespace HeuristicLab.Selection {
13  /// <summary>
14  /// A selector which tries to select two parents which differ in quality.
15  /// </summary>
16  [Item("NoSameMatesSelector", "A selector which tries to select two parents which differ in quality.")]
17  [StorableClass]
18  public class NoSameMatesSelector : StochasticSingleObjectiveSelector, ISingleObjectiveSelector {
19    private const string SelectorParameterName = "Selector";
20    private const string QualityDifferencePercentageParameterName = "QualityDifferencePercentage";
21    private const string QualityDifferenceMaxAttemptsParameterName = "QualityDifferenceMaxAttempts";
22    private const string QualityDifferenceUseRangeParameterName = "QualityDifferenceUseRange";
23
24    #region Parameters
25    public IValueParameter<ISingleObjectiveSelector> SelectorParameter {
26      get { return (IValueParameter<ISingleObjectiveSelector>)Parameters[SelectorParameterName]; }
27    }
28    public IFixedValueParameter<PercentValue> QualityDifferencePercentageParameter {
29      get { return (IFixedValueParameter<PercentValue>)Parameters[QualityDifferencePercentageParameterName]; }
30    }
31    public IFixedValueParameter<IntValue> QualityDifferenceMaxAttemptsParameter {
32      get { return (IFixedValueParameter<IntValue>)Parameters[QualityDifferenceMaxAttemptsParameterName]; }
33    }
34    public IFixedValueParameter<BoolValue> QualityDifferenceUseRangeParameter {
35      get { return (IFixedValueParameter<BoolValue>)Parameters[QualityDifferenceUseRangeParameterName]; }
36    }
37    #endregion
38
39    #region Properties
40    public ISingleObjectiveSelector Selector {
41      get { return SelectorParameter.Value; }
42      set { SelectorParameter.Value = value; }
43    }
44    public PercentValue QualityDifferencePercentage {
45      get { return QualityDifferencePercentageParameter.Value; }
46    }
47    public IntValue QualityDifferenceMaxAttempts {
48      get { return QualityDifferenceMaxAttemptsParameter.Value; }
49    }
50    public BoolValue QualityDifferenceUseRange {
51      get { return QualityDifferenceUseRangeParameter.Value; }
52    }
53    #endregion
54
55    [StorableConstructor]
56    protected NoSameMatesSelector(bool deserializing) : base(deserializing) { }
57    protected NoSameMatesSelector(NoSameMatesSelector original, Cloner cloner) : base(original, cloner) {
58      RegisterParameterEventHandlers();
59    }
60    public override IDeepCloneable Clone(Cloner cloner) {
61      return new NoSameMatesSelector(this, cloner);
62    }
63
64    public NoSameMatesSelector() : base() {
65      #region Create parameters
66      Parameters.Add(new ValueParameter<ISingleObjectiveSelector>(SelectorParameterName, "The inner selection operator to select the parents.", new TournamentSelector()));
67      Parameters.Add(new FixedValueParameter<PercentValue>(QualityDifferencePercentageParameterName, "The minimum quality difference from parent1 to parent2 to accept the selection.", new PercentValue(0.05)));
68      Parameters.Add(new FixedValueParameter<IntValue>(QualityDifferenceMaxAttemptsParameterName, "The maximum number of attempts to find parents which differ in quality.", new IntValue(5)));
69      Parameters.Add(new FixedValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", new BoolValue(true)));
70      #endregion
71
72      CopySelectedParameter.Hidden = true;
73      RegisterParameterEventHandlers();
74    }
75
76    [StorableHook(HookType.AfterDeserialization)]
77    private void AfterDeserialization() {
78      #region conversion of old NSM parameters
79      if (Parameters.ContainsKey(SelectorParameterName)) { // change SelectorParameter type from ISelector to ISingleObjectiveSelector
80        ValueParameter<ISelector> param = Parameters[SelectorParameterName] as ValueParameter<ISelector>;
81        if (param != null) {
82          ISingleObjectiveSelector selector = param.Value as ISingleObjectiveSelector;
83          if (selector == null) selector = new TournamentSelector();
84          Parameters.Remove(SelectorParameterName);
85          Parameters.Add(new ValueParameter<ISingleObjectiveSelector>(SelectorParameterName, "The inner selection operator to select the parents.", selector));
86        }
87      }   
88      // FixedValueParameter for quality difference percentage, max attempts, use range
89      if (Parameters.ContainsKey(QualityDifferencePercentageParameterName)) {
90        ValueParameter<PercentValue> param = Parameters[QualityDifferencePercentageParameterName] as ValueParameter<PercentValue>;
91        if (!(param is FixedValueParameter<PercentValue>)) {
92          PercentValue diff = param != null ? param.Value as PercentValue : null;
93          if (diff == null) diff = new PercentValue(0.05);
94          Parameters.Remove(QualityDifferencePercentageParameterName);
95          Parameters.Add(new FixedValueParameter<PercentValue>(QualityDifferencePercentageParameterName, "The minimum quality difference from parent1 to parent2 to accept the selection.", diff));
96        }
97      }
98      if (Parameters.ContainsKey(QualityDifferenceMaxAttemptsParameterName)) {
99        ValueParameter<IntValue> param = Parameters[QualityDifferenceMaxAttemptsParameterName] as ValueParameter<IntValue>;
100        if (!(param is FixedValueParameter<IntValue>)) {
101          IntValue attempts = param != null ? param.Value as IntValue : null;
102          if (attempts == null) attempts = new IntValue(5);
103          Parameters.Remove(QualityDifferenceMaxAttemptsParameterName);
104          Parameters.Add(new FixedValueParameter<IntValue>(QualityDifferenceMaxAttemptsParameterName, "The maximum number of attempts to find parents which differ in quality.", attempts));
105        }
106      }
107      if (Parameters.ContainsKey(QualityDifferenceUseRangeParameterName)) {
108        ValueParameter<BoolValue> param = Parameters[QualityDifferenceUseRangeParameterName] as ValueParameter<BoolValue>;
109        if (!(param is FixedValueParameter<BoolValue>)) {
110          BoolValue range = param != null ? param.Value as BoolValue : null;
111          if (range == null) range = new BoolValue(true);
112          Parameters.Remove(QualityDifferenceUseRangeParameterName);
113          Parameters.Add(new FixedValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", range));
114        }
115      }
116      if (!Parameters.ContainsKey(QualityDifferenceUseRangeParameterName)) // add use range parameter
117        Parameters.Add(new FixedValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", new BoolValue(true)));
118      #endregion
119
120      RegisterParameterEventHandlers();
121    }
122
123    protected override IScope[] Select(List<IScope> scopes) {
124      int parentsToSelect = NumberOfSelectedSubScopesParameter.ActualValue.Value;
125      if (parentsToSelect % 2 > 0) throw new InvalidOperationException(Name + ": There must be an equal number of sub-scopes to be selected.");
126      IScope[] selected = new IScope[parentsToSelect];
127      IScope[] parentsPool = new IScope[parentsToSelect];
128
129      double qualityDifferencePercentage = QualityDifferencePercentage.Value;
130      int qualityDifferenceMaxAttempts = QualityDifferenceMaxAttempts.Value;
131      bool qualityDifferenceUseRange = QualityDifferenceUseRange.Value;
132      string qualityName = QualityParameter.ActualName;
133
134      // calculate quality offsets   
135      double absoluteQualityOffset = 0;
136      double minRelativeQualityOffset = 0;
137      double maxRelativeQualityOffset = 0;
138      if (qualityDifferenceUseRange) {
139        // maximization flag is not needed because only the range is relevant
140        double minQuality = QualityParameter.ActualValue.Min(x => x.Value);
141        double maxQuality = QualityParameter.ActualValue.Max(x => x.Value);
142        absoluteQualityOffset = (maxQuality - minQuality) * qualityDifferencePercentage;
143      } else {
144        maxRelativeQualityOffset = 1.0 + qualityDifferencePercentage;
145        minRelativeQualityOffset = 1.0 - qualityDifferencePercentage;
146      }
147
148      int selectedParents = 0;
149      int poolCount = 0;
150      // repeat until enough parents are selected or max attempts are reached
151      for (int attempts = 1; attempts <= qualityDifferenceMaxAttempts && selectedParents < parentsToSelect - 1; attempts++) {
152        ApplyInnerSelector();
153        ScopeList parents = CurrentScope.SubScopes[1].SubScopes;
154
155        for (int indexParent1 = 0, indexParent2 = 1;
156             indexParent1 < parents.Count - 1 && selectedParents < parentsToSelect - 1;
157             indexParent1 += 2, indexParent2 += 2) {
158          double qualityParent1 = ((DoubleValue)parents[indexParent1].Variables[qualityName].Value).Value;
159          double qualityParent2 = ((DoubleValue)parents[indexParent2].Variables[qualityName].Value).Value;
160
161          bool parentsDifferent;
162          if (qualityDifferenceUseRange) {
163            parentsDifferent = (qualityParent2 > qualityParent1 - absoluteQualityOffset ||
164                                qualityParent2 < qualityParent1 + absoluteQualityOffset);
165          } else {
166            parentsDifferent = (qualityParent2 > qualityParent1 * maxRelativeQualityOffset ||
167                                qualityParent2 < qualityParent1 * minRelativeQualityOffset);
168          }
169
170          if (parentsDifferent) {
171            // inner selector already copied scopes, no cloning necessary here
172            selected[selectedParents++] = parents[indexParent1];
173            selected[selectedParents++] = parents[indexParent2];
174          } else if (attempts == qualityDifferenceMaxAttempts &&
175                     poolCount < parentsToSelect - selectedParents) {
176            // last attempt: save parents to fill remaining positions
177            parentsPool[poolCount++] = parents[indexParent1];
178            parentsPool[poolCount++] = parents[indexParent2];
179          }
180        }
181        // modify scopes
182        ScopeList remaining = CurrentScope.SubScopes[0].SubScopes;
183        CurrentScope.SubScopes.Clear();
184        CurrentScope.SubScopes.AddRange(remaining);
185      }
186      // fill remaining positions with parents which don't meet the difference criterion
187      if (selectedParents < parentsToSelect - 1) {
188        Array.Copy(parentsPool, 0, selected, selectedParents, parentsToSelect - selectedParents);
189      }
190      return selected;
191    }
192
193    #region Events
194    private void RegisterParameterEventHandlers() {
195      SelectorParameter.ValueChanged += new EventHandler(SelectorParameter_ValueChanged);
196      CopySelected.ValueChanged += new EventHandler(CopySelected_ValueChanged);
197    }
198
199    private void SelectorParameter_ValueChanged(object sender, EventArgs e) {
200      ParameterizeSelector(Selector);
201    }
202
203    private void CopySelected_ValueChanged(object sender, EventArgs e) {
204      if (CopySelected.Value != true) {
205        CopySelected.Value = true;
206        throw new ArgumentException(Name + ": CopySelected must always be true.");
207      }
208    }
209    #endregion
210
211    #region Helpers 
212    private void ParameterizeSelector(ISingleObjectiveSelector selector) {
213      selector.CopySelected = new BoolValue(true); // must always be true
214      selector.MaximizationParameter.ActualName = MaximizationParameter.Name;
215      selector.QualityParameter.ActualName = QualityParameter.Name;
216
217      IStochasticOperator stoOp = (selector as IStochasticOperator);
218      if (stoOp != null) stoOp.RandomParameter.ActualName = RandomParameter.Name;
219    }
220
221    private void ApplyInnerSelector() {
222      // necessary for inner GenderSpecificSelector to execute all operations in OperationCollection
223      Stack<IOperation> executionStack = new Stack<IOperation>();
224      executionStack.Push(ExecutionContext.CreateChildOperation(Selector));
225      while (executionStack.Count > 0) {
226        CancellationToken.ThrowIfCancellationRequested();
227        IOperation next = executionStack.Pop();
228        if (next is OperationCollection) {
229          OperationCollection coll = (OperationCollection)next;
230          for (int i = coll.Count - 1; i >= 0; i--)
231            if (coll[i] != null) executionStack.Push(coll[i]);
232        } else if (next is IAtomicOperation) {
233          IAtomicOperation operation = (IAtomicOperation)next;
234          next = operation.Operator.Execute((IExecutionContext)operation, CancellationToken);
235          if (next != null) executionStack.Push(next);
236        }
237      }
238    }
239    #endregion
240  }
241}
Note: See TracBrowser for help on using the repository browser.