Changeset 14453

Timestamp:

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

Author:

abeham

Message:

#2701:

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

Location:

branches/MemPRAlgorithm

Files:

• HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs (modified) (7 diffs)
• HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs (modified) (12 diffs)
• HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive1Shift.cs (modified) (1 diff)
• HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs (modified) (1 diff)
• HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/ExhaustiveSwap2.cs (modified) (1 diff)
• HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs (modified) (21 diffs)
• HeuristicLab.Algorithms.MemPR/3.3/SingleObjectiveSolutionScope.cs (modified) (1 diff)
• HeuristicLab.Encodings.PermutationEncoding/3.3/HeuristicLab.Encodings.PermutationEncoding-3.3.csproj (modified) (1 diff)
• HeuristicLab.Encodings.PermutationEncoding/3.3/SimilarityCalculators (added)
• HeuristicLab.Encodings.PermutationEncoding/3.3/SimilarityCalculators/HammingSimilarityCalculator.cs (added)
• HeuristicLab.Problems.QuadraticAssignment/3.3/QAPBasicProblem.cs (modified) (5 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs (modified) (1 diff)

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs

@@ -98 +98 @@
 
     protected override void TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int steps, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
+      var evaluations = 0;
       var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
-      if (double.IsNaN(scope.Fitness)) Evaluate(scope, token);
+      if (double.IsNaN(scope.Fitness)) {
+        Evaluate(scope, token);
+        evaluations++;
+      }
       SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null;
       var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone();
@@ -121 +125 @@
           current[idx] = !current[idx];
           Evaluate(currentScope, token);
+          evaluations++;
           var after = currentScope.Fitness;
 
@@ -151 +156 @@
       }
 
+      Context.IncrementEvaluatedSolutions(evaluations);
       scope.Adopt(bestOfTheWalk ?? currentScope);
     }
@@ -187 +193 @@
 
     protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) {
-      if (double.IsNaN(a.Fitness)) Evaluate(a, token);
-      if (double.IsNaN(b.Fitness)) Evaluate(b, token);
+      if (double.IsNaN(a.Fitness)) {
+        Evaluate(a, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
+      if (double.IsNaN(b.Fitness)) {
+        Evaluate(b, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
       if (Context.Random.NextDouble() < 0.5)
         return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true);
@@ -195 +207 @@
 
     protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) {
+      var evaluations = 0;
       var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone();
       var child = childScope.Solution;
@@ -213 +226 @@
           child[idx] = !child[idx]; // move
           Evaluate(childScope, token);
+          evaluations++;
           var s = childScope.Fitness;
           childScope.Fitness = cF;
@@ -236 +250 @@
         }
       }
+      Context.IncrementEvaluatedSolutions(evaluations);
       return best ?? childScope;
     }

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

@@ -252 +252 @@
       var p1 = Context.AtPopulation(i1);
       var p2 = Context.AtPopulation(i2);
-
-      if (double.IsNaN(p1.Fitness)) Evaluate(p1, token);
-      if (double.IsNaN(p2.Fitness)) Evaluate(p2, token);
 
       var parentDist = Dist(p1, p2);
@@ -361 +358 @@
 
     protected int Replace(ISingleObjectiveSolutionScope<TSolution> child, CancellationToken token) {
-      if (double.IsNaN(child.Fitness)) Evaluate(child, token);
+      if (double.IsNaN(child.Fitness)) {
+        Evaluate(child, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
+      if (IsBetter(child.Fitness, Context.BestQuality)) {
+        Context.BestQuality = child.Fitness;
+        Context.BestSolution = (TSolution)child.Solution.Clone();
+      }
 
       var popSize = MaximumPopulationSize;
@@ -460 +464 @@
     protected abstract ISolutionSubspace<TSolution> CalculateSubspace(IEnumerable<TSolution> solutions, bool inverse = false);
     protected virtual void Evaluate(ISingleObjectiveSolutionScope<TSolution> scope, CancellationToken token) {
-      Context.EvaluatedSolutions++;
       var prob = Problem as ISingleObjectiveProblemDefinition;
       if (prob != null) {
@@ -466 +469 @@
         scope.Fitness = prob.Evaluate(ind, Context.Random);
       } else RunOperator(Problem.Evaluator, scope, token);
-      if (IsBetter(scope.Fitness, Context.BestQuality))
-        Context.BestQuality = scope.Fitness;
     }
 
@@ -480 +481 @@
     #region Improve
     protected virtual int HillClimb(ISingleObjectiveSolutionScope<TSolution> scope, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
-      if (double.IsNaN(scope.Fitness)) Evaluate(scope, token);
+      if (double.IsNaN(scope.Fitness)) {
+        Evaluate(scope, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
       var before = scope.Fitness;
       var lscontext = Context.CreateSingleSolutionContext(scope);
@@ -486 +490 @@
       var after = scope.Fitness;
       Context.HillclimbingStat.Add(Tuple.Create(before, after));
+      Context.IncrementEvaluatedSolutions(lscontext.EvaluatedSolutions);
       return lscontext.Iterations;
     }
 
     protected virtual void PerformTabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int steps, CancellationToken token, ISolutionSubspace<TSolution> subspace = null) {
-      if (double.IsNaN(scope.Fitness)) Evaluate(scope, token);
+      if (double.IsNaN(scope.Fitness)) {
+        Evaluate(scope, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
       var before = scope.Fitness;
       var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
@@ -500 +508 @@
     protected abstract void TabuWalk(ISingleObjectiveSolutionScope<TSolution> scope, int steps, 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)) Evaluate(scope, token);
+      if (double.IsNaN(scope.Fitness)) {
+        Evaluate(scope, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
       var before = scope.Fitness;
       var newScope = (ISingleObjectiveSolutionScope<TSolution>)scope.Clone();
@@ -520 +531 @@
       var p2 = Context.AtPopulation(i2);
 
-      if (double.IsNaN(p1.Fitness)) Evaluate(p1, token);
-      if (double.IsNaN(p2.Fitness)) Evaluate(p2, token);
+      if (double.IsNaN(p1.Fitness)) {
+        Evaluate(p1, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
+      if (double.IsNaN(p2.Fitness)) {
+        Evaluate(p2, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
 
       return BreedAndImprove(p1, p2, token);
@@ -532 +549 @@
         Mutate(offspring, token, subspace); // mutate the solutions, especially to widen the sub-space
       }
-      if (double.IsNaN(offspring.Fitness)) Evaluate(offspring, token);
+      if (double.IsNaN(offspring.Fitness)) {
+        Evaluate(offspring, token);
+        Context.IncrementEvaluatedSolutions(1);
+      }
       Context.BreedingStat.Add(Tuple.Create(p1.Fitness, p2.Fitness, offspring.Fitness));
       if ((IsBetter(offspring, p1) && IsBetter(offspring, p2))
@@ -556 +576 @@
       var p2 = Context.AtPopulation(i2);
 
-      if (double.IsNaN(p1.Fitness)) Evaluate(p1, token);
-      if (double.IsNaN(p2.Fitness)) Evaluate(p2, token);
-
       return RelinkAndImprove(p1, p2, token);
     }
@@ -584 +601 @@
       SolutionModelTrainerParameter.Value.TrainModel(Context);
       var sample = ToScope(Context.Model.Sample());
+      Evaluate(sample, token);
+      Context.IncrementEvaluatedSolutions(1);
       if (Context.Population.Any(p => IsBetter(sample, p) || sample.Fitness == p.Fitness)) return sample;
 
@@ -608 +627 @@
 
     protected double ProbabilityAccept(ISingleObjectiveSolutionScope<TSolution> scope, IList<Tuple<double, double>> data) {
-      if (double.IsNaN(scope.Fitness)) Evaluate(scope, CancellationToken.None);
+      if (double.IsNaN(scope.Fitness)) {
+        Evaluate(scope, CancellationToken.None);
+        Context.IncrementEvaluatedSolutions(1);
+      }
       return ProbabilityAccept(scope.Fitness, data);
     }

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

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

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

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

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

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

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

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

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/SingleObjectiveSolutionScope.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Algorithms.MemPR {
-  [Item("MemPRScope", "Scope for a MemPR individual.")]
+  [Item("Solution Scope", "Scope for an individual/solution of a single-objective single-encoded problem.")]
   [StorableClass]
   public sealed class SingleObjectiveSolutionScope<T> : NamedItem, ISingleObjectiveSolutionScope<T> where T : class, IItem {

branches/MemPRAlgorithm/HeuristicLab.Encodings.PermutationEncoding/3.3/HeuristicLab.Encodings.PermutationEncoding-3.3.csproj

@@ -203 +203 @@
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="ShakingOperators\PermutationShakingOperator.cs" />
+    <Compile Include="SimilarityCalculators\HammingSimilarityCalculator.cs" />
   </ItemGroup>
   <ItemGroup>

branches/MemPRAlgorithm/HeuristicLab.Problems.QuadraticAssignment/3.3/QAPBasicProblem.cs

@@ -20 +20 @@
 #endregion
 
+using System.Linq;
+using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -25 +27 @@
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
+using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -30 +33 @@
 
 namespace HeuristicLab.Problems.QuadraticAssignment {
-  [Item("Basic Quadratic Assignment Problem (BQAP)", "The Quadratic Assignment Problem (QAP) can be described as the problem of assigning N facilities to N fixed locations such that there is exactly one facility in each location and that the sum of the distances multiplied by the connection strength between the facilities becomes minimal.")]
+  [Item("Basic Quadratic Assignment Problem (QAP)", "The Quadratic Assignment Problem (QAP) can be described as the problem of assigning N facilities to N fixed locations such that there is exactly one facility in each location and that the sum of the distances multiplied by the connection strength between the facilities becomes minimal.")]
   [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 141)]
   [StorableClass]
@@ -62 +65 @@
       Parameters.Add(weightsParameter = new ValueParameter<DoubleMatrix>("Weights", "The weights matrix.", new DoubleMatrix(5, 5)));
       Parameters.Add(distancesParameter = new ValueParameter<DoubleMatrix>("Distances", "The distances matrix.", new DoubleMatrix(5, 5)));
+
+      Operators.Add(new HammingSimilarityCalculator());
+      Operators.Add(new QualitySimilarityCalculator());
+      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
+
+      Parameterize();
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
       return new QAPBasicProblem(this, cloner);
+    }
+
+    protected override void OnEncodingChanged() {
+      base.OnEncodingChanged();
+      Parameterize();
+    }
+
+    private void Parameterize() {
+      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
+        similarityCalculator.SolutionVariableName = Encoding.SolutionCreator.PermutationParameter.ActualName;
+        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
+      }
     }
 
@@ -116 +137 @@
       Weights = weights;
       Distances = distances;
+      Encoding.Length = Weights.Rows;
 
       BestKnownQuality = double.NaN;

branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs

@@ -25 +25 @@
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization.Operators;
+using HeuristicLab.PluginInfrastructure;
 
 namespace HeuristicLab.Problems.TravelingSalesman {
@@ -34 +35 @@
   /// </remarks>
   [Item("TSPSimilarityCalculator", "An operator that performs similarity calculation between two traveling salesman solutions. The operator calculates the similarity based on the number of edges the two solutions have in common.")]
-  public sealed class TSPSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
+  [Obsolete("Please use the HammingSimilarityCalculator in the Encodings.PermutationEncoding plugin.")]
+  [NonDiscoverableType]
+  internal sealed class TSPSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
     protected override bool IsCommutative { get { return true; } }
 

branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

@@ -233 +233 @@
       Operators.Add(new TSPPathRelinker());
       Operators.Add(new TSPSimultaneousPathRelinker());
-      Operators.Add(new TSPSimilarityCalculator());
+      Operators.Add(new HammingSimilarityCalculator());
       Operators.Add(new QualitySimilarityCalculator());
-      Operators.Add(new NoSimilarityCalculator());
 
       Operators.Add(new BestTSPSolutionAnalyzer());