Changeset 12228 for branches

Timestamp:

03/19/15 17:16:39 (10 years ago)

Author:

apolidur

Message:

#2221: Local improvement operator for VNS

Location:

branches/PTSP

Files:

• HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.cs (modified) (2 diffs)
• HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs (modified) (3 diffs)
• HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj (modified) (3 diffs)
• HeuristicLab.Problems.PTSP/3.3/Improvers (added)
• HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInsertionLocalImprovement.cs (added)
• HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInversionLocalImprovement.cs (added)
• HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPAnalyticalInversionMovePathEvaluator.cs (modified) (4 diffs)
• HeuristicLab.Problems.PTSP/3.3/PTSP.cs (modified) (4 diffs)
• HeuristicLab.Problems.PTSP/3.3/PathPTSPTour.cs (added)
• PTSP.sln (modified) (2 diffs)

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

@@ -66 +66 @@
       for (int i = 0; i < p.Length - 1; i++) {
         for (int j = i + 1; j < p.Length - 1; j++) {
-          double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]].Value * ProbabilityMatrix[p[j]].Value;
+          double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];
           for (int k = i + 1; k < j; k++) {
-            sum1 = sum1 * (1 - ProbabilityMatrix[p[k]].Value);
+            sum1 = sum1 * (1 - ProbabilityMatrix[p[k]]);
           }
           A[i, j - 1] = sum1;
@@ -77 +77 @@
       for (int j = 0; j < p.Length - 1; j++) {
         for (int i = 0; i < j; i++) {
-          double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]].Value * ProbabilityMatrix[p[j]].Value;
+          double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];
           for (int k = j + 1; k < p.Length - 1; k++) {
-            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]].Value);
+            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
           }
           for (int k = 1; k < i; k++) {
-            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]].Value);
+            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
           }
           B[i, j] = sum2;

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

@@ -56 +56 @@
       Operators.Add(new PTSPEstimatedInversionMovePathEvaluator());
       Operators.Add(new PTSPEstimatedInsertionEvaluator());
+      Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
+      Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
       Encoding.ConfigureOperators(Operators.OfType<IOperator>());
     }
@@ -68 +70 @@
         realizations.Add(new ItemList<IntValue>());
         for (int j = 0; j < data.Dimension; j++) {
-          if (ProbabilityMatrix[j].Value > r.NextDouble()) {
+          if (ProbabilityMatrix[j] > r.NextDouble()) {
             realizations.ElementAt(i).Add(new IntValue(1));
           } else {
@@ -76 +78 @@
         
       }
+
       foreach (var op in Operators.OfType<PTSPPathMoveEvaluator>()) {
+        op.RealizationsParameter.Value = realizations;
+      }
+      foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
         op.RealizationsParameter.Value = realizations;
       }

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

@@ -21 +21 @@
     <ErrorReport>prompt</ErrorReport>
     <WarningLevel>4</WarningLevel>
+    <PlatformTarget>AnyCPU</PlatformTarget>
   </PropertyGroup>
   <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
@@ -112 +113 @@
     <Compile Include="DistanceMatrix.cs" />
     <Compile Include="EstimatedPTSP.cs" />
+    <Compile Include="Improvers\PTSPExhaustiveInsertionLocalImprovement.cs" />
+    <Compile Include="Improvers\PTSPExhaustiveInversionLocalImprovement.cs" />
     <Compile Include="Interfaces\IPTSPPathMoveEvaluator.cs" />
     <Compile Include="Interfaces\IPTSPMoveEvaluator.cs" />
@@ -119 +122 @@
     <Compile Include="MoveEvaluators\TwoOpt\PTSPAnalyticalInversionMovePathEvaluator.cs" />
     <Compile Include="MoveEvaluators\TwoOpt\PTSPEstimatedInversionMovePathEvaluator.cs" />
+    <Compile Include="PathPTSPTour.cs" />
     <Compile Include="PTSP.cs" />
     <Compile Include="Plugin.cs" />

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

@@ -35 +35 @@
   public class PTSPAnalyticalInversionMovePathEvaluator : PTSPPathMoveEvaluator, IPermutationInversionMoveOperator {
 
-    private static ItemList<DoubleValue> probabilities;
+    private static DoubleArray probabilities;
     private static DoubleMatrix A;
     private static DoubleMatrix B;
@@ -46 +46 @@
     }
 
-    public IValueParameter<ItemList<DoubleValue>> ProbabilitiesParameter {
-      get { return (IValueParameter<ItemList<DoubleValue>>)Parameters["Probabilities"]; }
+    public IValueParameter<DoubleArray> ProbabilitiesParameter {
+      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
     }
 
@@ -103 +103 @@
         case 1:
           if (j == i + 1) {
-            return (1/(1-probabilities[i+1].Value))*A[i,2]+(1 - probabilities[i].Value)*(A[i+1,1]-A[i+1,probabilities.Capacity-1]);
+            return (1/(1-probabilities[i+1]))*A[i,2]+(1 - probabilities[i])*(A[i+1,1]-A[i+1,probabilities.Length-1]);
           } else if (i == j) {
             return A[i,1];
           } else {
             // Equation 25
-            return ((1 - probabilities[i].Value) / (1 - probabilities[j].Value)) * RecursiveExpectedCost(1, i + 1, j - 1) + (1 - probabilities[i].Value) * (1);
+            return ((1 - probabilities[i]) / (1 - probabilities[j])) * RecursiveExpectedCost(1, i + 1, j - 1) + (1 - probabilities[i]) * (1);
           }
           
         case 2:
           if (j == i + 1) {
-            return (1 - probabilities[i + 1].Value) * (B[i, 1] - B[i, probabilities.Capacity - 1]) + (1 / (1 - probabilities[i].Value)) * (B[i + 1, 2]);
+            return (1 - probabilities[i + 1]) * (B[i, 1] - B[i, probabilities.Length - 1]) + (1 / (1 - probabilities[i])) * (B[i + 1, 2]);
           } else if (i == j) {
             return B[i,1];
@@ -123 +123 @@
         case 3:
           if (j == i + 1) {
-            return A[i, 2] + A[i + 1, 1] - A[i + 1, probabilities.Capacity - 1] + B[i, 1] - B[i, probabilities.Capacity - 1] + B[i + 1, 2];
+            return A[i, 2] + A[i + 1, 1] - A[i + 1, probabilities.Length - 1] + B[i, 1] - B[i, probabilities.Length - 1] + B[i + 1, 2];
           } else if (i == j) {
             return A[i,1]+B[i,1];

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

@@ -40 +40 @@
   public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
   IProblemInstanceConsumer<TSPData> {
+    private static readonly int DistanceMatrixSizeLimit = 1000;
+
     #region Parameter Properties
     public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
@@ -53 +55 @@
       get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
     }
-    public OptionalValueParameter<ItemList<DoubleValue>> ProbabilityMatrixParameter {
-      get { return (OptionalValueParameter<ItemList<DoubleValue>>)Parameters["ProbabilityMatrix"]; }
+    public ValueParameter<DoubleArray> ProbabilityMatrixParameter {
+      get { return (ValueParameter<DoubleArray>)Parameters["ProbabilityMatrix"]; }
     }
     public ValueParameter<IntValue> SampleSizeParameter {
@@ -79 +81 @@
       set { BestKnownSolutionParameter.Value = value; }
     }
-    public ItemList<DoubleValue> ProbabilityMatrix {
+    public DoubleArray ProbabilityMatrix {
       get { return ProbabilityMatrixParameter.Value; }
       set { ProbabilityMatrixParameter.Value = value; }
@@ -105 +107 @@
       Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true)));
       Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
-      Parameters.Add(new OptionalValueParameter<ItemList<DoubleValue>>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
+      Parameters.Add(new ValueParameter<DoubleArray>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
+
+      Coordinates = new DoubleMatrix(new double[,] {
+        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
+        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
+        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
+        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
+      });
+
+      ProbabilityMatrix = new DoubleArray(new double[] {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1});
       
     }
 
     public virtual 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 == DistanceMeasure.Att
+        || data.DistanceMeasure == DistanceMeasure.Manhattan
+        || data.DistanceMeasure == DistanceMeasure.Maximum))
+        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;
+
+      bool clearCoordinates = false, clearDistanceMatrix = false;
+      if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
+        Coordinates = new DoubleMatrix(data.Coordinates);
+      else clearCoordinates = true;
+
+      // reset them after assigning the evaluator
+      if (clearCoordinates) Coordinates = null;
+      if (clearDistanceMatrix) DistanceMatrix = null;
+
       DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
       // Get Probabilities of cities using random with seed from hash function on the Name of the instance
-      ProbabilityMatrix = new ItemList<DoubleValue>(data.Dimension);
+      ProbabilityMatrix = new DoubleArray(data.Dimension);
       Random r = new Random(data.Name.GetHashCode());
       for (int i = 0; i < data.Dimension; i++) {
-        ProbabilityMatrix.Add(new DoubleValue(r.NextDouble()));
+        ProbabilityMatrix[i] = r.NextDouble();
       }
       Encoding.Length = data.Dimension;
+
+      OnReset();
     }
   }

branches/PTSP/PTSP.sln

@@ -5 +5 @@
 MinimumVisualStudioVersion = 10.0.40219.1
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP-3.3", "HeuristicLab.Problems.PTSP\3.3\HeuristicLab.Problems.PTSP-3.3.csproj", "{97198965-AFEA-496B-B3B1-316905C43FD6}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP.Views-3.3", "HeuristicLab.Problems.PTSP.Views\3.3\HeuristicLab.Problems.PTSP.Views-3.3.csproj", "{90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}"
 EndProject
 Global
@@ -16 +18 @@
     {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|Any CPU.ActiveCfg = Release|Any CPU
     {97198965-AFEA-496B-B3B1-316905C43FD6}.Release|Any CPU.Build.0 = Release|Any CPU
+    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Debug|Any CPU.Build.0 = Debug|Any CPU
+    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.ActiveCfg = Release|Any CPU
+    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.Build.0 = Release|Any CPU
   EndGlobalSection
   GlobalSection(SolutionProperties) = preSolution