Changeset 12380 for branches/PTSP

Timestamp:

05/04/15 18:30:26 (10 years ago)

Author:

apolidur

Message:

#2221: Small refactoring and code cleaning

Location:

branches/PTSP

Files:

• HeuristicLab.Problems.PTSP.Tests-3.3/PTSPMoveEvaluatorTest.cs (modified) (1 diff)
• HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs (modified) (3 diffs)
• HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInversionLocalImprovement.cs (modified) (1 diff)
• HeuristicLab.Problems.PTSP/3.3/Interfaces/IPTSPMoveEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.PTSP/3.3/Interfaces/IPTSPPathMoveEvaluator.cs (deleted)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/OneShift/PTSPEstimatedInsertionEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/PTSPMoveEvaluator.cs (modified) (3 diffs)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/PTSPPathMoveEvaluator.cs (deleted)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPAnalyticalInversionMovePathEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPEstimatedInversionEvaluator.cs (added)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPEstimatedInversionMovePathEvaluator.cs (deleted)

branches/PTSP/HeuristicLab.Problems.PTSP.Tests-3.3/PTSPMoveEvaluatorTest.cs

@@ -79 +79 @@
         var move = StochasticInversionSingleMoveGenerator.Apply(tour, random);
 
-        double moveMatrix = PTSPEstimatedInversionMovePathEvaluator.EvaluateByDistanceMatrix(tour, move, distances,realizations);
+        double moveMatrix = PTSPEstimatedInversionEvaluator.EvaluateByDistanceMatrix(tour, move, distances,realizations);
 
         string failureString = string.Format(@"Inversion move is calculated with quality {0}, but actual difference is {4}.

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs

@@ -104 +104 @@
       Parameters.Add(new ValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation"));
       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
-      Operators.Add(new PTSPEstimatedInversionMovePathEvaluator());
+      Operators.Add(new PTSPEstimatedInversionEvaluator());
       Operators.Add(new PTSPEstimatedInsertionEvaluator());
       Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
@@ -121 +121 @@
     }
 
-    private int Ttest(int ProblemSize) {
-      MersenneTwister random = new MersenneTwister();
-      Permutation p1 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
-      Permutation p2 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
-      ItemList<ItemList<IntValue>> realizations = new ItemList<ItemList<IntValue>>();
-      int index = -1;
-      while (true) {
-        for (int i = index+1; i < index+5; i++) {
-          realizations.Add(new ItemList<IntValue>());
-          for (int j = 0; j < ProblemSize; j++) {
-            if (ProbabilityMatrix[j] > random.NextDouble()) {
-              realizations.ElementAt(i).Add(new IntValue(1));
-            } else {
-              realizations.ElementAt(i).Add(new IntValue(0));
-            }
-          }
-        }
-        index += 4;
-        double[] eval1 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p1);
-        double[] eval2 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p2);
-        double sx1x2 = Math.Sqrt((eval1[1]+eval2[1])/2);
-        int degrees = 2 * realizations.Count - 2;
-        double t = (eval1[0]-eval2[0])/(sx1x2*Math.Sqrt(2.0/(double)realizations.Count));
-      }
-    }
-
     public override void Load(PTSPData data) {
       base.Load(data);
-      // For now uses sample size of 20 but should use Student's t-test
-      //Ttest(data.Dimension);
       RealizationsSize = new IntValue(100);
       MersenneTwister r = new MersenneTwister();
+
+      // TODO : This should be made in another function and attached to a listener
       int countOnes = 0;
       Realizations = new ItemList<ItemList<IntValue>>(RealizationsSize.Value);
@@ -173 +147 @@
       }
 
-      foreach (var op in Operators.OfType<PTSPPathMoveEvaluator>()) {
+      foreach (var op in Operators.OfType<PTSPMoveEvaluator>()) {
         op.RealizationsParameter.Value = Realizations;
       }

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj

@@ -120 +120 @@
     <Compile Include="Improvers\PTSPExhaustiveInversionLocalImprovement.cs" />
     <Compile Include="Interfaces\I25MoveOperator.cs" />
-    <Compile Include="Interfaces\IPTSPPathMoveEvaluator.cs" />
     <Compile Include="Interfaces\IPTSPMoveEvaluator.cs" />
     <Compile Include="MoveEvaluators\OneShift\PTSPEstimatedInsertionEvaluator.cs" />
     <Compile Include="MoveEvaluators\PTSPMoveEvaluator.cs" />
-    <Compile Include="MoveEvaluators\PTSPPathMoveEvaluator.cs" />
     <Compile Include="MoveEvaluators\TwoOpt\PTSPAnalyticalInversionMovePathEvaluator.cs" />
-    <Compile Include="MoveEvaluators\TwoOpt\PTSPEstimatedInversionMovePathEvaluator.cs" />
+    <Compile Include="MoveEvaluators\TwoOpt\PTSPEstimatedInversionEvaluator.cs" />
     <Compile Include="MoveEvaluators\TwoPointFiveOpt\PTSP25MoveEvaluator.cs" />
     <Compile Include="MoveGenerators\Exhaustive25MoveGenerator.cs" />

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInversionLocalImprovement.cs

@@ -107 +107 @@
         double evaluations = 0.0;
         foreach (var move in ExhaustiveInversionMoveGenerator.Generate(assignment)) {
-          double moveQuality = PTSPEstimatedInversionMovePathEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
+          double moveQuality = PTSPEstimatedInversionEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
           evaluations += 2 * (move.Index2 - move.Index1 + 1) / (double)assignment.Length;
           if (maximization && moveQuality > bestQuality

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Interfaces/IPTSPMoveEvaluator.cs

@@ -20 +20 @@
 #endregion
 
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Optimization;
 using System;
-using HeuristicLab.Optimization;
 
 namespace HeuristicLab.Problems.PTSP {
-  public interface IPTSPMoveEvaluator : ISingleObjectiveMoveEvaluator, IMoveOperator {
+  public interface IPTSPMoveEvaluator : ISingleObjectiveMoveEvaluator, IMoveOperator, IPermutationMoveOperator {
     Type EvaluatorType { get; }
+    ILookupParameter<DoubleMatrix> CoordinatesParameter { get; }
+    ILookupParameter<DistanceMatrix> DistanceMatrixParameter { get; }
+    ILookupParameter<BoolValue> UseDistanceMatrixParameter { get; }
+
   }
 }

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/OneShift/PTSPEstimatedInsertionEvaluator.cs

@@ -31 +31 @@
   [Item("PTSPEstimatedInsertionEvaluator", "Evaluates an insertion move (1-shift)")]
   [StorableClass]
-  public class PTSPEstimatedInsertionEvaluator : PTSPPathMoveEvaluator, IPermutationTranslocationMoveOperator {
+  public class PTSPEstimatedInsertionEvaluator : PTSPMoveEvaluator, IPermutationTranslocationMoveOperator {
 
     public override Type EvaluatorType {

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/PTSPMoveEvaluator.cs

@@ -1 @@
-using System;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Operators;
 using HeuristicLab.Optimization;
-using HeuristicLab.Parameters;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.PTSP {
@@ -21 +43 @@
     }
 
+    public ILookupParameter<Permutation> PermutationParameter {
+      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
+    }
+    public ILookupParameter<DoubleMatrix> CoordinatesParameter {
+      get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
+    }
+    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
+      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
+    }
+    public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
+    }
+    public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
+      get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
+    }
+
     public ILookupParameter<DoubleValue> QualityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
@@ -33 +71 @@
     protected PTSPMoveEvaluator()
       : base() {
+      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
+      Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The city's coordinates."));
+      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
+      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated (if it does not exist already) and used for evaluation, otherwise false."));
+      Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
       Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a TSP solution."));
       Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The evaluated quality of a move on a TSP solution."));
     }
+
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code (remove with 3.4)
+      LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>;
+      if (oldDistanceMatrixParameter != null) {
+        Parameters.Remove(oldDistanceMatrixParameter);
+        Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
+        DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName;
+      }
+      #endregion
+    }
+
+    public override IOperation Apply() {
+      Permutation permutation = PermutationParameter.ActualValue;
+      DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
+      double relativeQualityDifference = 0;
+      if (UseDistanceMatrixParameter.ActualValue.Value) {
+        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 {
+        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);
+      else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference;
+      return base.Apply();
+    }
+
+    protected abstract double CalculateDistance(double x1, double y1, double x2, double y2);
+    protected abstract double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix);
+    protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates);
+
+    private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) {
+      DistanceMatrix distanceMatrix = new DistanceMatrix(c.Rows, c.Rows);
+      for (int i = 0; i < distanceMatrix.Rows; i++) {
+        for (int j = 0; j < distanceMatrix.Columns; j++)
+          distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
+      }
+      return (DistanceMatrix)distanceMatrix.AsReadOnly();
+    }
   }
 }

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPAnalyticalInversionMovePathEvaluator.cs

@@ -33 +33 @@
   [Item("PTSPAnalyticalInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) of the PTSP in with the closed form expression")]
   [StorableClass]
-  public class PTSPAnalyticalInversionMovePathEvaluator : PTSPPathMoveEvaluator, IPermutationInversionMoveOperator {
+  public class PTSPAnalyticalInversionMovePathEvaluator : PTSPMoveEvaluator, IPermutationInversionMoveOperator {
 
     private static DoubleArray probabilities;