Changeset 9605 for branches/LearningClassifierSystems/HeuristicLab.Optimization.Operators.LCS/3.3/Selection

Timestamp:

06/11/13 13:32:32 (12 years ago)

Author:

sforsten

Message:

#1980:

• set plugin dependencies
• added smart initialization
• added hierarchical selection
• fixed major and minor default rule
• fixed several smaller bugs
• some refactoring has been done

Location:

branches/LearningClassifierSystems/HeuristicLab.Optimization.Operators.LCS/3.3/Selection

Files:

• IHierarchicalSingleObjectiveEvaluator.cs (added)
• IHierarchicalSingleObjectiveSelector.cs (added)
• NichingTournamentSelector.cs (modified) (5 diffs)

branches/LearningClassifierSystems/HeuristicLab.Optimization.Operators.LCS/3.3/Selection/NichingTournamentSelector.cs

@@ -33 +33 @@
   [Item("NichingTournamentSelector", "Description missing")]
   [StorableClass]
-  public class NichingTournamentSelector : StochasticSingleObjectiveSelector, INichingSingleObjectiveSelector {
+  public class NichingTournamentSelector : StochasticSingleObjectiveSelector, INichingSingleObjectiveSelector, IHierarchicalSingleObjectiveSelector {
 
     #region Parameter Properties
@@ -50 +50 @@
     public ILookupParameter<ItemArray<IGAssistIndividual>> IndividualParameter {
       get { return (ILookupParameter<ItemArray<IGAssistIndividual>>)Parameters["Individual"]; }
+    }
+    public ILookupParameter<ItemArray<DoubleValue>> LengthParameter {
+      get { return (ILookupParameter<ItemArray<DoubleValue>>)Parameters["Length"]; }
+    }
+    public IValueLookupParameter<DoubleValue> LengthThresholdParameter {
+      get { return (IValueLookupParameter<DoubleValue>)Parameters["LengthThreshold"]; }
+    }
+    public IValueLookupParameter<IntValue> IterationHirachicalSelectionParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["IterationHirachicalSelection"]; }
+    }
+
+    public ILookupParameter<IntValue> IterationsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["Iterations"]; }
+    }
+    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
     }
     #endregion
@@ -65 +81 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("ParentsPerChild", ""));
       Parameters.Add(new ScopeTreeLookupParameter<IGAssistIndividual>("Individual", ""));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Length", "The length value contained in each sub-scope which is used for selection."));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("LengthThreshold", "", new DoubleValue(0.000001)));
+      Parameters.Add(new ValueLookupParameter<IntValue>("IterationHirachicalSelection", "", new IntValue(24)));
+      Parameters.Add(new LookupParameter<IntValue>("Iterations", ""));
+      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", ""));
     }
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -76 +97 @@
       bool maximization = MaximizationParameter.ActualValue.Value;
       List<double> qualities = QualityParameter.ActualValue.Where(x => IsValidQuality(x.Value)).Select(x => x.Value).ToList();
+      List<double> lengths = LengthParameter.ActualValue.Select(x => x.Value).ToList();
+      bool useLength = lengths.Count > 0;
+      double lengtThreshold = LengthThresholdParameter.ActualValue.Value;
       List<IGAssistIndividual> individuals = IndividualParameter.ActualValue.ToList();
       int groupSize = GroupSizeParameter.ActualValue.Value;
@@ -83 +107 @@
       //check if list with indexes is as long as the original scope list
       //otherwise invalid quality values were filtered
-      if (qualities.Count != scopes.Count || individuals.Count != scopes.Count) {
+      if (qualities.Count != scopes.Count || individuals.Count != scopes.Count || (useLength && lengths.Count != scopes.Count)) {
         throw new ArgumentException("The scopes contain invalid quality values (either infinity or double.NaN) on which the selector cannot operate.");
       }
 
       int parentsPerChild = ParentsPerChildParameter.ActualValue.Value;
-      var nicheComparer = GAssistNichesProblemDataParameter.ActualValue.GetPossibleNiches().First().Comparer;
-      var selectPerNiche = new Dictionary<IGAssistNiche, int>(nicheComparer);
-      var nicheScope = new Dictionary<IGAssistNiche, List<int>>(nicheComparer);
-
-      for (int i = 0; i < individuals.Count; i++) {
-        if (!nicheScope.ContainsKey(individuals[i].Niche)) {
-          nicheScope.Add(individuals[i].Niche, new List<int>());
-        }
-        nicheScope[individuals[i].Niche].Add(i);
-      }
-
-      var possibleNiches = nicheScope.Keys.ToList();
-      foreach (var niche in possibleNiches) {
-        selectPerNiche.Add(niche, count / possibleNiches.Count);
-      }
-
-      int curCount = 0;
-      while (curCount < count) {
-        IGAssistNiche niche = null;
-        int best = -1;
-        if (doNiching) {
-          niche = GetNiche(random, selectPerNiche, possibleNiches);
-        } else {
-          best = random.Next(scopes.Count);
-        }
-        for (int i = 0; i < parentsPerChild; i++) {
+
+      if (individuals.Any(x => x.Niche == null) && individuals.Any(x => x.Niche != null)) {
+        throw new ArgumentException("Either all individuals have a default action or none.");
+      }
+
+      //null cannot be a key in a dictionary (nicheScope), therefore torunament selection has to be done differently
+      //to keep it a little maintainable, the case that no default rule is used has been separated
+      if (individuals.Any(x => x.Niche == null)) {
+        //normal tournament selection
+        for (int i = 0; i < count; i++) {
+          int best = random.Next(scopes.Count);
           int index;
-          if (doNiching) {
-            best = nicheScope[niche][random.Next(nicheScope[niche].Count)];
-          }
           for (int j = 1; j < groupSize; j++) {
-            if (niche != null) {
-              index = nicheScope[niche][random.Next(nicheScope[niche].Count)];
-            } else {
-              index = random.Next(scopes.Count);
-            }
-            if (((maximization) && (qualities[index] > qualities[best])) ||
-                ((!maximization) && (qualities[index] < qualities[best]))) {
+            index = random.Next(scopes.Count);
+            if (IsBetterHirachical(index, best, qualities, lengths, lengtThreshold, useLength, maximization)) {
               best = index;
             }
           }
 
-          niche = individuals[best].Niche;
-
           if (copy)
-            selected[curCount] = (IScope)scopes[best].Clone();
+            selected[i] = (IScope)scopes[best].Clone();
           else {
-            selected[curCount] = scopes[best];
+            selected[i] = scopes[best];
             scopes.RemoveAt(best);
             qualities.RemoveAt(best);
           }
-          selectPerNiche[niche]--;
-          curCount++;
+        }
+      } else {
+        var nicheComparer = GAssistNichesProblemDataParameter.ActualValue.GetPossibleNiches().First().Comparer;
+        var selectPerNiche = new Dictionary<IGAssistNiche, int>(nicheComparer);
+        var nicheScope = new Dictionary<IGAssistNiche, List<int>>(nicheComparer);
+        //niching tournament selection
+        for (int i = 0; i < individuals.Count; i++) {
+          if (!nicheScope.ContainsKey(individuals[i].Niche)) {
+            nicheScope.Add(individuals[i].Niche, new List<int>());
+          }
+          nicheScope[individuals[i].Niche].Add(i);
+        }
+
+        var possibleNiches = nicheScope.Keys.ToList();
+        foreach (var niche in possibleNiches) {
+          selectPerNiche.Add(niche, count / possibleNiches.Count);
+        }
+
+        int curCount = 0;
+        while (curCount < count) {
+          IGAssistNiche niche = null;
+          int best = -1;
+          if (doNiching) {
+            niche = GetNiche(random, selectPerNiche, possibleNiches);
+          } else {
+            best = random.Next(scopes.Count);
+          }
+          for (int i = 0; i < parentsPerChild; i++) {
+            int index;
+            if (doNiching) {
+              best = nicheScope[niche][random.Next(nicheScope[niche].Count)];
+            }
+            for (int j = 1; j < groupSize; j++) {
+              if (niche != null) {
+                index = nicheScope[niche][random.Next(nicheScope[niche].Count)];
+              } else {
+                index = random.Next(scopes.Count);
+              }
+              if (IsBetterHirachical(index, best, qualities, lengths, lengtThreshold, useLength, maximization)) {
+                best = index;
+              }
+            }
+
+            niche = individuals[best].Niche;
+
+            if (copy)
+              selected[curCount] = (IScope)scopes[best].Clone();
+            else {
+              selected[curCount] = scopes[best];
+              scopes.RemoveAt(best);
+              qualities.RemoveAt(best);
+            }
+            selectPerNiche[niche]--;
+            curCount++;
+          }
         }
       }
       return selected;
+    }
+
+    private bool IsBetterHirachical(int indexTrue, int indexFalse, IList<double> qualities, IList<double> length, double hierarchicalThreshold, bool useLength, bool maximization) {
+      if (useLength && IterationsParameter.ActualValue.Value >= IterationHirachicalSelectionParameter.ActualValue.Value
+        && Math.Abs(qualities[indexTrue] - qualities[indexFalse]) <= hierarchicalThreshold
+        && length[indexTrue] != length[indexFalse]) {
+        return length[indexTrue] < length[indexFalse];
+      }
+      return IsBetter(indexTrue, indexFalse, qualities, maximization);
+    }
+
+    private bool IsBetter(int indexTrue, int indexFalse, IList<double> qualities, bool maximization) {
+      return ((maximization) && (qualities[indexTrue] > qualities[indexFalse])) ||
+             ((!maximization) && (qualities[indexTrue] < qualities[indexFalse]));
     }