Changeset 14551 for branches/MemPRAlgorithm

Timestamp:

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

Author:

abeham

Message:

#2701: refactored breeding, removed hillclimbing after breeding

Location:

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3

Files:

• Binary/BinaryMemPR.cs (modified) (4 diffs)
• LinearLinkage/LinearLinkageMemPR.cs (modified) (1 diff)
• MemPRAlgorithm.cs (modified) (1 diff)
• Permutation/PermutationMemPR.cs (modified) (10 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;

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

@@ -248 +248 @@
     }
 
-    protected override ISingleObjectiveSolutionScope<LinearLinkage> Breed(ISingleObjectiveSolutionScope<LinearLinkage> p1Scope, ISingleObjectiveSolutionScope<LinearLinkage> p2Scope, CancellationToken token) {
+    protected override ISingleObjectiveSolutionScope<LinearLinkage> Breed(ISingleObjectiveSolutionScope<LinearLinkage> p1, ISingleObjectiveSolutionScope<LinearLinkage> p2, CancellationToken token) {
       var cache = new HashSet<LinearLinkage>(new LinearLinkageEqualityComparer());
+      cache.Add(p1.Solution);
+      cache.Add(p2.Solution);
+
       var cachehits = 0;
-      var evaluations = 1;
+      var evaluations = 0;
+      var probe = ToScope((LinearLinkage)p1.Solution.Clone());
       ISingleObjectiveSolutionScope<LinearLinkage> offspring = null;
-      for (; evaluations < p1Scope.Solution.Length; evaluations++) {
-        var code = GroupCrossover.Apply(Context.Random, p1Scope.Solution, p2Scope.Solution);
-        if (cache.Contains(code)) {
+      while (evaluations < p1.Solution.Length) {
+        LinearLinkage c = null;
+        if (Context.Random.NextDouble() < 0.8)
+          c = GroupCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
+        else c = SinglePointCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
+        
+        if (cache.Contains(c)) {
           cachehits++;
           if (cachehits > 10) break;
           continue;
         }
-        var probe = ToScope(code);
         Evaluate(probe, token);
-        cache.Add(code);
+        evaluations++;
+        cache.Add(c);
         if (offspring == null || Context.IsBetter(probe, offspring)) {
           offspring = probe;
-          if (Context.IsBetter(offspring, p1Scope) && Context.IsBetter(offspring, p2Scope))
+          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
             break;
         }
       }
-      Context.IncrementEvaluatedSolutions(evaluations-1);
-      return offspring;
+      Context.IncrementEvaluatedSolutions(evaluations);
+      return offspring ?? probe;
     }
 

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

@@ -660 +660 @@
       if (Context.Population.All(p => Context.IsBetter(link, p)))
         HillClimb(link, token);
-      /*else if (!Eq(link, p1) && !Eq(link, p2) && Context.HillclimbingSuited(link.Fitness))
-        HillClimb(link, token, CalculateSubspace(new[] { p1.Solution, p2.Solution }, inverse: false));*/
-
+      // intentionally not making hill climbing after delinking in sub-space
       return link;
     }

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs

@@ -395 +395 @@
     private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossAbsolute(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
       var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
+      cache.Add(p1.Solution);
+      cache.Add(p2.Solution);
+
       var cacheHits = 0;
-      var evaluations = 1;
+      var evaluations = 0;
       ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
-      for (; evaluations <= p1.Solution.Length; evaluations++) {
+      while (evaluations < p1.Solution.Length) {
         Encodings.PermutationEncoding.Permutation c = null;
         var xochoice = Context.Random.Next(3);
@@ -413 +416 @@
         var probe = ToScope(c);
         Evaluate(probe, token);
+        evaluations++;
         cache.Add(c);
         if (offspring == null || Context.IsBetter(probe, offspring)) {
@@ -420 +424 @@
         }
       }
-      Context.IncrementEvaluatedSolutions(evaluations-1);
+      Context.IncrementEvaluatedSolutions(evaluations);
       return offspring;
     }
@@ -426 +430 @@
     private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
       var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
+      cache.Add(p1.Solution);
+      cache.Add(p2.Solution);
+
       var cacheHits = 0;
-      var evaluations = 1;
+      var evaluations = 0;
       ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
-      for (; evaluations <= p1.Solution.Length; evaluations++) {
+      while(evaluations < p1.Solution.Length) {
         Encodings.PermutationEncoding.Permutation c = null;
         var xochoice = Context.Random.Next(3);
@@ -444 +451 @@
         var probe = ToScope(c);
         Evaluate(probe, token);
+        evaluations++;
         cache.Add(c);
         if (offspring == null || Context.IsBetter(probe, offspring)) {
@@ -451 +459 @@
         }
       }
-      Context.IncrementEvaluatedSolutions(evaluations-1);
+      Context.IncrementEvaluatedSolutions(evaluations);
       return offspring;
     }
@@ -457 +465 @@
     private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
       var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
+      cache.Add(p1.Solution);
+      cache.Add(p2.Solution);
+
       var cacheHits = 0;
-      var evaluations = 1;
+      var evaluations = 0;
       ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
-      for (; evaluations <= p1.Solution.Length; evaluations++) {
+      while(evaluations <= p1.Solution.Length) {
         Encodings.PermutationEncoding.Permutation c = null;
         var xochoice = Context.Random.Next(3);
@@ -475 +486 @@
         var probe = ToScope(c);
         Evaluate(probe, token);
+        evaluations++;
         cache.Add(c);
         if (offspring == null || Context.IsBetter(probe, offspring)) {
@@ -482 +494 @@
         }
       }
-      Context.IncrementEvaluatedSolutions(evaluations-1);
+      Context.IncrementEvaluatedSolutions(evaluations);
       return offspring;
     }
 
     protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
-      if (double.IsNaN(a.Fitness)) {
-        Evaluate(a, token);
-        Context.IncrementEvaluatedSolutions(1);
-      }
-      if (double.IsNaN(b.Fitness)) {
-        Evaluate(b, token);
-        Context.IncrementEvaluatedSolutions(1);
-      }
-
       var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, ToScope(null));
       double quality;
@@ -626 +629 @@
       Context.IncrementEvaluatedSolutions(evaluations);
 
-      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
-      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
+      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Delinking produced invalid child");
 
       return bestChild ?? child;