Changeset 8319 for branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators

Timestamp:

07/24/12 15:04:37 (12 years ago)

Author:

jkarder

Message:

#1331:

• applied some of the changes suggested by ascheibe in comment:32:ticket:1331
• restructured path relinking and improvement operators and similarity calculators
• fixed bug in TSPMultipleGuidesPathRelinker

File:

• branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs (modified) (3 diffs)

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs

@@ -30 +30 @@
   /// An operator that performs similarity calculation between two traveling salesman solutions.
   /// </summary>
+  /// <remarks>
+  /// The operator calculates the similarity based on the number of edges the two solutions have in common.
+  /// </remarks>
   [Item("TSPSimilarityCalculator", "An operator that performs similarity calculation between two traveling salesman solutions.")]
-  public sealed class TSPSimilarityCalculator : SimilarityCalculator {
+  public sealed class TSPSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
     private TSPSimilarityCalculator(bool deserializing) : base(deserializing) { }
     private TSPSimilarityCalculator(TSPSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }
@@ -43 +46 @@
       if (left == null || right == null)
         throw new ArgumentException("Cannot calculate similarity because one of the provided solutions or both are null.");
-      if (left == right) return 1.0;
+      if (left.PermutationType != right.PermutationType)
+        throw new ArgumentException("Cannot calculate similarity because the provided solutions have different types.");
+      if (left.Length != right.Length)
+        throw new ArgumentException("Cannot calculate similarity because the provided solutions have different lengths.");
+      var comparer = new PermutationEqualityComparer();
+      if (object.ReferenceEquals(left, right) || comparer.Equals(left, right)) return 1.0;
 
+      switch (left.PermutationType) {
+        case PermutationTypes.Absolute:
+          return CalculateAbsolute(left, right);
+        case PermutationTypes.RelativeDirected:
+          return CalculateRelativeDirected(left, right);
+        case PermutationTypes.RelativeUndirected:
+          return CalculateRelativeUndirected(left, right);
+        default:
+          throw new InvalidOperationException("unknown permutation type");
+      }
+    }
+
+    private static double CalculateAbsolute(Permutation left, Permutation right) {
+      double similarity = 0.0;
+      for (int i = 0; i < left.Length && left[i] == right[i]; similarity = ++i) ;
+      return similarity / left.Length;
+    }
+
+    private static double CalculateRelativeDirected(Permutation left, Permutation right) {
+      throw new NotImplementedException();
+    }
+
+    private static double CalculateRelativeUndirected(Permutation left, Permutation right) {
       int[,] edges = new int[right.Length, 2];
       for (int i = 0; i < right.Length; i++) {
@@ -61 +92 @@
     }
 
-    public override double CalculateIndividualSimilarity(IScope left, IScope right) {
-      var sol1 = left.Variables[Target].Value as Permutation;
-      var sol2 = right.Variables[Target].Value as Permutation;
+    public override double CalculateSolutionSimilarity(IScope leftSolution, IScope rightSolution) {
+      var sol1 = leftSolution.Variables[SolutionVariableName].Value as Permutation;
+      var sol2 = rightSolution.Variables[SolutionVariableName].Value as Permutation;
 
       return CalculateSimilarity(sol1, sol2);