Changeset 5957

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:

• trunk/sources/HeuristicLab.Selection/3.3/NoSameMatesSelector.cs (modified) (6 diffs)

trunk/sources/HeuristicLab.Selection/3.3/NoSameMatesSelector.cs

@@ -1 +1 @@
 using System;
+using System.Linq;
 using System.Collections.Generic;
 using System.Threading;
@@ -22 +23 @@
 
     #region Parameters
-    public IValueParameter<ISelector> SelectorParameter {
-      get { return (IValueParameter<ISelector>)Parameters[SelectorParameterName]; }
-    }
-    public IValueParameter<PercentValue> QualityDifferencePercentageParameter {
-      get { return (IValueParameter<PercentValue>)Parameters[QualityDifferencePercentageParameterName]; }
-    }
-    public IValueParameter<IntValue> QualityDifferenceMaxAttemptsParameter {
-      get { return (IValueParameter<IntValue>)Parameters[QualityDifferenceMaxAttemptsParameterName]; }
-    }
-    public IValueParameter<BoolValue> QualityDifferenceUseRangeParameter {
-      get { return (IValueParameter<BoolValue>)Parameters[QualityDifferenceUseRangeParameterName]; }
+    public IValueParameter<ISingleObjectiveSelector> SelectorParameter {
+      get { return (IValueParameter<ISingleObjectiveSelector>)Parameters[SelectorParameterName]; }
+    }
+    public IFixedValueParameter<PercentValue> QualityDifferencePercentageParameter {
+      get { return (IFixedValueParameter<PercentValue>)Parameters[QualityDifferencePercentageParameterName]; }
+    }
+    public IFixedValueParameter<IntValue> QualityDifferenceMaxAttemptsParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[QualityDifferenceMaxAttemptsParameterName]; }
+    }
+    public IFixedValueParameter<BoolValue> QualityDifferenceUseRangeParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[QualityDifferenceUseRangeParameterName]; }
     }
     #endregion
 
     #region Properties
-    public IntValue NumberOfSelectedSubScopes {
-      get { return NumberOfSelectedSubScopesParameter.ActualValue; }
-    }
-    public ISelector Selector {
+    public ISingleObjectiveSelector Selector {
       get { return SelectorParameter.Value; }
       set { SelectorParameter.Value = value; }
@@ -57 +55 @@
     [StorableConstructor]
     protected NoSameMatesSelector(bool deserializing) : base(deserializing) { }
-    protected NoSameMatesSelector(NoSameMatesSelector original, Cloner cloner) : base(original, cloner) { }
+    protected NoSameMatesSelector(NoSameMatesSelector original, Cloner cloner) : base(original, cloner) {
+      RegisterParameterEventHandlers();
+    }
     public override IDeepCloneable Clone(Cloner cloner) {
       return new NoSameMatesSelector(this, cloner);
@@ -64 +64 @@
     public NoSameMatesSelector() : base() {
       #region Create parameters
-      Parameters.Add(new ValueParameter<ISelector>(SelectorParameterName, "The inner selection operator to select the parents."));
-      Parameters.Add(new ValueParameter<PercentValue>(QualityDifferencePercentageParameterName, "The minimum quality difference from parent1 to parent2 to accept the selection.", new PercentValue(0.05)));
-      Parameters.Add(new ValueParameter<IntValue>(QualityDifferenceMaxAttemptsParameterName, "The maximum number of attempts to find parents which differ in quality.", new IntValue(5)));
-      Parameters.Add(new ValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", new BoolValue(false)));
+      Parameters.Add(new ValueParameter<ISingleObjectiveSelector>(SelectorParameterName, "The inner selection operator to select the parents.", new TournamentSelector()));
+      Parameters.Add(new FixedValueParameter<PercentValue>(QualityDifferencePercentageParameterName, "The minimum quality difference from parent1 to parent2 to accept the selection.", new PercentValue(0.05)));
+      Parameters.Add(new FixedValueParameter<IntValue>(QualityDifferenceMaxAttemptsParameterName, "The maximum number of attempts to find parents which differ in quality.", new IntValue(5)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", new BoolValue(true)));
       #endregion
 
-      Initialize();
+      CopySelectedParameter.Hidden = true;
+      RegisterParameterEventHandlers();
     }
 
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
-      if (!Parameters.ContainsKey(QualityDifferenceUseRangeParameterName))
-        Parameters.Add(new ValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", new BoolValue(false)));
-      Initialize();
+      #region conversion of old NSM parameters
+      if (Parameters.ContainsKey(SelectorParameterName)) { // change SelectorParameter type from ISelector to ISingleObjectiveSelector
+        ValueParameter<ISelector> param = Parameters[SelectorParameterName] as ValueParameter<ISelector>;
+        if (param != null) {
+          ISingleObjectiveSelector selector = param.Value as ISingleObjectiveSelector;
+          if (selector == null) selector = new TournamentSelector();
+          Parameters.Remove(SelectorParameterName);
+          Parameters.Add(new ValueParameter<ISingleObjectiveSelector>(SelectorParameterName, "The inner selection operator to select the parents.", selector));
+        }
+      }   
+      // FixedValueParameter for quality difference percentage, max attempts, use range
+      if (Parameters.ContainsKey(QualityDifferencePercentageParameterName)) {
+        ValueParameter<PercentValue> param = Parameters[QualityDifferencePercentageParameterName] as ValueParameter<PercentValue>;
+        if (!(param is FixedValueParameter<PercentValue>)) {
+          PercentValue diff = param != null ? param.Value as PercentValue : null;
+          if (diff == null) diff = new PercentValue(0.05);
+          Parameters.Remove(QualityDifferencePercentageParameterName);
+          Parameters.Add(new FixedValueParameter<PercentValue>(QualityDifferencePercentageParameterName, "The minimum quality difference from parent1 to parent2 to accept the selection.", diff));
+        }
+      }
+      if (Parameters.ContainsKey(QualityDifferenceMaxAttemptsParameterName)) {
+        ValueParameter<IntValue> param = Parameters[QualityDifferenceMaxAttemptsParameterName] as ValueParameter<IntValue>;
+        if (!(param is FixedValueParameter<IntValue>)) {
+          IntValue attempts = param != null ? param.Value as IntValue : null;
+          if (attempts == null) attempts = new IntValue(5);
+          Parameters.Remove(QualityDifferenceMaxAttemptsParameterName);
+          Parameters.Add(new FixedValueParameter<IntValue>(QualityDifferenceMaxAttemptsParameterName, "The maximum number of attempts to find parents which differ in quality.", attempts));
+        }
+      }
+      if (Parameters.ContainsKey(QualityDifferenceUseRangeParameterName)) {
+        ValueParameter<BoolValue> param = Parameters[QualityDifferenceUseRangeParameterName] as ValueParameter<BoolValue>;
+        if (!(param is FixedValueParameter<BoolValue>)) {
+          BoolValue range = param != null ? param.Value as BoolValue : null;
+          if (range == null) range = new BoolValue(true);
+          Parameters.Remove(QualityDifferenceUseRangeParameterName);
+          Parameters.Add(new FixedValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", range));
+        }
+      }
+      if (!Parameters.ContainsKey(QualityDifferenceUseRangeParameterName)) // add use range parameter
+        Parameters.Add(new FixedValueParameter<BoolValue>(QualityDifferenceUseRangeParameterName, "Use the range from minimum to maximum quality as basis for QualityDifferencePercentage.", new BoolValue(true)));
+      #endregion
+
+      RegisterParameterEventHandlers();
     }
 
     protected override IScope[] Select(List<IScope> scopes) {
-      int count = NumberOfSelectedSubScopes.Value;
-      if (count % 2 > 0) throw new InvalidOperationException(Name + ": There must be an equal number of sub-scopes to be selected.");
-      int limit = count - 1;
-      IScope[] selected = new IScope[count];
+      int parentsToSelect = NumberOfSelectedSubScopesParameter.ActualValue.Value;
+      if (parentsToSelect % 2 > 0) throw new InvalidOperationException(Name + ": There must be an equal number of sub-scopes to be selected.");
+      IScope[] selected = new IScope[parentsToSelect];
+      IScope[] parentsPool = new IScope[parentsToSelect];
 
       double qualityDifferencePercentage = QualityDifferencePercentage.Value;
@@ -90 +131 @@
       bool qualityDifferenceUseRange = QualityDifferenceUseRange.Value;
       string qualityName = QualityParameter.ActualName;
-      
-      // get minimum and maximum quality, calculate quality offsets
-      double minQualityOffset = 0;
-      double maxQualityOffset = 0;
+
+      // calculate quality offsets   
+      double absoluteQualityOffset = 0;
+      double minRelativeQualityOffset = 0;
+      double maxRelativeQualityOffset = 0;
       if (qualityDifferenceUseRange) {
-        ItemArray<DoubleValue> qualities = QualityParameter.ActualValue;
-        double minQuality = double.MaxValue, maxQuality = double.MinValue;
-        for (int l = 0; l < qualities.Length; l++) {
-          if (qualities[l].Value < minQuality) minQuality = qualities[l].Value;
-          if (qualities[l].Value > maxQuality) maxQuality = qualities[l].Value;
-        } // maximization flag is not needed because only the range is relevant
-        minQualityOffset = (maxQuality - minQuality) * qualityDifferencePercentage;
+        // maximization flag is not needed because only the range is relevant
+        double minQuality = QualityParameter.ActualValue.Min(x => x.Value);
+        double maxQuality = QualityParameter.ActualValue.Max(x => x.Value);
+        absoluteQualityOffset = (maxQuality - minQuality) * qualityDifferencePercentage;
       } else {
-        maxQualityOffset = 1.0 + qualityDifferencePercentage;
-        minQualityOffset = 1.0 - qualityDifferencePercentage;
-      }
-
-      ScopeList parents, remaining;
-      double qualityParent1, qualityParent2;
-      bool parentsDifferent;
-      int attempts = 1;
-      int i, j, k = 0;
-      while (k < limit) { // repeat until enough parents are selected
+        maxRelativeQualityOffset = 1.0 + qualityDifferencePercentage;
+        minRelativeQualityOffset = 1.0 - qualityDifferencePercentage;
+      }
+
+      int selectedParents = 0;
+      int poolCount = 0;
+      // repeat until enough parents are selected or max attempts are reached
+      for (int attempts = 1; attempts <= qualityDifferenceMaxAttempts && selectedParents < parentsToSelect - 1; attempts++) {
         ApplyInnerSelector();
-        parents = CurrentScope.SubScopes[1].SubScopes;
-
-        for (i = 0; k < limit && i < parents.Count - 1; i += 2) {
-          j = i + 1;
-          qualityParent1 = ((DoubleValue)parents[i].Variables[qualityName].Value).Value;
-          qualityParent2 = ((DoubleValue)parents[j].Variables[qualityName].Value).Value;
-
+        ScopeList parents = CurrentScope.SubScopes[1].SubScopes;
+
+        for (int indexParent1 = 0, indexParent2 = 1; 
+             indexParent1 < parents.Count - 1 && selectedParents < parentsToSelect - 1; 
+             indexParent1 += 2, indexParent2 += 2) {
+          double qualityParent1 = ((DoubleValue)parents[indexParent1].Variables[qualityName].Value).Value;
+          double qualityParent2 = ((DoubleValue)parents[indexParent2].Variables[qualityName].Value).Value;
+
+          bool parentsDifferent;
           if (qualityDifferenceUseRange) {
-            parentsDifferent = (qualityParent2 > qualityParent1 - minQualityOffset ||
-                                qualityParent2 < qualityParent1 + minQualityOffset);
+            parentsDifferent = (qualityParent2 > qualityParent1 - absoluteQualityOffset ||
+                                qualityParent2 < qualityParent1 + absoluteQualityOffset);
           } else {
-            parentsDifferent = (qualityParent2 > qualityParent1 * maxQualityOffset ||
-                                qualityParent2 < qualityParent1 * minQualityOffset);
+            parentsDifferent = (qualityParent2 > qualityParent1 * maxRelativeQualityOffset ||
+                                qualityParent2 < qualityParent1 * minRelativeQualityOffset);
           }
 
-          // parents meet difference criterion or max attempts reached
-          if (attempts >= qualityDifferenceMaxAttempts || parentsDifferent) {
-            // inner selector already copied scopes
-            selected[k++] = parents[i];
-            selected[k++] = parents[j];
-            if (!CopySelected.Value) {
-              scopes.Remove(parents[i]);
-              scopes.Remove(parents[j]);
-            }
-            attempts = 1;
-          } else { // skip parents
-            attempts++;
+          if (parentsDifferent) { 
+            // inner selector already copied scopes, no cloning necessary here
+            selected[selectedParents++] = parents[indexParent1];
+            selected[selectedParents++] = parents[indexParent2];
+          } else if (attempts == qualityDifferenceMaxAttempts &&
+                     poolCount < parentsToSelect - selectedParents) {
+            // last attempt: save parents to fill remaining positions
+            parentsPool[poolCount++] = parents[indexParent1];
+            parentsPool[poolCount++] = parents[indexParent2];
           }
         }
         // modify scopes
-        remaining = CurrentScope.SubScopes[0].SubScopes;
+        ScopeList remaining = CurrentScope.SubScopes[0].SubScopes;
         CurrentScope.SubScopes.Clear();
         CurrentScope.SubScopes.AddRange(remaining);
       }
+      // fill remaining positions with parents which don't meet the difference criterion 
+      if (selectedParents < parentsToSelect - 1) {
+        Array.Copy(parentsPool, 0, selected, selectedParents, parentsToSelect - selectedParents);
+      }
       return selected;
     }
 
     #region Events
+    private void RegisterParameterEventHandlers() {
+      SelectorParameter.ValueChanged += new EventHandler(SelectorParameter_ValueChanged);
+      CopySelected.ValueChanged += new EventHandler(CopySelected_ValueChanged);
+    }
+
     private void SelectorParameter_ValueChanged(object sender, EventArgs e) {
-      IValueParameter<ISelector> selectorParam = (sender as IValueParameter<ISelector>);
-      if (selectorParam != null)
-        ParameterizeSelector(selectorParam.Value);
-    }
-    #endregion
-
-    #region Helpers
+      ParameterizeSelector(Selector);
+    }
+
+    private void CopySelected_ValueChanged(object sender, EventArgs e) {
+      if (CopySelected.Value != true) {
+        CopySelected.Value = true;
+        throw new ArgumentException(Name + ": CopySelected must always be true.");
+      }
+    }
+    #endregion
+
+    #region Helpers  
+    private void ParameterizeSelector(ISingleObjectiveSelector selector) {
+      selector.CopySelected = new BoolValue(true); // must always be true
+      selector.MaximizationParameter.ActualName = MaximizationParameter.Name;
+      selector.QualityParameter.ActualName = QualityParameter.Name;
+
+      IStochasticOperator stoOp = (selector as IStochasticOperator);
+      if (stoOp != null) stoOp.RandomParameter.ActualName = RandomParameter.Name;
+    }
+
     private void ApplyInnerSelector() {
-      IOperation next;
-      IAtomicOperation operation;
-      OperationCollection coll;
+      // necessary for inner GenderSpecificSelector to execute all operations in OperationCollection
       Stack<IOperation> executionStack = new Stack<IOperation>();
-
       executionStack.Push(ExecutionContext.CreateChildOperation(Selector));
       while (executionStack.Count > 0) {
         CancellationToken.ThrowIfCancellationRequested();
-        next = executionStack.Pop();
+        IOperation next = executionStack.Pop();
         if (next is OperationCollection) {
-          coll = (OperationCollection)next;
+          OperationCollection coll = (OperationCollection)next;
           for (int i = coll.Count - 1; i >= 0; i--)
             if (coll[i] != null) executionStack.Push(coll[i]);
         } else if (next is IAtomicOperation) {
-          operation = (IAtomicOperation)next;
+          IAtomicOperation operation = (IAtomicOperation)next;
           next = operation.Operator.Execute((IExecutionContext)operation, CancellationToken);
           if (next != null) executionStack.Push(next);
@@ -181 +237 @@
       }
     }
-
-    private void Initialize() {
-      SelectorParameter.ValueChanged += new EventHandler(SelectorParameter_ValueChanged);
-      if (Selector == null) Selector = new TournamentSelector();
-    }
-
-    private void ParameterizeSelector(ISelector selector) {
-      selector.CopySelected = new BoolValue(true); // must always be true
-      IStochasticOperator stoOp = (selector as IStochasticOperator);
-      if (stoOp != null) stoOp.RandomParameter.ActualName = RandomParameter.Name;
-      ISingleObjectiveSelector soSelector = (selector as ISingleObjectiveSelector);
-      if (soSelector != null) {
-        soSelector.MaximizationParameter.ActualName = MaximizationParameter.Name;
-        soSelector.QualityParameter.ActualName = QualityParameter.Name;
-      }
-    }
     #endregion
   }