Changeset 12183


Ignore:
Timestamp:
03/10/15 16:00:47 (3 years ago)
Author:
apolidur
Message:

#2221: Adding exact and sampling evaluation functions

Location:
branches/PTSP/HeuristicLab.Problems.PTSP/3.3
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj

    r12166 r12183  
    3737  </PropertyGroup>
    3838  <ItemGroup>
     39    <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     40      <SpecificVersion>False</SpecificVersion>
     41      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Collections-3.3.dll</HintPath>
     42      <Private>False</Private>
     43    </Reference>
    3944    <Reference Include="HeuristicLab.Common-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    4045      <SpecificVersion>False</SpecificVersion>
     
    103108    <None Include="Properties\AssemblyInfo.cs.frame" />
    104109    <None Include="Plugin.cs.frame" />
     110    <Compile Include="DistanceMatrix.cs" />
    105111    <Compile Include="PTSP.cs" />
    106112    <Compile Include="Plugin.cs" />
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

    r12166 r12183  
    4141  public sealed class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent,
    4242  IProblemInstanceConsumer<TSPData> {
     43    #region Parameter Properties
     44    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
     45      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
     46    }
     47    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
     48      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
     49    }
     50    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
     51      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
     52    }
     53    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
     54      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
     55    }
     56    public ValueParameter<BoolValue> UseAnalyticalEvaluationParameter {
     57      get { return (ValueParameter<BoolValue>)Parameters["UseAnalyticalEvaluation"]; }
     58    }
     59    public OptionalValueParameter<DistanceMatrix> ProbabilityMatrixParameter {
     60      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["ProbabilityMatrix"]; }
     61    }
     62    public ValueParameter<IntValue> SampleSizeParameter {
     63      get { return (ValueParameter<IntValue>)Parameters["SampleSize"]; }
     64    }
     65
     66    #endregion
     67
     68    #region Properties
     69    public DoubleMatrix Coordinates {
     70      get { return CoordinatesParameter.Value; }
     71      set { CoordinatesParameter.Value = value; }
     72    }
     73    public DistanceMatrix DistanceMatrix {
     74      get { return DistanceMatrixParameter.Value; }
     75      set { DistanceMatrixParameter.Value = value; }
     76    }
     77    public BoolValue UseDistanceMatrix {
     78      get { return UseDistanceMatrixParameter.Value; }
     79      set { UseDistanceMatrixParameter.Value = value; }
     80    }
     81    public Permutation BestKnownSolution {
     82      get { return BestKnownSolutionParameter.Value; }
     83      set { BestKnownSolutionParameter.Value = value; }
     84    }
     85    public BoolValue UseAnalyticalEvaluation {
     86      get { return UseAnalyticalEvaluationParameter.Value; }
     87      set { UseAnalyticalEvaluationParameter.Value = value; }
     88    }
     89    public DistanceMatrix ProbabilityMatrix {
     90      get { return ProbabilityMatrixParameter.Value; }
     91      set { ProbabilityMatrixParameter.Value = value; }
     92    }
     93    public IntValue SampleSize {
     94      get { return SampleSizeParameter.Value; }
     95      set { SampleSizeParameter.Value = value; }
     96    }
     97    #endregion
    4398    public override double Evaluate(Individual individual, IRandom random) {
    44       return random.NextDouble();
     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      }
    45143    }
    46144
     
    50148
    51149    [StorableConstructor]
    52     protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
    53     protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
     150    private ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
     151    private ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
    54152      : base(original, cloner) {
    55153    }
     
    58156    }
    59157    public ProbabilisticTravelingSalesmanProblem() {
    60       Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The coordinates of the cities."));
     158      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
     159      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
     160      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)));
     161      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."));
     163      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"));
    61165    }
    62166
    63167    public void Load(TSPData data) {
    64      
     168      SampleSize = new IntValue(20);
     169      DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
     170      // Get Probabilities of cities using random with seed from hash function on the Name of the instance
     171      ProbabilityMatrix = new DistanceMatrix(1, data.Dimension);
     172      Random r = new Random(data.Name.GetHashCode());
     173      for (int i = 0; i < data.Dimension; i++) {
     174        ProbabilityMatrix[0,i] = r.NextDouble();
     175      }
     176      Encoding.Length = data.Dimension;
    65177    }
    66178  }
Note: See TracChangeset for help on using the changeset viewer.