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

Timestamp:

06/22/12 11:11:38 (12 years ago)

Author:

jkarder

Message:

#1331:

• synced branch with trunk
• added custom interface (ISimilarityBasedOperator) to mark operators that conduct similarity calculation
• similarity calculators are now parameterized by the algorithm
• deleted SolutionPool2TierUpdateMethod
• deleted KnapsackMultipleGuidesPathRelinker
• moved IImprovementOperator, IPathRelinker and ISimilarityCalculator to HeuristicLab.Optimization
• added parameter descriptions
• fixed plugin references
• fixed count of EvaluatedSolutions
• fixed check for duplicate solutions
• minor code improvements

Location:

branches/ScatterSearch (trunk integration)

Files:

• . (modified) (2 props)
• HeuristicLab.Problems.TravelingSalesman/3.3/Improvers/TSPImprovementOperator.cs (modified) (7 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPMultipleGuidesPathRelinker.cs (modified) (2 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/Plugin.cs.frame (modified) (1 diff)
• HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs (modified) (5 diffs)

branches/ScatterSearch (trunk integration)

@@ -20 +20 @@
 bin
 protoc.exe
+_ReSharper.HeuristicLab 3.3 Tests

@@ -20 +20 @@
 bin
 protoc.exe
+_ReSharper.HeuristicLab 3.3 Tests

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

@@ -27 +27 @@
 using HeuristicLab.Operators;
 using HeuristicLab.Optimization;
-using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -44 +43 @@
     public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
       get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
-    }
-    public ILookupParameter<IEvaluator> EvaluatorParameter {
-      get { return (ILookupParameter<IEvaluator>)Parameters["Evaluator"]; }
     }
     public IValueParameter<IntValue> ImprovementAttemptsParameter {
@@ -67 +63 @@
       set { DistanceMatrixParameter.ActualValue = value; }
     }
-    public IEvaluator Evaluator {
-      get { return EvaluatorParameter.ActualValue; }
-      set { EvaluatorParameter.ActualValue = value; }
-    }
     public IntValue ImprovementAttempts {
       get { return ImprovementAttemptsParameter.Value; }
@@ -78 +70 @@
       get { return RandomParameter.ActualValue; }
       set { RandomParameter.ActualValue = value; }
-    }
-    private IItem Target {
-      get { return TargetParameter.ActualValue; }
     }
     #endregion
@@ -90 +79 @@
       : base() {
       #region Create parameters
-      Parameters.Add(new ScopeParameter("CurrentScope"));
-      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix"));
-      Parameters.Add(new LookupParameter<IEvaluator>("Evaluator"));
-      Parameters.Add(new ValueParameter<IntValue>("ImprovementAttempts", new IntValue(100)));
-      Parameters.Add(new LookupParameter<IRandom>("Random"));
-      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
+      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope that contains the solution to be improved."));
+      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
+      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."));
       #endregion
     }
@@ -105 +93 @@
     public override IOperation Apply() {
       Permutation currSol = CurrentScope.Variables[TargetParameter.ActualName].Value as Permutation;
+      if (currSol == null)
+        throw new ArgumentException("Cannot improve solution because it has the wrong type.");
       if (currSol.PermutationType != PermutationTypes.RelativeUndirected)
         throw new ArgumentException("Cannot improve solution because the permutation type is not supported.");
@@ -118 +108 @@
           Invert(currSol, a, b);
       }
+
+      CurrentScope.Variables.Add(new Variable("LocalEvaluatedSolutions", ImprovementAttempts));
 
       return base.Apply();

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

@@ -47 +47 @@
     public DistanceMatrix DistanceMatrix {
       get { return DistanceMatrixParameter.ActualValue; }
-      set { DistanceMatrixParameter.ActualValue = value; }
     }
     #endregion
@@ -57 +56 @@
       : base() {
       #region Create parameters
-      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix"));
+      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
       #endregion
     }

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

@@ -37 +37 @@
   [PluginDependency("HeuristicLab.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Optimization", "3.3")]
+  [PluginDependency("HeuristicLab.Optimization.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Parameters", "3.3")]
   [PluginDependency("HeuristicLab.Persistence", "3.3")]

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

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization.Operators;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.TravelingSalesman {
@@ -31 +31 @@
   /// </summary>
   [Item("TSPSimilarityCalculator", "An operator that performs similarity calculation between two traveling salesman solutions.")]
-  [StorableClass]
   public sealed class TSPSimilarityCalculator : SimilarityCalculator {
-    [StorableConstructor]
     private TSPSimilarityCalculator(bool deserializing) : base(deserializing) { }
     private TSPSimilarityCalculator(TSPSimilarityCalculator original, Cloner cloner) : base(original, cloner) { }
     public TSPSimilarityCalculator() : base() { }
 
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new TSPSimilarityCalculator(this, cloner);
+    public static double CalculateSimilarity(Permutation left, Permutation right) {
+      if (left == null || right == null)
+        throw new ArgumentException("Cannot calculate similarity because one of the provided solutions or both are null.");
+
+      int[,] edges = new int[right.Length, 2];
+      for (int i = 0; i < right.Length; i++) {
+        edges[right[i], 0] = right[(i + 1) % right.Length];
+        edges[right[i], 1] = right[(i - 1 + right.Length) % right.Length];
+      }
+
+      double similarity = 0.0;
+      for (int i = 0; i < left.Length; i++) {
+        int targetCity = left[(i + 1) % left.Length];
+        if (targetCity == edges[left[i], 0] || targetCity == edges[left[i], 1])
+          similarity++;
+      }
+
+      return similarity / left.Length;
     }
 
     protected override double CalculateSimilarity(IScope left, IScope right) {
-      Permutation v1 = left.Variables[TargetParameter.ActualName].Value as Permutation;
-      Permutation v2 = right.Variables[TargetParameter.ActualName].Value as Permutation;
+      Permutation sol1 = left.Variables[Target].Value as Permutation;
+      Permutation sol2 = right.Variables[Target].Value as Permutation;
 
-      int[,] edges = new int[v2.Length, 2];
-      for (int i = 0; i < v2.Length; i++) {
-        edges[v2[i], 0] = v2[(i + 1) % v2.Length];
-        edges[v2[i], 1] = v2[(i - 1 + v2.Length) % v2.Length];
-      }
-
-      double similarity = 0.0;
-      for (int i = 0; i < v1.Length; i++) {
-        int targetCity = v1[(i + 1) % v1.Length];
-        if (targetCity == edges[v1[i], 0] || targetCity == edges[v1[i], 1])
-          similarity++;
-      }
-
-      return similarity / v1.Length;
+      return CalculateSimilarity(sol1, sol2);
     }
   }

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

@@ -29 +29 @@
 using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Optimization;
-using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
@@ -352 +351 @@
       }
       foreach (ISimilarityCalculator op in Operators.OfType<ISimilarityCalculator>()) {
-        op.TargetParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
-        op.TargetParameter.Hidden = true;
+        op.Target = SolutionCreator.PermutationParameter.ActualName;
       }
     }
@@ -366 +364 @@
       if (data.Coordinates == null && data.Distances == null)
         throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
-      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == TSPDistanceMeasure.Att
-        || data.DistanceMeasure == TSPDistanceMeasure.Manhattan
-        || data.DistanceMeasure == TSPDistanceMeasure.Maximum
-        || data.DistanceMeasure == TSPDistanceMeasure.UpperEuclidean))
+      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
+        || data.DistanceMeasure == DistanceMeasure.Manhattan
+        || data.DistanceMeasure == DistanceMeasure.Maximum
+        || data.DistanceMeasure == DistanceMeasure.UpperEuclidean))
         throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
       if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
@@ -382 +380 @@
 
       TSPEvaluator evaluator;
-      if (data.DistanceMeasure == TSPDistanceMeasure.Att
-        || data.DistanceMeasure == TSPDistanceMeasure.Manhattan
-        || data.DistanceMeasure == TSPDistanceMeasure.Maximum
-        || data.DistanceMeasure == TSPDistanceMeasure.UpperEuclidean) {
+      if (data.DistanceMeasure == DistanceMeasure.Att
+        || data.DistanceMeasure == DistanceMeasure.Manhattan
+        || data.DistanceMeasure == DistanceMeasure.Maximum
+        || data.DistanceMeasure == DistanceMeasure.UpperEuclidean) {
         evaluator = new TSPDistanceMatrixEvaluator();
         UseDistanceMatrix = new BoolValue(true);
         DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
-      } else if (data.DistanceMeasure == TSPDistanceMeasure.Direct && data.Distances != null) {
+      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
         evaluator = new TSPDistanceMatrixEvaluator();
         UseDistanceMatrix = new BoolValue(true);
@@ -397 +395 @@
         UseDistanceMatrix = new BoolValue(data.Dimension <= DistanceMatrixSizeLimit);
         switch (data.DistanceMeasure) {
-          case TSPDistanceMeasure.Euclidean:
+          case DistanceMeasure.Euclidean:
             evaluator = new TSPEuclideanPathEvaluator();
             break;
-          case TSPDistanceMeasure.RoundedEuclidean:
+          case DistanceMeasure.RoundedEuclidean:
             evaluator = new TSPRoundedEuclideanPathEvaluator();
             break;
-          case TSPDistanceMeasure.Geo:
+          case DistanceMeasure.Geo:
             evaluator = new TSPGeoPathEvaluator();
             break;

@@ -20 +20 @@
 bin
 protoc.exe
+_ReSharper.HeuristicLab 3.3 Tests