Changeset 7669 for branches/HeuristicLab.Hive.Azure/HeuristicLab.Problems.TravelingSalesman

Timestamp:

03/28/12 15:47:26 (13 years ago)

Author:

spimming

Message:

#1680: merged changes from trunk into branch

Location:

branches/HeuristicLab.Hive.Azure

Files:

• . (modified) (2 props)
• HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPAlleleFrequencyAnalyzer.cs (modified) (1 diff)
• HeuristicLab.Problems.TravelingSalesman/3.3/Evaluators/TSPCoordinatesPathEvaluator.cs (modified) (4 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/Evaluators/TSPDistanceMatrixEvaluator.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/Evaluators/TSPDistanceMatrixEvaluator.cs)
• HeuristicLab.Problems.TravelingSalesman/3.3/HeuristicLab.Problems.TravelingSalesman-3.3.csproj (modified) (5 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/Interfaces/ITSPDistanceMatrixEvaluator.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/Interfaces/ITSPDistanceMatrixEvaluator.cs)
• HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TSPPathMoveEvaluator.cs (modified) (2 diffs)
• HeuristicLab.Problems.TravelingSalesman/3.3/Plugin.cs.frame (modified) (1 diff)
• HeuristicLab.Problems.TravelingSalesman/3.3/TSPLIB Sample Problems (deleted)
• HeuristicLab.Problems.TravelingSalesman/3.3/TSPLIBParser.cs (deleted)
• HeuristicLab.Problems.TravelingSalesman/3.3/TSPLIBTourParser.cs (deleted)
• HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs (modified) (12 diffs)

branches/HeuristicLab.Hive.Azure

@@ -3 +3 @@
 *.resharper
 *.suo
+*.user
 *.vsp
 Doxygen
+FxCopResults.txt
 Google.ProtocolBuffers-0.9.1.dll
 HeuristicLab 3.3.5.1.ReSharper.user

@@ -3 +3 @@
 *.resharper
 *.suo
+*.user
 *.vsp
 Doxygen
+FxCopResults.txt
 Google.ProtocolBuffers-0.9.1.dll
 HeuristicLab 3.3.5.1.ReSharper.user

branches/HeuristicLab.Hive.Azure/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPAlleleFrequencyAnalyzer.cs

@@ -60 +60 @@
       DoubleMatrix coords = CoordinatesParameter.ActualValue;
       DistanceMatrix dm = DistanceMatrixParameter.ActualValue;
+      if (dm == null && coords == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
       int source, target, h;
       double impact;

branches/HeuristicLab.Hive.Azure/HeuristicLab.Problems.TravelingSalesman/3.3/Evaluators/TSPCoordinatesPathEvaluator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -73 +74 @@
     }
 
+    public static double Apply(TSPCoordinatesPathEvaluator evaluator, DoubleMatrix coordinates, Permutation tour) {
+      DoubleMatrix c = coordinates;
+      Permutation p = tour;
+      double length = 0;
+      for (int i = 0; i < p.Length - 1; i++)
+        length += evaluator.CalculateDistance(c[p[i], 0], c[p[i], 1], c[p[i + 1], 0], c[p[i + 1], 1]);
+      length += evaluator.CalculateDistance(c[p[p.Length - 1], 0], c[p[p.Length - 1], 1], c[p[0], 0], c[p[0], 1]);
+      return length;
+    }
+
     public sealed override IOperation Apply() {
       if (UseDistanceMatrixParameter.ActualValue.Value) {
@@ -83 +94 @@
             if (dm == null) {  // check again to avoid race condition
               DoubleMatrix c = CoordinatesParameter.ActualValue;
+              if (c == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
               dm = new DistanceMatrix(c.Rows, c.Rows);
               for (int i = 0; i < dm.Rows; i++) {
@@ -101 +113 @@
         Permutation p = PermutationParameter.ActualValue;
         DoubleMatrix c = CoordinatesParameter.ActualValue;
-
+        if (c == null) throw new InvalidOperationException("No coordinates were given.");
         double length = 0;
         for (int i = 0; i < p.Length - 1; i++)

branches/HeuristicLab.Hive.Azure/HeuristicLab.Problems.TravelingSalesman/3.3/HeuristicLab.Problems.TravelingSalesman-3.3.csproj

@@ -115 +115 @@
     <Compile Include="Analyzers\TSPAlleleFrequencyAnalyzer.cs" />
     <Compile Include="DistanceMatrix.cs" />
+    <Compile Include="Evaluators\TSPDistanceMatrixEvaluator.cs" />
     <Compile Include="Evaluators\TSPEuclideanPathEvaluator.cs" />
     <Compile Include="Evaluators\TSPGeoPathEvaluator.cs" />
+    <Compile Include="Interfaces\ITSPDistanceMatrixEvaluator.cs" />
     <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveEuclideanPathEvaluator.cs" />
     <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveGeoPathEvaluator.cs" />
@@ -127 +129 @@
     <Compile Include="Plugin.cs" />
     <Compile Include="TravelingSalesmanProblem.cs" />
-    <Compile Include="TSPLIBTourParser.cs" />
     <Compile Include="PathTSPTour.cs" />
     <Compile Include="Evaluators\TSPCoordinatesPathEvaluator.cs" />
@@ -139 +140 @@
     <Compile Include="MoveEvaluators\TSPPathMoveEvaluator.cs" />
     <Compile Include="MoveEvaluators\TSPMoveEvaluator.cs" />
-    <Compile Include="TSPLIBParser.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
   </ItemGroup>
@@ -203 +203 @@
       <Private>False</Private>
     </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj">
+      <Project>{3540E29E-4793-49E7-8EE2-FEA7F61C3994}</Project>
+      <Name>HeuristicLab.Problems.Instances-3.3</Name>
+      <Private>False</Private>
+    </ProjectReference>
   </ItemGroup>
   <ItemGroup>
@@ -208 +213 @@
     <None Include="Plugin.cs.frame" />
     <None Include="Properties\AssemblyInfo.cs.frame" />
-    <None Include="TSPLIB Sample Problems\ch130.opt.tour" />
-    <None Include="TSPLIB Sample Problems\ch130.tsp" />
-    <None Include="TSPLIB Sample Problems\fl1400.tsp" />
-    <None Include="TSPLIB Sample Problems\gr666.opt.tour" />
-    <None Include="TSPLIB Sample Problems\gr666.tsp" />
   </ItemGroup>
   <ItemGroup>

branches/HeuristicLab.Hive.Azure/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TSPPathMoveEvaluator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -78 +79 @@
         DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
         if (distanceMatrix == null) {
+          if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
           distanceMatrix = CalculateDistanceMatrix(coordinates);
           DistanceMatrixParameter.ActualValue = distanceMatrix;
         }
         relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
-      } else relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates);
+      } else {
+        if (coordinates == null) throw new InvalidOperationException("No coordinates were given.");
+        relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates);
+      }
       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
       if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference);

branches/HeuristicLab.Hive.Azure/HeuristicLab.Problems.TravelingSalesman/3.3/Plugin.cs.frame

@@ -39 +39 @@
   [PluginDependency("HeuristicLab.Parameters", "3.3")]
   [PluginDependency("HeuristicLab.Persistence", "3.3")]
+  [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
   public class HeuristicLabProblemsTravelingSalesmanPlugin : PluginBase {
   }

branches/HeuristicLab.Hive.Azure/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

@@ -32 +32 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.PluginInfrastructure;
+using HeuristicLab.Problems.Instances;
 
 namespace HeuristicLab.Problems.TravelingSalesman {
@@ -37 +38 @@
   [Creatable("Problems")]
   [StorableClass]
-  public sealed class TravelingSalesmanProblem : SingleObjectiveHeuristicOptimizationProblem<ITSPEvaluator, IPermutationCreator>, IStorableContent {
+  public sealed class TravelingSalesmanProblem : SingleObjectiveHeuristicOptimizationProblem<ITSPEvaluator, IPermutationCreator>, IStorableContent,
+    IProblemInstanceConsumer<TSPData> {
+    private static readonly int DistanceMatrixSizeLimit = 1000;
     public string Filename { get; set; }
 
     #region Parameter Properties
-    public ValueParameter<DoubleMatrix> CoordinatesParameter {
-      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
+    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
+      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
     }
     public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
@@ -100 +103 @@
     private TravelingSalesmanProblem(TravelingSalesmanProblem original, Cloner cloner)
       : base(original, cloner) {
-      AttachEventHandlers();
+      RegisterEventHandlers();
     }
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -107 +110 @@
     public TravelingSalesmanProblem()
       : base(new TSPRoundedEuclideanPathEvaluator(), new RandomPermutationCreator()) {
-
-      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
+      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
       Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
       Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
@@ -130 +132 @@
 
       InitializeOperators();
-      AttachEventHandlers();
+      RegisterEventHandlers();
     }
 
@@ -146 +148 @@
       Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
       ParameterizeEvaluator();
+      ParameterizeSolutionCreator();
       UpdateMoveEvaluators();
       ParameterizeAnalyzers();
@@ -151 +154 @@
     }
     private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
-      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
-      Coordinates.Reset += new EventHandler(Coordinates_Reset);
+      if (Coordinates != null) {
+        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
+        Coordinates.Reset += new EventHandler(Coordinates_Reset);
+      }
       ParameterizeSolutionCreator();
       ClearDistanceMatrix();
@@ -195 +200 @@
       }
 
+      ValueParameter<DoubleMatrix> oldCoordinates = (Parameters["Coordinates"] as ValueParameter<DoubleMatrix>);
+      if (oldCoordinates != null) {
+        Parameters.Remove(oldCoordinates);
+        Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", oldCoordinates.Value, oldCoordinates.GetsCollected));
+      }
+
       if (Operators.Count == 0) InitializeOperators();
       #endregion
-      AttachEventHandlers();
-    }
-
-    private void AttachEventHandlers() {
+      RegisterEventHandlers();
+    }
+
+    private void RegisterEventHandlers() {
       CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
-      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
-      Coordinates.Reset += new EventHandler(Coordinates_Reset);
+      if (Coordinates != null) {
+        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
+        Coordinates.Reset += new EventHandler(Coordinates_Reset);
+      }
       SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
       Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
@@ -213 +226 @@
       Operators.Add(new TSPPopulationDiversityAnalyzer());
       ParameterizeAnalyzers();
-      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>().Cast<IOperator>());
+      var operators = new HashSet<IPermutationOperator>(new IPermutationOperator[] {
+        new OrderCrossover2(),
+        new InversionManipulator(),
+        new StochasticInversionMultiMoveGenerator()
+      }, new TypeEqualityComparer<IPermutationOperator>());
+      foreach (var op in ApplicationManager.Manager.GetInstances<IPermutationOperator>())
+        operators.Add(op);
+      Operators.AddRange(operators);
       ParameterizeOperators();
       UpdateMoveEvaluators();
@@ -227 +247 @@
     }
     private void ParameterizeSolutionCreator() {
-      SolutionCreator.LengthParameter.Value = new IntValue(Coordinates.Rows);
-      SolutionCreator.LengthParameter.Hidden = true;
+      if (Evaluator is ITSPDistanceMatrixEvaluator && DistanceMatrix != null)
+        SolutionCreator.LengthParameter.Value = new IntValue(DistanceMatrix.Rows);
+      else if (Evaluator is ITSPCoordinatesPathEvaluator && Coordinates != null)
+        SolutionCreator.LengthParameter.Value = new IntValue(Coordinates.Rows);
+      else SolutionCreator.LengthParameter.Value = null;
+      SolutionCreator.LengthParameter.Hidden = SolutionCreator.LengthParameter.Value != null;
       SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.RelativeUndirected);
       SolutionCreator.PermutationTypeParameter.Hidden = true;
@@ -246 +270 @@
         evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
         evaluator.UseDistanceMatrixParameter.Hidden = true;
+      }
+      if (Evaluator is ITSPDistanceMatrixEvaluator) {
+        var evaluator = (ITSPDistanceMatrixEvaluator)Evaluator;
+        evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
+        evaluator.DistanceMatrixParameter.Hidden = true;
       }
     }
@@ -310 +339 @@
 
     private void ClearDistanceMatrix() {
-      DistanceMatrixParameter.Value = null;
+      if (!(Evaluator is ITSPDistanceMatrixEvaluator))
+        DistanceMatrixParameter.Value = null;
     }
     #endregion
 
-    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName) {
-      TSPLIBParser tspParser = new TSPLIBParser(tspFileName);
-      tspParser.Parse();
-      Name = tspParser.Name + " TSP (imported from TSPLIB)";
-      if (!string.IsNullOrEmpty(tspParser.Comment)) Description = tspParser.Comment;
-      Coordinates = new DoubleMatrix(tspParser.Vertices);
-      if (tspParser.WeightType == TSPLIBParser.TSPLIBEdgeWeightType.EUC_2D) {
-        TSPRoundedEuclideanPathEvaluator evaluator = new TSPRoundedEuclideanPathEvaluator();
-        evaluator.QualityParameter.ActualName = "TSPTourLength";
-        Evaluator = evaluator;
-      } else if (tspParser.WeightType == TSPLIBParser.TSPLIBEdgeWeightType.GEO) {
-        TSPGeoPathEvaluator evaluator = new TSPGeoPathEvaluator();
-        evaluator.QualityParameter.ActualName = "TSPTourLength";
-        Evaluator = evaluator;
-      }
+    public void Load(TSPData data) {
+      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))
+        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)
+        throw new System.IO.InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
+
+      Name = data.Name;
+      Description = data.Description;
+
+      if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
+        Coordinates = new DoubleMatrix(data.Coordinates);
+      else Coordinates = null;
+
+      TSPEvaluator evaluator;
+      if (data.DistanceMeasure == TSPDistanceMeasure.Att
+        || data.DistanceMeasure == TSPDistanceMeasure.Manhattan
+        || data.DistanceMeasure == TSPDistanceMeasure.Maximum
+        || data.DistanceMeasure == TSPDistanceMeasure.UpperEuclidean) {
+        evaluator = new TSPDistanceMatrixEvaluator();
+        UseDistanceMatrix = new BoolValue(true);
+        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
+      } else if (data.DistanceMeasure == TSPDistanceMeasure.Direct && data.Distances != null) {
+        evaluator = new TSPDistanceMatrixEvaluator();
+        UseDistanceMatrix = new BoolValue(true);
+        DistanceMatrix = new DistanceMatrix(data.Distances);
+      } else {
+        DistanceMatrix = null;
+        UseDistanceMatrix = new BoolValue(data.Dimension <= DistanceMatrixSizeLimit);
+        switch (data.DistanceMeasure) {
+          case TSPDistanceMeasure.Euclidean:
+            evaluator = new TSPEuclideanPathEvaluator();
+            break;
+          case TSPDistanceMeasure.RoundedEuclidean:
+            evaluator = new TSPRoundedEuclideanPathEvaluator();
+            break;
+          case TSPDistanceMeasure.Geo:
+            evaluator = new TSPGeoPathEvaluator();
+            break;
+          default:
+            throw new InvalidDataException("An unknown distance measure is given in the instance!");
+        }
+      }
+      evaluator.QualityParameter.ActualName = "TSPTourLength";
+      Evaluator = evaluator;
+
+      BestKnownSolution = null;
       BestKnownQuality = null;
-      BestKnownSolution = null;
-
-      if (!string.IsNullOrEmpty(optimalTourFileName)) {
-        TSPLIBTourParser tourParser = new TSPLIBTourParser(optimalTourFileName);
-        tourParser.Parse();
-        if (tourParser.Tour.Length != Coordinates.Rows) throw new InvalidDataException("Length of optimal tour is not equal to number of cities.");
-        BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, tourParser.Tour);
+
+      if (data.BestKnownTour != null) {
+        try {
+          EvaluateAndLoadTour(data.BestKnownTour);
+        }
+        catch (InvalidOperationException) {
+          if (data.BestKnownQuality.HasValue)
+            BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
+        }
+      } else if (data.BestKnownQuality.HasValue) {
+        BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
       }
       OnReset();
     }
-    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName, double bestKnownQuality) {
-      ImportFromTSPLIB(tspFileName, optimalTourFileName);
-      BestKnownQuality = new DoubleValue(bestKnownQuality);
+
+    public void EvaluateAndLoadTour(int[] tour) {
+      var route = new Permutation(PermutationTypes.RelativeUndirected, tour);
+      BestKnownSolution = route;
+
+      double quality;
+      if (Evaluator is ITSPDistanceMatrixEvaluator) {
+        quality = TSPDistanceMatrixEvaluator.Apply(DistanceMatrix, route);
+      } else if (Evaluator is ITSPCoordinatesPathEvaluator) {
+        quality = TSPCoordinatesPathEvaluator.Apply((TSPCoordinatesPathEvaluator)Evaluator, Coordinates, route);
+      } else {
+        throw new InvalidOperationException("Cannot calculate solution quality, evaluator type is unknown.");
+      }
+      BestKnownQuality = new DoubleValue(quality);
     }
   }

@@ -3 +3 @@
 *.resharper
 *.suo
+*.user
 *.vsp
 Doxygen
+FxCopResults.txt
 Google.ProtocolBuffers-0.9.1.dll
 HeuristicLab 3.3.5.1.ReSharper.user