Changeset 15345 for branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Selector/LexicaseSelector.cs

Timestamp:

08/31/17 18:59:39 (7 years ago)

Author:

pkimmesw

Message:

#2665 Fixed Lexicase

File:

• branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Selector/LexicaseSelector.cs (modified) (4 diffs)

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Selector/LexicaseSelector.cs

@@ -30 +30 @@
   using HeuristicLab.Parameters;
   using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-  using HeuristicLab.Problems.ProgramSynthesis.Push.Extensions;
   using HeuristicLab.Problems.ProgramSynthesis.Push.Problem;
+  using HeuristicLab.Random;
   using HeuristicLab.Selection;
-  using Random;
 
   /// <summary>
@@ -59 +58 @@
     }
 
-    protected override IScope[] Select(List<IScope> population) {
+
+    protected override IScope[] Select(List<IScope> scopes) {
+      var count = NumberOfSelectedSubScopesParameter.ActualValue.Value;
+      var copy = CopySelectedParameter.Value.Value;
+      var random = RandomParameter.ActualValue;
+      var maximization = MaximizationParameter.ActualValue.Value;
+
+      //var qualities = QualityParameter.ActualValue;
+      //.Where(x => IsValidQuality(x.Value))
+      //.Select(x => x.Value)
+      //.ToList();
+
+      var caseQualities = CaseQualitiesParameter.ActualValue.ToList();
+
       var selected = Apply(
-        population,
-        NumberOfSelectedSubScopesParameter.ActualValue.Value,
-        CopySelectedParameter.Value.Value,
-        MaximizationParameter.ActualValue.Value,
-        RandomParameter.ActualValue,
-        CaseQualitiesParameter.ActualValue);
+        scopes,
+        count,
+        copy,
+        maximization,
+        random,
+        caseQualities);
 
       return selected;
@@ -72 +84 @@
 
     public static IScope[] Apply(
-      List<IScope> population,
+      List<IScope> scopes,
       int count,
       bool copy,
       bool maximization,
       IRandom random,
-      ItemArray<DoubleArray> caseQualities) {
+      List<DoubleArray> caseQualities) {
+
+      for (var i = 0; i < caseQualities.Count; i++) {
+        if (caseQualities[i].Length == 0) {
+          scopes.RemoveAt(i);
+          caseQualities.RemoveAt(i);
+        }
+      }
+
+      if (caseQualities.Any(x => x.Length != caseQualities[0].Length)) {
+        throw new ArgumentException("Not all case qualities have the same length");
+      }
+
       var selected = new IScope[count];
-      var repeats = (int)Math.Ceiling(count / (double)population.Count);
-      var caseCount = caseQualities[0].Length;
-      var source = Enumerable.Range(0, population.Count).ToList();
+      var candidates = Enumerable.Range(0, caseQualities.Count).ToList();
+      var orderSource = Enumerable.Range(0, caseQualities[0].Length).ToList();
 
-      for (var k = 0; k < repeats; k++) {
-        // The fitness cases are shuffled.
-        var fitnessCaseIndexes = Enumerable.Range(0, caseCount).Shuffle(random).ToList();
+      for (var i = 0; i < count; i++) {
+        var index = LexicaseSelect(
+          caseQualities,
+          candidates,
+          orderSource.Shuffle(random),
+          random,
+          maximization);
 
-        // copy list if required
-        var pool = repeats == 1 ? source : new List<int>(source);
-        var countLimit = Math.Min(count - k * population.Count, population.Count);
-
-        for (var i = 0; i < countLimit; i++) {
-          var candidates = pool;
-
-          for (var j = 0; j < fitnessCaseIndexes.Count && candidates.Count > 1; j++) {
-            candidates = GetBestIndividuals(maximization, caseQualities, candidates, fitnessCaseIndexes[j]);
-          }
-
-          /*  If only one individual remains, it is the chosen parent. If no more fitness cases are left, a parent is
-              chosen randomly from the remaining individuals */
-          var bestIndividualIndex = candidates.Count == 1 ? candidates[0] : candidates.Random(random);
-          var bestIndividual = population[bestIndividualIndex];
-
-          selected[k * population.Count + i] = copy ? (IScope)bestIndividual.Clone() : bestIndividual;
-
-          pool.Remove(bestIndividualIndex);
+        if (copy) {
+          selected[i] = (IScope)scopes[index].Clone();
+        } else {
+          selected[i] = scopes[index];
+          scopes.RemoveAt(index);
+          caseQualities.RemoveAt(index);
         }
       }
@@ -112 +126 @@
     }
 
-    private static List<int> GetBestIndividuals(bool maximization, ItemArray<DoubleArray> caseQualities, List<int> bestIndividuals, int index) {
-      var bestFitness = maximization ? double.NegativeInfinity : double.PositiveInfinity;
-      var result = new List<int>();
+    private static int LexicaseSelect(
+      List<DoubleArray> caseQualities,
+      List<int> candidates,
+      IEnumerable<int> order,
+      IRandom random,
+      bool maximization) {
 
-      for (var l = 0; l < bestIndividuals.Count; l++) {
-        var individual = bestIndividuals[l];
-        var caseQuality = caseQualities[individual][index];
+      foreach (var curCase in order) {
+        var nextCandidates = new List<int>();
 
-        if (bestFitness.IsAlmost(caseQuality)) {
-          result.Add(individual);
-        } else if (maximization && bestFitness < caseQuality ||
-                  !maximization && bestFitness > caseQuality) {
-          bestFitness = caseQuality;
-          result.Clear();
-          result.Add(individual);
+        var best = maximization
+          ? double.NegativeInfinity
+          : double.PositiveInfinity;
+
+        foreach (var candidate in candidates) {
+          if (caseQualities[candidate][curCase].IsAlmost(best)) {
+            // if the individuals is as good as the best one, add it
+            nextCandidates.Add(candidate);
+          } else if (
+             (maximization && (caseQualities[candidate][curCase] > best)) ||
+             (!maximization && (caseQualities[candidate][curCase] < best))) {
+            // if the individuals is better than the best one, remove all previous candidates and add the new one
+            nextCandidates.Clear();
+            nextCandidates.Add(candidate);
+            // also set the next best quality value
+            best = caseQualities[candidate][curCase];
+          }
+          // else {do nothing}
         }
 
-        bestIndividuals = result;
+        if (nextCandidates.Count == 1) {
+          return nextCandidates[0];
+        }
+
+        if (nextCandidates.Count < 1) {
+          return candidates.SampleRandom(random);
+        }
+
+        candidates = nextCandidates;
       }
 
-      return bestIndividuals;
+      return candidates.Count == 1
+        ? candidates[0]
+        : candidates.SampleRandom(random);
     }
   }