Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Interfaces/Interfaces.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Interfaces/Interfaces.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Interfaces/Interfaces.cs	(revision 14690)
@@ -25,4 +25,5 @@
 using HeuristicLab.Algorithms.MemPR.Grouping;
 using HeuristicLab.Algorithms.MemPR.Permutation;
+using HeuristicLab.Analysis.FitnessLandscape;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.BinaryVectorEncoding;
@@ -76,4 +77,8 @@
   }
 
+  public interface ILocalSearchPathContext<TSolution> : IExecutionContext where TSolution : class, IItem {
+    DirectedPath<TSolution> LocalSearchPaths { get; }
+  }
+
   public interface IEvaluationServiceContext<TSolution> : IExecutionContext {
     double Evaluate(TSolution solution, CancellationToken token);
Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs	(revision 14690)
@@ -220,4 +220,19 @@
     protected virtual TPopulationContext CreateContext() {
       return new TPopulationContext();
+    }
+
+    public void StartSync() {
+      using (var w = new AutoResetEvent(false)) {
+        EventHandler handler = (sender, e) => {
+          if (ExecutionState == ExecutionState.Paused
+          || ExecutionState == ExecutionState.Stopped)
+            w.Set();
+        };
+        ExecutionStateChanged += handler;
+        try {
+          Start();
+          w.WaitOne();
+        } finally { ExecutionStateChanged -= handler; }
+      }
     }
 
Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRContext.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRContext.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/MemPRContext.cs	(revision 14690)
@@ -40,6 +40,7 @@
   [StorableClass]
   public abstract class MemPRPopulationContext<TProblem, TSolution, TPopulationContext, TSolutionContext> : ParameterizedNamedItem,
-    IPopulationBasedHeuristicAlgorithmContext<TProblem, TSolution>, ISolutionModelContext<TSolution>, IEvaluationServiceContext<TSolution>
-      where TProblem : class, IItem, ISingleObjectiveHeuristicOptimizationProblem
+    IPopulationBasedHeuristicAlgorithmContext<TProblem, TSolution>, ISolutionModelContext<TSolution>, IEvaluationServiceContext<TSolution>,
+    ILocalSearchPathContext<TSolution>
+    where TProblem : class, IItem, ISingleObjectiveHeuristicOptimizationProblem
       where TSolution : class, IItem
       where TPopulationContext : MemPRPopulationContext<TProblem, TSolution, TPopulationContext, TSolutionContext>
@@ -169,4 +170,11 @@
       get { return relinkedPaths.Value; }
       set { relinkedPaths.Value = value; }
+    }
+
+    [Storable]
+    private IValueParameter<DirectedPath<TSolution>> localSearchPaths;
+    public DirectedPath<TSolution> LocalSearchPaths {
+      get { return localSearchPaths.Value; }
+      set { localSearchPaths.Value = value; }
     }
 
@@ -267,4 +275,5 @@
       byAdaptivewalking = cloner.Clone(original.byAdaptivewalking);
       relinkedPaths = cloner.Clone(original.relinkedPaths);
+      localSearchPaths = cloner.Clone(original.localSearchPaths);
       random = cloner.Clone(original.random);
       breedingStat = original.breedingStat.Select(x => Tuple.Create(x.Item1, x.Item2, x.Item3, x.Item4)).ToList();
@@ -296,4 +305,5 @@
       Parameters.Add(byAdaptivewalking = new ValueParameter<IntValue>("ByAdaptivewalking", new IntValue(0)));
       Parameters.Add(relinkedPaths = new ValueParameter<DirectedPath<TSolution>>("RelinkedPaths", new DirectedPath<TSolution>()));
+      Parameters.Add(localSearchPaths = new ValueParameter<DirectedPath<TSolution>>("LocalSearchPaths", new DirectedPath<TSolution>()));
       Parameters.Add(random = new ValueParameter<IRandom>("Random", new MersenneTwister()));
 
Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimb.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimb.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimb.cs	(revision 14690)
@@ -20,10 +20,10 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
 using System.Threading;
 using HeuristicLab.Algorithms.MemPR.Interfaces;
-using HeuristicLab.Algorithms.MemPR.Util;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -34,5 +34,6 @@
   public class ExhaustiveHillClimb<TContext> : NamedItem, ILocalSearch<TContext>
       where TContext : ISingleSolutionHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, Encodings.PermutationEncoding.Permutation>,
-                       IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation> {
+                       IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation>,
+                       ILocalSearchPathContext<Encodings.PermutationEncoding.Permutation> {
 
     [StorableConstructor]
@@ -49,10 +50,22 @@
 
     public void Optimize(TContext context) {
+      if (double.IsNaN(context.Solution.Fitness))
+        context.Evaluate(context.Solution, CancellationToken.None);
       var quality = context.Solution.Fitness;
       try {
-        var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, ref quality,
+        var path = new List<Tuple<Encodings.PermutationEncoding.Permutation, double>>();
+        path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)context.Solution.Solution.Clone(), quality));
+
+        var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, quality,
           context.Maximization, context.Evaluate, CancellationToken.None);
-        context.IncrementEvaluatedSolutions(result.Item1);
-        context.Iterations = result.Item2;
+
+        Tuple<Encodings.PermutationEncoding.Permutation, double, int> last = null;
+        foreach (var step in result) {
+          path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)step.Item1.Clone(), step.Item2));
+          last = step;
+        }
+        context.LocalSearchPaths.AddPath(path);
+        context.IncrementEvaluatedSolutions(last.Item3);
+        context.Iterations = path.Count - 2;
       } finally {
         context.Solution.Fitness = quality;
Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimbSubspace.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimbSubspace.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimbSubspace.cs	(revision 14690)
@@ -20,10 +20,10 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
 using System.Threading;
 using HeuristicLab.Algorithms.MemPR.Interfaces;
-using HeuristicLab.Algorithms.MemPR.Util;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -34,5 +34,6 @@
   public class ExhaustiveHillClimbSubspace<TContext> : NamedItem, ILocalSearch<TContext>
       where TContext : ISingleSolutionHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, Encodings.PermutationEncoding.Permutation>,
-                       IPermutationSubspaceContext, IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation> {
+                       IPermutationSubspaceContext, IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation>,
+                       ILocalSearchPathContext<Encodings.PermutationEncoding.Permutation> {
 
     [StorableConstructor]
@@ -49,10 +50,22 @@
 
     public void Optimize(TContext context) {
+      if (double.IsNaN(context.Solution.Fitness))
+        context.Evaluate(context.Solution, CancellationToken.None);
       var quality = context.Solution.Fitness;
       try {
-        var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, ref quality,
+        var path = new List<Tuple<Encodings.PermutationEncoding.Permutation, double>>();
+        path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)context.Solution.Solution.Clone(), quality));
+
+        var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, quality,
           context.Maximization, context.Evaluate, CancellationToken.None, context.Subspace.Subspace);
-        context.IncrementEvaluatedSolutions(result.Item1);
-        context.Iterations = result.Item2;
+
+        Tuple<Encodings.PermutationEncoding.Permutation, double, int> last = null;
+        foreach (var step in result) {
+          path.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)step.Item1.Clone(), step.Item2));
+          last = step;
+        }
+        context.LocalSearchPaths.AddPath(path);
+        context.IncrementEvaluatedSolutions(last.Item3);
+        context.Iterations = path.Count - 2;
       } finally {
         context.Solution.Fitness = quality;
Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive.cs	(revision 14690)
@@ -21,4 +21,5 @@
 
 using System;
+using System.Collections.Generic;
 using System.Threading;
 using HeuristicLab.Core;
@@ -33,23 +34,23 @@
 #endif
 
-    public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
-      ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
+    public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
+      double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
       CancellationToken token, bool[,] subspace = null) {
       if (double.IsNaN(quality)) quality = eval(perm, token);
-      Tuple<int, int> changes;
+      IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>> localSearchPath;
       switch (perm.PermutationType) {
         case PermutationTypes.Absolute:
-          changes = ExhaustiveSwap2.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
+          localSearchPath = ExhaustiveSwap2.HillClimb(random, perm, quality, maximization, eval, token, subspace);
           break;
         case PermutationTypes.RelativeDirected:
-          changes = Exhaustive1Shift.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
+          localSearchPath = Exhaustive1Shift.HillClimb(random, perm, quality, maximization, eval, token, subspace);
           break;
         case PermutationTypes.RelativeUndirected:
-          changes = Exhaustive2Opt.HillClimb(random, perm, ref quality, maximization, eval, token, subspace);
+          localSearchPath = Exhaustive2Opt.HillClimb(random, perm, quality, maximization, eval, token, subspace);
           break;
         default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
       }
       if (VALIDATE && !perm.Validate()) throw new ArgumentException("HillClimb produced invalid child");
-      return changes;
+      return localSearchPath;
     }
   }
Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs	(revision 14690)
@@ -21,4 +21,5 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using System.Threading;
@@ -30,6 +31,7 @@
 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
   public static class Exhaustive1Shift {
-    public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
-      ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
+    public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>>
+      HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
+      double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
       CancellationToken token, bool[,] subspace = null) {
       var evaluations = 0;
@@ -40,5 +42,4 @@
       }
       TranslocationMove lastSuccessMove = null;
-      var steps = 0;
       var neighborhood = ExhaustiveInsertionMoveGenerator.Generate(current).Shuffle(random).ToList();
       while (true) {
@@ -62,5 +63,5 @@
           evaluations++;
           if (FitnessComparer.IsBetter(maximization, q, quality)) {
-            steps++;
+            yield return Tuple.Create(current, q, evaluations);
             quality = q;
             lastSuccessMove = shift;
@@ -74,5 +75,5 @@
         if (lastSuccessMove == null) break;
       }
-      return Tuple.Create(evaluations, steps);
+      yield return Tuple.Create(current, quality, evaluations);
     }
   }
Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs	(revision 14690)
@@ -21,4 +21,5 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using System.Threading;
@@ -30,6 +31,7 @@
 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
   public static class Exhaustive2Opt {
-    public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
-      ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
+    public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>>
+      HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
+      double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
       CancellationToken token, bool[,] subspace = null) {
       var evaluations = 0;
@@ -40,5 +42,4 @@
       }
       InversionMove lastSuccessMove = null;
-      var steps = 0;
       var neighborhood = ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random).ToList();
       while (true) {
@@ -59,5 +60,5 @@
           evaluations++;
           if (FitnessComparer.IsBetter(maximization, q, quality)) {
-            steps++;
+            yield return Tuple.Create(current, q, evaluations);
             quality = q;
             lastSuccessMove = opt;
@@ -71,5 +72,5 @@
         if (lastSuccessMove == null) break;
       }
-      return Tuple.Create(evaluations, steps);
+      yield return Tuple.Create(current, quality, evaluations);
     }
   }
Index: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs	(revision 14690)
@@ -21,4 +21,5 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using System.Threading;
@@ -30,6 +31,7 @@
 namespace HeuristicLab.Algorithms.MemPR.Permutation.LocalSearch {
   public static class ExhaustiveSwap2 {
-    public static Tuple<int, int> HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
-      ref double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
+    public static IEnumerable<Tuple<Encodings.PermutationEncoding.Permutation, double, int>>
+      HillClimb(IRandom random, Encodings.PermutationEncoding.Permutation perm,
+      double quality, bool maximization, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval,
       CancellationToken token, bool[,] subspace = null) {
       var evaluations = 0;
@@ -40,5 +42,4 @@
       }
       Swap2Move lastSuccessMove = null;
-      var steps = 0;
       var neighborhood = ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random).ToList();
       while (true) {
@@ -58,5 +59,5 @@
           evaluations++;
           if (FitnessComparer.IsBetter(maximization, q, quality)) {
-            steps++;
+            yield return Tuple.Create(current, q, evaluations);
             quality = q;
             lastSuccessMove = swap;
@@ -73,5 +74,5 @@
         if (lastSuccessMove == null) break;
       }
-      return Tuple.Create(evaluations, steps);
+      yield return Tuple.Create(current, quality, evaluations);
     }
   }
Index: branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/CharacteristicCalculator/RandomWalkCalculator.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/CharacteristicCalculator/RandomWalkCalculator.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/CharacteristicCalculator/RandomWalkCalculator.cs	(revision 14690)
@@ -58,11 +58,12 @@
       characteristics = cloner.Clone(original.characteristics);
     }
-    public RandomWalkCalculator() {
+    public RandomWalkCalculator() : this(new RandomWalk()) { }
+    public RandomWalkCalculator(RandomWalk walker) {
       Name = ItemName;
       Description = ItemDescription;
-      walker = new RandomWalk();
+      this.walker = walker;
       characteristics = new CheckedItemList<StringValue>(
         new[] { "AutoCorrelation1", "CorrelationLength", "InformationContent",
-        "PartialInformationContent", "DensityBasinInformation", "InformationStability", 
+        "PartialInformationContent", "DensityBasinInformation", "InformationStability",
         "Diversity", "Regularity", "TotalEntropy", "PeakInformationContent",
         "PeakDensityBasinInformation" }.Select(x => new StringValue(x)));
@@ -91,10 +92,15 @@
         };
         walker.ExecutionStateChanged += evHandle;
-        walker.Start();
-        waitHandle.WaitOne();
-        walker.ExecutionStateChanged -= evHandle;
+        try {
+          walker.Start();
+          waitHandle.WaitOne();
+        } finally { walker.ExecutionStateChanged -= evHandle; }
       }
       foreach (var p in characteristics.CheckedItems) {
-        yield return new Result("RandomWalk." + walker.MutatorParameter.Value.Name + "." + p.Value.Value, walker.Results[p.Value.Value].Value);
+        var resultName = "RandomWalk." + walker.MutatorParameter.Value.Name + "." + p.Value.Value;
+        IResult result;
+        if (walker.Results.TryGetValue(p.Value.Value, out result)) {
+          yield return new Result(resultName, result.Value);
+        } else yield return new Result(resultName, new DoubleValue(0));
       }
       walker.Prepare(true);
Index: branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs
===================================================================
--- branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs	(revision 14681)
+++ branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs	(revision 14690)
@@ -32,4 +32,5 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Threading;
 
 namespace HeuristicLab.Analysis.FitnessLandscape {
@@ -50,4 +51,8 @@
     }
 
+    public IFixedValueParameter<BoolValue> LocalOptimaParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters["LocalOptima"]; }
+    }
+
     public int Paths {
       get { return PathsParameter.Value.Value; }
@@ -63,4 +68,9 @@
       get { return SeedParameter.Value != null ? SeedParameter.Value.Value : (int?)null; }
       set { SeedParameter.Value = value.HasValue ? new IntValue(value.Value) : null; }
+    }
+
+    public bool LocalOptima {
+      get { return LocalOptimaParameter.Value.Value; }
+      set { LocalOptimaParameter.Value.Value = value; }
     }
 
@@ -74,4 +84,5 @@
       Parameters.Add(new FixedValueParameter<BoolValue>("BestImprovement", "Whether the best of all alternatives should be chosen for each step in the path or just the first improving (least degrading) move should be made.", new BoolValue(true)));
       Parameters.Add(new OptionalValueParameter<IntValue>("Seed", "The seed for the random number generator."));
+      Parameters.Add(new FixedValueParameter<BoolValue>("LocalOptima", "Whether to perform walks between local optima.", new BoolValue(false)));
     }
 
@@ -90,9 +101,18 @@
 
       var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
+      if (LocalOptima) {
+        var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
+        QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
+      }
       var permutations = new List<Permutation> { perm };
       while (permutations.Count < pathCount + 1) {
         perm = (Permutation)permutations.Last().Clone();
         BiasedShuffle(perm, random);
-        permutations.Add(perm);
+        if (LocalOptima) {
+          var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
+          QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
+        }
+        if (HammingSimilarityCalculator.CalculateSimilarity(permutations.Last(), perm) < 0.75)
+          permutations.Add(perm);
       }
 
@@ -151,4 +171,5 @@
 
       for (var p = 0; p < f2.Count; p++) {
+        if (f2[p].Count <= 2) continue;
         var bump = 0;
         var flat = 0;
@@ -266,4 +287,5 @@
     }
 
+    // Center-of-Mass
     private static double ComBelowZero(IEnumerable<Tuple<Permutation, double>> path) {
       var area = 0.0;
Index: branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceDescriptor.cs
===================================================================
--- branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceDescriptor.cs	(revision 14681)
+++ branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceDescriptor.cs	(revision 14690)
@@ -1,5 +1,9 @@
-﻿using System.Linq;
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Analysis.FitnessLandscape;
+using HeuristicLab.Common;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Problems.QuadraticAssignment;
 
@@ -9,23 +13,38 @@
     public string Cls { get; private set; }
     public int Dimension { get; set; }
-    public double Sharpness { get; set; }
-    public double SharpnessSdev { get; set; }
-    public double Bumpiness { get; set; }
-    public double BumpinessSdev { get; set; }
-    public double Flatness { get; set; }
-    public double FlatnessSdev { get; set; }
-    public double Steadiness { get; set; }
-    public double SteadinessSdev { get; set; }
+
+    public string[] FeatureNames { get; set; }
+    public double[] FeatureValues { get; set; }
     
     private InstanceDescriptor() { }
 
-    public static InstanceDescriptor FromPathRelinkingAnalysis(QuadraticAssignmentProblem qap, int paths, int? seed) {
-      var walk = new QAPDirectedWalk {
-        Problem = qap,
-        BestImprovement = true,
-        Paths = paths,
-        Seed = seed
+    public InstanceDescriptor(string name, string cls, int dimension, string[] names, double[] values) {
+      Name = name;
+      Cls = cls;
+      Dimension = dimension;
+      FeatureNames = names;
+      FeatureValues = values;
+    }
+
+    public InstanceDescriptor(InstanceDescriptor other) {
+      Name = other.Name;
+      Cls = other.Cls;
+      Dimension = other.Dimension;
+      FeatureNames = (string[])other.FeatureNames.Clone();
+      FeatureValues = (double[]) other.FeatureValues.Clone();
+    }
+
+    public static InstanceDescriptor FromProblemOnly(QuadraticAssignmentProblem qap) {
+      return new InstanceDescriptor() {
+        Name = qap.Name,
+        Cls = GetClass(qap.Name),
+        Dimension = qap.Weights.Rows,
+        FeatureNames = new string[0],
+        FeatureValues = new double[0]
       };
-      var features = walk.Calculate().ToDictionary(x => x.Name, x => x.Value);
+    }
+
+    public static InstanceDescriptor FromPaths(QuadraticAssignmentProblem qap, List<List<Tuple<Permutation, double>>> trajectories) {
+      var features = QAPDirectedWalk.Calculate(trajectories).ToDictionary(x => x.Name, x => x.Value);
       
       return new InstanceDescriptor() {
@@ -33,12 +52,10 @@
         Cls = GetClass(qap.Name),
         Dimension = qap.Weights.Rows,
-        Sharpness = ((DoubleValue)features["Swap2.Sharpness"]).Value,
-        Bumpiness = ((DoubleValue)features["Swap2.Bumpiness"]).Value,
-        Flatness = ((DoubleValue)features["Swap2.Flatness"]).Value,
-        Steadiness = ((DoubleValue)features["Swap2.Steadiness"]).Value,
+        FeatureNames = features.Keys.ToArray(),
+        FeatureValues = features.Values.Select(x => ((DoubleValue)x).Value).ToArray()
       };
     }
 
-    private static string GetClass(string name) {
+    public static string GetClass(string name) {
       var cls = name.Substring(0, 3);
       var subCls = name.Last();
@@ -58,9 +75,5 @@
 
     public double CalculateSimilarity(InstanceDescriptor other) {
-      var sa = (Sharpness - other.Sharpness);
-      var bu = (Bumpiness - other.Bumpiness);
-      var fl = (Flatness - other.Flatness);
-      var se = (Steadiness - other.Steadiness);
-      return sa * sa + bu * bu + fl * fl + se * se;
+      return FeatureValues.Select((v, i) => (v - other.FeatureValues[i]) * (v - other.FeatureValues[i])).Sum();
     }
 
@@ -69,3 +82,31 @@
     }
   }
+
+  public class InstancesStandardizer {
+    private double[] featureMeans;
+    private double[] featureStdevs;
+
+    private InstancesStandardizer() { }
+
+    public static InstancesStandardizer Create(IList<InstanceDescriptor> instances) {
+      var standardizer = new InstancesStandardizer();
+      var featureLength = instances.First().FeatureValues.Length;
+      standardizer.featureMeans =
+        Enumerable.Range(0, featureLength)
+        .Select(x => instances.Select(y => y.FeatureValues[x]).Average()).ToArray();
+      standardizer.featureStdevs =
+        Enumerable.Range(0, featureLength)
+        .Select(x => instances.Select(y => y.FeatureValues[x]).StandardDeviation()).ToArray();
+
+      return standardizer;
+    }
+
+    public void Apply(IList<InstanceDescriptor> instances) {
+      for (var i = 0; i < instances.Count; i++) {
+        var inst = instances[i];
+        for (var x = 0; x < featureMeans.Length; x++)
+          inst.FeatureValues[x] = (inst.FeatureValues[x] - featureMeans[x]) / featureStdevs[x];
+      }
+    }
+  }
 }
Index: branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceExplorer.cs
===================================================================
--- branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceExplorer.cs	(revision 14690)
+++ branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceExplorer.cs	(revision 14690)
@@ -0,0 +1,73 @@
+﻿using System.Linq;
+using System.Threading;
+using HeuristicLab.Analysis.FitnessLandscape;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Problems.QuadraticAssignment;
+using HeuristicLab.SequentialEngine;
+
+namespace ProblemInstanceIdentifier {
+  public abstract class InstanceExplorer {
+
+    public abstract string Name { get; }
+    public abstract int Effort { get; }
+    protected InstanceExplorer() { }
+
+    public abstract InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null);
+  }
+
+  public class PathRelinkingExplorer : InstanceExplorer {
+    public int Paths { get; set; }
+    public bool LocalOptima { get; set; }
+
+    public override string Name { get { return "Path-Relinking Explorer"; } }
+    public override int Effort { get { return Paths; } }
+
+    public PathRelinkingExplorer() {
+      
+    }
+
+    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
+      var walk = new QAPDirectedWalk {
+        Problem = problem,
+        BestImprovement = true,
+        Paths = Paths,
+        Seed = seed,
+        LocalOptima = LocalOptima
+      };
+      var features = walk.Calculate().ToDictionary(x => x.Name, x => x.Value);
+
+      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
+        features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
+    }
+  }
+
+
+  public class RandomWalkExplorer : InstanceExplorer {
+    public int Iterations { get; set; }
+
+    public override string Name { get { return "Random-Walk Explorer"; } }
+    public override int Effort { get { return Iterations; } }
+
+    public RandomWalkExplorer() {
+
+    }
+
+    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
+      var walk = new RandomWalk() {
+        SeedParameter = { Value = { Value = seed ?? 0 } },
+        SetSeedRandomlyParameter = { Value = { Value = seed.HasValue } },
+        MaximumIterationsParameter = { Value = { Value = Iterations } },
+        RepetitionsParameter = { Value = { Value = 1 } }
+      };
+      walk.Problem = problem;
+      walk.Engine = new SequentialEngine();
+      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
+      var calculator = new RandomWalkCalculator(walk) { Problem = problem };
+      var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
+      
+      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
+        features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
+    }
+  }
+}
Index: branches/PerformanceComparison/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj
===================================================================
--- branches/PerformanceComparison/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj	(revision 14681)
+++ branches/PerformanceComparison/ProblemInstanceIdentifier/ProblemInstanceIdentifier.csproj	(revision 14690)
@@ -23,4 +23,5 @@
     <ErrorReport>prompt</ErrorReport>
     <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
@@ -32,4 +33,5 @@
     <ErrorReport>prompt</ErrorReport>
     <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
   </PropertyGroup>
   <ItemGroup>
@@ -67,4 +69,11 @@
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.Selection-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Selection-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.SequentialEngine-3.3">
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.SequentialEngine-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
@@ -78,4 +87,5 @@
   <ItemGroup>
     <Compile Include="InstanceDescriptor.cs" />
+    <Compile Include="InstanceExplorer.cs" />
     <Compile Include="Program.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
@@ -85,4 +95,8 @@
   </ItemGroup>
   <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Algorithms.MemPR\3.3\HeuristicLab.Algorithms.MemPR-3.3.csproj">
+      <Project>{9d274421-6332-4fbc-aae4-467ace27c368}</Project>
+      <Name>HeuristicLab.Algorithms.MemPR-3.3</Name>
+    </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Analysis.FitnessLandscape\3.3\HeuristicLab.Analysis.FitnessLandscape-3.3.csproj">
       <Project>{5fbdcd4a-3c2a-4ec6-83ce-34b29f43621a}</Project>
Index: branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs
===================================================================
--- branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs	(revision 14681)
+++ branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs	(revision 14690)
@@ -1,6 +1,8 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Globalization;
 using System.Linq;
 using System.Threading.Tasks;
+using HeuristicLab.Algorithms.MemPR.Permutation;
 using HeuristicLab.PluginInfrastructure;
 using HeuristicLab.Problems.Instances;
@@ -10,4 +12,9 @@
 namespace ProblemInstanceIdentifier {
   class Program {
+    private static HashSet<string> selectedInstances = new HashSet<string>() {
+      "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b",
+      "nug30", "rou20", "scr20", "sko42", "ste36a", "tai25a", "tai25b", "tho30", "wil50",
+      "RAND-S-6x6-36-25-AFFY-00_rand_rand_bl", "RAND-S-6x6-36-25-AFFY-00_rand_rand_ci"
+    };
     static void Main(string[] args) {
       var sync = new object();
@@ -18,7 +25,8 @@
         if (provider is TaillardQAPInstanceProvider) continue;
         Parallel.ForEach(provider.GetDataDescriptors(), desc => {
-          if (desc.Name == "esc16f") return;
+          if (!selectedInstances.Contains(desc.Name)) return;
+          //if (desc.Name == "esc16f") return;
           var qapData = provider.LoadData(desc);
-          if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
+          //if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
           var qap = new QuadraticAssignmentProblem();
           qap.Load(qapData);
@@ -29,16 +37,137 @@
       }
 
-      Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6:F2}\t{7:F2}", "Repetition", "KB-Paths", "Exp-Paths", "Cls-Hits", "Exact-Hits", "No-Hits", "Cls-Rank", "Exact-Rank");
-      var paths = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50 };
-      for (var r = 0; r < 20; r++) {
-        Parallel.ForEach(paths, kbPaths => {
-          foreach (var expPaths in paths) {
-            if (expPaths > kbPaths) continue;
+      /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls);
+      foreach (var cls in classes.OrderBy(x => x.Key)) {
+        Console.WriteLine("{0};{1}", cls.Key, cls.Count());
+      }*/
+
+      //var kb = GenerateKnowledgeBase(instances, 200, localOptima: false);
+
+
+      //var paths = new[] { 1, 2, 3, 5, 10, 20, 30, 50, 100, 200 };
+      //var kbExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray();
+      //var expExplorers = paths.Select(x => new PathRelinkingExplorer() { Paths = x }).ToArray();
+      //ExploreSelfIdentification(instances, kbExplorers, expExplorers);
+
+      var iterations = new[] { 100, 1000, 10000, 100000 };
+      var kbExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray();
+      var expExplorers = iterations.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray();
+      ExploreSelfIdentification(instances, kbExplorers, expExplorers);
+
+      //ExploreMemPrIdentification(instances);
+    }
+
+    private static List<InstanceDescriptor> GenerateKnowledgeBase(List<QuadraticAssignmentProblem> instances, InstanceExplorer explorer) {
+      var headerPrinted = false;
+      var sync = new object();
+      var kb = new List<InstanceDescriptor>();
+      Parallel.ForEach(instances.OrderBy(x => x.Weights.Rows), qap => {
+        var instance = explorer.Explore(qap);
+        lock (sync) {
+          if (!headerPrinted) {
+            headerPrinted = true;
+            Console.WriteLine(string.Join(";",
+              new [] { "Name", "Cls", "Dimension" }
+              .Concat(instance.FeatureNames)));
+          }
+          PrintInstanceLine(instance);
+          kb.Add(instance);
+        }
+      });
+      var standardizer = InstancesStandardizer.Create(kb);
+      var normalizedKb = kb.Select(x => new InstanceDescriptor(x)).ToList();
+      standardizer.Apply(normalizedKb);
+      Console.WriteLine();
+      foreach (var instance in kb) {
+        PrintInstanceLine(instance);
+      }
+      //return normalizedKb;
+      return kb;
+    }
+
+    private static void PrintInstanceLine(InstanceDescriptor instance) {
+      Console.WriteLine(string.Join(";",
+        new[] {instance.Name, instance.Cls, instance.Dimension.ToString(CultureInfo.CurrentCulture)}
+          .Concat(instance.FeatureValues.Select(x => x.ToString(CultureInfo.CurrentCulture)))));
+    }
+
+    private static void ExploreSelfIdentification(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] kbExplorer, InstanceExplorer[] expExporer) {
+      var sync = new object();
+      Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Effort", "Exp-Effort",
+        "Exact-Hits", "No-Hits", "Exact-Rank");
+      var kbSeeds = Enumerable.Range(0, 20).ToList();
+      var expSeeds = Enumerable.Range(20, 20).ToList();
+      for (var r = 0; r < 10; r++) {
+        var rlokal = r;
+        Parallel.ForEach(kbExplorer, kbPaths => {
+        //foreach (var kbPaths in kbExplorer) {
+          foreach (var expPaths in expExporer) {
+            //if (expPaths > kbPaths) continue;
             var kb = new List<InstanceDescriptor>();
             var exp = new List<InstanceDescriptor>();
             foreach (var qap in instances) {
-              kb.Add(InstanceDescriptor.FromPathRelinkingAnalysis(qap, kbPaths, null));
-              exp.Add(InstanceDescriptor.FromPathRelinkingAnalysis(qap, expPaths, null));
+              kb.Add(kbPaths.Explore(qap, kbSeeds[rlokal]));
+              exp.Add(expPaths.Explore(qap, expSeeds[rlokal]));
             }
+            var standardizer = InstancesStandardizer.Create(kb);
+            standardizer.Apply(kb);
+            standardizer.Apply(exp);
+            int exactCount = 0, clsCount = 0, missedCount = 0;
+            int exactRank = 0, clsRank = 0;
+            foreach (var e in exp) {
+              var ordered = kb.OrderBy(x => x.CalculateSimilarity(e)).ToList();
+              var bestMatch = ordered.First();
+              if (bestMatch.Cls == e.Cls) {
+                clsCount++;
+                if (bestMatch.Name == e.Name) exactCount++;
+              }
+              else missedCount++;
+              clsRank += ordered.FindIndex((id) => id.Cls == e.Cls) + 1;
+              exactRank += ordered.FindIndex((id) => id.Name == e.Name) + 1;
+            }
+            lock (sync) {
+              Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths.Effort, expPaths.Effort, exactCount,
+                missedCount, exactRank / (double) exp.Count);
+            }
+          }
+        });
+        //}
+      }
+    }
+    
+    private static void ExploreMemPrIdentification(List<QuadraticAssignmentProblem> instances) {
+      var sync = new object();
+      Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}", "Repetition", "KB-Runtime", "Exp-Runtime",
+        "Exact-Hits", "No-Hits", "Average-Rank");
+      var paths = new[] { 10 };
+      var repetitions = 10;
+      var kbSeeds = Enumerable.Range(0, repetitions).ToList();
+      var expSeeds = Enumerable.Range(repetitions, repetitions).ToList();
+      for (var r = 0; r < repetitions; r++) {
+        var rlokal = r;
+        Parallel.ForEach(paths, kbPaths => {
+          var memPr = new PermutationMemPR();
+          foreach (var expPaths in paths) {
+            //if (expPaths > kbPaths) continue;
+            var kb = new List<InstanceDescriptor>();
+            var exp = new List<InstanceDescriptor>();
+            foreach (var qap in instances.Select(x => (QuadraticAssignmentProblem)x.Clone())) {
+              memPr.Problem = qap;
+              memPr.Prepare(true);
+              memPr.Seed = kbSeeds[rlokal];
+              memPr.MaximumExecutionTime = TimeSpan.FromSeconds(kbPaths);
+              memPr.StartSync();
+              if (memPr.Context.RelinkedPaths.IsEmpty) continue;
+              kb.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList()));
+              memPr.Prepare(true);
+              memPr.Seed = expSeeds[rlokal];
+              memPr.MaximumExecutionTime = TimeSpan.FromSeconds(expPaths);
+              memPr.StartSync();
+              if (memPr.Context.RelinkedPaths.IsEmpty) continue;
+              exp.Add(InstanceDescriptor.FromPaths(qap, memPr.Context.RelinkedPaths.Paths.ToList()));
+            }
+            var standardizer = InstancesStandardizer.Create(kb);
+            standardizer.Apply(kb);
+            standardizer.Apply(exp);
             int exactCount = 0, clsCount = 0, missedCount = 0;
             int exactRank = 0, clsRank = 0;
@@ -54,5 +183,6 @@
             }
             lock (sync) {
-              Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5}\t{6:F2}\t{7:F2}", r, kbPaths, expPaths, clsCount, exactCount, missedCount, clsRank / (double)exp.Count, exactRank / (double)exp.Count);
+              Console.WriteLine("{0}\t{1}\t{2}\t{3}\t{4}\t{5:F2}", rlokal, kbPaths, expPaths, exactCount,
+                missedCount, exactRank / (double)exp.Count);
             }
           }
