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

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

Location:

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

Files:

• Improvers/TSPImprovementOperator.cs (modified) (4 diffs)
• PathRelinkers/TSPMultipleGuidesPathRelinker.cs (modified) (2 diffs)
• PathRelinkers/TSPPathRelinker.cs (modified) (1 diff)
• PathRelinkers/TSPSimultaneousPathRelinker.cs (modified) (1 diff)
• SimilarityCalculators/TSPSimilarityCalculator.cs (modified) (3 diffs)
• TravelingSalesmanProblem.cs (modified) (1 diff)

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/Improvers/TSPImprovementOperator.cs

@@ -34 +34 @@
   /// An operator that improves traveling salesman solutions.
   /// </summary>
+  /// <remarks>
+  /// The operator tries to improve the traveling salesman solution by swapping two randomly chosen edges for a certain number of times.
+  /// </remarks>
   [Item("TSPImprovementOperator", "An operator that improves traveling salesman solutions.")]
   [StorableClass]
-  public sealed class TSPImprovementOperator : SingleSuccessorOperator, IImprovementOperator {
+  public sealed class TSPImprovementOperator : SingleSuccessorOperator, ISingleObjectiveImprovementOperator {
     #region Parameter properties
     public ScopeParameter CurrentScopeParameter {
@@ -50 +53 @@
       get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     }
-    public IValueLookupParameter<IItem> TargetParameter {
-      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
+    public IValueLookupParameter<IItem> SolutionParameter {
+      get { return (IValueLookupParameter<IItem>)Parameters["Solution"]; }
     }
     #endregion
@@ -83 +86 @@
       Parameters.Add(new ValueParameter<IntValue>("ImprovementAttempts", "The number of improvement attempts the operator should perform.", new IntValue(100)));
       Parameters.Add(new LookupParameter<IRandom>("Random", "A pseudo random number generator."));
-      Parameters.Add(new ValueLookupParameter<IItem>("Target", "This parameter is used for name translation only."));
+      Parameters.Add(new ValueLookupParameter<IItem>("Solution", "The solution to be improved. This parameter is used for name translation only."));
       #endregion
     }
@@ -92 +95 @@
 
     public override IOperation Apply() {
-      Permutation currSol = CurrentScope.Variables[TargetParameter.ActualName].Value as Permutation;
+      Permutation currSol = CurrentScope.Variables[SolutionParameter.ActualName].Value as Permutation;
       if (currSol == null)
         throw new ArgumentException("Cannot improve solution because it has the wrong type.");

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPMultipleGuidesPathRelinker.cs

@@ -35 +35 @@
   /// An operator that relinks paths between traveling salesman solutions using a multiple guiding strategy.
   /// </summary>
+  /// <remarks>
+  /// The operator incrementally changes the initiating solution towards the guiding solution by correcting edges as needed. For each city it choses the best edge from all guiding solutions.
+  /// </remarks>
   [Item("TSPMultipleGuidesPathRelinker", "An operator that relinks paths between traveling salesman solutions using a multiple guiding strategy.")]
   [StorableClass]
-  public sealed class TSPMultipleGuidesPathRelinker : PathRelinker {
+  public sealed class TSPMultipleGuidesPathRelinker : SingleObjectivePathRelinker {
     #region Parameter properties
     public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
@@ -93 +96 @@
           }
         });
-        Invert(v1, i, bestCityIndex);
+        Invert(v1, currCityIndex + 1, bestCityIndex);
         solutions.Add(v1.Clone() as Permutation);
       }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPPathRelinker.cs

@@ -34 +34 @@
   /// An operator that relinks paths between traveling salesman solutions.
   /// </summary>
+  /// <remarks>
+  /// The operator incrementally assimilates the initiating solution into the guiding solution by correcting edges as needed.
+  /// </remarks>
   [Item("TSPPathRelinker", "An operator that relinks paths between traveling salesman solutions.")]
   [StorableClass]
-  public sealed class TSPPathRelinker : PathRelinker {
+  public sealed class TSPPathRelinker : SingleObjectivePathRelinker {
     [StorableConstructor]
     private TSPPathRelinker(bool deserializing) : base(deserializing) { }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPSimultaneousPathRelinker.cs

@@ -34 +34 @@
   /// An operator that relinks paths between traveling salesman solutions starting from both ends.
   /// </summary>
+  /// <remarks>
+  /// The operator incrementally assimilates the initiating solution into the guiding solution and vice versa by correcting edges as needed.
+  /// </remarks>
   [Item("TSPSimultaneousPathRelinker", "An operator that relinks paths between traveling salesman solutions starting from both ends.")]
   [StorableClass]
-  public sealed class TSPSimultaneousPathRelinker : PathRelinker {
+  public sealed class TSPSimultaneousPathRelinker : SingleObjectivePathRelinker {
     [StorableConstructor]
     private TSPSimultaneousPathRelinker(bool deserializing) : base(deserializing) { }

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

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

@@ -342 +342 @@
         op.PermutationParameter.Hidden = true;
       }
-      foreach (IImprovementOperator op in Operators.OfType<IImprovementOperator>()) {
-        op.TargetParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-        op.TargetParameter.Hidden = true;
-      }
-      foreach (IPathRelinker op in Operators.OfType<IPathRelinker>()) {
+      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
+        op.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
+        op.SolutionParameter.Hidden = true;
+      }
+      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
         op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
         op.ParentsParameter.Hidden = true;
       }
-      foreach (ISimilarityCalculator op in Operators.OfType<ISimilarityCalculator>()) {
-        op.Target = SolutionCreator.PermutationParameter.ActualName;
+      foreach (TSPSimilarityCalculator op in Operators.OfType<TSPSimilarityCalculator>()) {
+        op.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
       }
     }