Changeset 12191

Timestamp:

03/11/15 14:34:11 (9 years ago)

Author:

apolidur

Message:

#2221: Splitting PTSP into Analytical and Estimated

Location:

branches/PTSP/HeuristicLab.Problems.PTSP/3.3

Files:

• AnalyticalPTSP.cs (added)
• DistanceMatrix.cs (modified) (1 diff)
• EstimatedPTSP.cs (added)
• HeuristicLab.Problems.PTSP-3.3.csproj (modified) (3 diffs)
• Interfaces (added)
• Interfaces/IPTSPMoveEvaluator.cs (added)
• Interfaces/IPTSPPathMoveEvaluator.cs (added)
• MoveEvaluators (added)
• MoveEvaluators/OneShift (added)
• MoveEvaluators/PTSPMoveEvaluator.cs (added)
• MoveEvaluators/PTSPPathMoveEvaluator.cs (added)
• MoveEvaluators/TwoOpt (added)
• MoveEvaluators/TwoOpt/PTSPInversionMovePathEvaluator.cs (added)
• PTSP.cs (modified) (6 diffs)

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

@@ -1 +1 @@
 using System;
-using System;
 using System.Collections.Generic;
 using HeuristicLab.Common;

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

@@ -99 +99 @@
     <Reference Include="System" />
     <Reference Include="System.Core" />
+    <Reference Include="System.Drawing" />
     <Reference Include="System.Xml.Linq" />
     <Reference Include="System.Data.DataSetExtensions" />
@@ -108 +109 @@
     <None Include="Properties\AssemblyInfo.cs.frame" />
     <None Include="Plugin.cs.frame" />
+    <Compile Include="AnalyticalPTSP.cs" />
     <Compile Include="DistanceMatrix.cs" />
+    <Compile Include="EstimatedPTSP.cs" />
+    <Compile Include="Interfaces\IPTSPPathMoveEvaluator.cs" />
+    <Compile Include="Interfaces\IPTSPMoveEvaluator.cs" />
+    <Compile Include="MoveEvaluators\PTSPMoveEvaluator.cs" />
+    <Compile Include="MoveEvaluators\PTSPPathMoveEvaluator.cs" />
+    <Compile Include="MoveEvaluators\TwoOpt\PTSPInversionMovePathEvaluator.cs" />
     <Compile Include="PTSP.cs" />
     <Compile Include="Plugin.cs" />
@@ -115 +123 @@
   <ItemGroup>
     <None Include="HeuristicLab.snk" />
+  </ItemGroup>
+  <ItemGroup>
+    <Folder Include="MoveEvaluators\OneShift\" />
   </ItemGroup>
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />

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

@@ -37 +37 @@
 namespace HeuristicLab.Problems.PTSP {
   [Item("Probabilistic Traveling Salesman Problem", "Represents a Probabilistic Traveling Salesman Problem.")]
-  [Creatable("Problems")]
   [StorableClass]
-  public sealed class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
+  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
   IProblemInstanceConsumer<TSPData> {
     #region Parameter Properties
@@ -53 +52 @@
     public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
       get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
-    }
-    public ValueParameter<BoolValue> UseAnalyticalEvaluationParameter {
-      get { return (ValueParameter<BoolValue>)Parameters["UseAnalyticalEvaluation"]; }
     }
     public OptionalValueParameter<DistanceMatrix> ProbabilityMatrixParameter {
@@ -83 +79 @@
       set { BestKnownSolutionParameter.Value = value; }
     }
-    public BoolValue UseAnalyticalEvaluation {
-      get { return UseAnalyticalEvaluationParameter.Value; }
-      set { UseAnalyticalEvaluationParameter.Value = value; }
-    }
     public DistanceMatrix ProbabilityMatrix {
       get { return ProbabilityMatrixParameter.Value; }
@@ -96 +88 @@
     }
     #endregion
-    public override double Evaluate(Individual individual, IRandom random) {
-      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;
-      }
-    }
+    
 
     public override bool Maximization {
@@ -148 +95 @@
 
     [StorableConstructor]
-    private ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
-    private ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
+    protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
+    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
       : base(original, cloner) {
     }
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new ProbabilisticTravelingSalesmanProblem(this, cloner);
-    }
+
     public ProbabilisticTravelingSalesmanProblem() {
       Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
@@ -160 +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 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);
+    public virtual void Load(TSPData data) {
       DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
       // Get Probabilities of cities using random with seed from hash function on the Name of the instance