Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2221: Local improvement operator for VNS

File size: 3.5 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      Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
59      Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
60      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
61    }
62
63    public override void Load(TSPData data) {
64      base.Load(data);
65      // For now uses sample size of 20 but should use Student's t-test
66      SampleSize = new IntValue(20);
67      realizations = new ItemList<ItemList<IntValue>>(SampleSize.Value);
68      Random r = new Random();
69      for (int i = 0; i < SampleSize.Value; i++) {
70        realizations.Add(new ItemList<IntValue>());
71        for (int j = 0; j < data.Dimension; j++) {
72          if (ProbabilityMatrix[j] > r.NextDouble()) {
73            realizations.ElementAt(i).Add(new IntValue(1));
74          } else {
75            realizations.ElementAt(i).Add(new IntValue(0));
76          }
77        }
78       
79      }
80
81      foreach (var op in Operators.OfType<PTSPPathMoveEvaluator>()) {
82        op.RealizationsParameter.Value = realizations;
83      }
84      foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
85        op.RealizationsParameter.Value = realizations;
86      }
87    }
88  }
89}
Note: See TracBrowser for help on using the repository browser.