Changeset 12183 for branches/PTSP

Timestamp:

03/10/15 16:00:47 (10 years ago)

Author:

apolidur

Message:

#2221: Adding exact and sampling evaluation functions

Location:

branches/PTSP/HeuristicLab.Problems.PTSP/3.3

Files:

• DistanceMatrix.cs (added)
• HeuristicLab.Problems.PTSP-3.3.csproj (modified) (2 diffs)
• PTSP.cs (modified) (3 diffs)

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

@@ -37 +37 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Collections-3.3.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
     <Reference Include="HeuristicLab.Common-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
       <SpecificVersion>False</SpecificVersion>
@@ -103 +108 @@
     <None Include="Properties\AssemblyInfo.cs.frame" />
     <None Include="Plugin.cs.frame" />
+    <Compile Include="DistanceMatrix.cs" />
     <Compile Include="PTSP.cs" />
     <Compile Include="Plugin.cs" />

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

@@ -41 +41 @@
   public sealed class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
   IProblemInstanceConsumer<TSPData> {
+    #region Parameter Properties
+    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
+      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
+    }
+    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
+      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
+    }
+    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
+    }
+    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
+      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
+    }
+    public ValueParameter<BoolValue> UseAnalyticalEvaluationParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseAnalyticalEvaluation"]; }
+    }
+    public OptionalValueParameter<DistanceMatrix> ProbabilityMatrixParameter {
+      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["ProbabilityMatrix"]; }
+    }
+    public ValueParameter<IntValue> SampleSizeParameter {
+      get { return (ValueParameter<IntValue>)Parameters["SampleSize"]; }
+    }
+
+    #endregion
+
+    #region Properties
+    public DoubleMatrix Coordinates {
+      get { return CoordinatesParameter.Value; }
+      set { CoordinatesParameter.Value = value; }
+    }
+    public DistanceMatrix DistanceMatrix {
+      get { return DistanceMatrixParameter.Value; }
+      set { DistanceMatrixParameter.Value = value; }
+    }
+    public BoolValue UseDistanceMatrix {
+      get { return UseDistanceMatrixParameter.Value; }
+      set { UseDistanceMatrixParameter.Value = value; }
+    }
+    public Permutation BestKnownSolution {
+      get { return BestKnownSolutionParameter.Value; }
+      set { BestKnownSolutionParameter.Value = value; }
+    }
+    public BoolValue UseAnalyticalEvaluation {
+      get { return UseAnalyticalEvaluationParameter.Value; }
+      set { UseAnalyticalEvaluationParameter.Value = value; }
+    }
+    public DistanceMatrix ProbabilityMatrix {
+      get { return ProbabilityMatrixParameter.Value; }
+      set { ProbabilityMatrixParameter.Value = value; }
+    }
+    public IntValue SampleSize {
+      get { return SampleSizeParameter.Value; }
+      set { SampleSizeParameter.Value = value; }
+    }
+    #endregion
     public override double Evaluate(Individual individual, IRandom random) {
-      return random.NextDouble();
+      Permutation p = individual.Permutation();
+      if (UseAnalyticalEvaluation.Value) {
+        // 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]];
+            for (int k = i + 1; k < j; k++) {
+              sum1 = sum1 * (1 - ProbabilityMatrix[0, p[k]]);
+            }
+            firstSum += sum1;
+          }
+        }
+        double secondSum = 0;
+        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]];
+            for (int k = j + 1; k < p.Length - 1; k++) {
+              sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]);
+            }
+            for (int k = 1; k < i; k++) {
+              sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]);
+            }
+            secondSum += sum2;
+          }
+        }
+        return firstSum+secondSum;
+      } else {
+        // Estimation-based evaluation
+        Random r = new Random();
+        double estimatedSum = 0;
+        for (int i = 0; i < SampleSize.Value; i++) {
+          int singleRealization = -1;
+          for (int j = 0; j < p.Length - 1; j++) {
+            if (ProbabilityMatrix[0, p[j]] > r.NextDouble()) {
+              if (singleRealization != -1) {
+                estimatedSum += DistanceMatrix[singleRealization, p[j]];
+              }
+              singleRealization = p[j];
+            }
+          }
+        }
+        return estimatedSum / SampleSize.Value;
+      }
     }
 
@@ -50 +148 @@
 
     [StorableConstructor]
-    protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
-    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
+    private ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
+    private ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
       : base(original, cloner) {
     }
@@ -58 +156 @@
     }
     public ProbabilisticTravelingSalesmanProblem() {
-      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The 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 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 ValueParameter<BoolValue>("UseAnalyticalEvaluation", "Check to use analytical evaluation, uncheck to use estimation-based approach."));
+      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
+      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Size of the sample for the estimation-based evaluation"));
     }
 
     public void Load(TSPData data) {
-      
+      SampleSize = new IntValue(20);
+      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);
+      Random r = new Random(data.Name.GetHashCode());
+      for (int i = 0; i < data.Dimension; i++) {
+        ProbabilityMatrix[0,i] = r.NextDouble();
+      }
+      Encoding.Length = data.Dimension;
     }
   }