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

Timestamp:

12/06/16 15:07:45 (7 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

File:

• branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs (modified) (3 diffs)

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);