Index: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs	(revision 14456)
@@ -97,5 +97,5 @@
     }
 
-    protected override void TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int steps, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
+    protected override int TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
       var evaluations = 0;
       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
@@ -111,8 +111,10 @@
       for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness);
       var subN = subset != null ? subset.Count(x => x) : N;
-      if (subN == 0) return;
+      if (subN == 0) return 0;
       var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
 
-      for (var iter = 0; iter < steps; iter++) {
+      var steps = 0;
+      var stepsUntilBestOfWalk = 0;
+      for (var iter = 0; iter < int.MaxValue; iter++) {
         var allTabu = true;
         var bestOfTheRestF = double.NaN;
@@ -130,4 +132,5 @@
           if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) {
             bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
+            stepsUntilBestOfWalk = steps;
           }
 
@@ -138,4 +141,5 @@
           if (IsBetter(after, before) && !isTabu) {
             improved = true;
+            steps++;
             tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after);
           } else { // undo the move
@@ -147,4 +151,5 @@
             currentScope.Fitness = before;
           }
+          if (evaluations >= maxEvals) break;
         }
         if (!allTabu && !improved) {
@@ -153,9 +158,12 @@
           tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better);
           currentScope.Fitness = bestOfTheRestF;
+          steps++;
         } else if (allTabu) break;
+        if (evaluations >= maxEvals) break;
       }
 
       Context.IncrementEvaluatedSolutions(evaluations);
       scope.Adopt(bestOfTheWalk ?? currentScope);
+      return stepsUntilBestOfWalk;
     }
 
Index: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs	(revision 14456)
@@ -231,4 +231,5 @@
           Analyze(token);
           token.ThrowIfCancellationRequested();
+          if (Terminate()) return;
         }
         Context.HcSteps /= 2;
@@ -314,4 +315,7 @@
         Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
       else ((IntValue)res.Value).Value = Context.Iterations;
+      if (!Results.TryGetValue("HcSteps", out res))
+        Results.Add(new Result("HcSteps", new IntValue(Context.HcSteps)));
+      else ((IntValue)res.Value).Value = Context.HcSteps;
       if (!Results.TryGetValue("ByBreeding", out res))
         Results.Add(new Result("ByBreeding", new IntValue(Context.ByBreeding)));
@@ -491,5 +495,5 @@
       Context.HillclimbingStat.Add(Tuple.Create(before, after));
       Context.IncrementEvaluatedSolutions(lscontext.EvaluatedSolutions);
-      return lscontext.Iterations;
+      return lscontext.EvaluatedSolutions;
     }
 
@@ -501,10 +505,11 @@
       var before = scope.Fitness;
       var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
-      TabuWalk(newScope, steps, token, subspace);
+      var newSteps = TabuWalk(newScope, steps, token, subspace);
       Context.TabuwalkingStat.Add(Tuple.Create(before, newScope.Fitness));
+      //Context.HcSteps = (int)Math.Ceiling(Context.HcSteps * (1.0 + Context.TabuwalkingStat.Count) / (2.0 + Context.TabuwalkingStat.Count) + newSteps / (2.0 + Context.TabuwalkingStat.Count));
       if (IsBetter(newScope, scope) || (newScope.Fitness == scope.Fitness && Dist(newScope, scope) > 0))
         scope.Adopt(newScope);
     }
-    protected abstract void TabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
+    protected abstract int TabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int maxEvals, CancellationToken token, ISolutionSubspace<TSolution> subspace = null);
     protected virtual void TabuClimb(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
       if (double.IsNaN(scope.Fitness)) {
@@ -514,6 +519,7 @@
       var before = scope.Fitness;
       var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
-      TabuWalk(newScope, steps, token, subspace);
+      var newSteps = TabuWalk(newScope, steps, token, subspace);
       Context.TabuwalkingStat.Add(Tuple.Create(before, newScope.Fitness));
+      //Context.HcSteps = (int)Math.Ceiling(Context.HcSteps * (1.0 + Context.TabuwalkingStat.Count) / (2.0 + Context.TabuwalkingStat.Count) + newSteps / (2.0 + Context.TabuwalkingStat.Count));
       if (IsBetter(newScope, scope) || (newScope.Fitness == scope.Fitness && Dist(newScope, scope) > 0))
         scope.Adopt(newScope);
@@ -557,7 +563,5 @@
         || Context.Population.Any(p => IsBetter(offspring, p))) return offspring;
 
-      if (IsBetter(offspring.Fitness, Context.BestQuality))
-        HillClimb(offspring, token); // perform hillclimb in full solution space
-      else if (HillclimbingSuited(offspring))
+      if (HillclimbingSuited(offspring))
         HillClimb(offspring, token, subspace); // perform hillclimb in the solution sub-space
       return offspring;
@@ -589,7 +593,5 @@
       if (dist1 > 0 && dist2 > 0) {
         var subspace = CalculateSubspace(new[] { a.Solution, b.Solution }, inverse: true);
-        if (IsBetter(child.Fitness, Context.BestQuality))
-          HillClimb(child, token); // perform hillclimb in full solution space
-        else if (HillclimbingSuited(child)) {
+        if (HillclimbingSuited(child)) {
           HillClimb(child, token, subspace); // perform hillclimb in solution sub-space
         }
Index: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive.cs	(revision 14456)
@@ -35,16 +35,16 @@
     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));
Index: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs	(revision 14456)
@@ -21,8 +21,10 @@
 
 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,11 +32,16 @@
     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,6 +55,6 @@
           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);
Index: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs	(revision 14456)
@@ -21,8 +21,10 @@
 
 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,11 +32,16 @@
     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,5 +52,5 @@
           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;
 
Index: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs	(revision 14456)
@@ -21,8 +21,10 @@
 
 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,11 +32,16 @@
     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,5 +49,5 @@
             break;
           }
-          if (noTouch != null && (noTouch[swap.Index1, 0] || noTouch[swap.Index2, 0]))
+          if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
             continue;
 
Index: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs	(revision 14456)
@@ -144,9 +144,9 @@
     }
 
-    protected override void TabuWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int steps, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
+    protected override int TabuWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
       var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Context.Problem, scope);
       var quality = scope.Fitness;
       try {
-        TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, Context.HcSteps, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
+        return TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
       } finally {
         scope.Fitness = quality;
@@ -154,22 +154,25 @@
     }
 
-    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) {
+    public int TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
+      int newSteps = 0;
       switch (perm.PermutationType) {
         case PermutationTypes.Absolute:
-          TabuWalkSwap(random, perm, eval, ref quality, maxIterations, noTouch);
+          newSteps = TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);
           break;
         case PermutationTypes.RelativeDirected:
-          TabuWalkShift(random, perm, eval, ref quality, maxIterations, noTouch);
+          newSteps = TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);
           break;
         case PermutationTypes.RelativeUndirected:
-          TabuWalkOpt(random, perm, eval, ref quality, maxIterations, noTouch);
+          newSteps = TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);
           break;
         default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
       }
       if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child");
-    }
-
-    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) {
+      return newSteps;
+    }
+
+    public int TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
       var evaluations = 0;
+      var maximization = Context.Problem.Maximization;
       if (double.IsNaN(quality)) {
         quality = eval(perm, random);
@@ -189,5 +192,7 @@
       }
 
-      for (var iter = 0; iter < maxIterations; iter++) {
+      var steps = 0;
+      var stepsUntilBestOfWalk = 0;
+      for (var iter = 0; iter < int.MaxValue; iter++) {
         var allTabu = true;
         var bestOfTheRestF = double.NaN;
@@ -195,5 +200,5 @@
         var improved = false;
         foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random)) {
-          if (noTouch != null && (noTouch[swap.Index1, 0] || noTouch[swap.Index2, 0]))
+          if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
             continue;
 
@@ -203,5 +208,5 @@
           var q = eval(current, random);
           evaluations++;
-          if (q < quality) {
+          if (FitnessComparer.IsBetter(maximization, q, quality)) {
             overallImprovement = true;
             quality = q;
@@ -209,22 +214,24 @@
           }
           // check if it would not be an improvement to swap these into their positions
-          var isTabu = q >= tabu[swap.Index1, current[swap.Index1]] && q >= tabu[swap.Index2, current[swap.Index2]];
+          var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index1, current[swap.Index1]])
+                    && !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index2, current[swap.Index2]]);
           if (!isTabu) allTabu = false;
-          if (q < currentF && !isTabu) {
-            if (double.IsNaN(bestOfTheWalkF) || bestOfTheWalkF > q) {
+          if (FitnessComparer.IsBetter(maximization, q, currentF) && !isTabu) {
+            if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
               bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
               bestOfTheWalkF = q;
-            }
-
+              stepsUntilBestOfWalk = steps;
+            }
+            steps++;
             improved = true;
             // perform the move
             currentF = q;
             // mark that to move them to their previous position requires to make an improvement
-            tabu[swap.Index1, current[swap.Index2]] = Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
-            //LogAlways("Making Tabu [{0},{1}] = {2}", swap.Index1, current[swap.Index2], tabu[swap.Index1, current[swap.Index2]]);
-            tabu[swap.Index2, current[swap.Index1]] = Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
-            //LogAlways("Making Tabu [{0},{1}] = {2}", swap.Index2, current[swap.Index1], tabu[swap.Index2, current[swap.Index1]]);
+            tabu[swap.Index1, current[swap.Index2]] = maximization ? Math.Max(q, tabu[swap.Index1, current[swap.Index2]])
+                                                                   : Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
+            tabu[swap.Index2, current[swap.Index1]] = maximization ? Math.Max(q, tabu[swap.Index2, current[swap.Index1]])
+                                                                   : Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
           } else { // undo the move
-            if (!isTabu && (double.IsNaN(bestOfTheRestF) || q < bestOfTheRestF)) {
+            if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
               bestOfTheRest = swap;
               bestOfTheRestF = q;
@@ -233,8 +240,11 @@
             current[swap.Index1] = h;
           }
-        }
-        if (!allTabu && !improved) {
-          tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
-          tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
+          if (evaluations >= maxEvals) break;
+        }
+        if (!allTabu && !improved && bestOfTheRest != null) {
+          tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]])
+                                                                                   : Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
+          tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]])
+                                                                                   : Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
 
           var h = current[bestOfTheRest.Index1];
@@ -243,5 +253,7 @@
 
           currentF = bestOfTheRestF;
+          steps++;
         } else if (allTabu) break;
+        if (evaluations >= maxEvals) break;
       }
       Context.IncrementEvaluatedSolutions(evaluations);
@@ -250,11 +262,13 @@
         for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
       }
-    }
-
-    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 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) {
+      return stepsUntilBestOfWalk;
+    }
+
+    public int TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
+      return 0;
+    }
+
+    public int TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
+      var maximization = Context.Problem.Maximization;
       var evaluations = 0;
       if (double.IsNaN(quality)) {
@@ -263,9 +277,8 @@
       }
       Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
-      double bestOfTheWalkF = double.NaN;
+      var bestOfTheWalkF = double.NaN;
       var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
       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++) {
@@ -277,5 +290,7 @@
       }
 
-      for (var iter = 0; iter < maxIterations; iter++) {
+      var steps = 0;
+      var stepsUntilBestOfWalk = 0;
+      for (var iter = 0; iter < int.MaxValue; iter++) {
         var allTabu = true;
         var bestOfTheRestF = double.NaN;
@@ -287,5 +302,5 @@
           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;
 
@@ -294,5 +309,5 @@
           var q = eval(current, random);
           evaluations++;
-          if (q < quality) {
+          if (FitnessComparer.IsBetter(maximization, q, quality)) {
             overallImprovement = true;
             quality = q;
@@ -300,22 +315,32 @@
           }
           // check if it would not be an improvement to opt these into their positions
-          var isTabu = q >= tabu[current[prev], current[opt.Index1]] && q >= tabu[current[opt.Index2], current[next]];
+          var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[current[prev], current[opt.Index1]])
+                    && !FitnessComparer.IsBetter(maximization, q, tabu[current[opt.Index2], current[next]]);
           if (!isTabu) allTabu = false;
-          if (q < currentF && !isTabu) {
-            if (double.IsNaN(bestOfTheWalkF) || bestOfTheWalkF > q) {
+          if (!isTabu && FitnessComparer.IsBetter(maximization, q, currentF)) {
+            if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
               bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
               bestOfTheWalkF = q;
-            }
-
+              stepsUntilBestOfWalk = steps;
+            }
+
+            steps++;
             improved = true;
             // perform the move
             currentF = q;
             // mark that to move them to their previous position requires to make an improvement
-            tabu[current[prev], current[opt.Index2]] = Math.Min(q, tabu[current[prev], current[opt.Index2]]);
-            tabu[current[opt.Index2], current[prev]] = Math.Min(q, tabu[current[opt.Index2], current[prev]]);
-            tabu[current[opt.Index1], current[next]] = Math.Min(q, tabu[current[opt.Index1], current[next]]);
-            tabu[current[next], current[opt.Index1]] = Math.Min(q, tabu[current[next], current[opt.Index1]]);
+            if (maximization) {
+              tabu[current[prev], current[opt.Index2]] = Math.Max(q, tabu[current[prev], current[opt.Index2]]);
+              tabu[current[opt.Index2], current[prev]] = Math.Max(q, tabu[current[opt.Index2], current[prev]]);
+              tabu[current[opt.Index1], current[next]] = Math.Max(q, tabu[current[opt.Index1], current[next]]);
+              tabu[current[next], current[opt.Index1]] = Math.Max(q, tabu[current[next], current[opt.Index1]]);
+            } else {
+              tabu[current[prev], current[opt.Index2]] = Math.Min(q, tabu[current[prev], current[opt.Index2]]);
+              tabu[current[opt.Index2], current[prev]] = Math.Min(q, tabu[current[opt.Index2], current[prev]]);
+              tabu[current[opt.Index1], current[next]] = Math.Min(q, tabu[current[opt.Index1], current[next]]);
+              tabu[current[next], current[opt.Index1]] = Math.Min(q, tabu[current[next], current[opt.Index1]]);
+            }
           } else { // undo the move
-            if (!isTabu && (double.IsNaN(bestOfTheRestF) || q < bestOfTheRestF)) {
+            if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
               bestOfTheRest = opt;
               bestOfTheRestF = q;
@@ -324,19 +349,28 @@
             InversionManipulator.Apply(current, opt.Index1, opt.Index2);
           }
-        }
-        if (!allTabu && !improved) {
+          if (evaluations >= maxEvals) break;
+        }
+        if (!allTabu && !improved && bestOfTheRest != null) {
           var prev = bestOfTheRest.Index1 - 1;
           var next = (bestOfTheRest.Index2 + 1) % current.Length;
           if (prev < 0) prev += current.Length;
 
-          tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
-          tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
-          tabu[current[bestOfTheRest.Index2], current[next]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
-          tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
-
+          if (maximization) {
+            tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Max(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
+            tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
+            tabu[current[bestOfTheRest.Index2], current[next]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
+            tabu[current[next], current[bestOfTheRest.Index2]] = Math.Max(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
+          } else {
+            tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
+            tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
+            tabu[current[bestOfTheRest.Index2], current[next]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
+            tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
+          }
           InversionManipulator.Apply(current, bestOfTheRest.Index1, bestOfTheRest.Index2);
 
           currentF = bestOfTheRestF;
+          steps++;
         } else if (allTabu) break;
+        if (evaluations >= maxEvals) break;
       }
       Context.IncrementEvaluatedSolutions(evaluations);
@@ -345,4 +379,5 @@
         for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
       }
+      return stepsUntilBestOfWalk;
     }
 
@@ -478,4 +513,5 @@
 
     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 maximization = Context.Problem.Maximization;
       var evaluations = 0;
       var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
@@ -502,5 +538,5 @@
           var moveF = eval(child, random);
           evaluations++;
-          if (double.IsNaN(bestChange) || moveF < bestChange) {
+          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
             bestChange = moveF;
             bestOption = j;
@@ -516,5 +552,5 @@
           invChild[child[idx2]] = idx2;
           //Log(string.Join(", ", child));
-          if (double.IsNaN(best) || bestChange < best) {
+          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
             if (Dist(child, p2) > 0) {
               best = bestChange;
@@ -525,14 +561,18 @@
         }
       }
+      if (bestChild == null) {
+        best = eval(child, random);
+        evaluations++;
+      }
       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 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 maximization = Context.Problem.Maximization;
       var evaluations = 0;
       var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
@@ -557,5 +597,5 @@
           var moveF = eval(child, random);
           evaluations++;
-          if (double.IsNaN(bestChange) || moveF < bestChange) {
+          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
             bestChange = moveF;
             bestFrom = c < n ? n : c;
@@ -569,5 +609,5 @@
           Shift(child, bestFrom, bestTo);
           for (var i = Math.Min(bestFrom, bestTo); i < Math.Max(bestFrom, bestTo); i++) invChild[child[i]] = i;
-          if (double.IsNaN(best) || bestChange < best) {
+          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
             best = bestChange;
             bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
@@ -576,11 +616,18 @@
       } while (!double.IsNaN(bestChange));
 
+      if (bestChild == null) {
+        best = eval(child, random);
+        evaluations++;
+      }
       Context.IncrementEvaluatedSolutions(evaluations);
-      if (VALIDATE && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
+
+      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");
-      return bestChild;
+
+      return bestChild ?? child;
     }
 
     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 maximization = Context.Problem.Maximization;
       var evaluations = 0;
       var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
@@ -602,5 +649,4 @@
         Queue<Tuple<int, int>> bestQueue = null;
         bestChange = double.NaN;
-        //Log("{0}", string.Join(" ", child));
         for (var j = 0; j < p2.Length; j++) {
           if (IsUndirectedEdge(invChild, p2[j], p2.GetCircular(j + 1))) continue;
@@ -661,5 +707,5 @@
           var moveF = eval(child, random);
           evaluations++;
-          if (double.IsNaN(bestChange) || moveF < bestChange) {
+          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
             bestChange = moveF;
             bestQueue = new Queue<Tuple<int, int>>(undoStack.Reverse());
@@ -677,5 +723,5 @@
           }
           for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
-          if (double.IsNaN(best) || bestChange < best) {
+          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
             best = bestChange;
             bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
@@ -684,9 +730,13 @@
       } while (!double.IsNaN(bestChange));
 
+      if (bestChild == null) {
+        best = eval(child, random);
+        evaluations++;
+      }
       Context.IncrementEvaluatedSolutions(evaluations);
       
-      if (VALIDATE && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
+      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");
-      return bestChild;
+      return bestChild ?? child;
     }
 
Index: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Util/FitnessComparer.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Util/FitnessComparer.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Util/FitnessComparer.cs	(revision 14456)
@@ -23,6 +23,7 @@
   public static class FitnessComparer {
     public static bool IsBetter(bool maximization, double a, double b) {
-      return maximization && a > b
-             || !maximization && a < b;
+      return double.IsNaN(b) && !double.IsNaN(a)
+        || maximization && a > b
+        || !maximization && a < b;
     }
   }
Index: branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs
===================================================================
--- branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs	(revision 14455)
+++ branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs	(revision 14456)
@@ -123,4 +123,5 @@
     public TravelingSalesmanProblem() : base() {
       Encoding = new PermutationEncoding("TSPTour") { Length = 16 };
+      Encoding.PermutationTypeParameter.Value.Value = PermutationTypes.RelativeUndirected;
 
       Parameters.Add(distanceFunctionParameter = new FixedValueParameter<EnumValue<TSPDistanceFunction>>("DistanceFunction", "The distance function that is used to calculate distance among the coordinates.", new EnumValue<TSPDistanceFunction>(TSPDistanceFunction.RoundedEuclidean)));
