Changeset 14551 for branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary

Timestamp:

01/08/17 22:16:19 (8 years ago)

Author:

abeham

Message:

#2701: refactored breeding, removed hillclimbing after breeding

File:

• branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs (modified) (4 diffs)

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs

@@ -27 +27 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
 using HeuristicLab.Encodings.BinaryVectorEncoding;
 using HeuristicLab.Optimization;
@@ -156 +157 @@
       var evaluations = 0;
       var N = p1.Solution.Length;
-      if (double.IsNaN(p1.Fitness)) {
-        Evaluate(p1, token);
-        evaluations++;
-      }
-      if (double.IsNaN(p2.Fitness)) {
-        Evaluate(p2, token);
-        evaluations++;
-      }
-      var better = Problem.Maximization ? Math.Max(p1.Fitness, p2.Fitness)
-                                        : Math.Min(p1.Fitness, p2.Fitness);
-
+
+      var probe = ToScope((BinaryVector)p1.Solution.Clone());
 
       var cache = new HashSet<BinaryVector>(new BinaryVectorEqualityComparer());
@@ -172 +164 @@
       cache.Add(p2.Solution);
 
+      var cacheHits = 0;
       ISingleObjectiveSolutionScope<BinaryVector> offspring = null;
-      var probe = ToScope(new BinaryVector(N));
-      // first try all possible combinations of 1-point crossover
-      /*var order = Enumerable.Range(1, N - 2).Where(x => p1.Solution[x] != p2.Solution[x]).Shuffle(Context.Random).ToList();
-      foreach (var b in order) {
-        for (var i = 0; i <= b; i++)
-          probe.Solution[i] = p1.Solution[i];
-        for (var i = b + 1; i < probe.Solution.Length; i++)
-          probe.Solution[i] = p2.Solution[i];
-
-        // only add to cache, because all solutions must be unique
-        if (cache.Contains(probe.Solution)) continue;
-        cache.Add(probe.Solution);
+      while (evaluations < N) {
+        BinaryVector c = null;
+        var xochoice = Context.Random.Next(3);
+        switch (xochoice) {
+          case 0: c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(1)); break;
+          case 1: c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(2)); break;
+          case 2: c = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
+        }
+        if (cache.Contains(c)) {
+          cacheHits++;
+          if (cacheHits > 10) break;
+          continue;
+        }
         Evaluate(probe, token);
         evaluations++;
+        cache.Add(c);
         if (offspring == null || Context.IsBetter(probe, offspring)) {
-          // immediately return upon finding a better offspring than better parent
-          if (Context.IsBetter(probe.Fitness, better)) {
-            Context.IncrementEvaluatedSolutions(evaluations);
-            return probe;
-          }
-          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
-        }
-      }*/
-
-      var cacheHits = 0;
-      // if we got some evaluations left, try uniform crossover
-      while (evaluations < Math.Min(Context.LocalSearchEvaluations, N)) {
-        probe.Solution = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
-        if (cache.Contains(probe.Solution)) {
-          cacheHits++;
-          if (cacheHits > 10) break; // variability of uniform crossover is too low -> parents are too similar
-          continue;
-        } else cache.Add(probe.Solution);
-        Evaluate(probe, token);
-        evaluations++;
-        if (offspring == null || Context.IsBetter(probe, offspring)) {
-          // immediately return upon finding a better offspring than better parent
-          if (Context.IsBetter(probe.Fitness, better)) {
-            Context.IncrementEvaluatedSolutions(evaluations);
-            return probe;
-          }
-          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
+          offspring = probe;
+          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
+            break;
         }
       }
       Context.IncrementEvaluatedSolutions(evaluations);
-      // return best offspring found
       return offspring ?? probe;
     }
@@ -224 +194 @@
     protected override ISingleObjectiveSolutionScope<BinaryVector> Link(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token, bool delink = false) {
       var evaluations = 0;
-      if (double.IsNaN(a.Fitness)) {
-        Evaluate(a, token);
-        evaluations++;
-      }
-      if (double.IsNaN(b.Fitness)) {
-        Evaluate(b, token);
-        evaluations++;
-      }
-
       var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)a.Clone();
       var child = childScope.Solution;