Free cookie consent management tool by TermsFeed Policy Generator

Changeset 5957 for trunk/sources


Ignore:
Timestamp:
04/05/11 17:24:24 (14 years ago)
Author:
cfischer
Message:

#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:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Selection/3.3/NoSameMatesSelector.cs

    r5646 r5957  
    11using System;
     2using System.Linq;
    23using System.Collections.Generic;
    34using System.Threading;
     
    2223
    2324    #region Parameters
    24     public IValueParameter<ISelector> SelectorParameter {
    25       get { return (IValueParameter<ISelector>)Parameters[SelectorParameterName]; }
    26     }
    27     public IValueParameter<PercentValue> QualityDifferencePercentageParameter {
    28       get { return (IValueParameter<PercentValue>)Parameters[QualityDifferencePercentageParameterName]; }
    29     }
    30     public IValueParameter<IntValue> QualityDifferenceMaxAttemptsParameter {
    31       get { return (IValueParameter<IntValue>)Parameters[QualityDifferenceMaxAttemptsParameterName]; }
    32     }
    33     public IValueParameter<BoolValue> QualityDifferenceUseRangeParameter {
    34       get { return (IValueParameter<BoolValue>)Parameters[QualityDifferenceUseRangeParameterName]; }
     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]; }
    3536    }
    3637    #endregion
    3738
    3839    #region Properties
    39     public IntValue NumberOfSelectedSubScopes {
    40       get { return NumberOfSelectedSubScopesParameter.ActualValue; }
    41     }
    42     public ISelector Selector {
     40    public ISingleObjectiveSelector Selector {
    4341      get { return SelectorParameter.Value; }
    4442      set { SelectorParameter.Value = value; }
     
    5755    [StorableConstructor]
    5856    protected NoSameMatesSelector(bool deserializing) : base(deserializing) { }
    59     protected NoSameMatesSelector(NoSameMatesSelector original, Cloner cloner) : base(original, cloner) { }
     57    protected NoSameMatesSelector(NoSameMatesSelector original, Cloner cloner) : base(original, cloner) {
     58      RegisterParameterEventHandlers();
     59    }
    6060    public override IDeepCloneable Clone(Cloner cloner) {
    6161      return new NoSameMatesSelector(this, cloner);
     
    6464    public NoSameMatesSelector() : base() {
    6565      #region Create parameters
    66       Parameters.Add(new ValueParameter<ISelector>(SelectorParameterName, "The inner selection operator to select the parents."));
    67       Parameters.Add(new ValueParameter<PercentValue>(QualityDifferencePercentageParameterName, "The minimum quality difference from parent1 to parent2 to accept the selection.", new PercentValue(0.05)));
    68       Parameters.Add(new ValueParameter<IntValue>(QualityDifferenceMaxAttemptsParameterName, "The maximum number of attempts to find parents which differ in quality.", new IntValue(5)));
    69       Parameters.Add(new ValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", new BoolValue(false)));
     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)));
    7070      #endregion
    7171
    72       Initialize();
     72      CopySelectedParameter.Hidden = true;
     73      RegisterParameterEventHandlers();
    7374    }
    7475
    7576    [StorableHook(HookType.AfterDeserialization)]
    7677    private void AfterDeserialization() {
    77       if (!Parameters.ContainsKey(QualityDifferenceUseRangeParameterName))
    78         Parameters.Add(new ValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", new BoolValue(false)));
    79       Initialize();
     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();
    80121    }
    81122
    82123    protected override IScope[] Select(List<IScope> scopes) {
    83       int count = NumberOfSelectedSubScopes.Value;
    84       if (count % 2 > 0) throw new InvalidOperationException(Name + ": There must be an equal number of sub-scopes to be selected.");
    85       int limit = count - 1;
    86       IScope[] selected = new IScope[count];
     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];
    87128
    88129      double qualityDifferencePercentage = QualityDifferencePercentage.Value;
     
    90131      bool qualityDifferenceUseRange = QualityDifferenceUseRange.Value;
    91132      string qualityName = QualityParameter.ActualName;
    92      
    93       // get minimum and maximum quality, calculate quality offsets
    94       double minQualityOffset = 0;
    95       double maxQualityOffset = 0;
     133
     134      // calculate quality offsets   
     135      double absoluteQualityOffset = 0;
     136      double minRelativeQualityOffset = 0;
     137      double maxRelativeQualityOffset = 0;
    96138      if (qualityDifferenceUseRange) {
    97         ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
    98         double minQuality = double.MaxValue, maxQuality = double.MinValue;
    99         for (int l = 0; l < qualities.Length; l++) {
    100           if (qualities[l].Value < minQuality) minQuality = qualities[l].Value;
    101           if (qualities[l].Value > maxQuality) maxQuality = qualities[l].Value;
    102         } // maximization flag is not needed because only the range is relevant
    103         minQualityOffset = (maxQuality - minQuality) * qualityDifferencePercentage;
     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;
    104143      } else {
    105         maxQualityOffset = 1.0 + qualityDifferencePercentage;
    106         minQualityOffset = 1.0 - qualityDifferencePercentage;
    107       }
    108 
    109       ScopeList parents, remaining;
    110       double qualityParent1, qualityParent2;
    111       bool parentsDifferent;
    112       int attempts = 1;
    113       int i, j, k = 0;
    114       while (k < limit) { // repeat until enough parents are selected
     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++) {
    115152        ApplyInnerSelector();
    116         parents = CurrentScope.SubScopes[1].SubScopes;
    117 
    118         for (i = 0; k < limit && i < parents.Count - 1; i += 2) {
    119           j = i + 1;
    120           qualityParent1 = ((DoubleValue)parents[i].Variables[qualityName].Value).Value;
    121           qualityParent2 = ((DoubleValue)parents[j].Variables[qualityName].Value).Value;
    122 
     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;
    123162          if (qualityDifferenceUseRange) {
    124             parentsDifferent = (qualityParent2 > qualityParent1 - minQualityOffset ||
    125                                 qualityParent2 < qualityParent1 + minQualityOffset);
     163            parentsDifferent = (qualityParent2 > qualityParent1 - absoluteQualityOffset ||
     164                                qualityParent2 < qualityParent1 + absoluteQualityOffset);
    126165          } else {
    127             parentsDifferent = (qualityParent2 > qualityParent1 * maxQualityOffset ||
    128                                 qualityParent2 < qualityParent1 * minQualityOffset);
     166            parentsDifferent = (qualityParent2 > qualityParent1 * maxRelativeQualityOffset ||
     167                                qualityParent2 < qualityParent1 * minRelativeQualityOffset);
    129168          }
    130169
    131           // parents meet difference criterion or max attempts reached
    132           if (attempts >= qualityDifferenceMaxAttempts || parentsDifferent) {
    133             // inner selector already copied scopes
    134             selected[k++] = parents[i];
    135             selected[k++] = parents[j];
    136             if (!CopySelected.Value) {
    137               scopes.Remove(parents[i]);
    138               scopes.Remove(parents[j]);
    139             }
    140             attempts = 1;
    141           } else { // skip parents
    142             attempts++;
     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];
    143179          }
    144180        }
    145181        // modify scopes
    146         remaining = CurrentScope.SubScopes[0].SubScopes;
     182        ScopeList remaining = CurrentScope.SubScopes[0].SubScopes;
    147183        CurrentScope.SubScopes.Clear();
    148184        CurrentScope.SubScopes.AddRange(remaining);
    149185      }
     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      }
    150190      return selected;
    151191    }
    152192
    153193    #region Events
     194    private void RegisterParameterEventHandlers() {
     195      SelectorParameter.ValueChanged += new EventHandler(SelectorParameter_ValueChanged);
     196      CopySelected.ValueChanged += new EventHandler(CopySelected_ValueChanged);
     197    }
     198
    154199    private void SelectorParameter_ValueChanged(object sender, EventArgs e) {
    155       IValueParameter<ISelector> selectorParam = (sender as IValueParameter<ISelector>);
    156       if (selectorParam != null)
    157         ParameterizeSelector(selectorParam.Value);
    158     }
    159     #endregion
    160 
    161     #region Helpers
     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
    162221    private void ApplyInnerSelector() {
    163       IOperation next;
    164       IAtomicOperation operation;
    165       OperationCollection coll;
     222      // necessary for inner GenderSpecificSelector to execute all operations in OperationCollection
    166223      Stack<IOperation> executionStack = new Stack<IOperation>();
    167 
    168224      executionStack.Push(ExecutionContext.CreateChildOperation(Selector));
    169225      while (executionStack.Count > 0) {
    170226        CancellationToken.ThrowIfCancellationRequested();
    171         next = executionStack.Pop();
     227        IOperation next = executionStack.Pop();
    172228        if (next is OperationCollection) {
    173           coll = (OperationCollection)next;
     229          OperationCollection coll = (OperationCollection)next;
    174230          for (int i = coll.Count - 1; i >= 0; i--)
    175231            if (coll[i] != null) executionStack.Push(coll[i]);
    176232        } else if (next is IAtomicOperation) {
    177           operation = (IAtomicOperation)next;
     233          IAtomicOperation operation = (IAtomicOperation)next;
    178234          next = operation.Operator.Execute((IExecutionContext)operation, CancellationToken);
    179235          if (next != null) executionStack.Push(next);
     
    181237      }
    182238    }
    183 
    184     private void Initialize() {
    185       SelectorParameter.ValueChanged += new EventHandler(SelectorParameter_ValueChanged);
    186       if (Selector == null) Selector = new TournamentSelector();
    187     }
    188 
    189     private void ParameterizeSelector(ISelector selector) {
    190       selector.CopySelected = new BoolValue(true); // must always be true
    191       IStochasticOperator stoOp = (selector as IStochasticOperator);
    192       if (stoOp != null) stoOp.RandomParameter.ActualName = RandomParameter.Name;
    193       ISingleObjectiveSelector soSelector = (selector as ISingleObjectiveSelector);
    194       if (soSelector != null) {
    195         soSelector.MaximizationParameter.ActualName = MaximizationParameter.Name;
    196         soSelector.QualityParameter.ActualName = QualityParameter.Name;
    197       }
    198     }
    199239    #endregion
    200240  }
Note: See TracChangeset for help on using the changeset viewer.