Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs @ 12219

Last change on this file since 12219 was 12219, checked in by apolidur, 8 years ago

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

File size: 3.2 KB
Line 
1using System.Text;
2using System.Threading.Tasks;
3using HeuristicLab.Optimization;
4using HeuristicLab.PluginInfrastructure;
5using HeuristicLab.Core;
6using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
7using HeuristicLab.Problems.Instances;
8using HeuristicLab.Encodings.PermutationEncoding;
9using HeuristicLab.Common;
10using HeuristicLab.Parameters;
11using HeuristicLab.Data;
12using System;
13using System.Linq;
14using HeuristicLab.Problems.PTSP.MoveEvaluators.OneShift;
15
16namespace HeuristicLab.Problems.PTSP {
17  [Item("Estimated Probabilistic Traveling Salesman Problem", "Represents an estimated Probabilistic Traveling Salesman Problem.")]
18  [Creatable("Problems")]
19  [StorableClass]
20  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
21  IProblemInstanceConsumer<TSPData> {
22
23    private ItemList<ItemList<IntValue>> realizations;
24
25    [StorableConstructor]
26    private EstimatedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
27    private EstimatedProbabilisticTravelingSalesmanProblem(EstimatedProbabilisticTravelingSalesmanProblem original, Cloner cloner)
28      : base(original, cloner) {
29    }
30
31    public override IDeepCloneable Clone(Cloner cloner) {
32      return new EstimatedProbabilisticTravelingSalesmanProblem(this, cloner);
33    }
34
35    public override double Evaluate(Individual individual, IRandom random) {
36      Permutation p = individual.Permutation();
37      // Estimation-based evaluation
38      Random r = new Random();
39      double estimatedSum = 0;
40      for (int i = 0; i < realizations.Count; i++) {
41        int singleRealization = -1;
42        for (int j = 0; j < realizations[i].Count; j++) {
43          if (realizations[i][j].Value == 1) {
44            if (singleRealization != -1) {
45              estimatedSum += DistanceMatrix[singleRealization, p[j]];
46            }
47            singleRealization = p[j];
48          }
49        }
50      }
51      return estimatedSum / SampleSize.Value;
52    }
53
54    public EstimatedProbabilisticTravelingSalesmanProblem() {
55      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Size of the sample for the estimation-based evaluation"));
56      Operators.Add(new PTSPEstimatedInversionMovePathEvaluator());
57      Operators.Add(new PTSPEstimatedInsertionEvaluator());
58      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
59    }
60
61    public override void Load(TSPData data) {
62      base.Load(data);
63      // For now uses sample size of 20 but should use Student's t-test
64      SampleSize = new IntValue(20);
65      realizations = new ItemList<ItemList<IntValue>>(SampleSize.Value);
66      Random r = new Random();
67      for (int i = 0; i < SampleSize.Value; i++) {
68        realizations.Add(new ItemList<IntValue>());
69        for (int j = 0; j < data.Dimension; j++) {
70          if (ProbabilityMatrix[j].Value > r.NextDouble()) {
71            realizations.ElementAt(i).Add(new IntValue(1));
72          } else {
73            realizations.ElementAt(i).Add(new IntValue(0));
74          }
75        }
76       
77      }
78      foreach (var op in Operators.OfType<PTSPPathMoveEvaluator>()) {
79        op.RealizationsParameter.Value = realizations;
80      }
81    }
82  }
83}
Note: See TracBrowser for help on using the repository browser.