Free cookie consent management tool by TermsFeed Policy Generator

source: branches/histogram/HeuristicLab.Selection/3.3/NoSameMatesSelector.cs @ 6046

Last change on this file since 6046 was 6046, checked in by abeham, 13 years ago

#1465

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