Changeset 12259

Timestamp:

03/26/15 13:35:56 (10 years ago)

Author:

pfleck

Message:

#2350

• Individuals keep track of their last move.
• When trying to replace an individual, individuals with their last move long ago are prioritized to be replaced.
• Elites can now be replaced too if the quality is bad enough.

Location:

branches/ALPS/HeuristicLab.Algorithms.ALPS.SteadyState/3.3

Files:

• AlpsSsGeneticAlgorithmMainOperator.cs (modified) (2 diffs)
• AlpsSsMover.cs (modified) (3 diffs)

branches/ALPS/HeuristicLab.Algorithms.ALPS.SteadyState/3.3/AlpsSsGeneticAlgorithmMainOperator.cs

@@ -48 +48 @@
       var mutator = new Placeholder() { Name = "Mutator (Placeholder)" };
       var ageReducer = new DataReducer() { Name = "Calculate EvalsCreated" };
+      var lastMoveReducer = new DataReducer() { Name = "Calculate LastMove" };
       var subScopesRemover = new SubScopesRemover();
       var evaluator = new Placeholder() { Name = "Evaluator (Placeholder)" };
-     
+
 
       OperatorGraph.InitialOperator = selector;
@@ -74 +75 @@
       ageReducer.TargetParameter.ActualName = "EvalsCreated";
       ageReducer.TargetOperation.Value = new ReductionOperation(ReductionOperations.Assign);
+      ageReducer.Successor = lastMoveReducer;
 
-      ageReducer.Successor = subScopesRemover;
+      lastMoveReducer.ParameterToReduce.ActualName = "LastMove";
+      lastMoveReducer.ReductionOperation.ActualName = "AgeInheritance";
+      lastMoveReducer.ReductionOperation.Value = null;
+      lastMoveReducer.TargetParameter.ActualName = "LastMove";
+      lastMoveReducer.TargetOperation.Value = new ReductionOperation(ReductionOperations.Assign);
+      lastMoveReducer.Successor = subScopesRemover;
 
       subScopesRemover.Successor = evaluator;

branches/ALPS/HeuristicLab.Algorithms.ALPS.SteadyState/3.3/AlpsSsMover.cs

@@ -142 +142 @@
       var currentLayer = layers.SubScopes[i];
       var currentIndividual = currentLayer.SubScopes[j];
+      ((IntValue)currentIndividual.Variables["LastMove"].Value).Value = evals;
+
       if (i < n - 1) {
         var nextLayer = layers.SubScopes[i + 1];
@@ -152 +154 @@
       }
     }
-    private int? FindReplaceable(IScope layer, IScope individualToReplace) {
+    private int? FindReplaceable(IScope layer, IScope replacingCandidate) {
       int layerNumber = ((IntValue)layer.Variables["Layer"].Value).Value;
 
@@ -159 +161 @@
         let quality = ((DoubleValue)individual.Variables[qualityVariableName].Value).Value
         let evalsCreated = ((IntValue)individual.Variables["EvalsCreated"].Value).Value
+        let lastMove = ((IntValue)individual.Variables["LastMove"].Value).Value
         let age = (evals - evalsCreated) / popSize
-        select new { individual, quality, age }
-        ).Select((x, index) => new { index, x.individual, x.quality, x.age })
+        select new { individual, quality, age, lastMove }
+        ).Select((x, index) => new { index, x.individual, x.quality, x.age, x.lastMove })
         .ToList();
 
       var ageLimit = layerNumber < n - 1 ? ageLimits[layerNumber] : int.MaxValue;
 
+      // Individuals which are too old are first priority to be replaced
       var toOldIndividual = individuals.FirstOrDefault(x => x.age >= ageLimit);
       if (toOldIndividual != null)
         return toOldIndividual.index;
 
-      // Take last, because it is the worst quality (sorted already before choosing TargetIndex)
-      var worstIndividual = individuals.LastOrDefault();
-      double replaceQuality = ((DoubleValue)individualToReplace.Variables[qualityVariableName].Value).Value;
-      if (worstIndividual != null && (maximization ? worstIndividual.quality < replaceQuality : worstIndividual.quality > replaceQuality))
+      double replacingCandidateQuality = ((DoubleValue)replacingCandidate.Variables[qualityVariableName].Value).Value;
+      var worseIndividuals = individuals.Where(individual =>
+            maximization
+              ? individual.quality < replacingCandidateQuality
+              : individual.quality > replacingCandidateQuality)
+           .ToList();
+      // Then take the worst individual where the last move happed m * n evaluations ago
+      int lastMoveLimit = evals - m * n;
+      var worstIndividual = worseIndividuals.LastOrDefault(individual => individual.lastMove < lastMoveLimit);
+      if (worstIndividual != null)
+        return worstIndividual.index;
+      // If no individual moved n * m evaluations ago, take the worst
+      worstIndividual = worseIndividuals.LastOrDefault();
+      if (worstIndividual != null)
         return worstIndividual.index;
 
-      return rand.Next(elites, layer.SubScopes.Count);
+      // No individual found for replacement
+      return null;
     }
   }