Changeset 14456 for branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch

Timestamp:

12/06/16 15:07:45 (8 years ago)

Author:

abeham

Message:

#2701:

• Using evaluated solutions from HC as max evaluations for tabu walking in MemPR
• Fixed some bugs in MemPR (permutation) regarding subspace calculation (true means okay, false means no)
• Fixed bug in TSP

Location:

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

Files:

• Exhaustive.cs (modified) (1 diff)
• Exhaustive1Shift.cs (modified) (3 diffs)
• Exhaustive2Opt.cs (modified) (3 diffs)
• ExhaustiveSwap2.cs (modified) (3 diffs)

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

@@ -35 +35 @@
     public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
       ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, double> eval,
-      CancellationToken token, bool[,] noTouch = null) {
+      CancellationToken token, bool[,] subspace = null) {
       if (double.IsNaN(quality)) quality = eval(perm);
       Tuple<int, int> changes;
       switch (perm.PermutationType) {
         case PermutationTypes.Absolute:
-          changes = ExhaustiveSwap2.HillClimb(random, perm, ref quality, maximization, eval, token, noTouch);
+          changes = ExhaustiveSwap2.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
           break;
         case PermutationTypes.RelativeDirected:
-          changes = Exhaustive1Shift.HillClimb(random, perm, ref quality, maximization, eval, token, noTouch);
+          changes = Exhaustive1Shift.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
           break;
         case PermutationTypes.RelativeUndirected:
-          changes = Exhaustive2Opt.HillClimb(random, perm, ref quality, maximization, eval, token, noTouch);
+          changes = Exhaustive2Opt.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
           break;
         default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));

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

@@ -21 +21 @@
 
 using System;
+using System.Linq;
 using System.Threading;
 using HeuristicLab.Algorithms.MemPR.Util;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
@@ -30 +32 @@
     public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
       ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, double> eval,
-      CancellationToken token, bool[,] noTouch = null) {
+      CancellationToken token, bool[,] subspace = null) {
+      var evaluations = 0;
       var current = perm;
-      if (double.IsNaN(quality)) quality = eval(current);
+      if (double.IsNaN(quality)) {
+        quality = eval(current);
+        evaluations++;
+      }
       TranslocationMove lastSuccessMove = null;
-      int steps = 0, evaluations = 0;
+      var steps = 0;
+      var neighborhood = ExhaustiveInsertionMoveGenerator.Generate(current).Shuffle(random).ToList();
       while (true) {
-        foreach (var shift in ExhaustiveInsertionMoveGenerator.Generate(current)) {
+        foreach (var shift in neighborhood) {
           if (lastSuccessMove != null && shift.Index1 == lastSuccessMove.Index1 && shift.Index2 == lastSuccessMove.Index2 && shift.Index3 == lastSuccessMove.Index3) {
             // been there, done that
@@ -48 +55 @@
           var next3 = (shift.Index3 + 1) % current.Length;
           if (prev3 < 0) prev3 += current.Length;
-          if (noTouch != null && ((noTouch[current[prev1], current[shift.Index1]] || noTouch[current[shift.Index1], current[next1]]
-                                || noTouch[current[prev3], current[shift.Index3]] || noTouch[current[shift.Index3], current[next3]])))
+          if (subspace != null && !(subspace[current[prev1], current[shift.Index1]] && subspace[current[shift.Index1], current[next1]]
+                                && subspace[current[prev3], current[shift.Index3]] && subspace[current[shift.Index3], current[next3]]))
             continue;
           TranslocationManipulator.Apply(current, shift.Index1, shift.Index2, shift.Index3);

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

@@ -21 +21 @@
 
 using System;
+using System.Linq;
 using System.Threading;
 using HeuristicLab.Algorithms.MemPR.Util;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
@@ -30 +32 @@
     public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
       ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, double> eval,
-      CancellationToken token, bool[,] noTouch = null) {
+      CancellationToken token, bool[,] subspace = null) {
+      var evaluations = 0;
       var current = perm;
-      if (double.IsNaN(quality)) quality = eval(current);
+      if (double.IsNaN(quality)) {
+        quality = eval(current);
+        evaluations++;
+      }
       InversionMove lastSuccessMove = null;
-      int steps = 0, evaluations = 0;
+      var steps = 0;
+      var neighborhood = ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random).ToList();
       while (true) {
-        foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(current)) {
+        foreach (var opt in neighborhood) {
           if (lastSuccessMove != null && opt.Index1 == lastSuccessMove.Index1 && opt.Index2 == lastSuccessMove.Index2) {
             // been there, done that
@@ -45 +52 @@
           var next = (opt.Index2 + 1) % current.Length;
           if (prev < 0) prev += current.Length;
-          if (noTouch != null && ((noTouch[current[prev], current[opt.Index1]]) || (noTouch[current[opt.Index2], current[next]])))
+          if (subspace != null && !(subspace[current[prev], current[opt.Index1]] && subspace[current[opt.Index2], current[next]]))
             continue;
 

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

@@ -21 +21 @@
 
 using System;
+using System.Linq;
 using System.Threading;
 using HeuristicLab.Algorithms.MemPR.Util;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
@@ -30 +32 @@
     public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
       ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, double> eval,
-      CancellationToken token, bool[,] noTouch = null) {
+      CancellationToken token, bool[,] subspace = null) {
+      var evaluations = 0;
       var current = perm;
-      if (double.IsNaN(quality)) quality = eval(current);
+      if (double.IsNaN(quality)) {
+        quality = eval(current);
+        evaluations++;
+      }
       Swap2Move lastSuccessMove = null;
-      int steps = 0, evaluations = 0;
+      var steps = 0;
+      var neighborhood = ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random).ToList();
       while (true) {
-        foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current)) {
+        foreach (var swap in neighborhood) {
           if (lastSuccessMove != null && swap.Index1 == lastSuccessMove.Index1 && swap.Index2 == lastSuccessMove.Index2) {
             // been there, done that
@@ -42 +49 @@
             break;
           }
-          if (noTouch != null && (noTouch[swap.Index1, 0] || noTouch[swap.Index2, 0]))
+          if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
             continue;