Changeset 12219

Timestamp:

03/18/15 12:01:21 (10 years ago)

Author:

apolidur

Message:

#2221: First version of 1-shift and 2-p-opt moves

Location:

branches/PTSP/HeuristicLab.Problems.PTSP/3.3

Files:

• AnalyticalPTSP.cs (modified) (3 diffs)
• EstimatedPTSP.cs (modified) (5 diffs)
• HeuristicLab.Problems.PTSP-3.3.csproj (modified) (2 diffs)
• Interfaces/IPTSPPathMoveEvaluator.cs (modified) (1 diff)
• MoveEvaluators/OneShift/PTSPEstimatedInsertionEvaluator.cs (added)
• MoveEvaluators/PTSPPathMoveEvaluator.cs (modified) (2 diffs)
• MoveEvaluators/TwoOpt/PTSPAnalyticalInversionMovePathEvaluator.cs (added)
• MoveEvaluators/TwoOpt/PTSPEstimatedInversionMovePathEvaluator.cs (added)
• MoveEvaluators/TwoOpt/PTSPInversionMovePathEvaluator.cs (deleted)
• PTSP.cs (modified) (4 diffs)

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

@@ -33 +33 @@
     public override double Evaluate(Individual individual, IRandom random) {
       Permutation p = individual.Permutation();
+      // Compute A and B matrices
+      DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1);
+      DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1);
+      //for (int i = 0; i < p.Length; i++) {
+      //  for (int k = 0; k < p.Length - 1; k++) {
+      //    double firstPartial = 0;
+      //    for (int r = k; k < p.Length - 1; r++) {
+      //       double sum0 = DistanceMatrix[p[i],p[i+r]]* ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[i+r]];
+      //       for(int s = i+1; s < i+r; s++) {
+      //         sum0 = sum0 * (1 - ProbabilityMatrix[0, p[s]]);
+      //       }
+      //       firstPartial+=sum0;
+      //    }
+      //    double secondPartial = 0;
+      //    for (int r = k; k < p.Length - 1; r++) {
+      //       double sum1 = DistanceMatrix[p[i-r],p[i]]* ProbabilityMatrix[0, p[i-r]] * ProbabilityMatrix[0, p[i]];
+      //       for (int s = i + 1; s < p.Length-1; s++) {
+      //         sum1 = sum1 * (1 - ProbabilityMatrix[0, p[s]]);
+      //       }
+      //       for (int t = 1; t < i-1; t++) {
+      //         sum1 = sum1 * (1 - ProbabilityMatrix[0, p[t]]);
+      //       }
+      //       secondPartial+=sum1;
+      //    }
+      //    A[i, k] = firstPartial;
+      //    B[i, k] = secondPartial;
+      //  }
+      //}
+      
       // Analytical evaluation
       double firstSum = 0;
       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[0, p[i]] * ProbabilityMatrix[0, p[j]];
+          double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]].Value * ProbabilityMatrix[p[j]].Value;
           for (int k = i + 1; k < j; k++) {
-            sum1 = sum1 * (1 - ProbabilityMatrix[0, p[k]]);
+            sum1 = sum1 * (1 - ProbabilityMatrix[p[k]].Value);
           }
+          A[i, j - 1] = sum1;
           firstSum += sum1;
         }
@@ -47 +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[0, p[i]] * ProbabilityMatrix[0, p[j]];
+          double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]].Value * ProbabilityMatrix[p[j]].Value;
           for (int k = j + 1; k < p.Length - 1; k++) {
-            sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]);
+            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]].Value);
           }
           for (int k = 1; k < i; k++) {
-            sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]);
+            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]].Value);
           }
+          B[i, j] = sum2;
           secondSum += sum2;
         }
+      }
+      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
+        op.AParameter.Value = A;
+        op.BParameter.Value = B;
       }
       return firstSum + secondSum;
@@ -61 +96 @@
 
     public AnalyticalProbabilisticTravelingSalesmanProblem() {
-      Operators.Add(new PTSPInversionMovePathEvaluator());
+      Operators.Add(new PTSPAnalyticalInversionMovePathEvaluator());
     }
 
     public override void Load(TSPData data) {
       base.Load(data);
-      // Compute A and B matrices
+      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
+        op.ProbabilitiesParameter.Value = ProbabilityMatrix;
+      }
     }
 

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

@@ -11 +11 @@
 using HeuristicLab.Data;
 using System;
+using System.Linq;
+using HeuristicLab.Problems.PTSP.MoveEvaluators.OneShift;
 
 namespace HeuristicLab.Problems.PTSP {
@@ -18 +20 @@
   public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
   IProblemInstanceConsumer<TSPData> {
+
+    private ItemList<ItemList<IntValue>> realizations;
 
     [StorableConstructor]
@@ -34 +38 @@
       Random r = new Random();
       double estimatedSum = 0;
-      for (int i = 0; i < SampleSize.Value; i++) {
+      for (int i = 0; i < realizations.Count; i++) {
         int singleRealization = -1;
-        for (int j = 0; j < p.Length - 1; j++) {
-          if (ProbabilityMatrix[0, p[j]] > r.NextDouble()) {
+        for (int j = 0; j < realizations[i].Count; j++) {
+          if (realizations[i][j].Value == 1) {
             if (singleRealization != -1) {
               estimatedSum += DistanceMatrix[singleRealization, p[j]];
@@ -50 +54 @@
     public EstimatedProbabilisticTravelingSalesmanProblem() {
       Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Size of the sample for the estimation-based evaluation"));
-      Operators.Add(new PTSPInversionMovePathEvaluator());
+      Operators.Add(new PTSPEstimatedInversionMovePathEvaluator());
+      Operators.Add(new PTSPEstimatedInsertionEvaluator());
+      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
     }
 
@@ -57 +63 @@
       // For now uses sample size of 20 but should use Student's t-test
       SampleSize = new IntValue(20);
+      realizations = new ItemList<ItemList<IntValue>>(SampleSize.Value);
+      Random r = new Random();
+      for (int i = 0; i < SampleSize.Value; i++) {
+        realizations.Add(new ItemList<IntValue>());
+        for (int j = 0; j < data.Dimension; j++) {
+          if (ProbabilityMatrix[j].Value > r.NextDouble()) {
+            realizations.ElementAt(i).Add(new IntValue(1));
+          } else {
+            realizations.ElementAt(i).Add(new IntValue(0));
+          }
+        }
+        
+      }
+      foreach (var op in Operators.OfType<PTSPPathMoveEvaluator>()) {
+        op.RealizationsParameter.Value = realizations;
+      }
     }
   }

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

@@ -114 +114 @@
     <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\PTSPInversionMovePathEvaluator.cs" />
+    <Compile Include="MoveEvaluators\TwoOpt\PTSPAnalyticalInversionMovePathEvaluator.cs" />
+    <Compile Include="MoveEvaluators\TwoOpt\PTSPEstimatedInversionMovePathEvaluator.cs" />
     <Compile Include="PTSP.cs" />
     <Compile Include="Plugin.cs" />
@@ -124 +126 @@
     <None Include="HeuristicLab.snk" />
   </ItemGroup>
-  <ItemGroup>
-    <Folder Include="MoveEvaluators\OneShift\" />
-  </ItemGroup>
+  <ItemGroup />
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <PropertyGroup>

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

@@ -29 +29 @@
     ILookupParameter<DistanceMatrix> DistanceMatrixParameter { get; }
     ILookupParameter<BoolValue> UseDistanceMatrixParameter { get; }
+
   }
 }

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

@@ -47 +47 @@
       get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
     }
+    public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
+      get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
+    }
 
     [StorableConstructor]
@@ -57 +60 @@
       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..."));
     }
 

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

@@ -53 +53 @@
       get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
     }
-    public OptionalValueParameter<DistanceMatrix> ProbabilityMatrixParameter {
-      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["ProbabilityMatrix"]; }
+    public OptionalValueParameter<ItemList<DoubleValue>> ProbabilityMatrixParameter {
+      get { return (OptionalValueParameter<ItemList<DoubleValue>>)Parameters["ProbabilityMatrix"]; }
     }
     public ValueParameter<IntValue> SampleSizeParameter {
@@ -79 +79 @@
       set { BestKnownSolutionParameter.Value = value; }
     }
-    public DistanceMatrix ProbabilityMatrix {
+    public ItemList<DoubleValue> ProbabilityMatrix {
       get { return ProbabilityMatrixParameter.Value; }
       set { ProbabilityMatrixParameter.Value = value; }
@@ -105 +105 @@
       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<DistanceMatrix>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
+      Parameters.Add(new OptionalValueParameter<ItemList<DoubleValue>>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
       
     }
@@ -112 +112 @@
       DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
       // Get Probabilities of cities using random with seed from hash function on the Name of the instance
-      ProbabilityMatrix = new DistanceMatrix(1, data.Dimension);
+      ProbabilityMatrix = new ItemList<DoubleValue>(data.Dimension);
       Random r = new Random(data.Name.GetHashCode());
       for (int i = 0; i < data.Dimension; i++) {
-        ProbabilityMatrix[0,i] = r.NextDouble();
+        ProbabilityMatrix.Add(new DoubleValue(r.NextDouble()));
       }
       Encoding.Length = data.Dimension;