Changeset 12191


Ignore:
Timestamp:
03/11/15 14:34:11 (7 years ago)
Author:
apolidur
Message:

#2221: Splitting PTSP into Analytical and Estimated

Location:
branches/PTSP/HeuristicLab.Problems.PTSP/3.3
Files:
11 added
3 edited

Legend:

Unmodified
Added
Removed
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/DistanceMatrix.cs

    r12183 r12191  
    11using System;
    2 using System;
    32using System.Collections.Generic;
    43using HeuristicLab.Common;
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj

    r12183 r12191  
    9999    <Reference Include="System" />
    100100    <Reference Include="System.Core" />
     101    <Reference Include="System.Drawing" />
    101102    <Reference Include="System.Xml.Linq" />
    102103    <Reference Include="System.Data.DataSetExtensions" />
     
    108109    <None Include="Properties\AssemblyInfo.cs.frame" />
    109110    <None Include="Plugin.cs.frame" />
     111    <Compile Include="AnalyticalPTSP.cs" />
    110112    <Compile Include="DistanceMatrix.cs" />
     113    <Compile Include="EstimatedPTSP.cs" />
     114    <Compile Include="Interfaces\IPTSPPathMoveEvaluator.cs" />
     115    <Compile Include="Interfaces\IPTSPMoveEvaluator.cs" />
     116    <Compile Include="MoveEvaluators\PTSPMoveEvaluator.cs" />
     117    <Compile Include="MoveEvaluators\PTSPPathMoveEvaluator.cs" />
     118    <Compile Include="MoveEvaluators\TwoOpt\PTSPInversionMovePathEvaluator.cs" />
    111119    <Compile Include="PTSP.cs" />
    112120    <Compile Include="Plugin.cs" />
     
    115123  <ItemGroup>
    116124    <None Include="HeuristicLab.snk" />
     125  </ItemGroup>
     126  <ItemGroup>
     127    <Folder Include="MoveEvaluators\OneShift\" />
    117128  </ItemGroup>
    118129  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

    r12183 r12191  
    3737namespace HeuristicLab.Problems.PTSP {
    3838  [Item("Probabilistic Traveling Salesman Problem", "Represents a Probabilistic Traveling Salesman Problem.")]
    39   [Creatable("Problems")]
    4039  [StorableClass]
    41   public sealed class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
     40  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
    4241  IProblemInstanceConsumer<TSPData> {
    4342    #region Parameter Properties
     
    5352    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
    5453      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
    55     }
    56     public ValueParameter<BoolValue> UseAnalyticalEvaluationParameter {
    57       get { return (ValueParameter<BoolValue>)Parameters["UseAnalyticalEvaluation"]; }
    5854    }
    5955    public OptionalValueParameter<DistanceMatrix> ProbabilityMatrixParameter {
     
    8379      set { BestKnownSolutionParameter.Value = value; }
    8480    }
    85     public BoolValue UseAnalyticalEvaluation {
    86       get { return UseAnalyticalEvaluationParameter.Value; }
    87       set { UseAnalyticalEvaluationParameter.Value = value; }
    88     }
    8981    public DistanceMatrix ProbabilityMatrix {
    9082      get { return ProbabilityMatrixParameter.Value; }
     
    9688    }
    9789    #endregion
    98     public override double Evaluate(Individual individual, IRandom random) {
    99       Permutation p = individual.Permutation();
    100       if (UseAnalyticalEvaluation.Value) {
    101         // Analytical evaluation
    102         double firstSum = 0;
    103         for (int i = 0; i < p.Length - 1; i++) {
    104           for (int j = i + 1; j < p.Length - 1; j++) {
    105             double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[j]];
    106             for (int k = i + 1; k < j; k++) {
    107               sum1 = sum1 * (1 - ProbabilityMatrix[0, p[k]]);
    108             }
    109             firstSum += sum1;
    110           }
    111         }
    112         double secondSum = 0;
    113         for (int j = 0; j < p.Length - 1; j++) {
    114           for (int i = 0; i < j; i++) {
    115             double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[j]];
    116             for (int k = j + 1; k < p.Length - 1; k++) {
    117               sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]);
    118             }
    119             for (int k = 1; k < i; k++) {
    120               sum2 = sum2 * (1 - ProbabilityMatrix[0, p[k]]);
    121             }
    122             secondSum += sum2;
    123           }
    124         }
    125         return firstSum+secondSum;
    126       } else {
    127         // Estimation-based evaluation
    128         Random r = new Random();
    129         double estimatedSum = 0;
    130         for (int i = 0; i < SampleSize.Value; i++) {
    131           int singleRealization = -1;
    132           for (int j = 0; j < p.Length - 1; j++) {
    133             if (ProbabilityMatrix[0, p[j]] > r.NextDouble()) {
    134               if (singleRealization != -1) {
    135                 estimatedSum += DistanceMatrix[singleRealization, p[j]];
    136               }
    137               singleRealization = p[j];
    138             }
    139           }
    140         }
    141         return estimatedSum / SampleSize.Value;
    142       }
    143     }
     90   
    14491
    14592    public override bool Maximization {
     
    14895
    14996    [StorableConstructor]
    150     private ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
    151     private ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
     97    protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
     98    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
    15299      : base(original, cloner) {
    153100    }
    154     public override IDeepCloneable Clone(Cloner cloner) {
    155       return new ProbabilisticTravelingSalesmanProblem(this, cloner);
    156     }
     101
    157102    public ProbabilisticTravelingSalesmanProblem() {
    158103      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
     
    160105      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)));
    161106      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
    162       Parameters.Add(new ValueParameter<BoolValue>("UseAnalyticalEvaluation", "Check to use analytical evaluation, uncheck to use estimation-based approach."));
    163107      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("ProbabilityMatrix", "The matrix which contains the probabilities of each of the cities."));
    164       Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Size of the sample for the estimation-based evaluation"));
     108     
    165109    }
    166110
    167     public void Load(TSPData data) {
    168       SampleSize = new IntValue(20);
     111    public virtual void Load(TSPData data) {
    169112      DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
    170113      // Get Probabilities of cities using random with seed from hash function on the Name of the instance
Note: See TracChangeset for help on using the changeset viewer.