Changeset 14453 for branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation

Timestamp:

12/05/16 12:27:19 (8 years ago)

Author:

abeham

Message:

#2701:

• Worked on MemPR algorithm for permutations
  • Made Evaluate() method mostly thread-safe and moved evaluated solutions counting to caller
• Removed TSP specific similarity calculator (it is actually not specific to the TSP) and added it to the permutation encoding as HammingSimilarityCalculator
• Fixed bug in qap basicproblem

Location:

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

Files:

• LocalSearch/StaticAPI/Exhaustive1Shift.cs (modified) (1 diff)
• LocalSearch/StaticAPI/Exhaustive2Opt.cs (modified) (1 diff)
• LocalSearch/StaticAPI/ExhaustiveSwap2.cs (modified) (1 diff)
• PermutationMemPR.cs (modified) (21 diffs)

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs

@@ -67 +67 @@
         if (lastSuccessMove == null) break;
       }
-      return Tuple.Create(steps, evaluations);
+      return Tuple.Create(evaluations, steps);
     }
   }

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs

@@ -64 +64 @@
         if (lastSuccessMove == null) break;
       }
-      return Tuple.Create(steps, evaluations);
+      return Tuple.Create(evaluations, steps);
     }
   }

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs

@@ -66 +66 @@
         if (lastSuccessMove == null) break;
       }
-      return Tuple.Create(steps, evaluations);
+      return Tuple.Create(evaluations, steps);
     }
   }

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

@@ -154 +154 @@
     }
 
-    public static void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
+    public void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
       switch (perm.PermutationType) {
         case PermutationTypes.Absolute:
@@ -170 +170 @@
     }
 
-    public static void TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
-      if (double.IsNaN(quality)) quality = eval(perm, random);
+    public void TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
+      var evaluations = 0;
+      if (double.IsNaN(quality)) {
+        quality = eval(perm, random);
+        evaluations++;
+      }
       Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
       double bestOfTheWalkF = double.NaN;
@@ -177 +181 @@
       var currentF = quality;
       var overallImprovement = false;
-      //Console.WriteLine("Current    {0}", string.Join(", ", current));
       var tabu = new double[current.Length, current.Length];
       for (var i = 0; i < current.Length; i++) {
@@ -191 +194 @@
         Swap2Move bestOfTheRest = null;
         var improved = false;
-        //LogAlways("TabuWalk ({0}/{2}): {1}   ({3})", iter, currentF, maxIterations, string.Join(", ", current));
         foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random)) {
           if (noTouch != null && (noTouch[swap.Index1, 0] || noTouch[swap.Index2, 0]))
@@ -200 +202 @@
           current[swap.Index2] = h;
           var q = eval(current, random);
+          evaluations++;
           if (q < quality) {
             overallImprovement = true;
@@ -233 +236 @@
         if (!allTabu && !improved) {
           tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
-          //LogAlways("Making Tabu [{0},{1}] = {2}", bestOfTheRest.Index1, current[bestOfTheRest.Index1], tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
           tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
-          //LogAlways("Making Tabu [{0},{1}] = {2}", bestOfTheRest.Index2, current[bestOfTheRest.Index2], tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
 
           var h = current[bestOfTheRest.Index1];
@@ -244 +245 @@
         } else if (allTabu) break;
       }
+      Context.IncrementEvaluatedSolutions(evaluations);
       if (!overallImprovement && bestOfTheWalk != null) {
         quality = bestOfTheWalkF;
@@ -250 +252 @@
     }
 
-    public static void TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
+    public void TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
       return;
     }
 
-    public static void TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
-      if (double.IsNaN(quality)) quality = eval(perm, random);
+    public void TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxIterations = int.MaxValue, bool[,] noTouch = null) {
+      var evaluations = 0;
+      if (double.IsNaN(quality)) {
+        quality = eval(perm, random);
+        evaluations++;
+      }
       Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
       double bestOfTheWalkF = double.NaN;
@@ -287 +293 @@
 
           var q = eval(current, random);
+          evaluations++;
           if (q < quality) {
             overallImprovement = true;
@@ -333 +340 @@
         } else if (allTabu) break;
       }
+      Context.IncrementEvaluatedSolutions(evaluations);
       if (!overallImprovement && bestOfTheWalk != null) {
         quality = bestOfTheWalkF;
@@ -456 +464 @@
     }
 
-    public static Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
+    public Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
       if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
       switch (p1.PermutationType) {
@@ -469 +477 @@
     }
 
-    public static Encodings.PermutationEncoding.Permutation RelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
+    public Encodings.PermutationEncoding.Permutation RelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
+      var evaluations = 0;
       var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
 
@@ -492 +501 @@
           Swap(child, invChild[p2[idx]], idx);
           var moveF = eval(child, random);
+          evaluations++;
           if (double.IsNaN(bestChange) || moveF < bestChange) {
             bestChange = moveF;
@@ -515 +525 @@
         }
       }
-      //Log(string.Join(", ", p2));
+      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 (bestChild == null) best = eval(child, random);
       return bestChild ?? child;
     }
 
-    public static Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
+    public Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
+      var evaluations = 0;
       var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
 
@@ -545 +556 @@
           else Shift(child, from: c, to: n);
           var moveF = eval(child, random);
+          evaluations++;
           if (double.IsNaN(bestChange) || moveF < bestChange) {
             bestChange = moveF;
@@ -564 +576 @@
       } while (!double.IsNaN(bestChange));
 
+      Context.IncrementEvaluatedSolutions(evaluations);
       if (VALIDATE && !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");
@@ -569 +582 @@
     }
 
-    public static Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
+    public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
+      var evaluations = 0;
       var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
 
@@ -646 +660 @@
           }
           var moveF = eval(child, random);
+          evaluations++;
           if (double.IsNaN(bestChange) || moveF < bestChange) {
             bestChange = moveF;
@@ -659 +674 @@
           while (bestQueue.Count > 0) {
             var m = bestQueue.Dequeue();
-            //Log("Applying opt {0} {1}", m.Item1, m.Item2);
-            //Log("{0}", string.Join(" ", child));
             Opt(child, m.Item1, m.Item2);
-            //Log("{0}", string.Join(" ", child));
           }
           for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
@@ -672 +684 @@
       } while (!double.IsNaN(bestChange));
 
-      //Log("{0}", string.Join(" ", p2));
+      Context.IncrementEvaluatedSolutions(evaluations);
+      
       if (VALIDATE && !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");
@@ -681 +694 @@
       var d = Math.Abs(invP[a] - invP[b]);
       return d == 1 || d == invP.Length - 1;
-    }
-
-    private static void Move(Encodings.PermutationEncoding.Permutation child, int from, int to) {
-      if (child.PermutationType == PermutationTypes.Absolute) {
-        // swap
-        Swap(child, from, to);
-      } else if (child.PermutationType == PermutationTypes.RelativeDirected) {
-        // shift
-        Shift(child, from, to);
-      } else if (child.PermutationType == PermutationTypes.RelativeUndirected) {
-        // opt
-        Opt(child, from, to);
-      } else throw new ArgumentException(string.Format("Unknown permutation type {0}", child.PermutationType));
-    }
-
-    private static void Move(PermutationTypes type, bool[] arr, int from, int to) {
-      switch (type) {
-        case PermutationTypes.Absolute: {
-            /*var h = arr[from];
-            arr[from] = arr[to];
-            arr[to] = h;*/
-            arr[from] = false;
-            arr[to] = false;
-            break;
-          }
-        case PermutationTypes.RelativeDirected: {
-            var original = (bool[])arr.Clone();
-            var number = original[from];
-            int i = 0;  // index in new permutation
-            int j = 0;  // index in old permutation
-            while (i < original.Length) {
-              if (j == from) {
-                j++;
-              }
-              if (i == to) {
-                arr[i] = number;
-                i++;
-              }
-              if ((i < original.Length) && (j < original.Length)) {
-                arr[i] = original[j];
-                i++;
-                j++;
-              }
-            }
-            break;
-          }
-        case PermutationTypes.RelativeUndirected: {
-            if (from > to) {
-              var hu = from;
-              from = to;
-              to = hu;
-            }
-            for (int i = 0; i <= (to - from) / 2; i++) {  // invert permutation between breakpoints
-              var temp = arr[from + i];
-              arr[from + i] = arr[to - i];
-              arr[to - i] = temp;
-            }
-            break;
-          }
-        default:
-          throw new ArgumentException(string.Format("Unknown permutation type {0}", type));
-      }
     }